P4427 [BJOI2018] 求和
谔谔题。这个问题看上去很不可维护，而且让我想到了 P5305 旧词。结果发现怎么 \(k\le50\)，那我直接跑 \(50\) 遍不就好了？
P4429 [BJOI2018] 染色
神仙题。考虑先用一些比较简单的情况搞到一些性质继续研究。那我们不妨只对原图黑白染色，得到性质“原图必为二分图”；然后显然每个连通块分开研究是完全可以的，因此只考虑一个连通块即可。
接下来可以从每个点本身开始考虑。笔者最开始考虑的是递推，去探究“假设”删去一个点以后的图和原图的关系。然后我们发现以下几个小性质：
- 所有的 \(\deg{u}\le1\) 的点均可忽略不计。
- 一条链或一个偶环必然有解（前者为后者引理）。
想到把图拆成若干个极小的偶环，然后考虑两个偶环相交时的情况。
1.交集为一个点。这个容易证明必不可能，构造一个诱导链就可以了。
2.交集为一条路径。这个情况下会产生一些 \(\deg\ge3\) 的点，而这样的个数万万不能超过两个，否则，任取两个 \(\deg\ge3\)（不妨设就是 \(3\) 吧）的点 \(u, v\)，它们的所有路径的交点一旦在除了 \(u, v\) 以外的点相交，会出现两个环相交的尴尬情况。因此 \(\deg\ge3\) 的点不会超过两个。
然后考虑 \(\deg\ge4\) 的点，有了上面的引理，可以发现绝不存在 \(\deg\ge4\) 的点。因此只要满足：
- 要么不存在 \(\deg\ge3\) 的点；
- 要么不存在 \(\deg\ge4\) 的点，仅存在两个 \(\deg=3\) 的点，且存在两个同时与他们两个相邻的二度点。
容易在合理的时间复杂度内判定这两个性质。
P4457 [BJOI2018] 治疗之雨
神秘题。预处理出每一轮的所有可能是显然的，然后我们考虑怎么递推求解原式，容易想到的是 \(f[i]\) 从所有 \(i\) 一轮操作可以到的数所转移而来，即 \(1\sim i+1\)。这样我们获得了一个 \(O(n^3)\) 的高消做法。
但是高消太慢了，考虑加速高消。发现 \(f[i]\) 可以用 \(f[i]\) 表示出来，这意味着我们这样表示一遍 \(f[i]\) 以后代入，仅求出 \(f[1]\) 然后再回代。
这样是 \(O(n^2)\) 的。
P4428 [BJOI2018] 二进制
好玩题。题目看上去十分神秘，考虑考察一下他要求的东西，看看有没有什么性质。
首先因为 \(2,3\) 很接近，所以我们打表观察一下 \(2^k\bmod 3\) 的值，经验丰富的人可以直接发现，\(2^k\equiv 1+(k\bmod 2)(\mod 3)\)。那么我就想要知道，能否分配这个段内所有的 \(1\) 让他们对 \(\mod 3\) 有“正确的贡献”。
令 \(x,y\) 分别为 \(1\) 放在权值为 \(1,-1\) 的位置的个数，容易发现总可以让 \(x=y\) 或 \(x=y+3\)，取决于 \(1\) 个数的奇偶性。因此我们可以迅速地求出某个区间是否合法——要么 \(1\) 个数是偶数，要么个数是奇数个，但是 \(x+y=\operatorname{len}-(\operatorname{len} + 1\bmod 2)\)。
现在可以快速判定了，怎么快速统计呢？用线段树可以轻易做到，反过来统计 \(0\) 的个数和区间长度的奇偶性即可。
P4458 [BJOI2018] 链上二次求和
傻逼题。出题人，你是不会好好说话吗？
原题其实就是区间加，全局查所有长度在 \([l,r]\) 内的区间，区间内元素和的和。对序列做二阶前缀和，就可以快速询问了。
如何快速修改？朴素的改肯定要炸，但是我们考虑区间加对一阶前缀和相当于加等差数列和区间加，对于二阶前缀和也有式子可推。然后随便线段树维护一下。
P4459 [BJOI2018] 双人猜数游戏
奇妙题。本来以为这个题会有什么比较厉害的结论，结果其实没有。令 \(dp[i][j][k]\) 为说了 \(i-1\) 次不知道后，说话人知不知道 \((j,k)\) 是正确答案。
那么我该怎么确定呢？要么之前就已经确定（\(dp[i-2][j][k]=\operatorname{true}\)），要么上一次可能的区间内只有这一个不知道了（，然后前一个人还不知道），要么上两次可能的区间内只有这一个不知道了，最后就是对方的新增“确定”只有一个数。
这四种分别转移，因为是提交答案（而且数据范围极小），我们可以发现这样做是合理的。按照这样 dp 即可。
标签：BJOI2018,要么,BJOI,个数,解题,2018,区间,考虑,deg From： https://www.cnblogs.com/Piggy424008/p/17938097/bjoi2018-report