验题人题解 | 排位赛#12

userId_undefined

wtcqwq

2024-09-18 10:56:37

发布于：上海

102阅读
0回复
0点赞

AcgoRank12 验题人题解

wtcqwq 2024.8.30

A

暴力统计即可。

如果使用 char ch[N] 来存储，那么长度是 strlen(ch)。

注意整型运算得到浮点数结果需要事先写 1.0* 强制转换类型

void solve(){
	ll cnt=0; cin>>n;
	for(ll i=1;i<=n;i++){
		string str;
		cin>>str;
		if(str.size()>5) cnt++;
	}
	ll x=ceil(1.0*cnt/n*100.0);
	cout<<x<<"%AI, "<<100-x<<"%Human";
}

B

Sol 1

对于 Li,RiL_i,R_i 较小的情况，我们可以用暴力枚举的方式。即，对于 Li∼RiL_i\sim R_i 内的每一个数，判断是奇数还是偶数，并数一下一共有几个。

时间复杂度 O(qA)O(qA)，其中 A=max⁡Ri−LiA=\max R_i-L_i。

期望得分 5050 分。

Sol 2

对于 Li,RiL_i,R_i 中等的情况，我们可以用前缀和。即，设 f1,if_{1,i} 表示 1∼i1\sim i 中有几个奇数，f2,if_{2,i} 表示 1∼i1\sim i 中有几个偶数。求 l∼rl\sim r 内有几个奇数/偶数，可以用前缀和相减去求，即答案为 fTi,Ri−fTi,Li−1f_{T_i,R_i}-f_{T_i,L_i-1}。

时间复杂度 O(A+q)O(A+q)，空间复杂度 O(A)O(A)，AA 与上文同理。

期望得分 5050 分。

Sol 3

考虑到是连续区间，想想有没有数学解法。

  • Case 1，l,rl,r 同奇偶。

    这时候 r−l+1r-l+1 是一个偶数，也就是与 l,rl,r 奇偶性相同的那种数会多 11 个。

    假设 l,rl,r 均为奇数，则奇数会有 r−l2+1\frac{r-l}2+1 个，偶数有 r−l2\frac{r-l}{2} 个。均为偶数同理。

    你可以自己手酸找找规律。

  • Case 2，l,rl,r 不同奇偶

    这时候奇偶个数一样，都是 r−l+12\frac{r-l+1}2 个。

将上述过程实现即可，单次询问是 O(1)O(1) 的，总复杂度 O(q)O(q)。

void solve(){
	ll opt,l,r;
	cin>>opt>>l>>r;
	ll cnt1=(r-l+1)/2;
	if((r-l)&1){
		cout<<cnt1<<endl; 
	}
	else{
		if((opt&1)==(l&1)) cout<<cnt1+1<<endl;
		else cout<<cnt1<<endl;
	}
}

C

Sol 1

不难发现，题意就是 0101 背包，用朴素的 0101 背包方式维护即可。

准确地说，用 dp 维护，设 fi,wf_{i,w} 表示考虑前 ii 个物品，重量不超过 ww 的最大价值。

那么我们的决策其实只有第 ii 个物品选/不选。

  • 选

    此时，重量会累计 wiw_i，价值会累计 viv_i。

    考虑此时重量为 ww，则选以前，重量是 w−wiw-w_i。

    所以 fi,w=fi−1,w−wi+vif_{i,w}=f_{i-1,w-w_i}+v_i。

  • 不选

    此时的情况与 fi−1,wf_{i-1,w} 一摸一样，即 fi,w=fi−1,wf_{i,w}=f_{i-1,w}。

综上所述，dp 的状态转移方程就昭然若揭了，即

fi,w=max⁡(fi−1,w,fi−1,w−wi+vi)f_{i,w}=\max(f_{i-1,w},f_{i-1,w-w_i+v_i})

最后答案即为 fn,mf_{n,m}。

时间复杂度、空间复杂度均为 O(nm)O(nm)。

期望得分 50 分

Sol 2

上面做法的瓶颈是 mm 大（本题 mm 可以达到 10910^9）时时间复杂度就会变得不可接受。

我们惊奇的发现，viv_i 和 wiw_i 的值域似乎很不同。

也就是说，就算所有东西都买上，总价值也只有 ∑vi≤103×100=105\sum v_i \le 10^3\times 100 = 10^5。

这时候可以想到 dp 的一种经典 trick，状态和目标函数转换。

也就是原来的方程 fi,w=vf_{i,w}=v，我们想成 gi,v=wg_{i,v}=w。

也就是，gi,vg_{i,v} 表示前 ii 个物品，价值是 vv 的最小重量。

与前面的决策讨论类似，具体讨论过程留给读者自己思考。

gi,v=min⁡(gi−1,v−vi+wi,gi−1,v)g_{i,v}=\min(g_{i-1,v-v_i}+w_i,g_{i-1,v})

答案是最大的 vv 使得 gn,v≤mg_{n,v}\le m。

时间复杂度 O(nV)O(nV)，空间复杂度 O(nV)O(nV)。此处 V=∑viV=\sum v_i。

这时会 MLE。

我们发现 gg 的决策，只依赖于上一行。也就是往前的两行三行四行都没有用了，可以不再记录。

采用 滚动数组 的方式进行记录，空间复杂度降为 O(V)O(V)。

如果不会滚动数组可以借鉴代码或者自行百度。

void solve(){
	cin>>n>>m;
	for(ll i=1;i<=n;i++){
		cin>>w[i]>>v[i];
	}
	ll V=accumulate(v+1,v+1+n,0);
	ll ans=0;
	for(ll j=0;j<=V;j++) dp[0][j]=1e18;
	dp[0][0]=0;
	for(ll i=1;i<=n;i++){
		for(ll j=0;j<=V;j++) dp[i&1][j]=dp[i&1^1][j];
		for(ll j=v[i];j<=V;j++){
			dp[i&1][j]=min(dp[i&1^1][j-v[i]]+w[i],dp[i&1][j]);
			if(dp[i&1][j]<=m) ans=max(ans,j);
		}
	}
	cout<<ans<<endl;
}

D

今年的高考题改编。

E

这是一种与出题人不同的做法。

如果一个烟花爆炸后每秒可以散开 11 格，那么在 ii 秒到达的格子都有 ii 格距离。这个距离是曼哈顿距离。

也就是说，一个烟花会在爆炸后第 xx 秒到达所有曼哈顿距离为 xx 的格子。

那么，考虑到这个烟花的爆炸时间 ziz_i，也就是第 zi+xz_i+x 秒到达所有曼哈顿距离为 xx 的点。

设烟花位置在 (x,y)(x,y)，当前点在 (i,j)(i,j)，那么 (i,j)(i,j) 会在 (zi+∣x−i∣+∣y−j∣)(z_i+|x-i|+|y-j|) 时刻看到烟花。

也就是对于格子 (i,j)(i,j)，第一次看到烟花的时刻即为【原谅我使用了很撇脚的 oo 作为下标，因为 i,j,ki,j,k 都用掉了】

min⁡o=1k(zo+∣xo−i∣+∣yo−j∣)\min^k_{o=1}(z_o+|x_o-i|+|y_o-j|)

绝对值并不优雅，考虑拆绝对值。

<img src="https://cdn.luogu.com.cn/upload/image_hosting/p5opeapq.png" style="zoom:50%;" />

我们如果能快速计算四种情况分别最优的点当作这种情况的代表，就可以只比较这四个点的优劣。

  • 情况一

    此时 x≤i,y≤jx\le i,y\le j，上式的值为 z+i−x+j−yz+i-x+j-y。

    在这种情况内部，i+ji+j 的值恒定，我们需要 z−x−yz-x-y 最小的点。

  • 情况二

    此时 x≥i,y≤jx\ge i,y\le j，上式的值为 z+x−i+j−yz+x-i+j-y。

    在这种情况内部，−i+j-i+j 的值恒定，我们需要 z+x−yz+x-y 最小的点。

  • 情况三

    此时 x≤i,y≥jx\le i,y\ge j，上式的值为 z+i−x+y−jz+i-x+y-j。

    在这种情况内部，i−ji-j 的值恒定，我们需要 z−x+yz-x+y 最小的点。

  • 情况四

    此时 x≥i,y≥jx\ge i,y\ge j，上式的值为 z+x−i+y−jz+x-i+y-j。

    在这种情况内部，−i−j-i-j 的值恒定，我们需要 z+x+yz+x+y 最小的点。

我们可以通过二维前缀最值的方式预处理出各种情况下最小的点，然后比较这四个点的优劣即可。

相比于正解，这个做法不依赖 kk 的大小，时间复杂度为 O(nm)O(nm)。空间复杂度也是 O(nm)O(nm)，但带有的五倍常数较大，感谢出题人不杀之恩。

这道题可能讲的有点玄乎，没看懂可以看代码或者群里找我。

void solve(){
	cin>>n>>m>>k;
	for(ll i=1;i<=k;i++){
		cin>>x[i]>>y[i]>>z[i];
		f[x[i]][y[i]]=z[i];
	}
	for(ll i=0;i<=n+1;i++) for(ll j=0;j<=m+1;j++){
		g1[i][j]=g2[i][j]=g3[i][j]=g4[i][j]=1e18;
	}
	for(ll i=1;i<=n;i++)
		for(ll j=1;j<=m;j++){
			if(f[i][j]) g1[i][j]=f[i][j]-i-j;
			g1[i][j]=min(g1[i][j],min(g1[i-1][j],g1[i][j-1]));
		}
	for(ll i=n;i>=1;i--)
		for(ll j=1;j<=m;j++){
			if(f[i][j]) g2[i][j]=f[i][j]+i-j;
			g2[i][j]=min(g2[i][j],min(g2[i+1][j],g2[i][j-1]));
		}
	for(ll i=1;i<=n;i++)
		for(ll j=m;j>=1;j--){
			if(f[i][j]) g3[i][j]=f[i][j]-i+j;
			g3[i][j]=min(g3[i][j],min(g3[i][j+1],g3[i-1][j]));
		}
	for(ll i=n;i>=1;i--)
		for(ll j=m;j>=1;j--){
			if(f[i][j]) g4[i][j]=f[i][j]+i+j;
			g4[i][j]=min(g4[i][j],min(g4[i][j+1],g4[i+1][j]));
		}
	ll now=1;
	ll ans=0;
	for(ll i=0;i<=n;i++){
		for(ll j=1;j<=m;j++){
			now*=233ll; now%=mod;
			if(!i) continue;
			ll res=min(g1[i][j]+i+j,min(g2[i][j]-i+j,min(g3[i][j]+i-j,g4[i][j]-i-j)));
			ans+=res*now%mod;
			ans%=mod;
		}
	}
	cout<<ans<<endl;
}
userId_undefined
去预览
0/2000

全部评论 4

  • userId_undefined

    不会c++的c++

    出道萌新空间掌握者循环·循环打卡人格式·格式排版员分支·分支解题者I/O·IO入门者

    我和“小白之都”的小伙伴都在ACGO等你，快用这个专属链接加入我们吧！ac

    2024-09-10 来自 江苏

    0
  • userId_undefined

    不会c++的c++

    出道萌新空间掌握者循环·循环打卡人格式·格式排版员分支·分支解题者I/O·IO入门者

    我和“小白之都”的小伙伴都在ACGO等你，快用这个专属链接加入我们吧！https://www.acgo.cn/application/1833320977037103104

    2024-09-10 来自 江苏

    0
  • userId_undefined

    小鱼

    出道萌新快乐小狗

    强的！

    2024-09-10 来自 浙江

    0
  • userId_undefined

    复仇者_帅童

    小有名气CSP-J一等奖出题人

    不放T6差评

    2024-09-09 来自 广东

    0
    • userId_undefined

      Macw07

      回复复仇者_帅童

      他验题的时候还没有 T6。所以他没有验 T6。

      2024-09-10 来自 美国

      0

热门讨论