没有参加 NOI2021 捏，所以题面都是贺来的！

看神仙打架真好玩！

懒得组织语言了所以所谓题解都是一大堆支离破碎的 observation

Day 1

T1 - 愚蠢的在线法官 by pjq

题目大意.

给出一棵树（点有点权 $v$$v$）和一个节点序列 $A_i$$A_i$，请你求出

$$\begin{array}{c}\left|\begin{array}{cccc}{v}_{\text{LCA}(A_1,A_1)}& v_{\text{LCA}(A_1,A_2)}& \dots & v_{\text{LCA}(A_1,A_k)}\\ v_{\text{LCA}(A_2,A_1)}& v_{\text{LCA}(A_2,A_2)}& \dots & v_{\text{LCA}(A_2,A_k)}\\ ⋮& ⋮& \ddots & ⋮\\ v_{\text{LCA}(A_k,A_1)}& v_{\text{LCA}(A_k,A_2)}& \dots & v_{\text{LCA}(A_k,A_k)}\end{array}\right|\end{array}$$

$n\le 5\times {10}^5$$n\le 5\times10^5$。

• $A_i$$A_i$ 如果有重直接返回 $0$$0$。否则可以按任意顺序 sort。当然取 DFS 序最为舒适。
• 如果 $A_i$$A_i$ 选了 $A_j$$A_j$，就画出路径 $A_i\to A_j$$A_i\rightarrow A_j$。每条边不会被同向经过两次。（否则可以交换两个点的目标，这会反转符号并抵消，类似 LGV 引理。）
• 于是有显然的 DP，每个子树只有两种状态：需要一条边进且需要一条边出；或自给自足。

T2 - 这是一道集训队胡策题 by xym

题意.

给出一个 $n\times n$$n\times n$ 的 01 矩阵 $c$$c$，求有多少长度为 $n$$n$ 的 01 序列 $a,b$$a,b$，满足 $c_{i,j}=a_i\vee c_{i,j}=b_j$$c_{i,j}=a_i\lor c_{i,j}=b_j$。答案对 $998244353$$998244353$ 取模。

$n\le 5000$$n\le 5000$。

可见，我们所要满足的就是

怎么看怎么不能算！

关键在于，由于上式必定 $\le 1$$\le 1$，于是它等价于

自然也等价于

枚举 $a_i$$a_i$ 中 $1$$1$ 的个数和 $b_i$$b_i$ 中 $1$$1$ 的个数即可。（$\sum _{i,j}[c_{i,j}=a_i]$$\sum_{i,j}[c_{i,j}=a_i]$ 只需要取最大值）

T3 - 树上的孤独 by lbc

题目大意.

有一棵大小为 $20$$20$ 的树 $T_A$$T_A$ 和一棵大小为 $2\times {10}^5$$2\times 10^5$ 的树 $T_B$$T_B$，每个点都有一个颜色。

你要支持两种操作：

• 修改 $T_A$$T_A$ 上某个点的颜色；（这个操作不强制在线。）

• 问：在 $T_A$$T_A$ 上 $P_A$$P_A$ 的子树中距离 $P_A$$P_A$ 至多为 $D_A$$D_A$ 的节点的颜色集合，和在 $T_B$$T_B$ 上 $P_B$$P_B$ 的子树中距离 $P_B$$P_B$ 至多为 $D_B$$D_B$ 的节点的颜色集合的并的大小。

• • $D_A$$D_A$ 和 $D_B$$D_B$ 是强制在线的，需要通过之前的询问答案解密。$P_A,P_B$$P_A,P_B$ 不强制在线。

$q\le {10}^6$$q\le 10^6$。

离线求出：在 $T_B$$T_B$ 上，每个点，每个颜色离自己的最近距离（最小 dep）。线段树合并即可。$O(m\log m)$$O(m\log m)$。

$T_A$$T_A$ 实在太小了，没有什么特别好的办法。现在的问题就是对 $T_A$$T_A$ 中变得合法的每一种颜色，确认它是否在 $T_B$$T_B$ 也合法，实际上我们可以大力求它在 $T_B$$T_B$ 中离 $P_B$$P_B$ 的最近距离。这样还可以支持那个迫真在线，非常舒适。

现在我们拆出了 $qn$$qn$ 个询问。这东西是可以离线的，那我们也就没必要在线段树上苦痛，直接 dsu on tree 就好。

Day 2

T1 - 序列 by ztr

题目大意.

现在有一个未知的、长度为 $n$$n$ 的、元素皆是 $[1,{10}^9]$$[1,10^9]$ 中的整数的序列 $a$$a$。现在有一些信息，形如：$a_i,a_j,a_k$$a_i,a_j,a_k$ 的中位数的值是 $X$$X$。

请你构造一个符合条件的 $a$$a$，或者报告无解。

$n,m\le {10}^5$$n,m\le 10^5$。

构造 2-SAT：

• $[a_i\ge v]\Rightarrow [a_i\ge v-1]$$[a_i\ge v]\Rightarrow [a_i\ge v-1]$。

• 对于一条信息 $(a_i,a_j,a_k,X)$$(a_i,a_j,a_k,X)$，

• • $a_i>X\Rightarrow a_j\le X,a_i<X\Rightarrow a_j\ge X$$a_i>X\Rightarrow a_j\le X,a_i<X\Rightarrow a_j\ge X$，其他组合同理。

可见有意义的总点数为 $O(m)$$O(m)$ 个。跑一跑即可。

T2 - Imbalance by yg

题目大意.

问有多少个 $1,-1$$1,-1$ 构成的序列满足：

• 其前缀是一个给定的串 $S$$S$；
• 所有长为 $k$$k$ 的子串元素和皆不为零。

$n,k\le 100$$n,k\le 100$。

先不考虑 $S$$S$​。

对于 $k\le 20$$k\le 20$，显然是 sb 题。

对于更大的 $k$$k$，可以看成是在一个周长为 $k$$k$ 的圆柱上游走，问有多少不与自身相交的路径。此时周期数不超过 $5$$5$，大力爆枚每个周期的起点（${20}^5/120$$20^5/120$）然后大力 LGV（$5^3$$5^3$）即可。

如果考虑 $S$$S$，上面的做法依然适用，只不过难写一些。

T3 - 学姐买瓜 by zjr

题目大意.

$n$$n$ 次操作，每次操作形如：

• 加入一个关键区间 $[l,r]$$[l,r]$。
• 询问：考虑 $[l,r]$$[l,r]$ 的所有子关键区间，问最大不相交区间数。

$n,m\le 3\times {10}^5$$n,m\le 3\times 10^5$。

考虑求最大不相交区间数的那个贪心，你会发现加入一个区间的效果就是区间改父亲。珂朵莉树 + LCT（LCT 上的一个点表示一群父亲相同的点）即可。

Day 3

T1 - Lovely Dogs by cxr

题目大意.

定义函数

$$f_d(p_1^{k_1}{p}_2^{k_2}\dots )=\prod _i(-1{)}^{k_i}[k_i<d]$$

现在有一棵树，点的编号恰是 $1\sim n$$1\sim n$ 的排列。你要对每个子树 $T$$T$ 求 $\sum _{u,v\in T}{f}_d(uv)$$\sum_{u,v\in T}f_d(uv)$。

$n\le 2\times {10}^5$$n\le2\times10^5$。

基本的思路是 dsu on tree。

考虑容斥，记 $g_d(p_1^{k_1}{p}_2^{k_2}\dots )=\prod _i(-1{)}^{k_i}$$g_d(p_1^{k_1}p_2^{k_2}\ldots)=\prod_{i}(-1)^{k_i}$，所欲求的就是

为了迎合 dsu on tree，我们把这玩意化成某个固定的 $v$$v$ 产生的贡献的形式：

事实上我们可以只枚举 $g|v$$g|v$：如果 $g$$g$ 不整除 $v$$v$ 又有最后一个条件成立，那么直接有 $f_d(u)=0$$f_d(u)=0$，这种 $u$$u$ 是可以直接忽略的。

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

T2 - Alice、Bob 与 DFS by zlm

真·明哥题

题目大意.

现在有一个 DAG，每个点的出边被认为有序。每个点要么是黑点，要么是白点。

有 $k$$k$ 个程序，形如：从 $r$$r$（$r$$r$ 不一定全相同）开始进行 DFS。

• 对于黑点，程序会无条件地依次访问其出边，并递归搜索；
• 对于白点，程序会在访问每条出边前询问是否跳过该出边；
• 所有程序在对某个点的搜索开始前会自动暂停。

一开始，所有程序均处于开始搜索起始点前的暂停状态。

有两名玩家在进行博弈。双方轮流进行以下操作，不能操作者输：

• 选择一个搜索过程尚未完全结束的程序，将其从暂停状态中恢复；
• 继续执行该程序，在程序将要访问白点的出边时决定是否跳过该边， 直到该程序完全结束或再次暂停。

双方均采取最优策略。判断先手是否必胜。

$n\le 2\times {10}^5,m\le 4\times {10}^5$$n\le 2\times10^5,m\le 4\times10^5$。

下面认为遍历边的顺序是从左至右。

先来考虑【所有点皆为白点、该 DAG 是一棵外向树，起始点总是外向树的根】的简单情形。

此时，dfs(x) 的后继状态是：

• $x$$x$ 的儿子们；
• $x$$x$ 的右兄弟们；
• $fa(x)$$fa(x)$ 的右兄弟们；
• ……
• 失败状态。

设 $u$$u$ 的子树在 DFS 序中是 $[u_L,u_R]$$[u_L,u_R]$，实际上 $u$$u$ 的后继状态就是

• $v_L>u_R$$v_L>u_R$ 的 $v$$v$；
• 并上 $u$$u$ 的儿子。

直接求个 SG 函数即可。

现在试试推广到【所有点皆为白点、DAG 不必是外向树】的情况。此时一个状态可被一组自 $r$$r$ 开始首尾相接的边描述。自然，这时状态数太多了无法承受。

我们已经知道某状态的后继状态由两部分组成：

• 祖先们的右兄弟；
• 当前节点的儿子们。

后者只依赖于当前节点 $u$$u$。我们尝试把前者黑箱化为一个集合 $S$$S$。设这时的 SG 值 集合 为 $f(u,S)$$f(u,S)$。

显然，设 $u$$u$ 的儿子们为（从右至左）$v_1,v_2,...$$v_1,v_2,...$，有

……是啊，确实很显然，但是好像没什么用啊？

下面开始高端操作了！记 ${\text{mex}}_i(S)$$\text{mex}_i(S)$ 为 $S$$S$ 中第 $i$$i$ 个未出现的元素。显然，$\text{mex}(S)={\text{mex}}_1(S)$$\text{mex}(S)=\text{mex}_1(S)$。我们断言，【$\text{mex}f(u,S)$$\text{mex}f(u,S)$ 必可表为 ${\text{mex}}_{\ast }S$$\text{mex}_*S$】。事实上，你只需要注意到：

就可以归纳出刚刚的结论了。其实我们还可以得到（一层一层嗯展开）

只需要求出 $\text{mex}f(u,\{0\})$$\text{mex}f(u,\{0\})$（其实，显然，它也直接是从 $u$$u$ 开始 dfs 的答案）。用树状数组优化的暴力转移已经可以通过。

最后一个问题，【黑点】。不难发现：

• 黑点的存在实际上否定了自己除最右的儿子外回溯到 $S$$S$ 的可能性，让它们只能回溯到自己的下一个兄弟。即

• 对于一个黑点 $u$$u$，$f(u,S)$$f(u,S)$ 要么为 $\{0\}$$\{0\}$ 要么为 $\{1\}$$\{1\}$。

于是是容易判断的。实际上，更进一步，黑点的 $f(u,S)$$f(u,S)$ 只有以下四种可能：

而当我们再回头查看白点时，我们发现黑点的存在破坏了之前归纳得出的结论。或许可以考虑修正一下？

注意 $S$$S$ 中大于 $1$$1$ 的元素不会影响黑点 $f(u,\ast )$$f(u,*)$ 的取值，因此我们只需要对四种情况分讨即可。事实上更近一步有

T3 - 音符大师 by dyp

题目大意.

你有两只手，宽度均为 $L$$L$，一开始均处于 $[0,L]$$[0,L]$。

现在有 $n$$n$ 个音符依次出现在 $a_i$$a_i$ 处，你要移动你的手来保证每次音符出现时都被至少一只手覆盖。手从 $[x,x+L]$$[x,x+L]$ 移动到 $[y,y+L]$$[y,y+L]$ 不需要时间，但需要代价 $|x-y|$$|x-y|$。问最小移动代价。

$n\le 5\times {10}^4,L\le 50$$n\le 5\times10^4,L\le 50$。

考虑这样一个 DP：手分别在【$[a_i,a_i+L]$$[a_i,a_i+L]$ 或 $[a_i-L,a_i]$$[a_i-L,a_i]$】（用一个 $0/1$$0/1$ 变量记一下）和【$[a_j,a_j+L]$$[a_j,a_j+L]$ 或 $[a_j-L,a_j]$$[a_j-L,a_j]$】处，下一个音符是 $i+1$$i+1$。

转移时这样考虑：

• 先用当前的两只手接一段音符；
• 把手移到【$[a_k,a_k+L]$$[a_k,a_k+L]$ 或 $[a_k-L,a_k]$$[a_k-L,a_k]$】，接一段音符，直到 $k+1$$k+1$。

因此，如果我们找出第一个接不住的音符 $X$$X$，那么 $a_k$$a_k$ 的取值就只有 $L$$L$ 种了。（因为必须接得住 $X$$X$）

当然，它不够快。

我们对每个 $i$$i$ 开一个线段树，里面维护 $(i,j)$$(i,j)$ 的 DP 值。

考虑第一个 $\mathbf{\text{i}}$$\textbf{i}$ 接不到 的元素 $X^{\prime }$$X'$，它可能能被 $a_j$$a_j$ 接到也可能不能接到，如果是前者，那么 $a_j$$a_j$ 的取值极其有限，暴力转移即可；如果是后者，则可以批量转移上去（需要支持线段树合并）。

时间复杂度 $O(nL\log n)$$O(nL\log n)$。

Day4

T1 - 基础图论练习题 by djq

瑇

unavailable yet

T2 - 机器 by ckw

线性规划全家桶！

题目大意.

给定一张有向图，点有点权 $h_i$$h_i$ 和 $p_i$$p_i$ 个入管道、$q_i$$q_i$ 个出管道。如果 $u$$u$ 可以到达 $v$$v$，那么任意 $u$$u$ 的入管道就可以和任意 $v$$v$ 的出管道匹配，并获得权值 $h_u-h_v-a_{u,i}-b_{v,j}$$h_u-h_v−a_{u,i}−b_{v,j}$。最大化总代价。

$n\le 2000,m\le 20000,p_i,q_i\le 2000$$n\le 2000,m\le 20000,p_i,q_i\le 2000$。

忽略点权，全部加到 $a_i,b_i$$a_i,b_i$ 上。有显然的网络流模型。

自然写出线性规划：

我们把一个点上从 $S$$S$ 连来的边 / 连向 $T$$T$ 的边作为一个整体考虑。

具体来说：如果固定它们对流量的影响（即固定从 $S$$S$ 进入 $u$$u$ 的流量 - 从 $T$$T$ 进入 $u$$u$ 的流量），那么对【边们各自是否满流】的选择是唯一且可以预先处理的。更近一步，它对权值的影响是上凸的。

因此我们把线性规划重写为

以下细节值得注意：

• 我们处理凸包形贡献的方式。
• 注意与源汇相连的边的流量已经算进 $X$$X$ 里了，$f$$f$ 是原图中边的流量。
• 注意我们直接让 $X$$X$ 的范围没有限制；实际上我们是通过调整 $E$$E$ 使得超过范围的 $X$$X$ 贡献为 $-\mathrm{\infty }$$-\infty$ 来起到限制它的效果的。

自然，把 $min(\dots ,0)$$\min(\ldots,0)$ 写开：

转成对偶：

故技重施：当 $Y_u$$Y_u$ 确定时，$\sum D^{+}-\sum D^{-}$$\sum D^+-\sum D^-$ 的最优选择是可以确定的，而且对贡献的影响也是一个凸壳。即，该线性规划可以写为

这是一个与 保序回归 问题几乎相同的问题：所有定义和证明都可以搬过来（除了 $L_p$$L_p$ 均值要改成凸包上的最低点）。我们只需要跑 log 次最大流（整体二分的每一层一次）即可通过。

T3 - 数列重排 by gyh

题目大意.

现在有 $n$$n$ 个数，保证 $i$$i$ 出现的次数是 $\{0,X,X+1\}$$\{0,X,X+1\}$ 之一。

你要对所有 $k$$k$ 求出：若把这些数随意排列，$\text{mex}\ge k$$\text{mex}\ge k$ 的区间个数最多可以是多少。

我们称 $<k$$<k$ 的元素为白球，$\ge k$$\ge k$ 的元素为黑球。可见黑球并不影响 $\text{mex}$$\text{mex}$。

我们来考虑怎么排列白球。直观地想，肯定是形如 $0123\dots 0123\dots$$0123\ldots 0123\ldots$。如果有出现 $X+1$$X+1$ 次的元素，那就尽量把它们放到每一个周期的开头，让整个序列形如 $0123\dots 0123\dots 01$$0123\ldots0123\ldots01$。

暴力打表可以发现这是对的！

那么现在的问题就是怎么插黑球。定义一个黑球的贡献 $w$$w$ 是以它为开头 / 结尾的区间数。

自然考虑调整法：

• 如果某个黑球和左端点无贡献，可以把它移到最左端。右端亦然。
• 如果两个黑球中白球数 $<k$$<k$，那么把其中 $w$$w$ 较小的移到 $w$$w$ 较大的旁边一定不劣。

因而，（结合打表的结果），我们猜测：答案形如

此时，我们发现贡献总和形如

其中 $L$$L$ 是连续段长度。

由此，接下来的分析就很简单了。结论为：前 $2k-2$$2k-2$ 个黑球平均分配于两端，之后的黑球对每个黑球段平均分配。

Day5

T1 - Speike & Tom by wcz

ix35 哥哥，你就不能少整点这种活吗

unavailable yet

T2 - 聚会 by wwc

题目大意.

请用一堆三元环完美覆盖 $K_n$$K_n$ 的每一条边。

$n\le 3000$$n\le 3000$。保证 $n=6k+3$$n=6k+3$ 或 $6k+1$$6k+1$。

保证：只要 $n$$n$ 满足以上条件就必定有解。

Welcome to the Sacred Order of Steiner Systems

直接丢 ppt：这里

T3 - 细菌 by zzh

题目大意.

现在有一个 $n\times m\times k$$n\times m\times k$ 的立方体，你要从指定位置开始游走 $d$$d$ 步：每一步可以让任意一个坐标 $\pm 1$$\pm 1$。

问，有多少路径始终没有游走出边界。

$n,m,k,d\le 1.2\times {10}^5$$n,m,k,d\le 1.2\times 10^5$。

先考虑一维的情况，记起始坐标为 $s$$s$。对于高维只需要把三个方向卷起来。

我会 $O(nd)$$O(nd)$！直接 DP！

想想别的做法？

考虑容斥掉那些接触过左/右边界的路径。接触过左边界的路径数为

但是这样会把那些又接触了 L 又接触了 R 的路径数重！那么再数 LR/RL/LRL/RLR……这种东西不会超过 $d/n$$d/n$ 个！……但是好像不好算？

理一下思路。以上问题可以描述成：

从原点开始向右向上走，且不能越过 $y=x-s$$y=x-s$ 和 $y=x+t$$y=x+t$ 的路径有多少条？

考虑终结于特定的 $(x,y)$$(x,y)$ 的路径：我们已经知道它是不超过 $d/n$$d/n$ 个组合数。

然后考虑全体路径。对于大部分的【当前位置】，向上向右都是可以走的；只对于 $O(1)$$O(1)$ 个【边界位置】，我们需要进行容斥。所要容斥掉的其实就是上一个问题的答案。

所以复杂度是 $O(d^2/n)$$O(d^2/n)$！

两个结合起来根号分治一下，于是就过了。