2025/03 & 2025/04 做题记录
绿色是自己做出来的，红色是自己没做出来的。
文化课选手做几个 OI 题陶冶情操，所以这里没几个题。
\color{green}\text{P8478 「GLR-R3」清明}
- 看到乘积先拆成每个最后的台阶选一个上面的水滴。依次考虑初始状态每个台阶水滴去哪里并状压哪些台阶已经选了水滴，可以做到
O(n^32^k) 。显然我们得找个O(\text{poly}(n)2^{n-k}) 的东西拼起来。注意到只有n-k-1 个最终台阶的水滴来源不是一个前缀，对它们容斥之后每个台阶的水滴来源都是一个前缀，于是容易设计多项式复杂度的 DP。复杂度O(n^32^{n-k}) ，拼起来是O(n^32^{\frac{n}{2}}) 。
\color{green}\text{CF2045K GCDDCG}
- 考虑下
i=1 咋求答案。那就是\sum_{x \mid \text{gcd}(A)}\sum _{y \mid \text{gcd}(B)} \mu(x) \mu(y) 状物对吧。枚举完x,y 之后答案会和x,y,\text{lcm}(x,y) 有关，可以快速计算。打个表发现\text{lcm}(x,y) \le n 的对数只有一千多万对（实际上据题解说好像有重磅结论是O(n \log^2n) 的），于是对于这些数对暴力计算贡献，然后\text{lcm}(x,y)>n 的推下式子对于x,y 分别是独立的两堆东西乘起来，那就好算。对每个i 跑上面那个算法是\sum_i\frac{n}{i}\log^2 \frac{n}{i} 即O(n \log^3n) 的，把不是 square-free 的数对剪枝掉跑得飞快。
\color{red}\text{P10175 「OICon-02」Subtree Value}
- 枚举每个
p^c 做，最后合并答案。相当于每个点有个多项式(a_i+x) ，记一个连通块的权值为里面所有点多项式的乘积。考虑对每种连通块大小求出该大小的所有连通块的权值之和，然后带入该连通块的大小求值即可。考虑插值求出多项式，注意到x^{\underline{pc}} \equiv 0 \pmod {p^c} ，于是这个多项式一定不超过(pc-1) 次。复杂度O(n^2UV) 。
\color{red}\text{P9157 「GLR-R4」夏至}
- 设
F(n,m)=\sum_{i=1}^m f(ni) ，答案为\sum_{i=1}^n F(i,m) 。计算F(n,m) ，枚举n 最大质因子p^c 在m 侧被选了几次，则F(n,m)=\sum_{i \ge 0} \left(F\left(\frac{n}{p^c},\left\lfloor\frac{m}{p^i}\right\rfloor\right)-F\left(\frac{n}{p^{c-1}},\left\lfloor\frac{m}{p^{i+1}}\right\rfloor\right)\right)f(p^{c+i}) 。这里有一步小容斥，就是用至少i 次的贡献减去至少(i+1) 次的贡献，强制多钦定的那个p 可以放到n 那一侧，所以c 就变成(c-1) 。递归边界为n=1 ，此时 PN 筛计算即可。这里递归的总转移数在本题数据范围下只有2 \times 10^7 的样子。预处理n \times m \le 10^6 的F(n,m) 可以显著优化常数。
\color{red}\text{P8570 [JRKSJ R6] 牵连的世界}
- zak 科技。求
\sum_{i \le n \land j \le m}f(ij) 其中f(n) 为积性函数。如果只算\gcd(i,j)=1 的f(ij)=f(i)f(j) 之和，直接莫反容易O(n \log\log n) 。考虑枚举\gcd 为d ，设h(n)=\frac{f(d^2n)}{f(d^2)} ，则h 为积性函数，且f(ij)=h(i)h(j)f(d^2) ，于是可以用刚刚的做法。总复杂度O(n \log n \log \log n) 。本题直接f(n)=\sigma_0(n)\varphi(n) 就好了。
\color{red}\text{P6837 [IOI 2020] 数蘑菇}
- 首先你会一个
O(\sqrt n) 的做法，就是先每次问两个直到得到O(\sqrt n) 个同色蘑菇（不妨设是 A），然后你问\texttt{A,?,A,?,A,?,A} 这样的东西就可以每次获取O(\sqrt n) 个蘑菇里有多少个 A。然后你要卡常。OU 告诉我们，这里有这样一个 trick：考虑取小整数k ，初始维护前k 个蘑菇可能的所有情况（有2^k 种），每次随机K=1000 种询问，取最坏情况下情况数减少最多的一种。情况减少后尝试加入接下来的蘑菇，维护总情况数保持在O(2^k) 级别。
\color{green}\text{P11927 [PA 2025] 重金属 / Heavy Metal}
- 想到折半就做完了。启示大概是单起点单终点求路径的形式很适合折半。
\color{red}\text{CF2048H Kevin and Strange Operation}
- 重新刻画操作：把所有
[1,p) 的 1 连续段向右延伸一格，然后删除开头。可以不管删除开头这个部分，最后如果操作了i 次则只保留(n-i) 位。延伸可以以 1 连续段为单位考虑，也就是选一个前缀的 1 连续段延伸一格。只需对每个 1 连续段被延伸的次数 DP。
\color{red}\text{P8519 [IOI 2021] 钥匙}
- 如果从
u 出发最终能到达v 的话，连一条有向边(u,v) 。那么我们所求的答案一定在出度为0 的 SCC 里。考虑对每个出度为0 的 SCC 求一个点，如果能求出来的话，从这些点出发暴力遍历的复杂度是对的。怎么求呢，你发现只需维护一个每个点出度至多为1 的生成森林，每次拉两个的根出来看一下有没有边，连不了之后所有根节点就是我们要的。但是这个太暴力了，我们考虑 Boruvka 的过程，每次从每棵树的根节点出发遍历，以这个树的大小的代价来获得它连向的外面的点或者直接把它标记为无出度 SCC 里的点。这样做一轮树的数量至少减半，于是是O((n+m)\log n) 的。
\color{green}\text{CF1687D Cute number}
- 实际上相当于有一些区间，然后找一个最小的
x 使得x+a_i 都在区间里。一个显然的观察是答案是O(V^2) 的。枚举a_1+x 在哪个区间，然后你注意到此时每个a_i 最后只能到达至多一个确定的区间，每个a_i 的贡献是把合法的x 对某个范围取交。这样暴力做就是O(nV) 。考虑优化，刚刚的过程实际上相当于枚举每个a_i ，找到一个它对应的区间，考虑改成枚举区间并处理它对应的a_i 的贡献。注意到如果x+a_1 所在区间长度为l 则只会枚举O(\frac{V}{l}) 个区间，所以复杂度为调和级数的O(V \log V) 。
\color{green}\text{[AGC045A] Xor Battle}
- 倒着做，维护一个集合
S 代表当且仅当走到这里的时候在集合S 里会使得0 获胜。发现S 总是可以被一个线性基表示，做完了。
\color{red}\text{[AGC044E] Random Pawn}
- 环没有任何用，可以从最大值断环为链。
b_i=0 的问题所有人都会做，见 P5155。有b_i 的情况，记答案为f_i ，就是f_i=\max\left(\frac{f_{i-1}+f_{i+1}}{2}-b_i,a_i\right) ，考虑设参数c_i 使得f_i-c_i=\max\left(\frac{(f_{i-1}-c_{i-1})+(f_{i+1}-c_{i+1})}{2},a_i-c_i\right) ，这样就归约到了b_i=0 的问题。c_i 所有人都会算。
\color{green}\text{P6222 「P6156 简单题」加强版}
直接莫反就是
\color{green}\text{P7486 「Stoi2031」彩虹}
取个
\color{red}\text{Gym103428C Assign or Multiply}
简单转化一下就变成了：循环卷积意义下 01 背包，对每个