2023 联考日记

打表可以发现一些规律。观察到相同数值都连续排布，把每一种数值看成一块，不难通过累加求出每一块的左右端点 $[l,r]$，只需要统计每个块内有多少个下标模 $m$ 余 $r$ 的数即可。

时间复杂度 $\mathcal{O}(t\sqrt{n})$。

答案在 $2^{65}$ 量级，需要 __int128 才行。

神秘结论题。

先考虑没有高级魔法的情况。把一个增量 $(\Delta x,\Delta y)$ 看成向量，对于所有点 $(x_0,y_0)$，令 $S=\{(x,y) \mid (x,y)=(x_0+\Delta x,y_0+\Delta y)\}$ 为它的基元。如果某个点的基元的所有点都在边界内，则要求这些点的异或和为 $0$。结论不会证。

现在把高级魔法加进来。忽略超出边界的情况，可以通过若干次异或把它们分别变成向量 $(2,0),(0,2),(2,1)$，当成普通魔法处理就行了。

注意如果有 $(2,0),(0,2)$ 要把 $(1,0),(0,1)$ 删掉。因为要去掉不共线的向量，

枚举每一种选取魔法的子集即可。时间复杂度 $\mathcal{O}(nm2^k)$。

考场上好像做出了出题人所有的提示性部分分，但是没拼起来。好像拼起来就是正解了。

考虑 $x_i\bmod L$ 取到 $k$ 的方案数。令 $b_i=a_i\bmod L$，就是

$\left\lfloor\dfrac{a_i}{L}\right\rfloor+[k<b_i]$

对于每一组互不相同的余数排列 $(k_1,k_2,\cdots k_n)$ 答案为

$\prod \left(\left\lfloor\dfrac{a_i}{L}\right\rfloor+[k_i<b_i]\right)$

我们把这个东西用乘法分配律展开，钦定 $t$ 个位置上选择 $[k_i<b_i]$，对这些位置按照 $b_i$ 排序，从小往大选，每次选择都会让后面的数少一种选择。这些位置上的答案就算出来了。而其他位置就有 $A_{L-t}^{n-t}$ 种排列方法。

把所有数按照 $b_i$ 排序。令 $f(i,j)$ 表示考虑前 $i$ 个数中钦定 $j$ 个的方案数之和。这里先不考虑其他位置。那么就有

$f(i,j)=\left\lfloor\dfrac{a_i}{L}\right\rfloor f(i-1,j)+(b_i-(j-1))\times f(i-1,j-1)$

最后答案就是

$\sum_{t=0}^n A_{L-t}^{n-t}\times f(n,t)$

时间复杂度 $\mathcal{O}(n^2)$。

巨大 dp。先放一放。

手玩几组数据会发现同色边的数量相比异色边总是很小的。事实上，同色边最小的方案一定是满足条件的。

如果 $u$ 存在$\geq 2$ 个与 $u$ 同色的相邻节点，我们对 $u$ 的颜色取反，一定会让同色边数量减少。而合法的染色方案要求不存在这样的 $u$，即同色边数量最小。

现在只需要构造一组同色边最小的方案。先钦定所有点为同一种颜色，把所有能够调整的点扔进一个队列里，调整完再考虑其相邻点，如果还能继续调整就扔进队列里。

时间复杂度 $\mathcal{O}(n+m)$。

原题是 P6678。

容易发现每一列的两个元素是绑定的，旋转只可能改变它们的上下关系。

考虑初始时的一列 $(a,b)$，如果结束状态时变为了 $(b,a)$，只能通过旋转奇数次做到，反之就只能通过旋转偶数次做到。到这里就可以判断无解了。

现在计算最小旋转次数。将结束状态标号为 $1\sim n$，能对应得到初始状态为 $n$ 的一个排列。我们可以通过交换相邻两项使得其有序。而这就是逆序对数。

时间复杂度 $\mathcal{O}(n\log n)$。

原题是 CF1198D。

对于一个 $H\times W$ 的矩形，我们一定可以通过枚举一条切割线，将矩形切割成两部分分别处理。

不妨设 $W\geq H$，那么覆盖矩形的代价不超过 $W$。如果每一条竖线都会穿过一个 T 组成的连通块，需要的代价至少是 $W$，那么就可以选择不切割。

设计 dp 状态 $f(a,b,c,d)$ 表示覆盖以 $(a,b)$ 为左下角 $(c,d)$ 为右上角的矩形的最小代价。暴力枚举分界线转移。

时间复杂度 $\mathcal{O}(n^5)$。

先可以得到一个 30 分做法。设 $f(u,i)$ 为以 $u$ 为根的子树中 $u$ 的连通块大小为 $i$ 时的答案。枚举 $u$ 的儿子 $v$，对于边 $(u,v)$ 选不选分别转移即可。$\mathcal{O}(n^2)$。

正解是一个利用斯特林数拆幂的神秘做法。

$x^k=\sum_{i=0}^k \binom{x}{i}{k\brace i} i!$

而斯特林数 $\displaystyle {k\brace i}$ 在 $k<i$ 时都为 $0$，所以上式的枚举上界会被 $k$ 限制。

考虑一个抽象的 dp 状态。设 $f(u,j)$ 表示以 $u$ 为根的子树中，所有保留方案下，“不与 $u$ 连通的连通块大小 $k$ 次方之积乘上与 $u$ 连通的点中选出 $j$ 个的方案数”之和。这样以 $u$ 为根的实际答案可以写为

$C_u=\sum_{i=0}^k{k\brace i}f(u,i)i!$

现在就只需要求 $f(u,i)$ 了，而这个就可以转移了。考虑树上背包，合并 $u$ 的子树中在 $v$ 之间子树的答案和 $v$ 子树答案，为了避免转移顺序的问题，用一个辅助数组 $f'$。

当钦定不断掉 $(u,v)$ 之间的边时，与 $u$ 连通的部分大小增加到 $i+j$，这两块分别由 $u$ 和 $v$ 贡献，则有

$f'(u,S)\sum_{i+j=S}f(u,i)\times f(v,j)$

当钦定 $(u,v)$ 断掉时，与 $u$ 联通的部分大小不变，而每一种之前的方案都要乘上 $v$ 子树内的答案。从而有

$f'(u,i)=f(u,i)\times C_v$

由于 $k$ 限制了转移上界，所以这就是一个有限制的树形背包，精细实现可以做到时间复杂度 $\mathcal{O}(nk)$。

赛时连暴力分都没拼出来，太傻逼了。

考虑每一个攻击力带来的影响。所有 $h_i$ 都可以按照 $\left\lceil\dfrac{h_i}{A_q}\right\rceil$ 的值分成长度为 $A_q$ 的段，只需要算每一段内的 $a_i$ 总和。

维护一个树状数组，将 $a_i$ 以 $h_i$ 为下标丢进去，这样就可以快速算整段的和了。对于剩下的散块，我们可以暴力维护。

实现细节上，因为 $A_i$ 非严格递增，需要跳过 $A_i=A_{i-1}$ 的情况。时间复杂度 $\mathcal{O}(V\log^2V)$。

先考虑只有 $0/1$ 的情况。我们把一条要求 $(l,r,1)$ 看成“区间覆盖为 $1$”，一条 $(l,r,0)$ 看成“区间查询是否有 $0$”。一个区间查询不合法，当且仅当这个区间全都被覆盖上了。

考虑删掉的要求是区间询问。如果不合法的区间询问大于 $1$ 个，那么删掉哪个都没用。如果恰有一个不合法，那么只有删掉这一个是有用的，删其他合法的区间询问都没用。

考虑删掉的要求是区间覆盖。如果删掉 $(l_i,r_i,1)$ 有用，必要条件是 $[l_i,r_i]$ 中有恰被覆盖了一次的位置，撤掉这次操作可以让这些位置变成 $0$。

现在假设我们已经处理出了一个区间覆盖中只被覆盖一次的所有位置，我们考虑新加入的这些 $0$ 能否使可能不合法的询问变得合法，发现如果存在一个可能不合法的询问区间没有跨过任何一个 $0$，那么删除该区间覆盖就是不合法的。

具体判断这件事情，找出 $(l_i,r_i,1)$ 中所有只被覆盖了一次位置，这些位置中最左的应该小于等于不合法的询问区间中右端点的最小的右端点，最右的应该大于等于不合法的询问区间中左端点最大的左端点。

时间复杂度 $\mathcal{O}(n\log x_i)$。实现方式很抽象。

转化完是一个神秘数论题，先放一放。

通过一系列分析可以得到结论。如果至少有 $4$ 种选出偶数个轨道使得 $r_i$ 之和为偶数的方案就可以，否则不行。背包一下就好了。$\mathcal{O}(\sum r_i)$。

一些特殊情况，当 $n$ 为奇数，或半径总和为奇数时不行。

考虑二分答案 $x$。如果存在相邻的元素之和大于 $x$，就要删掉一个，而删掉更大的一个是不劣的。

然而我们要处理新产生的相邻关系。考虑用一个栈，每次将 $a_i$ 与栈顶比较，将更大的删掉。

还要处理环状的相邻关系，可以把栈换成双端队列，最后在栈顶和栈底反复弹即可。

时间复杂度 $\mathcal{O}(n\log a_i)$。

神秘 dp。

设 $f(i,j,k)$ 为前 $i$ 个点形成了 $j$ 个连通块，且还缺 $k$ 个儿子的方案数。由于左右儿子有区分，我们要手动钦定儿子是左儿子还是右儿子。

钦定 $i+1$ 没有儿子。

• 给 $i+1$ 新建一棵树。$f(i,j,k)\rightarrow f(i+1,j+1,k)$。
• 将 $i+1$ 接到之前某个缺儿子的点下面。$k\times f(i,j,k)\rightarrow f(i+1,j,k-1)$。

钦定 $i+1$ 只有一个儿子。我们需要钦定儿子的左右。同时由于要求每个点的儿子中存在一个编号大于它，所以不能将之前的某棵树接在它下面。

• 给 $i+1$ 新建一棵树。$2\times f(i,j,k)\rightarrow f(i+1,j+1,k+1)$。
• 将 $i+1$ 接到之前某个缺儿子的点下面。$2\times k\times f(i,j,k)\rightarrow f(i+1,j,k)$。

钦定 $i+1$ 有两个儿子。

• 给 $i+1$ 新建一棵树。$f(i,j,k)\rightarrow f(i+1,j+1,k+2)$。
• 将 $i+1$ 接到之前某个缺儿子的点下面。$k\times f(i,j,k)\rightarrow f(i+1,j,k+1)$。
• 将之前某棵树接到 $i+1$ 下面。需要钦定接在左儿子上还是右儿子上。$2\times j\times f(i,j,k)\rightarrow f(i+1,j,k+1)$。
• 将之前某棵树接到 $i+1$ 下面，并把 $i+1$ 接到某个缺儿子的点下面。$2\times k\times (j-1)\times f(i,j,k)\rightarrow f(i+1,j-1,k)$。$j-1$ 是因为，已经把 $i+1$ 接到了一个缺儿子的节点下，那么这个节点所在的根就不能接在 $i+1$ 下了。

时间复杂度 $\mathcal{O}(n^3)$。

可以发现 $f(x,y)=f(kx,ky)$，所以不妨只考虑 $\gcd(x,y)=1$ 的情况。

同时发现 $x+y$ 在变化的过程中不变，而 $x,y$ 一奇一偶无论怎么变化都不会相等。所以只考虑 $x,y$ 都为奇数的情况。

不妨设 $x>y$，则有 $f(x,y)=f(2y,x-y)+1=f\left(y,\dfrac{x-y}{2}\right)+1$。这样会让 $x+y$ 不断除以 $2$。从而只有当 $x+y=2^k$ 时，$f(x,y)=k$，其余情况全都为 $0$。

反过来考虑，对于每一个 $k$，能使得 $f(a_i,a_j)=k$ 的 $i,j$ 只有 $\mathcal{O}(\log n)$ 组。我们把所有 $f(a_i,a_j)=k$ 的点对 $(i,j)$ 拿出来，钦定 $i<j$，看作二维平面上 $(i,j)$ 处有一个权值为 $k$ 的点。这样每次询问就是在查 $x\in [l,r]$，$y\in [l,r]$ 矩形中点权和。二维数点即可。

时间复杂度 $\mathcal{O}(n\log n)$。

神秘题。

看懂了题面，实际上就是两种操作：区间 $+1$，查询区间一堆根号下取整状物的求和。

会发现其实只有 $\mathcal{O}(\sqrt{n})$ 次区间 $+1$ 操作会让 $\lfloor\sqrt{a_i}\rfloor$ 增加，并且相同的取值必然位于一个连续段内。

我们考虑把这些增量“攒在一起”更新。用线段树维护区间答案，区间加法标记，区间 $\lfloor\sqrt{a_i}\rfloor$ 的总和，以及区间内下一次有数到达“下一段”还需要的最小增加次数。如果区间内有数到达下一段的增加次数为 $0$，就需要重构整棵子树。

根据势能分析，时间复杂度 $\mathcal{O}(n\sqrt{n}\log n)$。

反悔贪心。copy 一下机房同学的题解。

要选的肯定是一个前缀中所有的 $0$ 和这之后的所有 $1$。令 $a_i = 0$ 的数权值为正，$a_i = 1$ 的数权值为负，不修改时答案即为 $\max\limits_i {sum_i} + sum1_n$，$sum1_n$ 为所有 $a_i = 1$ 的数的 $b_i$ 之和，这是比较显然的。

现在考虑翻转操作，结论：当你翻转 $k$ 次时，相当于你可以多选 $k-1$ 个区间，方法类似你可以从右往左，一次翻转到倒数第二个区间的右端点，就能翻出你想要的形式。

模拟费用流分析，转为反悔贪心，策略为：每次选当前序列的最大子段和加入答案，然后把这一段$01$ 反转，即区间乘 $-1$，线段树维护即可。

细节很多就是了。写了好久。

还没补。

线段树分治板子。但是我之前没学过线段树分治，痛失大分。

将颜色放到时间轴上，认为颜色为 $c$ 的边在时间 $[1,c-1]$ 和 $[c+1,k]$ 出现。每次就是查图是否连通。线段树分治即可。

时间复杂度 $\mathcal{O}(n\log^2n)$。

神秘贪心。

若存在 $[a_i,b_i]$ 与区间 $[a_j,b_j]$ 不交，那么交换 $a_i,a_j$ 可以带来 $2\times (\min\{a_i,b_i\}-\max\{a_j,b_j\})$ 的额外收益。

令 $c_i=\min\{a_i,b_i\}$，$d_i=\max\{a_i,b_i\}$，将 $c_i$ 降序排序，$d_i$ 升序排序，从头不断取，大减小即可。

如果这么取不够 $k$ 次操作，可以直接丢弃后面的操作。因为如果 $[a_i,b_i]$ 和 $[a_j,b_j]$ 有交，交换不会使答案变化。后面 $k$ 次可以交换来交换去。

这么做需要特判 $n=2$。

用区间最大值位置把区间划分，会发现积水量相当于每个位置的前缀最大值减去当前位置高度。后缀同理。

用线段树维护区间最大值，区间最大值位置，区间最大值左侧前缀最大值减去每个位置高度之和，右侧后缀最大值减去每个位置高度之和。

合并两个区间时，大区间的右侧水体积相当于原来左区间的右侧水体积被右区间最大值“挡住”了一下，于是可以在左区间上使用类似楼房重建的做法二分到恰好被右区间挡住的位置，这个位置前采用原来的右侧水体积，这个位置后被右区间最大值覆盖。

时间复杂度 $\mathcal{O}(n\log n+m\log ^2n)$。

类似 SDOI 的某道题。但是不完全一样。

仍然建出 $A\rightarrow B$ 和 $B\rightarrow A$ 的最短路 DAG，就是 $C$ 走到 DAG 上某个点，走到某个后继，再走到 $D$。就是一个拓扑排序做链上前缀 $\min$ 和后缀 $\min$ 状物。

时间复杂度 $\mathcal{O}(m\log m)$。

厉害题。

包含 $x$ 的最大子段和可以拆成 $l< x\leq r$ 最大的前缀和 $S_r$ 减去最小的前缀和 $S_l$。同时，全局加 $x$ 相当于给 $S_i$ 加上 $i\times x$。

考虑离线，维护出每次询问时全局的增量 $k$，只需要查询 $\max\limits_{r\geq x}\{S_r+kr\}-\min\limits_{l<x}\{S_l+kl\}$。

令 $f(i)=S_i+ki$，将 $-k$ 看作斜率，$i$ 看作 $x$ 坐标，$S_i$ 看作 $y$ 坐标，这就是一个最大化/最小化截距的问题。将所有点按照 $x$ 排序后加入，二分凸包切点即可。