2023.8.10 做题记录
ARC107D
题意：给出数 \(N,K\)，求有多少有理数可重集 \(S\) 满足以下条件：
- \(|S|=N,\sum_\limits{i\in S} i=K\)
- \(\forall i\in S,i=\frac{1}{2^j}(j\in \mathbb{N})\)
分析：用动态规划求解，设 \(f_{i,j}\) 为 \(N=i,K=j\) 的答案。
由于空集只能通过增加 \(1\) 和将目前元素全部除以 \(2\) 来转化成符合条件的有理数集合，因此 \(f_{i-1,j-1}\) 与 \(f_{i,j\times 2}\) 分别对应以上两种操作。
复盘：遇到关于集合的 dp 可以考虑从集合的构造上进行计数 dp。
AGC004C
题意：给定一个网格图，有些位置已经被涂色。要求构造两个相同大小的网格图，并且在上面涂色，需要保证颜色四联通。满足这两个网格的涂色部分的重合位置恰好是给定的网格图的涂色位置。保证边界上不被涂色。
分析：给出一种构造方案：初始的第一个图和第二个图如下：
####. ....#
#.... .####
####. ....#
#.... .####
####. ....#
再将要求重合的点在对应的图上涂色即可。
复盘：这题一开始做的时候没看到保证边界上不被涂色的条件，所以一直没有构造思路，因此当没有思路时，要回看题目，注意有没有审错题目。
CF1270G
题意：给出 \(n\) 个整数 \(a_1,a_2,\dots a_n\)，保证 \(\forall a_i,i-n\le a_i\le i-1\)。
找到这些整数的非空子集，使得它们的和为 \(0\)。
分析：考虑转化所给条件，原条件相当于 \(1\le i-a_i\le n\)。
对于每个 \(i\)，考虑将 \(i\) 到 \(i-a_i\) 连边。这时的图是一个基环树内向森林，找到基环树的环即可。
原因：\(i\) 走到 \(i-a_i\) 的过程相当于 \(i\) 减去 \(a_i\)，因此走过这个环就可以理解为 \(i\) 减掉若干个数仍为 \(i\)，因此这些数的和为 \(0\)。
复盘：神仙题。
关键点在于转化条件后想到建边找环。
这题需要对算法进行充分的了解和掌握，外加灵光一闪才能做，毕竟 tourist 赛时都不能场切。
CF1364E
题意：交互题。
有一个固定长度为 \(n\) 的排列 \(P\)，值域为 \([0,n-1]\)。你可以进行不超过 \(4269\) 次询问 \(x,y\)，并得到 \(P_x|P_y\)，之后要输出这个排列。
分析：不难发现只要找到 \(0\)，再通过 \(n-1\) 次询问即可得到排列。
因此问题转化为在 \(n+173\) 次询问中找到 \(0\)。
考虑如何求 \(P_i\) 的确定值：随机一个下标 \(x\)，不断询问 \((x,i)\)，并将逐次答案相与，如果随机 \(x\) 次，答案算错的概率最坏为 \(11\times 2^{-x}\)，在 \(x\) 取一个比较大的值如 \(20\) 时可以忽略不计。
将序列从 \(1\sim n\) 扫一遍，我们钦定每次询问 \((i,cur)\)，当 \((i,cur)=P_{cur}\) 时候，显然二进制分解下 \(P_i\) 是 \(P_{cur}\) 的真子集，于是将 \(cur\) 设为 \(i\)，容易发现，这一定是 \(P_{cur}\) 不断缩小的过程，而扫一遍后 \(P_{cur}\) 一定等于 \(0\)。
可以将排列事先进行随机，防止出题人构造的极端数据导致询问超出限制。
复盘：算是一道比较经典的交互题，处处体现了交互题中 「随机」 的套路，而又考察了对位运算性质的熟悉程度，是一道非常具有学习意义的题目。
还有几道题目明天更新。