ACGORANK12 验题人题解
wtcqwq 2024.8.30
A
暴力统计即可。
如果使用 char ch[N] 来存储，那么长度是 strlen(ch)。
注意整型运算得到浮点数结果需要事先写 1.0* 强制转换类型
B
SOL 1
对于 Li,RiL_i,R_iLi ,Ri 较小的情况，我们可以用暴力枚举的方式。即，对于 Li∼RiL_i\sim R_iLi ∼Ri 内的每一个数，判断是奇数还是偶数，并数一下一共有几个。
时间复杂度 O(qA)O(qA)O(qA)，其中 A=maxRi−LiA=\max R_i-L_iA=maxRi −Li 。
期望得分 505050 分。
SOL 2
对于 Li,RiL_i,R_iLi ,Ri 中等的情况，我们可以用前缀和。即，设 f1,if_{1,i}f1,i 表示 1∼i1\sim i1∼i 中有几个奇数，f2,if_{2,i}f2,i 表示 1∼i1\sim i1∼i 中有几个偶数。求 l∼rl\sim rl∼r 内有几个奇数/偶数，可以用前缀和相减去求，即答案为 fTi,Ri−fTi,Li−1f_{T_i,R_i}-f_{T_i,L_i-1}fTi ,Ri −fTi ,Li −1 。
时间复杂度 O(A+q)O(A+q)O(A+q)，空间复杂度 O(A)O(A)O(A)，AAA 与上文同理。
期望得分 505050 分。
SOL 3
考虑到是连续区间，想想有没有数学解法。
* Case 1，l,rl,rl,r 同奇偶。
这时候 r−l+1r-l+1r−l+1 是一个偶数，也就是与 l,rl,rl,r 奇偶性相同的那种数会多 111 个。
假设 l,rl,rl,r 均为奇数，则奇数会有 r−l2+1\frac{r-l}2+12r−l +1 个，偶数有 r−l2\frac{r-l}{2}2r−l 个。均为偶数同理。
你可以自己手酸找找规律。
* Case 2，l,rl,rl,r 不同奇偶
这时候奇偶个数一样，都是 r−l+12\frac{r-l+1}22r−l+1 个。
将上述过程实现即可，单次询问是 O(1)O(1)O(1) 的，总复杂度 O(q)O(q)O(q)。
C
SOL 1
不难发现，题意就是 010101 背包，用朴素的 010101 背包方式维护即可。
准确地说，用 dp 维护，设 fi,wf_{i,w}fi,w 表示考虑前 iii 个物品，重量不超过 www 的最大价值。
那么我们的决策其实只有第 iii 个物品选/不选。
* 选
此时，重量会累计 wiw_iwi ，价值会累计 viv_ivi 。
考虑此时重量为 www，则选以前，重量是 w−wiw-w_iw−wi 。
所以 fi,w=fi−1,w−wi+vif_{i,w}=f_{i-1,w-w_i}+v_ifi,w =fi−1,w−wi +vi 。
* 不选
此时的情况与 fi−1,wf_{i-1,w}fi−1,w 一摸一样，即 fi,w=fi−1,wf_{i,w}=f_{i-1,w}fi,w =fi−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}) fi,w =max(fi−1,w ,fi−1,w−wi +vi )
最后答案即为 fn,mf_{n,m}fn,m 。
时间复杂度、空间复杂度均为 O(nm)O(nm)O(nm)。
期望得分 50 分
SOL 2
上面做法的瓶颈是 mmm 大（本题 mmm 可以达到 10910^9109）时时间复杂度就会变得不可接受。
我们惊奇的发现，viv_ivi 和 wiw_iwi 的值域似乎很不同。
也就是说，就算所有东西都买上，总价值也只有 ∑vi≤103×100=105\sum v_i \le 10^3\times 100 = 10^5∑vi ≤103×100=105。
这时候可以想到 dp 的一种经典 trick，状态和目标函数转换。
也就是原来的方程 fi,w=vf_{i,w}=vfi,w =v，我们想成 gi,v=wg_{i,v}=wgi,v =w。
也就是，gi,vg_{i,v}gi,v 表示前 iii 个物品，价值是 vvv 的最小重量。
与前面的决策讨论类似，具体讨论过程留给读者自己思考。
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}) gi,v =min(gi−1,v−vi +wi ,gi−1,v )
答案是最大的 vvv 使得 gn,v≤mg_{n,v}\le mgn,v ≤m。
时间复杂度 O(nV)O(nV)O(nV)，空间复杂度 O(nV)O(nV)O(nV)。此处 V=∑viV=\sum v_iV=∑vi 。
这时会 MLE。
我们发现 ggg 的决策，只依赖于上一行。也就是往前的两行三行四行都没有用了，可以不再记录。
采用 滚动数组 的方式进行记录，空间复杂度降为 O(V)O(V)O(V)。
如果不会滚动数组可以借鉴代码或者自行百度。
D
今年的高考题改编。
E
这是一种与出题人不同的做法。
如果一个烟花爆炸后每秒可以散开 111 格，那么在 iii 秒到达的格子都有 iii 格距离。这个距离是曼哈顿距离。
也就是说，一个烟花会在爆炸后第 xxx 秒到达所有曼哈顿距离为 xxx 的格子。
那么，考虑到这个烟花的爆炸时间 ziz_izi ，也就是第 zi+xz_i+xzi +x 秒到达所有曼哈顿距离为 xxx 的点。
设烟花位置在 (x,y)(x,y)(x,y)，当前点在 (i,j)(i,j)(i,j)，那么 (i,j)(i,j)(i,j) 会在 (zi+∣x−i∣+∣y−j∣)(z_i+|x-i|+|y-j|)(zi +∣x−i∣+∣y−j∣) 时刻看到烟花。
也就是对于格子 (i,j)(i,j)(i,j)，第一次看到烟花的时刻即为【原谅我使用了很撇脚的 ooo 作为下标，因为 i,j,ki,j,ki,j,k 都用掉了】
mino=1k(zo+∣xo−i∣+∣yo−j∣)\min^k_{o=1}(z_o+|x_o-i|+|y_o-j|) o=1mink (zo +∣xo −i∣+∣yo −j∣)
绝对值并不优雅，考虑拆绝对值。
<img src="https://cdn.luogu.com.cn/upload/image_hosting/p5opeapq.png" style="zoom:50%;" />
我们如果能快速计算四种情况分别最优的点当作这种情况的代表，就可以只比较这四个点的优劣。
* 情况一
此时 x≤i,y≤jx\le i,y\le jx≤i,y≤j，上式的值为 z+i−x+j−yz+i-x+j-yz+i−x+j−y。
在这种情况内部，i+ji+ji+j 的值恒定，我们需要 z−x−yz-x-yz−x−y 最小的点。
* 情况二
此时 x≥i,y≤jx\ge i,y\le jx≥i,y≤j，上式的值为 z+x−i+j−yz+x-i+j-yz+x−i+j−y。
在这种情况内部，−i+j-i+j−i+j 的值恒定，我们需要 z+x−yz+x-yz+x−y 最小的点。
* 情况三
此时 x≤i,y≥jx\le i,y\ge jx≤i,y≥j，上式的值为 z+i−x+y−jz+i-x+y-jz+i−x+y−j。
在这种情况内部，i−ji-ji−j 的值恒定，我们需要 z−x+yz-x+yz−x+y 最小的点。
* 情况四
此时 x≥i,y≥jx\ge i,y\ge jx≥i,y≥j，上式的值为 z+x−i+y−jz+x-i+y-jz+x−i+y−j。
在这种情况内部，−i−j-i-j−i−j 的值恒定，我们需要 z+x+yz+x+yz+x+y 最小的点。
我们可以通过二维前缀最值的方式预处理出各种情况下最小的点，然后比较这四个点的优劣即可。
相比于正解，这个做法不依赖 kkk 的大小，时间复杂度为 O(nm)O(nm)O(nm)。空间复杂度也是 O(nm)O(nm)O(nm)，但带有的五倍常数较大，感谢出题人不杀之恩。
这道题可能讲的有点玄乎，没看懂可以看代码或者群里找我。
