2022 训练实录
22-06-24
NOIO2020 #2 游戏
好久没搞 OI 真的蠢了。
恰好立刻转至少，所以设 \(f(x)\) 为钦定 \(x\) 对非平局回合的情况，\(g(x)\) 为恰好 \(x\) 对非平局回合的情况。那么：
\[f(x)=\sum^m_{i=x}\binom i n g(i) \]应用二项式反演有：
\[g(x)=\sum^m_{i=x}(-1)^{i-x}\binom i n f(i) \]剩下的问题就是求出 \(f(x)\)，套路的，设 \(f_{u,i}\) 表示在以 \(u\) 为根的子树内已经选出 \(i\) 对的方案数，树形背包转移即可，记得考虑选 \(u\) 的方案。
时间复杂度 \(O(n^2)\)，评价：Common。Link
APIO2022 排列
优质题，很可惜不懂正解。
考虑几个乱搞，第一个是直接丢不相交的若干个单调递增序列上去，但是似乎不怎么优秀，第二个是考虑二进制拆分，考虑添加进来的丢前面还是丢后面，似乎可以有 \(90+\)。
考虑优化第二种做法，或者说，我们继续乱搞。首先将这个做法进行劣化，比如说我们考虑每一次添加都使现在的上升子序列增加的尽可能多但是不要让他爆掉 \(k\)，可以考虑利用 DP，\(\displaystyle f_i=1+\sum_{a_j
这个做法也足够优秀，但是仍然没有满分潜质，考虑随机化，因为每一步如果都拉满反而容易达不到效果，随机地看需不需要随机地取一个更劣的结果就行了。
启示：一个做法烂记得别抛弃它，万一搞了个随机化就莫名其妙过了呢。
评价：Great。Link
APIO2022 游戏
牛逼题，大概自己研究了 1h，然后看题解理解了 1h。
显然的是，考虑维护一个 \(pre_i\) 表示最大的可以来的传送器，\(suf_i\) 表示最小的可以到的传送器，当一个非特殊点的 \(pre_i\ge suf_i\) 时，成环。暴力地进行搜索可以在 \(O((n+m)k)\) 的时间复杂度内解决问题，获得 \(60\text{pts}\)，想到这里就想不动了。
考虑优化，这里很难想到的是将 \((pre_u,suf_u)\) 看成一个区间，同时注意到不用实时维护 \(pre_i,suf_i\) 而是只需判断。考虑一条新边 \((u,v)\)，提取出 \(u,v\) 分别对应的区间，根据这两个关系讨论：
-
相离，仅当区间 \(u\) 在区间 \(v\) 右边时找到环，此时存在一个 \(pre_u\to u\to v\to suf_v \to pre_u\) 的环。
-
重合，不可能出现环。
-
相互包含，此时考虑更新 \(pre\) 与 \(suf\)。
-
区间 \(v\) 在 \(u\) 的左儿子内：更新 \(suf_u\) 为 \(suf_v\)，然后递归，注意到实际上只需要把区间 \(u\) 变成它的左儿子就行了。
-
区间 \(u\) 在 \(v\) 的左儿子内：更新 \(pre_v\) 为 \(pre_u\)，然后递归，与上述同理。
-
其他情况不需讨论。
-
上述的递归指，暴力扫出所有与它有边的点进行 extend。
启示：注意一些东西不需要实时维护的就不要实时维护，类似于搞一个懒标记会更好。
时间复杂度：势能分析可得为 \(O((n+m)\log k)\)，评价：Epic。Link
22-06-25
SNOI2017 炸弹
极其显然的有一个线段树优化建图的大复杂算法，很明显我不想写，不过考场上可能就开冲了，时间复杂度 \(O(n\log n)\)，期望得分 \(100\) 分，但是很难写，爪仑还在写！！！1。
有一个更为优秀的一个单调栈做法，虽然实际上较为隐性：
考虑先求出单独向左炸炸的最远是 \(L_i\)，这里同时用向左的炸弹反向炸回可能炸出的半径 \(r_{L_i}-(x_i-x_{L_i})\) 更新 \(r_i\)，这是一个类似单调栈的过程，线性完成：
FOR(i,2,n) while(L[i]>1&&x[i]-x[L[i]-1]<=r[i]) {
r[i]=max(r[i],r[L[i]-1]-(x[i]-x[L[i]-1]));
L[i]=L[L[i]-1];
}
接下来考虑 \(R_i\) 的求出，注意这里可能存在右边炸左边的情况，同时左边炸右边已经在上面考虑：
ROF(i,n-1,1) while(R[i]由此，问题在 \(O(n)\) 的时间复杂度内完成，评价：Great。
启示：对于一道题目需要有所取舍。Link
SNOI2020 水池
纯纯的码农题，我还没写，先鸽一会。
一个一个操作来分析：
-
操作一：实际上是向左找出第一个高过 \(h\) 的挡板，向右找出第一个高过 \(h\) 的挡板，然后就 cover 一下完事。
-
操作二：考虑向左找到与之液面相平的，向右找到与之液面相平的，此时左边液面变为右挡板高度，右边液面变为左挡板高度，打懒标记即可。
-
操作三：单点修改，跑路。
-
操作四：单点询问，跑路。
可持久化就可持久化线段树就行了。
时间复杂度 \(O(n\log n)\)，评价：Trash。
坑点：修改操作二的时候注意依赖顺序。
启示：想清楚再搞。Link
22-06-26
CTT2017 简单数据结构
数据结构测试考这个？
这个题显然不是数据结构，直接 DP。
因为题目涉及到开头数，所以设 \(f_i\) 表示以 \(i\) 开头的最长上升倍数倍数子序列长度，\(g_i\) 表示答案为 \(i\) 的开头个数。
题目有以下三个特殊点：
-
每个数互不相同。
-
值域是 \(10^6\) 而非 \(10^9\)。
-
每个数最多进来 \(10\) 次。
根据 1.，\(f_i\) 的最大值仅为 \(20\)，因为 \(2^{20}=1048576>10^6\)，所以说在维护出来 \(f_i\) 之后我们可以以 \(\log M\) 的时间复杂度内求出答案，这部分的复杂度是 \(O(Q\log M)\)。
接下来的问题是维护 \(f_i\)，考虑要求的操作：
-
左边插入，枚举一手倍数，是均摊 \(\log\) 的。
-
左边删除，最左边的一点影响都没有 haha，直接删了跑路。
-
右边插入，我们需要枚举约数，考虑到一些更新上的问题，我们新设出 \(h_{i,j}\) 表示以 \(i\) 开头的，长度为 \(j\) 的上升倍数倍数子序列有多少个，这样可以以 \(\log M\) 的代价推出 \(f_i\)。
-
右边删除，与上面类似。
发现单次复杂度很诡异，是 \(d(M)\log M\) 的，所以复杂度就是 \(O(Qd(M)\log M)\) 了？但是就是过了。
评价：Great，Link。
启示：注意到每一个细节，一些看似不可做的题可以迎刃而解。
APIO2022 交互库配置
虽然好像不算做题，但是先写进来吧。
配置了一手 APIO 的三个题，感觉上还在架构上存在一些问题，可能后期还需要调整？
-
mars：唯一的通信题，在配置的途中暂时没有考虑传信息的可能，我感觉打乱交互顺序就行了，暂时先搁着，等有人这样艹过去了再来改。
-
game：挺鬼畜的交互库解法，十分神必，大概是保证了次数一定用完？感觉有点拉，我在修改的时候把自己标程粘上去了。
-
perm：最简单的配置吧，All OK。
加起来就用了 4h+ 吧，慢了。
22-06-27
BJOI2019 光线
随机到的，什么沙比提。
考虑合并两块玻璃，求出新玻璃的折射率与透光率。
\[a=a_ia_j+a_ib_jb_ia_j+a_ib_jb_ib_jb_ia_j+\ldots=a_ia_j(1+b_ib_j+(b_ib_j)^2+\ldots)\\ b=b_i+a_ib_ja_i+a_ib_jb_ib_ja_i+\ldots = b_i+a_i^2b_j(1+b_ib_j+(b_ib_j)^2+\ldots) \]由等比数列求和，或者说 \(\frac 1 {1-x}\) 这类封闭形式，有：
\[a=\frac{a_ia_j}{1-b_ib_j},b=b_i+\frac{a_i^2b_j}{1-b_ib_j} \]模拟即可，时间复杂度 \(O(n\log \bmod)\)，作为送分题十分到位，评价：Common。
Hint：以后还是自己写一个 modint 好，不然这种蠢题又会调上一会。Link