2024-11-28总结

今天做了一些gmoj题，感觉t4不是很可做，没有改/wul。

赛时采用了从后往前开题的策略，感觉不是很舒服，所以noip正赛时不会这么做了。

同时测空间失手了，只用了 /bin/time -p -v 来测，忘记这个测的是用多少测多少而不是比赛时的开多少测多少。忘记了 &ST-&ED 这个方法。比赛时不能忘！

过一会儿打算学一下arbiter怎么配置，打算比赛时直接用它测。

一定要留够30分钟。

物流 (logistics.cpp) (File IO)

上面说了空间没开够。

动态最小生成树板题，但是 \(n<=3000\)，不用lct，直接暴力。

小 C 写代码（code） (File IO)

汉明距离板题，众所周知，汉明距离没有确定做法（好像有了？我正在学习。）

所以直接枚举每个数有多少个位置被修改，找到就退出，期望很优。

mod (File IO)

ucup的题：The 3rd Universal Cup. Stage 3: Ukraine Knocker - 题目 - QOJ.ac

这是一个比较人类智慧的方法：

1. 观察到我们钦定每次 \(\bmod x\) 操作中 \(x>\frac{\max a_i}{2}\)，对答案不会有影响，因为只需要在操作 \(x\) 前把它的倍数 \(2x,3x,\cdots,\lfloor\frac{500}{x}\rfloor x\) 都操作一遍，而这样对于答案是不会有影响的。
2. 观察到满足上一条后，\(\bmod x\) 操作相当于将大于等于 \(x\) 的数全部减去 \(x\)，因为 \(x>\frac{\max a_i}{2}\)，所以对答案不会有影响。
3. 一个数只会被操作（因大于等于 \(x\) 而减去 \(x\)）一遍，考虑证明：设 \(a_i\) 减去了 \(d_i\)，将操作顺序改为按 \(d_i\) 从大到小操作，如果原本的 \(d_i\) 序是满足上面那个大于最大值的二分之一的，排序后也一定也满足 \(d_i>\frac{\max a_i}{2}\)。那么从大到小排序后对于任意 \(i\) 都有 \(d_i>a_i-d_j(j<i)\)，也就是一个 \(a_i\) 不会被操作大于一次。

有了上面这些性质之后这道题真的就可以做了。将 \(a_i\) 从小到大排序，设 \(f_{i,x}\) 表示考虑 \(1\sim i\)，最小的操作至少为将大于 \(x\) 的数减去 \(x\)（换句话说，最小值至少为 \(x\)）。转移就是这次操作为减去 \(k(k> a[i]/2)\)，找到最后一个 \(j\) 满足 \(a_j<k\)，转移即可： \[ f_{i,x}\gets f_{j,\max(x,a_i-k+1)} \] 后面的取 \(\max\) 可以这么理解：因为这里最小的操作为 \(x\)，所以前面最小的操作至少要大于等于 \(x\)。同时因为这里要求将大于 \(k\) 的数减去 \(k\)，最大的数是 \(a_i-k\)，为了让这个数合法，所以前面最小的操作应该不小于 \(a_i-k+1\)。

接下来是一些杂题：

P5283 十二省联考 2019 异或粽子 - 洛谷 | 计算机科学教育新生态

我是人机，看错题目了，以为每个馅儿只能用一次，也就是异或区间不交。

原来是馅儿集合不交。

那就很容易了，利用淘金这道题的经典思路，用一个堆，最开始加入每个点与它异或之后最大的数，然后取出来之后往堆中加入第二大的数，取出来之后加入第三大的数……

P2506 SCOI2008 劣质编码 - 洛谷 | 计算机科学教育新生态

玄学dp。

猜想状态不会很多，直接用bfs即可。

然后就是记录到达字符串的每个位置的方案数为多少，如果某个时刻到达字符串结尾的方案数超过 \(3\) 就结束。