验题人题解 | 排位赛#12

wtcqwq

2024-09-18 10:56:37

发布于：上海

95阅读

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

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

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

期望得分 $50$ 分。

Sol 2

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

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

期望得分 $50$ 分。

Sol 3

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

Case 1， $l,r$ 同奇偶。

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

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

你可以自己手酸找找规律。
Case 2， $l,r$ 不同奇偶

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

将上述过程实现即可，单次询问是 $O(1)$ 的，总复杂度 $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

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

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

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

选

此时，重量会累计 $w_i$ ，价值会累计 $v_i$ 。

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

所以 $f_{i,w}=f_{i-1,w-w_i}+v_i$ 。
不选

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

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

$f_{i,w}=\max(f_{i-1,w},f_{i-1,w-w_i+v_i})$

最后答案即为 $f_{n,m}$ 。

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

期望得分 50 分

Sol 2

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

我们惊奇的发现， $v_i$ 和 $w_i$ 的值域似乎很不同。

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

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

也就是原来的方程 $f_{i,w}=v$ ，我们想成 $g_{i,v}=w$ 。

也就是， $g_{i,v}$ 表示前 $i$ 个物品，价值是 $v$ 的最小重量。

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

$g_{i,v}=\min(g_{i-1,v-v_i}+w_i,g_{i-1,v})$

答案是最大的 $v$ 使得 $g_{n,v}\le m$ 。

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

这时会 MLE。

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

采用滚动数组的方式进行记录，空间复杂度降为 $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

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

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

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

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

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

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

$\min^k_{o=1}(z_o+|x_o-i|+|y_o-j|)$

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

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

情况一

此时 $x\le i,y\le j$ ，上式的值为 $z+i-x+j-y$ 。

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

此时 $x\ge i,y\le j$ ，上式的值为 $z+x-i+j-y$ 。

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

此时 $x\le i,y\ge j$ ，上式的值为 $z+i-x+y-j$ 。

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

此时 $x\ge i,y\ge j$ ，上式的值为 $z+x-i+y-j$ 。

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

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

相比于正解，这个做法不依赖 $k$ 的大小，时间复杂度为 $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;
}

有帮助，赞一个

去预览

0/2000

全部评论 4

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

2024-09-10 来自江苏
0
AC
我和“小白之都”的小伙伴都在ACGO等你，快用这个专属链接加入我们吧！https://www.acgo.cn/application/1833320977037103104

2024-09-10 来自江苏
0
暴躁小鱼
强的！

2024-09-10 来自浙江
0
‮队团加不）ด้้童帅_者仇复
不放T6差评

2024-09-09 来自广东
0
- Macw07
  回复‮队团加不）ด้้童帅_者仇复
  他验题的时候还没有 T6。所以他没有验 T6。
  
  2024-09-10 来自美国
  0

AcgoRank12 验题人题解

A

B

Sol 1

Sol 2

Sol 3

C

Sol 1

Sol 2

D

E

全部评论 4

热门讨论