Day 7 / 2024-10-02
开 T1，发现 \(n\le 16\)，感觉是个状压 DP 状物，但是手玩了半天还不会，写了个 \(30\) pts 的爆搜。
T2，感觉应该是有规律的，但是并没有细推，也没有打个表看看，最后只会 \(5\) pts 的 BFS 爆搜。
T3，删边，似乎没有多少时间了，写了 \(20\) pts 的 DFS 爆搜。
T4，邻域查询，感觉像是个数据结构题，但是不是太会。
对于 \(n,q\le 2000\)，直接 \(O(nq)\) 的 DFS，还有对于只有操作 \(3\)，求个 DFS 序并用线段树维护一下即可，这样有了 \(20\) pts。
估分：\(30+5+20+20=75\)。
实际：\(30+5+20+10=65\)，T4 DFS 挂了 \(10\) pts，唉。
讲题发现 T1 的状压是简单的，T2 的规律打表发现后也是简单的，T3 的图情况求个生成树就成为树情况了，很寄。
Day 8 / 2024-10-03
T1，卡牌游戏，有 \(3\) 种操作，很想 DP。
但是发现有后效性，不好转移，也不好设状态。
爆搜只有 \(10\) pts，太少了，必须想正解。
发现可以从后往前转移，设了个空间为 \(n^4\)，时间也为 \(n^4\) 的 DP，\(n\) 只有 \(100\)，看上去勉强可过。
发现每次转移只与后一个位置有关，于是可以滚掉一维，这样空间变为 \(n^3\) 的了。
时间方面，发现前面每一次枚举似乎都不到上界，当 \(n=100\) 时打了个表，发现只跑了大概 \(2\times 10^7\) 次，感觉很可过。
很快写完了，但是 \(T\) 组数据，本地其中一组数据都要跑 \(300\) 多毫秒，又卡了一下上界变为 \(200\) 多毫秒，很绷。抱着试一试的心态交了一发，发现 \(10\) 组数据只用了 \(100\) 多毫秒，很震撼，速度竟然是本地的 \(10\) 倍。
此时大概 \(1.5\) h。
T2 像是数据结构题，写了个 \(n^4\) 的做法（但是肯定跑不满），发现能过 \(n^3\) 的点。
考虑优化，会了 \(n^2\) 的做法。后面就不会了。写了 \(n^2\) 的 \(30\) pts。
T3 像是大模拟，题算是读懂了，但是不太会做法，跳了。
T4 对于 \(n=1\) 的情况时好算的，对于 \(n=2\) 的情况打了个表，推出了每维方案数与 \(c\) 有关的式子，上个快速幂就行了。这样有了 \(20\) pts。
结束，估分 \(100+30+0+20=150\)。
实际，\(100+30+0+20=150\)，没挂分，感觉良好。
T2 正解是大力分块，感觉好复杂，T3 似乎是手玩一下就能想出做法的，但是赛时没有时间。T4 正解怎么还有卷积，畏惧了。
Day 9 / 2024-10-04
成为全场唯 \(2\) 的小丑。
T1 感觉很可做啊，推了一下发现每一位上如果同时有 \(1\) 和 \(0\)，就一定会合并为 \(0\)。
还可以处理出每个数要向左和向右合并多少次。
但是具体到算答案就卡住了，因为不知道向左还是向右，然后就不会了。
此时 \(1\) h。
T2 感觉是性质题，但是没看出来什么，写了个 \(O(2^{n+m}nm)\) 的爆搜，样例都 TLE，寄完了。
交上去还是 TLE。心凉了。
此时 \(2\) h。
开 T3，设了个 DP，很快写出个 \(n^2\) 的 DP，写完后发现代码好短啊，对转移的限制条件也只有两个，遂考虑优化。
有两个限制条件，对于任何一个都是好优化的，但是放在一起就很复杂，想了 \(30\) min 无果。
突然发现第 \(2\) 个限制条件不需要满足，因为如果不满足，对应的 \(f\) 的值为 \(0\)，加上 \(0\) 与不加上 \(0\) 没有区别。
简单了，需要实现单点加，区间求和，写了个树状数组就过了，跑的速度还可以。
此时 \(3\) h。
T4 挺好懂的，会 \(n^2\) 的做法，鉴于现在 T1 为 \(0\) 分，又回去看 T1 了。
最后 \(1\) h 很痛苦，几乎接近正解了，但因为不会证正确性而否决，最后连爆搜也没有时间写，\(0\) 分收场。
同学们都好强，hthntd 样例有 \(350\) 分，很多过了 T1 和 T3。
估分：\(0+0+100+0=100\)。
实际：\(0+0+100+0=100\)。
出来 Heldivis 给我讲了 T1，发现很简单啊，证明也很好证，唉。
评完之后，发现过了 T3 且 T1 \(0\) 分的只有两个人，而我是其中之一。
T2 贪心做法很神奇，hthntd 的赛时 \(70\) 分 TLE 在了判无解上面，改成 bitset 判复杂度将为 \(O(\dfrac{n^3}{w})\) 就能卡过了。
总结：还是要去想部分分的，不会正解时多拿部分分。手玩和打表都要尝试。
标签：10,20,代码,30,T1,2024,100,pts,Day From： https://www.cnblogs.com/zhujiangyuan/p/18447586/dmy2024_7