当 $k$ 较大时

• 黑色格无三连……

  • 任意三个连续的格子中至多有两个黑色格……
  • 黑色格比例 $\le \frac{2}{3}$
• $k > \left\lfloor\frac{2}{3}n\right\rfloor$ 时无解。

构造答案

$k = \frac{2}{3}n$

$k = \frac{1}{2}n$

可见，它们可自由组合

$\left\lceil\frac{1}{2}n\right\rceil \le n \le \left\lfloor\frac{2}{3}n\right\rfloor$ 时均可构造。

目前的结论

• $k > \left\lfloor\frac{2}{3}n\right\rfloor$ 时无解。
• $\left\lceil\frac{1}{2}n\right\rceil \le n \le \left\lfloor\frac{2}{3}n\right\rfloor$ 时可通过组合基本型来构造合法答案；
• $k < \left\lceil\frac{1}{2}n\right\rceil$ 时……无解

$k < \left\lceil\frac{1}{2}n\right\rceil$ 时一定有白色格三连？

• 显然 $n$ 越大，$k$ 越小时越容易产生白色格三连，因此不妨默认 $n$ 为奇数且 $k=\left\lceil\frac{1}{2}n\right\rceil - 1$。
• 先从最基本的 $n=5, k=2$ 开始...

$n=5, k=2$

• 以下称第 $j$ 列从上至下第 $i$ 个黑色格为“第 $i$ 条链的第 $j$ 个格子”；
• 第 2 条链的格子分布？

第 1, 5 列的范围是显然的；
如果第 2 条链的第 2/3/4 个格子在第 3 行的话...

• 第 2 条链的格子分布；
• 由对称性得到第 1 条链的分布；
• 叠加？

$n, k$ 更大时？（$k=\lfloor\lceil\frac{1}{2}n\rfloor\rceil - 1$）

结论

• $k > \left\lfloor\frac{2}{3}n\right\rfloor$ 时无解。
• $\left\lceil\frac{1}{2}n\right\rceil \le n \le \left\lfloor\frac{2}{3}n\right\rfloor$ 时可通过组合基本型来构造合法答案；
• $k < \left\lceil\frac{1}{2}n\right\rceil$ 时……无解

引言

冷知识：这题曾经可能会选入今年 CTS 或者联合省选。只是因为各种各样的原因这题很早（今年一月）就没了。

其实不是一道很难的题目，思路想清楚了就非常简单了，代码也很短，最难写的地方甚至只是一个最简单情况的特判。

叫做“列队”是因为本题是因军训列队有感而出。某种意义上也是一种提示。

作为投题列表里少见的 ds 题，这题刚投就被选上了。有没有人以为这是 lxl 题？

开 5s 单纯是不想完全卡掉带 $\log$ 的做法，实际上这题只要实现优秀或者调过块长多带一点 $\log$ 都是轻松过的。

这题把大数据塞在了开头，避免卡评测太严重。

比赛情况

本题预期难度是 medium+ 到 hard。不过对于熟练的 OI 选手其实应该是 medium？

来自长郡中学的队伍 Centroid.reborn(2025) 以 5 发罚时的战绩取得了首杀，似乎是写了有着巨大常数的莫队二次离线，经过各种卡常最后以 4.67s 艰难通过了。（其实没有造极限数据，认真造的话估计可以卡到 20s）

剩下的几支队伍基本都是写巨大难写的根号分治做法的。

场上甚至没看到人写正解……

题意简述

给定一个 $n \times m$ 的排列矩阵。

维护 $q$ 次操作。查询为假设反复按行列进行排序直到某次失败，最后查询单点值；修改为交换两个数。

$1 \le n \times m \le 2 \times 10^5$，$1 \le q \le 2 \times 10^5$，5s/2GB。

思路

我们先证明一个引理：排序两轮后就不可能再修改了。

为什么？我们考虑把所有小于 $w$ 的数赋值为 $0$，其余赋值成 $1$，那么排序两轮后 $0$ 就会聚集在左上角而 $1$ 就会聚集在右下角。

对每个 $w$ 都如此就意味着不会再有“逆序”存在了。

于是只用分类“一次都没成功排序”和“成功排序了 $1 \sim 2$ 次”的情况。

这只用维护有多少个行内相邻的“逆序”即可判断。而这是容易做到 $O(1)$ 维护的。

第一种情况只用维护矩阵的实际形态即可解决，难点在于第二种情况。

容易发现这样问题就变成了求各行第 $y$ 小数中，第 $x$ 小的是多少。看上去就不像能 polylog 的样子。

由于限制了矩阵总大小，容易想到根号分治类算法，但是估计很难写，所以我们换个思路。

注意到这是排列，于是我们不妨考虑对每个数维护其处于的位置，然后对这个“位置数组”进行分块。

我们现在要找到一个最小的位置 $p$，使得 $p$ 之前出现过至少 $y$ 次的行号有 $x$ 种。

于是设立间断点 $0, B, 2B, \cdots$，记录间断点之前的每种行号的出现次数，以及开桶记录每个出现次数对应了多少合法（至少这么多次数）的行号。

修改操作只用修改 $O(nm/B)$ 个间断点处的信息，每次是 $O(1)$，复杂度即为 $O(nm/B)$。

而查询操作可以先通过二分或者枚举找到答案位于哪个块，再在块内不断尝试添加单项直至合法。这部分复杂度即为 $O(\log(nm/B) + B)$。

取 $B = $Θ\Theta(\sqrt{nm})$，总复杂度即可做到 $O((nm + q)\sqrt{nm})$，可以通过此题。

std 写了 2kb，没有调过块长，跑了约 700ms。

没有特意卡带 $\log$ 的做法。

总结

题出的好！难度适中，覆盖知识点广，题目又着切合实际的背景，解法比较自然。给出题人点赞！

简要题意

有 $N$ 个人，$L$ 把锁和 $(L+K)$ 把钥匙。其中有 $L$ 把真钥匙，分别可以打开一把锁；另外 $K$ 把钥匙是假的，不能打开任何锁。

所有人按顺序尝试钥匙。每个人的策略都是最大化选择的钥匙打开选择的门的概率。如果有多种概率最大的组合，则等概率选择其中一种。

求打开所有锁之后每个人开锁次数的期望。

$1\le N\le 50$, $1\le L\le 5000$, $0\le K\le 50$

求解策略

为了解决这个问题，我们需要知道每个人具体会如何选择钥匙和锁。

显然，最开始的人不知道任何信息，所以只能随机选择一把钥匙和一把锁。

如果第一个人没有打开锁，第二个人有三种选法：选同一把钥匙开不同锁，选不同钥匙开同一把锁，选不同钥匙和锁。

选同一把钥匙开不同锁，或者选不同钥匙开同一把锁，解锁概率都是 $1/(L+K-1)$；选不同钥匙和锁的解锁概率是

$$\frac{1 - \frac{1}{L+K-1}}{L+K-1} = \frac{L+K-2}{(L+K-1)^2} < \frac{1}{L+K-1}$$

所以第二个人会以 $(L-1)/(2L+K-2)$ 的概率选同一把钥匙开不同锁，以 $(L+K-1)/(2L+K-2)$ 概率选不同钥匙开同一把锁。

结论

同理可以继续分析后续各人的策略。结论为：如果第二个人选择了同一把钥匙，则接下来每个人都会选择这把钥匙；如果第二个人选择了同一把锁，则接下来每个人都会选择这把锁。

不难想到记录 $f_i(l, k)$ 表示 $L=l, K=k$ 时第 $i$ 个人的期望开锁次数，则可以对 $f$ 进行 DP。

另一种做法是，记 $p_i(l, k)$ 表示已经打开了 $l$ 把锁，发现 $k$ 把假钥匙，轮到第 $i$ 个人进行首次尝试的概率（此时除了 $l$ 和 $k$ 以外没有任何额外信息，重置到所有组合等概率的状态），另外记 $E_i$ 表示答案。

出题人写的是后一种写法，验题人写的是前一种写法，都可以通过。

转移

因为决策有三类，所以转移分为三种：第一个人直接开锁，第二个人开锁（分相同钥匙还是相同锁讨论），后续其余人开锁（同样分类讨论）。

前两种转移都是 $O(1)$ 的，第三种转移如果直接做是 $O(L+K)$ 的，总复杂度 $O(NLK\cdot (L+K))$，不能通过本题。

推式子可知，对于第三种转移而言，恰是某一次尝试时解锁的概率是相等的。直观理解：多人抓阄，是每个人按顺序抓并直接打开，还是所有人先抓完再一起打开，并不影响每个人抽中的概率。

由此可知，我们只需要统计每个第三种转移中，每个人可以尝试多少次，再乘上相应的概率即可。这样可以将复杂度降低到 $O(NLK\cdot N)$，但仍然不能通过。

如果你常数足够小，有可能可以松过去

进一步优化

冷静分析：因为尝试是按顺序进行的，所以尝试的次数很平均。

• 如果尝试次数 $x$（如果是相同钥匙，就是剩余锁的数量；如果是相同锁，就是剩余钥匙的数量）恰好是 $N$ 的倍数，则每个人恰好试 $x/N$ 次。
• 否则，前 $x \mod N$ 个人可以试 $\lceil x/N \rceil$ 次，其余人可以试 $\lfloor x/N \rfloor$ 次。

因为相同尝试次数（也即相同转移系数）的极长连续段只有 $O(1)$ 个，所以可以用前缀和的方式，将第三种转移优化到 $O(1)$。总复杂度 $O(NLK)$，可以通过本题。

简要题意

给定包含 $N$ 个长度为 $M$ 的 01 串的集合 $S$，有 $Q$ 组询问，每个询问给出一个长度为 $M$ 的 01 串 $t_i$，求集合 $$\left\{u\in \mathbb{Z}_2^M\left|\exists T\subseteq S,\ \mathrm{s.t.}\ u = t_i \oplus \bigoplus_{v\in T} v\right.\right\}$$ 中，对应位为 $1$ 的下标序列的字典序最小的 01 串。

$1\le N, M, k\le 2000$

题解

字典序

处理最小化字典序问题，一个经典思路是按位贪心。在本题中，由于需要最小化的串长不固定，故贪心思路为：

• 如果 $u$ 可以为全零串，则答案即为全零串；否则，应使第一个为 $1$ 的下标尽可能小。
• 在确定第一个 $1$ 的下标后，检查是否可以将后缀全部变成 $0$，如果可以则输出；否则，应使第二个为 $1$ 的下标尽可能小。
• $\ldots$

上述贪心等价于：

• 如果 $u$ 可以为全零串，则答案即为全零串；否则，应尽量使第 1 位为 $1$。
• 如果确定第 1 位后，从第 2 位起可以为全零，则输出；否则，应尽量使第 12 位为 $1$。
• $\ldots$

我会线性基

因为涉及到异或，不难想到用线性基来处理本题。假设我们已经将 $S$ 处理成了相应的基向量。

对于每个询问，首先把所有主元清零，使得询问串最多只有自由元的位置非零。如果此时询问串变成全零串，则答案即为全零串。

否则，按主元顺序处理每个基向量。需要再次异或上一个基向量，当且仅当异或可以使询问串主元对应位置变成 $1$（也即此时询问串主元位置为 $0$）。特别地，如果异或完，主元位置之后变成全零，则答案即为当前串。

使用 bitset 处理，复杂度即为 $O(NMQ/w)$, 其中 $w$ 表示 bitset 位长。

除上述做法以外，还有各种使用线性基的处理方式，在此不详细展开。

不推荐考场实现的做法（简要版）

得到线性基之后，可以考虑补充没有主元对应的标准基，这样可以得到 $\mathbb{Z}_2^M$ 的一组基 $B$。将询问在 $B$ 下分解，则答案为全零串当且仅当补充的标准基的系数为 $0$。

检查完一个 $S$ 的主元位置 $x$ 后，如果这一位之后没有非零自由元，则输出当前串；否则，为了在子空间 $\mathbb{Z}_2^{M-x}$ 中处理询问串的后 $(M-x)$ 位，需要将 $x$ 对应的基向量（去掉主元的 $1$ 之后）在该子空间中重新分解，更新系数。

English version

Firstly, consider a classical dp to calculate $dp_{u,k}$ as the number of delete $k$ vertices in subtree $u$ without considering deleting vertex $n-i+1$ everyday. This is trivial.

Then, due to the existence of an “automatic deletion” process, we cannot view the selected points within the subtree of $u$ as operations with only relative order, because they may be illegal. However, we consider the final operation sequence, putting the vertex chosen on the $i$ th day in the position $n-i+1$. That is, if we firstly choose $4$, then $3$, then $1$, it will be $0431$. Then, one vertex $u$ must be put in position $u$ or later.

Then, we find that for the subtree of vertex $u$ with DFS order interval $[l,r]$, all vertex can't be put in position before $l$, and always legal to put in position after $r$ if parent-child relations are satisfied.

So we consider a dp $f_{u,i,j,k}$ which represents that the subtree of $u$ leaves position $i$ for ancestors (which means nothing can be placed at position $i$ or before, and if $i=0$, then nothing is left for ancestors), there are $j$ empty spaces (not including the one left for ancestors), and $k$ vertices need to be put into positions after the subtree of $u$. In the $i=0$ case,we merge subtrees,and the subtree with smaller DFS order can put some backward operations into the space of the subtree with bigger DFS order.

Specifically, consider the sons of $u$ enumerated in reverse order of DFS, and the son is $v$.Then enumerate $w$ as how many backward operations from $v$ will fill in space of $u$. The transition is $f_{u,0,j+j1-w,k+k1-w} \leftarrow f_{u,0,j+j1-w,k+k1-w}+f_{u,0,j,k}\times f_{v,0,j1,k1}\times {j \choose w}\times{k+k1-w \choose k}$.

For $f_{v,i,j,k}(i\neq 0)$, it won't interfere the transition with its following siblings. And for $f_{u,i,j,k}$, just consider where to put $u$. The answer for $i$ operations is $f_{1,i,i-2,0}$.

中文版本

对于树上选一个点删去一个子树方案数这个经典问题，一个常见的 dp 是记 $dp_{u,k}$ 为 $u$ 子树选 $k$ 个点方案数，转移时兄弟间用组合数将其合并，然后祖先要选就必须选在它们前面，这一部分 $O(n^2)$。

回到本题，由于存在“自动删点”的过程因此我们不能将 $u$ 子树内选的点看成只有相对顺序的操作，因为其可能不合法。但我们考虑最终的操作序列，没有的位置留空：比如样例 $1$ 中第一次选 $4$，第二次选 $3$，第三次选 $1$，那么操作序列即为 $0 4 3 1$。也就是第 $i$ 次选的点放在 $n-i+1$ 的位置上。这样，我们发现一个点 $u$ 只能填在 $u$ 及以后的位置，那么对于一个点 $u$ 的子树，其 dfs 序区间为 $[l,r]$，那么 $u$ 子树的点填到 $r$ 以后的位置一定合法，而 $u$ 留的空其前面的兄弟和祖先填进去只要没有父子关系干扰一定合法，于是我们考虑 dp。

考虑一个 dp $f_{u,i,j,k}$ 表示 $u$ 子树 $i$ 这个位置留给祖先（也就是说 $i$ 及以前不能放东西，如果 $i=0$ 就不留），有 $j$ 个空（不包含给祖先留的），有 $k$ 个点要填到 $u$ 子树以后的位置。先考虑 $i=0$ 情况。那么合并两个子树的时候就是 dfs 序更小的子树可以选一些向后的操作填到 dfs 序更大子树的空里面。然后两个子树的空合并，向后操作合并。

具体来说，考虑 $u$ 的儿子按 dfs 序倒序枚举，对于一个儿子 $v$，那么合并 $f_{u,0,j,k}$ 和 $f_{v,0,j1,k1}$ 的时候先枚举一个 $w$ 代表选多少个 $v$ 中的向后操作填到 $u$ 的 $v$ 之后的子树，转移即为 $f_{u,0,j+j1-w,k+k1-w}\leftarrow f_{u,0,j+j1-w,k+k1-w}+f_{u,0,j,k}\times f_{v,0,j1,k1}\times {j \choose w}\times{k+k1-w \choose k}$。

再考虑 $f_{v,i,j1,k1}$ ，发现它需要给祖先留空并不影响其和后面兄弟的转移，因此转移同上，只是 $v$ 留的空 $u$ 同样需要留，所以转移到 $f_{u,i,j+j1-w,k+k1-w}$。注意这里需要预处理转移系数（因为 $i$ 取任何值转移系数相同）才能达到 $O(n^5)$。

然后考虑 $f_{u,i,j,k}$ 的转移，即 $v$ 后面的子树已经留了空。那么 $v$ 子树现在不能放任何东西，但是可以用一些向后的操作填 $i$ 后面的空，这里用 $dp_{v,k}$ 去转移即可。

子树转移完后，接下来是 $u$ 自身的操作。$u$ 可以有几种选择：

• 不填，那么会多一个空 $f_{u,i,j,k}\rightarrow f_{u,i,j+1,k}$，如果把这个空留给祖先填，那么 $f_{u,0,j,k}\rightarrow f_{u,dfn_u,j,k}$。
• 填到子树准备的空里面，此时有两种选择：一是不再给祖先留空，那么 $f_{u,i,j,k}\rightarrow f_{u,0,j+1,k}$，一种是在 $i$ 前面重新给祖先留一个空，那么 $f_{u,i,j,k}\rightarrow f_{u,i_1,j+1,k}(i_1 < i)$。
• 填自己，此时不能给上面留空，$f_{u,0,j,k}$ 不变。
• 让自己变为向后操作，那么 $u$ 子树内现在不能填任何东西，但是可以给祖先留空，$f_{u,i,siz_u-2,k}\rightarrow f_{u,i,siz_u-1,k+1},f_{u,0,siz_u-1,k}\rightarrow f_{u,0,siz_u,k+1}$。

最后求答案的时候，对于要求 $k$ 次操作，相当于给 $1$ 在 $n-k+1$ 的位置留了空，同时恰好只有 $n-k$ 个空（那么后面就没有空，就是合法的操作序列），输出即可。

English version

Firstly, consider a classical dp to calculate $dp_{u,k}$ as the number of delete $k$ vertices in subtree $u$ without considering deleting vertex $n-i+1$ everyday. This is trivial.

Then, due to the existence of an “automatic deletion” process, we cannot view the selected points within the subtree of $u$ as operations with only relative order, because they may be illegal. However, we consider the final operation sequence, putting the vertex chosen on the $i$ th day in the position $n-i+1$. That is, if we firstly choose $4$, then $3$, then $1$, it will be $0431$. Then, one vertex $u$ must be put in position $u$ or later.

Then, we find that for the subtree of vertex $u$ with DFS order interval $[l,r]$, all vertex can't be put in position before $l$, and always legal to put in position after $r$ if parent-child relations are satisfied.

So we consider a dp $f_{u,i,j,k}$ which represents that the subtree of $u$ leaves position $i$ for ancestors (which means nothing can be placed at position $i$ or before, and if $i=0$, then nothing is left for ancestors), there are $j$ empty spaces (not including the one left for ancestors), and $k$ vertices need to be put into positions after the subtree of $u$. In the $i=0$ case,we merge subtrees,and the subtree with smaller DFS order can put some backward operations into the space of the subtree with bigger DFS order.

Specifically, consider the sons of $u$ enumerated in reverse order of DFS, and the son is $v$.Then enumerate $w$ as how many backward operations from $v$ will fill in space of $u$. The transition is $f_{u,0,j+j1-w,k+k1-w} \leftarrow f_{u,0,j+j1-w,k+k1-w}+f_{u,0,j,k}\times f_{v,0,j1,k1}\times {j \choose w}\times{k+k1-w \choose k}$.

For $f_{v,i,j,k}(i\neq 0)$, it won't interfere the transition with its following siblings. And for $f_{u,i,j,k}$, just consider where to put $u$. The answer for $i$ operations is $f_{1,i,i-2,0}$.

中文版本

对于树上选一个点删去一个子树方案数这个经典问题，一个常见的 dp 是记 $dp_{u,k}$ 为 $u$ 子树选 $k$ 个点方案数，转移时兄弟间用组合数将其合并，然后祖先要选就必须选在它们前面，这一部分 $O(n^2)$。

回到本题，由于存在“自动删点”的过程因此我们不能将 $u$ 子树内选的点看成只有相对顺序的操作，因为其可能不合法。但我们考虑最终的操作序列，没有的位置留空：比如样例 $1$ 中第一次选 $4$，第二次选 $3$，第三次选 $1$，那么操作序列即为 $0 4 3 1$。也就是第 $i$ 次选的点放在 $n-i+1$ 的位置上。这样，我们发现一个点 $u$ 只能填在 $u$ 及以后的位置，那么对于一个点 $u$ 的子树，其 dfs 序区间为 $[l,r]$，那么 $u$ 子树的点填到 $r$ 以后的位置一定合法，而 $u$ 留的空其前面的兄弟和祖先填进去只要没有父子关系干扰一定合法，于是我们考虑 dp。

考虑一个 dp $f_{u,i,j,k}$ 表示 $u$ 子树 $i$ 这个位置留给祖先（也就是说 $i$ 及以前不能放东西，如果 $i=0$ 就不留），有 $j$ 个空（不包含给祖先留的），有 $k$ 个点要填到 $u$ 子树以后的位置。先考虑 $i=0$ 情况。那么合并两个子树的时候就是 dfs 序更小的子树可以选一些向后的操作填到 dfs 序更大子树的空里面。然后两个子树的空合并，向后操作合并。

具体来说，考虑 $u$ 的儿子按 dfs 序倒序枚举，对于一个儿子 $v$，那么合并 $f_{u,0,j,k}$ 和 $f_{v,0,j1,k1}$ 的时候先枚举一个 $w$ 代表选多少个 $v$ 中的向后操作填到 $u$ 的 $v$ 之后的子树，转移即为 $f_{u,0,j+j1-w,k+k1-w}\leftarrow f_{u,0,j+j1-w,k+k1-w}+f_{u,0,j,k}\times f_{v,0,j1,k1}\times {j \choose w}\times{k+k1-w \choose k}$。

再考虑 $f_{v,i,j1,k1}$ ，发现它需要给祖先留空并不影响其和后面兄弟的转移，因此转移同上，只是 $v$ 留的空 $u$ 同样需要留，所以转移到 $f_{u,i,j+j1-w,k+k1-w}$。注意这里需要预处理转移系数（因为 $i$ 取任何值转移系数相同）才能达到 $O(n^5)$。

然后考虑 $f_{u,i,j,k}$ 的转移，即 $v$ 后面的子树已经留了空。那么 $v$ 子树现在不能放任何东西，但是可以用一些向后的操作填 $i$ 后面的空，这里用 $dp_{v,k}$ 去转移即可。

子树转移完后，接下来是 $u$ 自身的操作。$u$ 可以有几种选择：

• 不填，那么会多一个空 $f_{u,i,j,k}\rightarrow f_{u,i,j+1,k}$，如果把这个空留给祖先填，那么 $f_{u,0,j,k}\rightarrow f_{u,dfn_u,j,k}$。
• 填到子树准备的空里面，此时有两种选择：一是不再给祖先留空，那么 $f_{u,i,j,k}\rightarrow f_{u,0,j+1,k}$，一种是在 $i$ 前面重新给祖先留一个空，那么 $f_{u,i,j,k}\rightarrow f_{u,i_1,j+1,k}(i_1 < i)$。
• 填自己，此时不能给上面留空，$f_{u,0,j,k}$ 不变。
• 让自己变为向后操作，那么 $u$ 子树内现在不能填任何东西，但是可以给祖先留空，$f_{u,i,siz_u-2,k}\rightarrow f_{u,i,siz_u-1,k+1},f_{u,0,siz_u-1,k}\rightarrow f_{u,0,siz_u,k+1}$。

最后求答案的时候，对于要求 $k$ 次操作，相当于给 $1$ 在 $n-k+1$ 的位置留了空，同时恰好只有 $n-k$ 个空（那么后面就没有空，就是合法的操作序列），输出即可。