用 .xlsx 来记真是太傻逼了。换个 .md 来记。
256. xsy5244 数数 (calc)
打个表嬴麻了。
257. xsy5255 树树（tree）
长剖推推推，差分一下过了。
258. xsy5256 数树（graph）
按照值域分块，每个块记最前最后两个点。过了。
259. pjudge21792 【NOIP Round #6】抉择
不会做。考虑乱搞！
设 \(f_{i,v}\) 表示前 \(i\) 个数，最后一个选的数是 \(v\) 的权值。记 \(mx = max(f_{i,v})\)，发现对于 \(f_{i,v} + v \leq mx\) 的 \(v\) 其实可以直接扔掉。写了这个玩意，跑得飞快。
然后 fst 了（草）。发现是忘记判 \(v \& a_i = 0\) 的转移了。无能狂怒。
260. pjudge21793 【NOIP Round #6】重生
每个任务拆成两种思考。当场二分答案。然后发现是贪心地思考能思考的东西里权值最大的。
261. pjudge21794 【NOIP Round #6】遍历
圆方树板子题。
262. pjudge21795 【NOIP Round #6】排序
考虑如何 sort 一个 01 序列。先把相邻的同色块合并。注意到一次操作之后倒过来看，相当于区间 reverse。0101010101 这个东西，按照 2|1|2|1|2|1... 分段，所以 01|0|10|1|01|0|1 -> 1000111001，每次连续段会除以 3。做完了。
263. arc167c MST on Line++
不会做！身败名裂。
考虑计算 \(a_{i+1} - a_i\) 的贡献，就是选 \(i\) 个 0，然后对于每个 0 之间的空位，长度 \(\leq k\) 的话贡献减一。那就枚举 \((l,r)\)，声称 \(l,r\) 是 0，这一对的贡献就是 \({n - (r-l+1) \choose i-2}\)。
264. arc167d Good Permutation
从小往大扫。考虑第 \(i\) 个，找到最小的和它不在同一个环的点 \(j\)。如果 \(j < p_i\)，就 \(swp(i,ip_j)\)。否则如果第 \(i\) 个所在的环有且仅有 \(\{1,..,i\}\)，也要 \(swp(i,ip_j)\)。
265. arc167e One Square in a Triangle
神仙构造。首先几个小的 \(S\) 不合法判掉（？。
考虑 \(S\) 是偶数的情况，取个以 \({S \over 2}\) 为底的三角形，这是容易的。
考虑 \(S\) 是奇数的情况。令 \(S = 2x + 1\)。 则构造 \((-1,s-1),(0,0),(3,4-x)\)，这个三角形。考虑合法的正方形 \((a,a+1) \times (b,b+1)\)。\(a = -1\) 显然无解。\(a = 0\) 有个 \((0,0)\)。注意到 \((1,{3 \over 2})\) 在三角形的边上，所以 \(a =1 / 2\) 也无解。
266. lg9746 「KDOI-06-S」合并序列
记 \(f_{l,r}\) 表示 \([l,r]\) 这个区间能不能缩成一个点。
\(f_{l,r} \leftarrow f_{l,p1} * f_{u,v} * f_{p2,r} * [s(l,p1)\ XOR\ s(u,v)\ XOR\ s(p2,r) == 0]\)。
设 \(g_{r,v}\) 表示最大的 \(l'\)，使得存在 \(r' \leq r，f_{l',r'} =1,s(l',r') = v\)。
对于固定的 \(r\)，枚举 \(l,p1\)。发现这相当于要找看 \([p1+1,r]\) 里能不能找到 \(u,v,p2\)。那记个 \(h_{v}\) 表示最大的 \(u\)。每次算完 \(f_{l,r}\) 之后顺便更新一下即可。
267. cf1868d Flower-like Pseudotree
想题的时候神志不清，当场暴毙。。
首先特判掉一些平凡的情况。比如是不是一个大环之类的。
扔掉所有叶子，然后假装环的长度是 2，把 deg 最大的两个点当作环点，变成两条链。发现如果链长度相等就做完了。链长度不相等考虑把多出来的那个点扔上去。发现扔不上去只有 \(O(1)\) 种情况。大力分讨就行了。
268.cf1864g Magic Square
考虑如果有两行移动了且移动距离相等，并且有一列移动了，则一定不合法。交换行列同理。
对于每一行，如果有数操作完行不变，这一行的移动距离只能是列的变化量。如果没有数操作完行不变，说明每一列都移动了，和上面矛盾。
那就对于当前局面，发现会有若干个合法的行或列，并且行和列只能存在一种。同时有就非法了。那就把答案乘上 \(cnt!\)。合法行的定义是转完之后，每个元素的列到了目标位置。行和列只能存在一种的证明是容易的，考虑交点即可。
269. xsy5247 树数（greedy）
鉴定完毕，不太想写。
考虑操作 2 怎么做。
假装 \(u\) 在 \(x\) 子树里面。记 \(f_u\) 表示 \(u\) 和 \(u\) 的所有轻子树里到 \(u\) 的最小距离。枚举 \(u\) 这条重链上的每个点 \(v\)，往里的答案就是 \(min (f_v + dis(u,v)) = -dis(u,top_u) + min(f_v + dis(v,top_v))\)。所以记 \(g_u = f_u + dis(u,top_u)\)，维护 \(g\) 即可。往外的答案可以通过维护 \(h_u = f_u - dis(u,top_u)\) 计算。维护 \(h\) 即可。
\(u\) 在外面的是容易的。发现操作 3 跟上面的讨论没啥区别。不管了。
考虑 \(rev(1,u)\)。每条重链 \(rev\) 的是重链的一个前缀。非常好维护啊.jpeg。然后有 \(O(\log)\) 的 \(f\) 需要处理，非常好维护啊.jpeg。
270. cf1731f Function Sum
非常傻逼的一个题。直接枚举每个点，权值，左右两边的信息。是个多项式，随便插插就搞定了。
271. cf623d Birthday
有点意思。
设 \(f(t)\) 是第 \(t\) 时刻依然存活的概率。答案就是 \(\sum _{i}^{+\infin} f(i)\)。
注意到 \(f(t) = 1 - \prod_i (1 - (1 -p_i)^{c_i})\)，其中 \(c_i\) 是这个人被抓的次数。发现每次选最优的人抓必然不劣。暴力模拟 \(10^6\) 轮即可。
272. cf923d Perpetual Subtraction
把式子写出来，发现是线性变换的形式，大概是要把一个上三角矩阵对角化。上三角矩阵的特征值就等于对角线上的值。所以特征向量可以直接 $Av - \lambda Iv =0 $ 大力求出来。然后你发现 \(A = BCB^{-1}\) 的 \(B\) 和 \(B^{-1}\) 都非常好看，就做完了（？。
273. cf1427g One Billion Shades of Grey
感觉比较牛逼。
第一个思路是假装这东西是 \(p = 1\) 的保序回归！所以还是可以整体二分。至于向 \([a,b]\) 取整的证明，感觉不是很会证，也懒得看题解了，假装它是对的！
第二个思路是假装上面向 \([a,b]\) 取整是对的。假装它是 01 序列，每个值都 01 一下就做完了。发现 \(O(n)\) 次 \(dinic\) 的图都差不多，所以可以暴力退流降一下复杂度。
274. 浅谈保序回归问题 高睿泉
我来写个阉割版的学习过程！
前面的若干东西咕了。
保序回归的定义：有一个 DAG（*），\(u \rightarrow v\) 表示 \(f_u \leq f_v\)。对每个点有 \((y_i,w_i)。\)要求最小化 \(\sum\limits_{i=1}^n w_i |f_i - y_i |^p\)，其中 \(p \in [1,+\infin)\)。
*：我也不太确定是不是一定要 DAG。感觉有些情况下不是 DAG 也能做（？）。有无懂哥指导一下。
\(p=1\)
称数列向 \([a,b]\) 取整，即小于 \(a\) 的变成 \(a\)，大于 \(b\) 的变成 \(b\)。记 \(pos_p(S)\) 为满足 \(\sum_{i \in S} w_i|y_i -k |^p\) 最小时的 \(k\) 的取值。在 \(p = 1\) 的情况下，\(pos_p(S)\) 是一个区间。在 \(p> 1\) 的情况下，\(pos_p(S)\) 是一个点。
引理：我们声称，对于一个区间 \([a,b]\)，如果不存在集合 \(S\) 使 \(pos_p(S) \sub [a,b]\)，且存在原问题的答案序列 \(f_i\) 满足均不在 \((a,b)\) 内，则 \(f_i\) 向 \([a,b]\) 取整后等于令 \(f_i \in [a,b]\) 的答案。证明可以使用若干调整和反证法！我不会证！我感性理解。
然后注意到，\(p = 1\) 时，\((i,i+1)\) 总是满足上述条件。就可以快乐二分了！
\(p > 1\)
注意到，上述引理是成立的。但是要找个合适的区间。因为 \(pos_p(S)\) 构成的数集是稀疏的，可以取常见的区间 \((mid,mid+\epsilon)\)。此时分别计算 \(f_i = mid\) 的权值和 \(f_i = mid+ \epsilon\) 的权值。同除 \(\epsilon\) 之后发现就是原函数在 \(mid\) 处的导数。至于 \(f_i \leq f_j\) 的条件可以看作 \(i \geq mid \rightarrow j \geq mid\)，可以最小权闭合子图实现。这样可以求得原问题的 实数 解。
\(p> 1\) 的整数解
假装我们现在正在进行 \(solve(l,r,vec)\)。
当 \(r-l > 1\) 的时候，我们可以用上述算法递归 $solve(l,mid,low) $ 和 \(solve(mid,r,high)\)。
当 \(r-l = 0\) 是容易的。
当 \(r-l = 1\) 时，不能使用上述算法！但是此时只有两种取值，所以也可以做一个最小权闭合子图，这样就做完了。
\(p = \infin\)
要求最小化 \(\max_{i = 1}^n (w_i |y_i - f_i|)\)，同样有 \(f\) 的偏序关系。
可以当场二分答案，然后做个 \(DAG\) 上 \(dp\)，是 \(O(m \log v)\) 的。
后面的部分咕了。
275. loj #3301. 「联合省选 2020 A」魔法商店
我草来活了。
看一眼，发现价格最低的限制相当于以 \(a\) 做基，然后对于 \(v_i = v_{a_{p1}} \ xor ... \ xor \ v_{a_{pk}}\)，连边 \(p_j \rightarrow i\)。价格最高同理。
那就是裸的 \(p = 2\) 的保序回归。
276. cf1615h Reindeer Games
尼玛，这位更是重量级。
277. cf1854e Game Bundles
没猜错的话，大概是随若干个值很小的，和等于 30 的数。前面大力做背包。然后后面放 > 30 的数。
猜对了。
278. pjudge21739 【NOIP Round #5】青鱼和序列
把整个序列看作 01 序列，0 代表正的 \(a_1,..,a_n\)，1 代表反的。
发现要么全是 0，要么 0 和 1 数量相等。直接算就行了。
279. pjudge21740 【NOIP Round #5】青鱼和怪兽
大概暴力转移会成环。那就二分答案，设 \(dp_{n,m} = x\)，看最后自己能不能更新自己。
280. pjudge21741 【NOIP Round #5】青鱼和区间
草怎么没做出来。
设覆盖 \(i\) 的集合是 \(S_i\)，问题转化成不能有 \(S_i = S_j\)。
考虑第一个没被选进区间的 ，找到一个最右的 \(j\) 满足 \(S_j = S_i\)，把 \([i,j]\) 看作一个子区间。假装这样可以搞出 \(t\) 个区间，贡献就是内部瞎选乘上 \(dp_t\)。
背包即可。
281. cf1838f Stuck Conveyor
假装我们已经找到了问题点的方向，那就可以很简单地 \(\log n + 1\) 次操作找出它的位置。
用 \(O(1)\) 次询问找到方向是容易的。可能会有点 corner case，不管了。
282. cf1781g Diverse Coloring
不会做呜呜呜呜呜呜呜呜。
声称除了四个点的菊花图，其余所有树的答案都是 \(n \bmod 2\)。
考虑构造。链和点数 \(\leq 3\) 是容易的。否则以某个三度点为根，记 \(d_u\) 表示 \(u\) 子树内，另外一种颜色减去 \(u\) 的颜色的个数。对于不是根的点，容易做到 \(d_u \in [-1,2]\)。
接下来暴力合并 \(d_{rt}\)，枚举 \(d_{rt} \in [-4,5]\) 的每个可能的儿子的状态，发现把 $d_{rt} $ 卡进 \([-1,1]\) 是相对容易的。其中有一种情况需要反转一条链。不过不重要！那就做完了。
283. pjudge21622 【ExPR #1】守卫 2
可以看出，每个点的答案，就是以它为根，进行某种直链剖分，最后前 \(k\) 长的链距离和。所以一个点的最优解是它的长链剖分。
考虑以直径的两端分别 dfs，最后答案取 max。钦定 \(u\) 有一条链通向 \(rt\)。考虑 \(u \rightarrow v\) 的变化，按照 \(v\) 是否是 \(u\) 的长儿子讨论，只会加入/删除 \(O(1)\) 条链，所以做完了。
题解看起来只用 dfs 一次，看起来和我差不多，但不钦点 \(u\) 有 \(rt\) 的链。换根的时候讨论一下就行。
284. pjudge21620 【ExPR #1】下降
草怎么还是不会。
考虑描述下降的过程。发现是从后往前扫，记录一个 \(vis\) 数组。扫到 \(x\) 的时候，找到 \(\leq x\) 的第一个 $vis_x =0 $ 的位置 \(y\)，那么这个位置最终就会是 \(y\)。如果 \(y \geq 1\)，就把 \(vis_y\) 复制成 \(1\)。
考虑如何 dp。设 \(f_{i,j}\) 表示当前从后往前扫完 \(i\)，\(vis\) 数组最底下的连续段长度恰好是 \(j\) 的方案数。假装我们不区分每个数的第一次和第二次出现。设 \(i\) 前面有 \(rem\) 个非 0，\(out\) 个 0。
扫到一个 0 的时候，\(f_{i,j} \leftarrow (j-out) f_{i+1,j}\)。因为不区分第一次和第二次出现，所以最后一段共有 \(j\) 个空位，然后前面有 \(out\) 个数已经填了。
扫到一个 1 的时候，考虑这个数是否会让 \(j\) 变化。如果不变，就是随便扔到上面去，\(f_{i,j} \leftarrow f_{i+1,j}\)。否则枚举 \(nj = j+1+k\)，\(f_{i,nj} \leftarrow {rem-j \choose k}coef_k (k+2) f_{i+1,j}\)。\(coef_i\) 是选 \(i\) 个数，恰好填满 \(i\) 个连续的格子的方案数。
285. pjudge21614 【PR #1】守卫
怎么又不会。自闭了。
只有最小生成树上的边有用。从大到小尝试删边，合法性用 flow 判断。然后就对了。困了不想写了。
286. cf1034d Intervals of Intervals
绷。二分，考虑求出 \(\geq mid\) 的线段数。考虑用 set 维护线段。扫描线，一个线段 \(i\) 覆盖旧的线段 \(j\)，意味着 \([j+1,i]\) 的贡献 += 线段长度。然后双指针即可。
287. cf1845e Boxes and Balls
傻逼题。0 看作 -1。发现前缀和的差至多是根号。暴力 dp 即可。
288. cf870f Paths
发现有且仅有 1 和 \(> {n \over 2}\) 的质数不能被到达。
一步到达的大概是 \(\sum i - \varphi(i)\)。
两步能到达的是 \(x = px' \rightarrow pq \rightarrow qy' = y\)。枚举 \(p\) 和 \(q\) 计算即可。
三步一定能到达，因为 \(x = px' \rightarrow 2p \rightarrow 2q\rightarrow qy' = y\)。
代码懒得写了。
289. cf1083f The Fair Nut and Amusing Xor
什么答辩题。考虑令 \(c_i = a_i \ XOR \ b_i,d_i = c_i \ XOR \ c_{i+1}\)。发现一次操作就是 \(d_i\) 和 \(d_{i+k}\) 同时异或 \(c\)。那就模 \(k\) 分段，相当于问有多少个点的前缀 \(XOR\) 是 0。值域很小，分块瞎搞搞就做完了。