2018.1 (GZEZ-XSY)

OI

比赛策略总结

1. 一般来说可以分为3种题：签到题（往往思考5分钟能得到正解）可做题（可能需要思考半个小时）不可做题（一般来说就没有任何思路）
2. 首要的策略是花30~40分钟通读题面，做一些简单的思考（无需深入分析，以广度为主，尝试套用各种套路），找到签到题。对于这种易拿分的题，需要快速实现，并且进行对拍。
3. 其次对于不可做题（思考15min无突破口），应尽快拿性价比高的部分分（单位时间能拿到尽量多的分数）
4. 分配良好的话，此时可能还有将近3个小时，可以尝试去深入分析可做题，根据情况判断是写暴力还是正解。
5. 每道题写之前一定要再次思考是否正确，各种细节想清楚。尤其是一些分类讨论题，每一类情况都要考虑清楚再写。谨防出现写假做法的情况。
6. 写代码的时候一定要保持专注（时间允许能适当休息？），尽量自底向上实现（这与思考的过程相反）。
7. 如果估计肯定写不完了，就不要去徒劳思考正解了。
8. 最后一个小时很关键，这个时候一般要进行一些收尾工作：再次进行对拍，对于前面没写的，性价比比较低的部分分再尝试去写。
9. 最后15分钟一定不要写代码（思绪会很乱），应当以检查为主。最后5分钟就应该去检查文件，做好离场准备。
10. 需要谨记：千万不能死磕一道题
11. 在纠结中，时间就被浪费了，还不如去打打暴力

单场总结

4：T3暴力没写（10分也是分，在确保之前的分拿稳之后去写）
5：T1 FST（仔细审题！）T3 没有分析性质（题目并不难）
5：T1 没想仔细（调试浪费过多时间）导致 T2 30暴力T3 10暴力没写
39：T1 忘记基本容斥套路（浪费了3小时仍是0分），T2细节较多（一定要想清楚），切记不要在比赛的时候尝试任何新的算法！这样的代价是巨大的
17：T1 是联赛题，细节没考虑清楚；T2细节较多；T3经典套路题（和前一场一样，浪费了许多时间）
4：T1 联赛题（以后看到这种数据范围果断往分块想）；T2比较麻烦；T3竟然也是分块题，之后就应该是经典套路了。
6：T1联赛题，T2最大权闭合子图（靠对拍捡回一条命），T3阅读理解（暴力fft可以做到50分），预处理需要BM优化。
3->14:T1不想说，自己代码能力不够；T2，联赛题，不过要把调试语句删了才能A；T3，出题人用脚造数据也是niubi。暴力打稳是前提，注意不要留调试语句
怎么XJ的题质量堪忧，怎么回事啊
79：最惨的一次qaq感觉进场后状态就不大对。这次是zzq出的题。看到T1后就想到之前的T2，不会 构造/交互，直接乱搞；T2发现讨论不清楚，跳过；可能大部分时间都在想T3，可是为什么我发现结论后不会维护呢qaq。然后T1T3全场AC，暴力又因为各种奇怪的原因fst，成功垫底。

1.3

A 发现是个有通配符的KMP上DP，矩阵乘法优化一下。一个常数优化：矩阵里的元素维护一个pair，这样可以减少一半常数。

B 感觉这种不具有很好性质的MST通用搞法就是boruvka算法。这样可以划分为 $O(\log n)$ 次整体处理，限制比较少。为了不连到自己的联通块，线段树维护一个最小和次小（属于不同联通块）就行了。

C 一个比较重要的性质是可以对 $2a_i$ 取摸。剩下一个问题是能不能拼出 $B/2$，这个只要对 $O(\sqrt A)$ 种 $a_i$ DP就行了，状态的值设为最少用掉几个当前这种 $a_i$ 即可。

1.5

A 通信题，有两种做法。一种做法可以考虑线性基，一个16*16的随机01矩阵的满秩概率很高，再加入一行就可以达到$57.7\%$的概率。另外一种做法是考虑可逆（一一映射）的代数结构————多项式（其点值顺序无关），模一个大质数即可；最优可以做到$13$次询问，把$256$比特划分为$13$份，看作一个$13$次多项式即可。

B 神仙题，待补。

C 注意到每个节点的开始时间是以他为一端的链的点权和，这样状态数是$O(n)$的，直接$O(n^2)$DP即可。`

1.6

A 树分块+bitset。

B 把$O(2^{2n})$长的序列搞出来时显然的。考虑分治优化，如果只有一条边跨过，显然只用分治一边即可，实现的时候可以带上系数。类似于二维线段树的复杂度分析即可（如果不加这个优化复杂度应该和KDtree一样 $O(2^n)$）这个东西是假的，请三思。待看官方复杂度证明

C 神仙题，待补，参见CTSC2018暴力写挂。

1.8

T1思考方向错误，T2，T3暴力写挂正解不会

A 边DP边容斥，无法分辨的缩到一起。

B 枚举进位，瞎搞。

C 回文串性质，待补

1.9

T1写挂，T3思考方向不对，T2 Niubi

A 原题。

B 需要一些观察。考虑ask(a,b)与ask(b,a)均为'n'，当且仅当a或b中有1才会出现，否则一定可以确定相对关系；对于特殊的1,2,3，我们最后处理。考虑将序列划分为>3与<=3的部分，发现如果找到了一个<=3的东西，剩下两边的cmp就只需要一次了。因为限制的是交互（cmp）次数，换成二分插入排序就能过了。

C 考虑01排序网络，之后就好办了。

1.11

A 无脑分块

B 大概这种题可以怎么出：先搞一个乱搞做法，再针对这个乱搞写dmk，比赛的时候下发。简直有毒

C 环的个数是 $O(\log n)$ 的，对于每个环单独考虑。考虑分块，求出每个块在转了$k$次的贡献。在环上把特殊的点标记出来，对应位置的差为$k$时才有贡献，反过来之后就是一个卷积的形式了。

1.12

A 瞎DP

B 考虑分治，取中间值 $x$。以 $x$ 处的导数为权值，对于限制 $x \rightarrow y$ 建边。然后跑最小权闭合子图，一个结论是存在一个最优解使得包含与最小权闭合子图中的点变化后均>=x。大概利用导数非减的性质即可证明。如果不是最小权闭合子图的部分，经过$x$时候导数是正的，显然更不优。对于任意二阶导数非负的函数都是成立的

大概纠正了一直以来的两个误区：

• 最大权闭合子图不需要是DAG，不过缩点可以减小常数
• 求最小鸽一定要在残量网络上跑，例如原来的反向边能够退流，也是能扩展的。找最小割dfs/bfs还是最好的方案。

1.14

(220->120)

A 瞎点分。

B 瞎搞。

C 发现这是个对偶图为树的最短路问题。直接最小鸽就好了，限制就是个经典的模型，建流量无穷的边。
一个细节是：这里的图是有向图，所以建边还要建立inf的反向边，使得一路的方向都一样。
网络流还是要多练练。。

1.15

A 大概可以构造一个连锁反应。

B 挺妙的一个构造，考虑下面这幅图：

首先是一个结论，m 可以考虑每个块平均对应一个新的线。
对于长度1,2的，可以作为基本“零件”
考虑一个长度大于3的，在开头绕一下，然后不断延伸。
长度为2的和1的都有拼接的方案，如图所示。
一种情况是没有长度为2以及只多出一段，那么下一次开始的时候只需要绕半段。
接下来只剩下1，2的，就随便搞了。

C 按照位来分治，讨论后发现答案就是i^p[i]的最高位最大值。