10/25 – 21noip赛前20天 day8

T1构造题，T2线代，T3是树上问题，T4字符串。

选择先做T2，首先一眼有 $50$ 分的做法，直接暴力枚举三元组，放到一个矩阵里，求三阶行列式，若行列式不为 $0$，则三个向量是线性无关的。

后面又想到去把 $n$ 个向量都扔到一个矩阵里，每次枚举前两个，快速找到第三个，但并不会快速找到第三个的方法，只能是一些常数级别的优化。赛时发布通知，说 T1 为了防止被错误做法卡过去，把数据加强了。就去看 T1 了。

先自己手算了前 $20$ 的，发现方案不唯一，于是就都列出来，然后找有没有统一的构造方法。

先发现对于偶数 $x=2\cdot y$，可以递归到子问题 $y$，然后把每个数都 $\times 2$ ，一定合法。

然后就开始找奇数的规律。发现要想不和递归后的问题重复，就每次减去 $3$ 的最高次幂，然后再递归子问题。

不确定对不对，因为 $100$ 分要高精度，先写了个 $70$ 分数据范围的验证正确性。

构造题验证正确性要自己写 $\rm{checker}$，考场上写错了，调了半天 $\rm{checker}$，差点以为是自己解法错了。

时间也不是很多了，就没去写高精度，先去看了看后面的题。大概花了半个小时，得到了自己暴力都不会的结论。

最后还剩二十分钟去写高精度，没调出来。

估分 $70+50+0+0$，得分 $0+50+0+0$。

第一题输出格式错了，后面因为不舒服就没检查，改完上去就有 $70$ 分，加个高精就是 $100$ 分。

排名：$92/156$。

10/26 – 21noip赛前20天 day9

按题目编号顺序开题。

T1又是奇怪的结论题，手造数据试了试，猜了一个：$\operatorname{Ans}=\max($白色连通块个数，黑色连通块个数$)$.

试了好几组自己造的数据，都是对的，就交上去了，去看了 T2。耗时 $\rm{30min}$.

观察数据范围发现，因为取模的特殊性，打暴力都要写高精度，肯定是直接找到策略贪心地选。

思考一下发现，对于每个数而言，一定先做操作三，其次是连续的操作二，最后做操作一。想到这，就感觉快做出来了。

想到赋值操作只保留最大的那次，转化为加法操作。对一次加法操作，转化为乘上 $\frac{a}{b}$，然而并不知道连续的加法操作如何处理，就没继续往这个方向想了。

赛后才知道，距离正解只差一步了，因为加法一定是先加大的数，再加小的数，所以排序后，加上的是连续段。把每个加法操作转化为：作用在前一次加法操作后的数上的乘法操作即可。然后直接全局找最大的 $m$ 次乘法操作即可计算。

又想了一会还是不会（因为正确的方向已经被自己否定掉了），写了 $30$ 部分分，在 1h30min 的时候回到了T1。因为是猜的结论，想拿对拍验证一下，结果WA on Test #1.

看了一下，确实是个反例，而且直接随机数据就很容易出反例。开始重新想 T1。

模拟了一下过程，如果把连通块缩成一个点，构成的新树一定是：一层黑，一层白，一层黑，一层白这样交替下去的。然而还是不会，就在新树上找规律。

想在新树上DP，想了个状态+转移方程写出来了，对拍能找到反例。于是就循环在找反例、改DP上 1h 左右，最后终于找到一组反例，设定的状态完全无法解决。突然想到把上面两种错误做法合到一起，取最优解，交上去，赛后发现也可以获得 $70$ 分的高分。

但毕竟没有正确性，只能再重新想。在还剩30min的时候猜出：答案为缩点后的树的直径，写完之后拍不出来反例。感觉很神奇，就把前面的删掉，只保留了树的直径。

T3T4没时间了。

估分 $100+30+0+0$，得分 $100+35+0+0$.

T1对拍假做法花了太长时间，导致没看后面的题。不过T3T4没几个人拿到部分分。

所以在对拍出错解之后，应该先检查一下正确性再继续调代码，不然如果最后发现做法假了，就会浪费很多时间。

排名：$91/158$。

10/31 – 21秋季noip10连 day8

先看了T1。30min之后连样例都看不懂，还和期望有关，估计不会，就直接跳了。

T2，首先注意到数据范围中 $1\leq Q\leq 15$，想要容斥处理。手推了一下只会处理两个区间的交集，三个往上就不行了。先写了个10分暴力，1.5h的时候写完。

观察了一下榜，发现T4有不少提交，把T3和T4题意看完之后，先去尝试做了T4。对没有修改的情况，又是结论题。试了几组数据完全找不到规律，暴力也不知道每次该怎么修改，2h时去写C。

看完题感觉和数论相关，但我并不会快速判断能否到达源点，也想不到什么把状态转化的方法。对暴力的部分，想了一个分层图的做法，要分 $2^n$ 层，时间复杂度不是很好，估计也写不出来，就继续回去推T2了。

$\rm{sub2}$ 中 $1\leq Q\leq 8$。想到了一个方法是按区间端点离散化，枚举每段内模 $9$ 的余数，再判断是否合法，复杂度分析上是 $10^{2Q}\cdot \log Q$ 的，但如果在 DFS 的同时判断当前区间是否合法，并且区间端点有重合的话，也许有 $30$ 分。

3.5h时通过特别水的大样例。

再回来看T3，发现打暴力的 $40$ 分并不需要分层图，只需要在 DFS 时加一维：当前所学习到的移动方式即可，用二进制压缩的方式存到一个数里面。这样 DFS 状态数最多是 $(2|x_i|)^2\times 2^n=400\times 400\times 32=5120000$.

打标记的时候习惯性的加了个回溯，找了半天才发现不需要回溯。删掉之后在本地跑样例会爆栈，终端报 segmentation fault.

这时候就剩五分钟了，静态查错也看不出来啥问题。突然想到可能是Mac的本地栈空间比较小，在OJ上交了一下，确实能正常运行样例。

最后两分钟发现 T3 无解的情况要输出 $-1$ 而不是最大值，补了个特判交上去。

估分：$0+(10\sim 30)+40+0$，得分 $0+10+50+0$.

T2有 subtask 绑定，$30$ 分的部分超时了一个点。T3没有 subtask 绑定，输出的 $-1$ 多拿到了 $10$ 分。

排名：$39/168$，大部分人总分都没上 $100$。

11/07 – 21秋季noip10连 day9

按顺序开题，第一题看懂之后就能有一些思路。

先想到的是预处理出 $f_{i, j}$，表示对于第 $i$ 种狗子，选其的任意一个子集，子集的智力和 $\bmod m$ 为 $j$ 的方案数。

对于前 $60\rm{pts}$ 的数据， $a_i\leq 10$，$f$ 可以用组合数直接算。1h左右想到这里。

之后，每种狗子只能选一种 $\bmod m$ 的取值，于是就变成分组背包。耗时1.5h，估分 $60$。

然后想满分做法，当 $a_i$ 增大时，复杂度瓶颈在预处理部分，想了好久不知道咋弄， 就去看 T2 了。

T2题面里说是字符串，读了一遍就知道，这题和字符串的算法没关系。

先手模了一下数据范围里的特殊性质，发现和奇偶性有关。大概是先倒着隔一个选一个，再正着也来一遍。

又想到在 $ai$ 和 $a{i+1}$ 之间的这段，一定是整体正或者负，所以就每段只留 $2$ 个数，写了个大一点的数据手模。

发现规律还是类似的，倒着的时候字符串内部为正序，正着的时候字符串内部为倒序。就直接模拟，线性复杂度，估分 $100$，还剩 1.5h。

去看了一遍T3，没什么思路，先跳到T4了。

看懂题之后 $n^2$ 的暴力很显然，有 $30$ 分。还有 $10$ 分的特殊性质，用前缀和优化一下就好了。估分 $40$，写完还剩1h.

T3还是不会，返回去看T1。往组合上面想，不可避免的要枚举子集大小，复杂度里直接带着 $10^9$。还剩 20min 的时候终于想到能利用周期性质的做法了。因为只需要考虑一个周期与前面已经处理好的连续周期之间的合并，每次转移的方法一定是相同的，考虑矩阵快速幂。

复杂度是 $\mathcal{O}(m^3\log_2 a_i)$，往里面带数值的时候把 $m, n$ 弄混了，导致 $20^3\rightarrow 100^3$，没看错也写不完了。

赛后证明这种矩阵快速幂做法可行，但不必要这么麻烦。存在只用矩阵快速幂、不用分组背包的做法，也有都不用的做法。

估分 $60+100+0+40$，得分 $60+100+0+40$，排名 $77/168$.

T1一大堆人过，赛时思路卡在一个方向上的时间太久了。

11/08 – 21noip赛前20天 day15

先读了每道题。做T1，拿到之后只想到 $\mathcal{O}(n^2m)$ 的暴力，空间复杂度也要 $\mathcal{O}(n^2)$，能拿到 $30$ 分。看完题+写完这部分花了1h.

继续想正解，题目最下面说：

附：需要用 __builtin_popcountll() 来计算 64 位整数的 popcount，而不是 __builtin_popcount()。

等于 $64$ 的是 $m$，是操作的次数。想的过于复杂导致没做出来，过了30min去看T2。

T2，最大化每段平均值的最小值，想到二分答案。想如何 $\rm{check}$ 的过程中先想到了DP做法，就去往DP方向上想了。能找到好多种状态表示，与序列前 $i$ 位，已经分出 $j$ 段，最小的平均值为 $k$ 中的一些有关。

在 2h 的时候确定了一种时间复杂度为 $\mathcal{O}(n^2k)$，空间复杂度为 $\mathcal{O}(nk)$ 的 DP，$k\leq n\leq 500$ 可以过，$40$ 分。

继续看怎么优化这个DP，对着转移顺序看了一会，没发现可以用数据结构维护或者和可以利用的单调性。

再想二分答案的 $\rm{check}$ 过程，整体减掉 $x$，就等价于要把序列分成 $k$ 段，每段元素和 $\geq 0$。又想DP处理这个，不会。

还剩1h，去看了一眼 T3 和 T4，只有 T4 的暴力可做，有 $20$ 分，先没写，回去看 T1。

又发现 $n\leq 2\times 10^4$， 感觉题意就是可以 $\mathcal{O}(n^2)$ 加小常数通过。

想到对每个点对单独计算贡献，把每个点在 $m$ 次操作中处于的点集压到 unsigned long long 里面存。

具体地，$v_1[i]$ 拆成二进制位之后，$v_1[i][j]=1$ 当且仅当 $i$ 在第 $j$ 轮的时候处于点集 $x$，$v_2[i]$ 同理。

这样可以通过简单位运算得知，每个点对之间在哪些轮次时会被翻转，用题目给到的 __builtin_popcountll() 计算 popcount 即可。

调完还剩 15min，去写 T4 的暴力。写完只花了不到 $10$ 分钟，但过不了样例。

到最后也没看出来是因为 $i,j$ 写混，丢掉 $20$ 分。

估分 $100+40+0+0$，得分 $100+50+0+0$，排名 $101/147$.

11/10 – 21noip赛前20天 day17

T1 看上去和博弈论相关，两人在过程中都按照最优策略去选，暴力都没法打。

对着大样例模拟了一个多小时，发现对于每个环，只有两种情况。第一种是先手获得 $4$，后手获得 $a_i-4$；第二种是先手获得 $0$，后手获得 $a_i$，并交换先后手的顺序。

如果对每个点搜索所属情况复杂度是 $\mathcal{O}(2^n)$，能拿到 $60$ 分，可以接受。

但赛后发现这样是不正确的。

对于选取的顺序问题，在想到上面的两种情况之前，感觉上应当升序或者降序去取，模拟大样例的时候也是按照升序去做的。

写代码的时候没加 sort，发现也能通过大样例，于是就忽略了顺序问题。考试最后几分钟发现了这个问题，因为其实并没有想清楚排序有没有必要，就没有加上去。

由于数据点绑定 $\rm{subtask}$，$60\to 0$。

写完 T1 还剩 2h，去做 T2。

T2 看懂题面就去打暴力了，用并查集维护是否在同一个连通块内，每次判断需要合并的两点是否已经属于一个连通块。

写了一下，能过大样例也就没想太多，直接交上去了。

然而这样并不是正确的。在连通块中，是允许存在偶环的，只是不允许存在奇环。所以更准确的，应当判断合并后是否仍然是一张二分图，我暴力的方法是不正确的。

于是这题也 $0$ 分了。

去看 T3&4 还剩 1h。

想了半个小时的 T3，发现拿分都比较困难，就去写 T4 的暴力。

首先有 $10$ 分暴力直接枚举，后面还有个 $20$ 分的部分，感觉需要在线段树上操作，比较麻烦，想清楚的时候只剩 10 分钟了，也没去写。

赛后发现后面的 $20$ 分有不需要线段树的做法。时间复杂度虽然没有保障，但在随机数据下跑的很快，也可以拿到这 $20$ 分。

估分 $60+30+0+10$，得分 $0+0+0+10$。

在处理这种需要找性质的题的时候，没什么思路。经常是想到了差不多的地方，但是细节想不清楚，也证明不出。

多刷 CF 可能有用？