260708 - 260819
260708 A
题意有时间再补
结构就是一个缺口，两边都往两边照，下面某个位置把缺口填上了。从上到下加点，如果当前点把空隙填住了，就是空隙在左右两边的 \(s_j2^{len_j\times i}\) 之和，直接做可以做到 \(O(n\sqrt n)\)。实际上一个空隙在分裂之前产生的贡献形如一个等比数列，所以可以对每个空隙单独做，时间复杂度 \(O(n\log n)\)。
260708 B
题意有时间再补
按值排序，每个队列就是取前 \(k\) 个中 \(pos\) 的最小值，因此我们只关心下降链。下降链上相邻的两个点之间的部分（左闭右开）会影响到一个区间的 \(k\)。考虑每次向队列中加入一个点会造成哪些变化，形如删除下降链上的点，或者将一个后缀的点向右平移。由于下降链的变化量是 \(O(n)\) 的，我们可以对每个区间分别计算，我们只关心两个关键操作之间的平移操作的总数，这些平移会贡献到一个区间的 \(k\)，这玩意显然可以计算。
更简单的，总变化量等于末减初再加上二倍下降的贡献，因此可以不统计上升的贡献，所以就不用维护平移了。
260708 C
题意有时间再补
轮廓线可以做到 \(O(nm2^m)\)，场上没写完。
实际上四个格子只能是 AA\n BC 或者各种旋转对称。把相邻相等的两个格子之间的边拉出来，发现每个不在边界上的格点恰好连接一条线，也就是非边界的格点的一个完美匹配。
考虑充分性，经过大量手模实际上可以近似得到与题解相同的结论，大概就是一行的一个极长连续段两侧的两个位置相等当且仅当连续段长度为奇数，然后猜测变化量和坐标的奇偶性有关，手模一下发现是对的。具体的，就是 \((i,j)\to (i,j+1)\) 或 \((i,j)\to (i+1,j)\) 的变化量等于 \(1+(i+j)\bmod 2\)。正确性是显然的，只需对四个格子分讨即可。
二分图最大权完美匹配需要用原始对偶，时间复杂度 \(O(n^4\log n)\)。
260709 A
题意有时间再补
第一次询问可以得到 \(n-1\) 位信息，之后每次只能得到 \(n-2\) 位信息，所以 \(k\) 次询问能得到 \(k(n-2)+1\) 的信息，\(k(n-2)+1\ge \frac{n(n-1)}{2}\)，解得 \(k\ge \frac{n+1}{2}\)，因此题目给出的限制就是下界。
从一个点 \(x\) 开始，按照 \(x,x+1,x-1,x+2,x-2\cdots\) 的顺序把 \(n\) 个点遍历一遍，再从连续的 \(\lfloor\frac{n}{2}\rfloor+1\) 个点作为起点依次问一遍，写个高斯消元发现不论 \(n\) 的奇偶，矩阵都是满秩的，所以考虑构造。对于 \(n\) 是偶数，由于我们 \(1,2,n,3,n-1,\cdots\) 正反各问了一遍，所以每个点的度数是知道的，所以其它询问 reverse 之后的结果也是知道的，也就是剩下的 \(\frac{n}{2}-1\) 个点作为起点询问的结果也是知道的。按照差值 \(d=j-i\) 从小到大处理所有边，只需要 \(res[i+d/2][i,j]\) 以及中间所有边的结果。
考虑奇数，设我们询问的是 \(1\sim \lceil\frac{n}{2}\rceil\) 的所有点，首先我们可以立即得到 \([1+\lceil\frac{n}{2}\rceil,n+1]\) 的度数（\(n+1\) 表示 \(1\)），就是每次询问的最后一个数。考虑把 \(1\) 和 \(\lceil\frac{n}{2}\rceil\) 两次询问拿出来，通过上面点的度数可以知道每条竖着的边（需要自己画图），从而知道下面点的度数。这样就也得到了所有询问 reverse 之后的结果，参考上面的做法即可。如果中心点落在上半部分，遍历方向是反的，需要分讨。
260709 B
考虑按列分块，长度到达 \(B\) 或者包含的修改操作超过 \(B\) 个就分一块，完全包含当前块的修改不算。考虑处理完全包含当前块的查询操作，我们只需要求出每行的最大值，然后复合一下 \(p^{-1}\)，然后用 \(O(n)-O(1)\) rmq 维护即可。注意不同的行也只有 \(O(B)\) 个，所以从上到下扫描线，当前行有修改的时候暴力前缀和求出 \(\max\)，然后加上完全包含当前块的修改操作对当前行的影响 \(g_i\) 即可。
考虑处理和当前块交叉或者被完全包含的查询操作，仍然考虑上面的扫描线，分别计算每个等价类的贡献，就是要查询等价类中 \(q_i\in [L_1,R_1]\) 的行的最大的 \(g_i\) 以及等价类中一段区间的最大值。二者都是 rmq 问题，前者需要用一些手法来做到线性离散化，后者直接做 rmq 即可。取 \(B=O(\sqrt n)\)，时间复杂度 \(O(n\sqrt n)\)。
线性 rmq 直接提前把询问按照右端点排序，然后用单调栈套并查集即可。
loj6267 生成随机数
260711 B
首先对于一种序列，若有解则每段的颜色种类数是唯一的，因此可以在外层枚举这个，枚举到 \(\frac{n}{k}\) 即可。然后，对于一个序列考虑从左往右贪心，可以尽可能向左匹配，也可以尽可能向右匹配，不难说明分 \(i\) 段后两种策略的右端点 \(l_i,r_i\) 之间的端点也可以取到，所以充要条件就是 \(l_k\le n\le r_k\)，这玩意可以差分成 \([l_k\le n]-[r_k<n]\)。
考虑如何计算 \(l_k\)，只需要满足划分的每一段的最后一个位置都在前面没出现过，可以预处理 \(w_{i,j,k}\) 表示向区间中填 \(k+cnt\) 种颜色的方案数，其中 \(cnt\) 表示出现过的固定的的颜色数，于是可以 \(O(1)\) 计算；考虑如何计算 \(r_k\)，需要满足每一段的下一个位置都没出现过，因此需要把这个东西记进状态里，看似是 \(O(kn^2m)\) 实则所有没出现过的数贡献相等，因此转移数是 \(O(kn^3)\)。为了做到线性转移，需要分讨 \(a_j\) 和 \(a_{i+1}\) 的关系，需要分讨 \(a_j\) 在 \([j+1,i]\) 中是否出现等等。
260711 C
260712 B
赛时想了一个对无根树判定的方法，大概是返祖边构成的路径的外子树有交什么的，反正一个子树只有 \(3\) 种状态（外子树都不行，除了伸出去的路径末端都不行，两者都行），然后 dp 套 dp 和暴力卷积一下即可，复杂度 \(O(m3^n)\)，场上没调完，痛失 \(38pts\)。
考虑点双怎么做，如果一棵生成树有两个可能的根 \(x,y\)，考虑 \(x,y\) 在树上的路径，如果路径上某些点挂了非空的子树，并且子树内有连向路径上其他点的返祖边，那么 \(x,y\) 之中至少有一个不能作为根，根据定义路径上这个点是割点，与点双矛盾。因此点双的所有点都在这条路径上，说明这是一条哈密顿回路。
因此点双的一棵生成树至多有两个点能作为根，当且仅当树是一条哈密顿回路时有两个。考虑推广到图上，考虑能成为根的点是什么样，发现一个点双不能有三个方向包含合法的根节点，并且如果两个点能成为根，那么它们在圆方树上的路径上的圆点也都能成为根，因此这些根形如一个连通块。考虑点边容斥，用每个点作为根的答案，减去点双中钦定两个点作为根的答案（形成哈密顿回路的数量，乘以其他点双的根朝向自己的方案数），前者精细实现可以做到 \(O(n^22^n)\)，哈密顿回路也可以做到 \(O(n^22^n)\)。
260714 A
260714 B
P10042 [CCPC 2023 北京市赛] 三染色
P11613 [PA 2016] 覆盖 / Pokrycia
260716 A
260716 B
P8478 「GLR-R3」清明
显然是把乘积的贡献拆了，转化成一个什么路径权值和。对于 \(k\le 16\) 可以 \(O(nk^22^k)\) 暴力卷积。
对于 \(k\ge 16\)，暴力卷积是 \(O(2^{n-k}(n-k)^2(2k-n)^3)\)，因为指数增长快于任意多项式，所以复杂度就是 \(O(2^{n-k}(n-k)^2)\) 的，用 desmos 或者打表得常数最大为 \(32\)，在 \(k-\frac{n}{2}=4\) 时取等。