2 月做题记录
CF1608F MEX counting
Links
- 题目链接
- 提交记录
- 官方题解
题解：
- 首先显然考虑 DP ，设计状态：有一维显然是 \(i\)，然后 \(k\) 表示当前的 mex 值 ，最后 \(j\) 表示已经选的数中 \(>k\) 的数的个数。
- 然后就是很神仙的转移，考虑从 \(i\) 转移到 \(i+1\)。
- 如果加入 \(a_i\) 对 mex 不产生贡献，即 \(a_i \neq k\) ，则有 \(f_{i,j,k} \times k \rightarrow f_{i+1,j,k}\)（在 \([1,k]\) 中选择 \(a_i\)）, \(f_{i,j,k} \times j \rightarrow f_{i+1,j,k}\)（在 \(j\) 个数中选择 \(a_i\)），\(f_{i,j,k} \rightarrow f_{i+1,j+1,k}\) （选择了一个 \(>k\) 且没有出现过的数）。
- 如果加入 \(a_i\) 对 mex 产生了贡献，即 \(a_i = k\)，那么考虑枚举 \(k \rightarrow t\)，\([k,t-1]\) 之间的数必须全部出现，转移则为 \(f_{i,j,k} \times \frac{j!}{{(j-(t-k+1))!}}\)，相当于在 \(j\) 个数中选出 \(t-k+1\) 个数且要求有序。
- 然而这样的复杂度是 \(O(n^2k^2)\) 的，瓶颈在于第二种转移。
- 那么现在考虑优化，首先改主动转移为被动转移，然后令 \(T=j+k\)，设状态为 \(f_{i,T,k}\)，那么第二种转移就变为了 \(\sum\limits_{k < t} \frac{(j-k)!}{(j+1-t)!} \times f_{i,j,k} \rightarrow f_{i+1,j+1,t}\)，然后这个可以前缀和优化，空间可以滚动数组，最后总复杂度为 \(O(n^2k)\)，常数很大，需要卡常。
总结： 关键在于状态的设计以及 \(j+k\) 的发现。
Codechef DESTRUCT
Links
- 题目链接
- 提交记录
题解：
- 一次操作分为两个人显然不太可做，于是考虑改成这个样子： B 先选一个堆，然后 A、B 轮流拿石子和给对方选堆。
- 然后一个经典的考虑博弈论的手法是：如果当前必败，考虑能不能让对方接下来把自己的活干完。
- 然后就很神奇：如果当前 \(a_i>1\) ，拿完必败的话，就拿剩 1 个，再选这个给对方，这样对方就陷入了自己刚才的处境；否则自己拿完。也就是说，第一个拿到 \(a_i > 1\) 的堆的人必胜（全为 1 特判即可）。
- 所以一开始每个人肯定强迫对方拿 1，判断奇偶性即可。
Codechef TABRARRAY
Links
- 题目链接
- 提交记录
题解：
- 由于祖先是儿子的倍数，那么相当于对于每个质因子，父亲的次数 \(\geq\) 儿子的次数，所以不妨对于每个质因子分开考虑方案数。
- 分析一下数据规模：由于 \(\prod a_i \leq 10^{12}\)，那么一个质因子最多出现 \(\log K=40\) 次，同时除根以外的数中一个质因子至少出现 \(2\) 次，所以最大质因子 \(=\sqrt{k}=10^6\)，可以线性筛。
- 观察到根节点比较特殊，不妨设 \(a_1=lcm_{k \in [2,n]}a_k\)，最后给根乘上些东西即可（\([1,\frac{K}{mul}]\)，\(mul\) 为整棵树的 \(a_i\) 的乘积）。
- 考虑对于每个质因子 \(p\) 分别 dp，设 \(f_{i,j,k}\) 为以 \(i\) 为根的子树内 \(p\) 总次数为 \(j\) ，\(i\) 上 \(p\) 的次数为 \(k\) 的方案总数，转移类似树上背包即可，注意转移完之后需要处理单独出现当前根上出现的方案数（根节点不能处理，原因是之前的假设）。
- 然后 dp 完之后令 \(s_i=\sum\limits_{j}{f_{1,i,j}}\) ，dfs 做一个背包统计即可，具体见代码。
- 总复杂度 \(O(n \log^4 K + \sqrt{k} \log K)\)
总结： 对于倍数关系可以从质因子的角度出发。
CF1610H Squid Game
Links
- 题目链接
- 提交记录
题解：
- 思路非常神仙。
- 如果树是一条链，那么变成了经典的点覆盖区间问题，尽量选浅的点即可。
- 首先解决所有直链，如果直链是一条边显然无解。如果不是一条边，那么设 \(dep_u
- 在所有直链解决完后如果有一条弯链不合法，那么根就必选。
- 总复杂度 \(O(n \log n)\)，瓶颈在于 lca 以及跳祖先，用树剖实现，加上 FastIO 后在 luogu 上跑了最优解。
CF1119G Get Ready for the Battle
Links
- 题目链接
- 提交记录
- 官方题解
题解：
- 先猜答案：\(ans=\lceil \frac{\sum h_i}{n} \rceil\)，然后考虑如何构造。
- 所以要尽量不浪费。考虑构造。首先一开始让所有人打第一个敌人，只要他的血量 \(
- 然后就没了，构造可以差分，具体见代码。
CF1571I Physical Examination
Links
- 题目链接
- 提交记录
题解：
- 考虑对于一个确定的 \(x\)，可以贪心的判合法性。
- 然后判的过程中可以知道 \(x\) 偏大还是偏小，直接二分就没了。
CF1297H Paint the String
Links
- 题目链接
- 提交记录
题解：
- 对于最大值最小，我们不妨钦定 \(a\) 串为最大值，接下来手玩一下。
- 假设当前考虑到 \(i\)，那么分三种情况讨论：
- 如果 \(s_i < a_1\)，那么可以直接把后缀 \(i\) 当作 \(b\)，这对于当前必然是最优的。
- 如果 \(s_i > a_1\)，由于 \(b
- 如果 \(s_i = a_1\)，可以把 \(s_i\) 接在 \(a\) 后面；也可以把 \(s_i\) 当成 \(b\)，那么这个时候 \(a_1=b_1\)，所以就可以转化成 \(2\) 以后的比较大小。然后变成了多决策的最优化问题。可以利用这个来 dp。
- 设 \(f_{i,j}\) 为考虑了前 \(i\) 位字符串，\(b\) 的大小为 \(j\) 的最小的 \(a\)，转移见代码。
- 复杂度 \(O(Tn^3)\)
P4886 快递员
Links
- 题目链接
- 提交记录
题解：
- 考虑先任意选出 \(x\)，求出所有点对的权值。考虑建出以 \(x\) 为根的树，那么一个点对的权值即为两个点的深度和，找出那些权值最大的点对。
- 如果对于一个权值最大的点对 \((u,v)\), \(u\) 和 \(v\) 分属 \(x\) 的两棵不同子树，那么无论 \(x\) 怎样移动，答案不可能变小，即当前答案即为最终答案。
- 如果存在 \(\geq 2\) 个最大点对分布在 \(x\) 的不同子树内，\(x\) 无论向哪棵子树移动，原来的最大值必然变大，答案同样不可能变小。
- 除了以上两种情况，只有 \(x\) 向着最大值所在的子树内移动，答案才可能变小。
- 这个过程相当于只递归一边的点分治，每次令 \(x\) 为重心，总复杂度 \(O(n \log n)\)。
- 注意递归过程中需要记录最小值，因为答案可能变劣。
CF1017G The Tree
Links
- 题目链接
- 提交记录
题解：
- 神仙题。
- 首先如果每次直接查单点颜色是 \(O(1)\) 的，所以考虑把复杂度向询问倾斜。
- 先忽略操作2，可以发现每次 \(1\) 操作相当于向下传递一层，那么当前查询的点 \(x\) 到根的路径上如果存在一个点 \(y\) 开始到 \(x\) 的路径上下传了 \(dep_x-dep_y\) 次，容易发现点 \(x\) 一定是黑色的。
- 于是只需要考虑每个点到根的路径的后缀和最大值是否 \(\geq len\) 。可以用一个 trick：把每个点的初始点权设为 \(-1\)，然后只需要查是否存在一个后缀和 \(\geq 0\) 相当于查后缀和的最大值就好了，可以树剖维护。
- 然后考虑操作 2，我们可以想到把整棵子树设为 \(-1\)，在此基础上把子树的根的点权再减去其父亲到根的路径的后缀和最大值即可。
CF1552F Telepanting
Links
- 题目链接
- 提交记录
题解：
- 首先可以发现，到达任意一个位置 \(x\) 时，所有 \(y_i
- 然后可以设 \(f_i\) 表示从 \(y_i\) 扔回 \(x_i\) 再走回 \(y_i\) 的用时，可以
lower_bound出第一个 \(y_k > x_i\) 的 \(k\)，则 \(f_i=y_i-x_i+\sum\limits_{j=k}^i{f_j}\) - 答案即为一开始激活的所有 \(f_i\) 再加上 \(x_n+1\)。