十一月
P10991 选段排序
给定长度为 \(n\) 的序列 \(a\)，和 \(p,q(p<q)\)，可以进行一次区间排序，最大化 \(a_q-a_p\)。
不会做，贺题解。
结论：排序的区间 \([l,r]\) 要么 \(l=p\) 要么 \(r=q\)。
证明：对于 \(l=p\) 的情况，如果此时 \(r<q\) 则 \(a_q\) 不变，而 \(l\) 左移不会使 \(a_p\) 变小。
如果\(r\ge q\)，\(l\) 左移如果加入一个小于当前 \(a_p\) 的数则结果不变，加入的数大小在 \(a_p\) 和 \(a_q\) 之间则 \(a_q\) 不变 \(a_q\) 变小。只有加入的数 \(>a_q\) 才有可能对答案有贡献。
在上述状态下，如果把 \(r\) 左移，删去的数 \(\ge a_p\)，则 \(a_q\) 变大，\(\le a_p\) 和上述一样贡献。
P11013 C 粉碎
题挺好就是不会做。
长度为 \(n\) 的序列 \(a\)。依次加入一个双向队列中，可以左入也可以右入，当队列中出现两个相同的数时，把这两个数以及两个数之间的数删去，求最多删几个数。
容易证明的是删除的区间是一段前缀，我们只要找到最后一组被删掉的数就可以了。
考虑 \(dp\)，令 \(f_i\) 表示是否能将 \([1,i-1]\) 中与 \(a_i\) 相同的都删去，注意这里 \(a_i\) 不删去。
转移有两种，一种是 \(pre_i\) 和 \({pre_{pre_i}}\) 粉碎，还有一种是被其他的删去的时候删去 \((pre_i,i)\)。
有一种即可：\(f_i|=f_j,j\in[pre_i,i)\)
P3514 [POI2011] LIZ-Lollipop
什么都不会做被薄纱。
长度为 \(n\) 的序列 \(a\)，\(a\in{1,2}\)，\(m\) 次询问，求一个和为 \(x\) 的区间，没有则报告无解。
容易证明，若 \(k\) 可行，那么 \(k-2\) 也可行，左右删 \(2\) 或者两边各删一个 \(1\)。
然后看左边和右边那个 \(1\) 更近一点就可以判断另一种奇偶的最大值了。
CF1733D2 Zero-One (Hard Version)
给定一个 01 序列，两种操作，一种把相邻两个数取反，代价为 \(x\)，另一种把不相邻的两个数取反，代价为 \(y\)。
约定下面 \(n\) 表示 \(1\) 的个数，\(a_i\) 表示位置。\(n\) 是奇数无解。
如果 \(x\ge y\) 那么用二操作肯定是优的，当 \(n\ge 4\) 可以用 \(\frac{n}{2}\) 次二操作。
\(x<y\) 可以dp，令 \(f_i\) 为处理完前 \(i\) 个的最小代价，\(i\) 为奇数时为处理完 \(i-1\) 个（不一定是前 \(i-1\) 个）的最小代价。
如果直接做一操作，\(f_i=f_{i-2}+(a_i-a_{i-1})\times x\)。
操作二：
\(f_i=f_{i-1},i\in even\)
\(f_i=f_{i-1}+y,i\in odd\)
CF1305F Kuroni and the Punishment
长度为 \(n\) 的序列 \(a\)。其中 \(n\le 10^6,a_i\le10^{12}\)。每次操作可以把每个数 \(+1\) 或 \(-1\)，求最少多少次操作可以把所有数的 \(\gcd\) 变为 \(>1\)。
显然答案小于等于 \(n\)，全部变成偶数。
根据上面这条，操作数大于 \(2\) 的数最多有一半，至少有一半的数不变或者 \(+1\) 或者 \(-1\)。随机五十个数分解质因数，每次判断即可。
CF467D Dreamoon and Sets
给定 \(n\) 和 \(k\)，\(n\le 10000,k\le100\)。
需要构造 \(n\) 个四元组，不出现相同元素，每一组的 \(\gcd\) 为 \(k\)。
这个 \(k\) 显然没什么用，考虑四个互质的数，至多一个偶数，可以构造出一个 \((x,x+1,x+2,x+4)\)。