chx沟槽的黑冰茶出题组,这么喜欢构造是吧,吃nm的构史去吧.
E
看上去和构造没什么关系,但实际上充分性需要手动搓出一个调整方案. 一开始很容易观察到,每次操作都会令总和增加或减少 $2$,所以总和的奇偶性不变. 不过手玩一下会发现一个更强的不变量:能够操作的两张牌差值为 $1$,所以其中恰好一张是奇数,另一张是偶数;同时加减 $1$ 以后二者的奇偶性互换,因此整个牌堆中奇数牌的数量始终不变.
除此之外,若两个牌堆原本不同,那么初始牌堆中必须存在一对差值为 $1$ 的牌,否则连第一次操作都做不了. 操作又是可逆的,所以从最后一步倒推可知,目标牌堆中也必须存在这样一对牌.
接下来说明这些条件确实充分. 先在初始牌堆中保留一对相邻数作为工具牌. 这两张牌可以不断同时增加或减少 $1$,所以工具对能够被整体移动到任意位置 $(x,x+1)$. 现在再拿一张值为 $x$ 的牌,对它与工具牌中的 $x+1$ 同时加 $1$,便有
$$\{x\}\cup\{x,x+1\} \longrightarrow \{x+2\}\cup\{x,x+1\}.$$这里三张牌的身份发生了交换,但题目只关心牌的点数而不区分牌本身,所以新的 $(x,x+1)$ 仍然可以作为工具对. 将它整体移回原位以后,效果就等价于在保持工具对不变的同时令另一张牌增加 $2$. 减少 $2$ 也完全类似:
$$\{x\}\cup\{x-1,x\} \longrightarrow \{x-2\}\cup\{x-1,x\}.$$因此只要保留一对相邻数,其余任意一张牌都可以增加或减少任意偶数. 分别从初始和目标牌堆中选出一个相邻数对,它们都恰好包含一个奇数和一个偶数. 若两个牌堆的奇数牌数量相同,删去这两个数对后,剩余的奇数牌和偶数牌仍能分别一一匹配. 每组匹配的两个数奇偶性相同,差值为偶数,于是利用上面的工具对逐张调整即可;最后再将工具对整体移动成目标牌堆中预留的相邻数对.
综上,若两个牌堆已经相同,答案显然为 Yes. 否则当且仅当两个牌堆都含有一对相邻数,并且奇数牌的数量相同时有解. 将两个序列排序后即可同时判断是否相同以及是否存在相邻数,时间复杂度为 $\mathcal O(n\log n)$.
F
比较板的贪心,不过首先需要把这个分治过程换一种方式理解. 一个询问会在第一次遇到位于自身区间内的分治点时被处理,所以如何划分当前区间其实不重要,关键只是选出了哪些 mid. 若希望所有询问都在前 $d$ 层被处理,那么前 $d$ 层出现的分治点必须满足每个询问区间都至少包含其中一个点.
深度为 $d$ 的二叉分治树至多包含
$$1+2+\cdots+2^{d-1}=2^d-1$$个分治点. 设覆盖全部询问区间至少需要 $k$ 个点,那么显然有 $2^d-1\ge k$,即
$$d\ge\left\lceil\log_2(k+1)\right\rceil.$$反过来,把这 $k$ 个覆盖点按照坐标排序,每次选择中间的点作为当前 mid,再对左右两侧递归,就能构造一棵高度为 $\lceil\log_2(k+1)\rceil$ 的平衡分治树. 每个询问都包含至少一个覆盖点,在遇到第一个属于自己的点之前又一定会被完整地分到同一侧,所以它必然能在这个深度以内得到处理. 因此问题等价于在数轴上选择最少的点,使每个询问区间都包含至少一个所选点.
剩下的就是经典区间选点. 将所有区间按照右端点从小到大排序,取第一个尚未覆盖区间的右端点作为新的覆盖点,再跳过所有包含它的区间,不断重复即可. 这个选择可以用交换论证证明:设当前右端点最小的区间为 $[l,r]$,任意合法方案都必须在其中选择某个 $p\le r$;由于其他剩余区间的右端点都不小于 $r$,把 $p$ 替换成 $r$ 不会让原本被 $p$ 覆盖的区间失去覆盖,却可能覆盖更多右侧的区间.
设贪心得到的点数为 $k$,答案就是 $\lceil\log_2(k+1)\rceil$. 排序后线性扫描即可,时间复杂度为 $\mathcal O(q\log q)$.
M
神秘线性代数构造题. 由于题目钦定了 $\det(A_\emptyset)=1$,取 $S=\emptyset,S'=T$ 就能发现每个主子式的值其实已经被唯一确定:
$$\det(A_T)\equiv 1+\sum_{i\in T}a_i\pmod {998244353}.$$反过来,只要所有主子式都满足这个式子,任取 $S\subseteq S'$ 后将二者相减就能自动满足原条件. 特别地,取 $T=\{i\}$ 可知对角线必须满足 $A_{i,i}=a_i+1$.
接下来手玩一下 $2\times2$ 的情况,可以得到
$$\begin{pmatrix} a_1+1 & a_2\\ a_1 & a_2+1 \end{pmatrix},$$它的行列式恰好为 $1+a_1+a_2$. 观察这个形式并直接推广,令
$$A_{i,j}=a_j+[i=j],$$也就是
$$A=I+\boldsymbol 1a^{\mathsf T},$$其中 $\boldsymbol 1$ 是全为 $1$ 的列向量. 对于任意 $T\subseteq[n]$,对应主子矩阵仍然具有相同结构
$$A_T=I+\boldsymbol 1_Ta_T^{\mathsf T}.$$由矩阵行列式引理可得
$$\det(A_T) =1+a_T^{\mathsf T}\boldsymbol 1_T =1+\sum_{i\in T}a_i,$$正好就是需要的值. 因此输出时令对角位置为 $a_i+1$,其余第 $j$ 列的元素全部为 $a_j$ 即可,所有元素对 $998244353$ 取模. 时间复杂度为 $\mathcal O(n^2)$,也就是输出整个矩阵所需的复杂度.
C
这个题是一个纯狗屎的对脑电波题,既繁琐又冗余,出题人梅伊阁诗人.
H
很有意思的 01-Trie 交互题. 首先把未知集合中的所有数都看成长度为 $30$ 的二进制串,并放到一棵 01-Trie 上. 关键在于,虽然交互器每次返回的是整个集合中的最大异或值,我们仍然可以把一次询问强制限制在某棵已知非空的 Trie 子树中.
假设这棵子树的公共前缀为 $p$. 构造询问值 $c$ 时,将前缀部分取成 $p$ 的逐位取反. 这样子树内任意元素与 $c$ 异或后,对应的高位前缀都会全部变成 $1$;子树外的元素则会在某个更高位得到 $0$,所以无论低位如何取值都不可能成为全局最大值. 接下来只需控制剩余低位:
- 若低位全部填 $0$,交互器选中的就是该子树中的最大值.
- 若低位全部填 $1$,低位的大小关系被反转,交互器选中的就是该子树中的最小值.
设交互器的回答为 $r$,那么被选中的原数就是 $r\oplus c$. 因此只要知道一棵非空子树的前缀,就能各用一次询问得到它的最大值与最小值.
一开始询问 $c=0$,直接得到整个集合的最大值 $mx$;再询问
$$c=2^{30}-1,$$此时异或会反转全部 $30$ 位的大小关系,所以将回答再与 $c$ 异或即可得到最小值 $mn$. 找到 $mn$ 与 $mx$ 从高到低第一个不同的二进制位. 在此之前二者拥有相同前缀,并且所有元素都位于 $[mn,mx]$ 中,所以整棵 Trie 在这段前缀上都没有分叉. 到达第一个不同位时,$mn$ 的这一位为 $0$,$mx$ 的这一位为 $1$,于是这里正好分成两个非空子树.
左子树的最小值已经确定为 $mn$,所以只需询问它的最大值 $mx_0$;右子树的最大值已经确定为 $mx$,所以只需询问它的最小值 $mn_1$. 这样原问题就被拆成了两个完全相同的子问题
$$[mn,mx_0],\qquad [mn_1,mx].$$若某个子树的两个端点相等,由于集合中的元素互不相同,这棵子树中便只有这一个元素,直接剪掉递归分支. 否则继续寻找两个端点的最高不同位并按照同样的方法分叉. 整个过程就是在压缩后的 01-Trie 上递归拆分子树. 同时维护目前找到的所有互异元素,一旦数量达到 $n$ 就立刻停止询问.
最后验证询问次数. 在任意一次完整拆分之后,当前递归前沿中的子树互不相交并覆盖整个集合. 设其中有 $a$ 棵单点子树和 $b$ 棵非单点子树,那么目前已经确定的互异元素数为
$$K=a+2b,$$因为单点子树贡献一个端点,非单点子树则贡献两个不同的端点. 初始时前沿只有根;每完整拆分一棵非单点子树需要两次询问,并使前沿子树数量增加 $1$. 若已经完成了 $s$ 次拆分,就有
$$a+b=s+1.$$只要还没有找齐全部元素,就有 $K<n$ 且 $b\ge 1$,因此
$$K=a+2b=(a+b)+b\ge s+2.$$于是尚未结束时一定有 $s\le n-3$,再完成至多一次拆分便会找齐所有元素. 完整拆分次数至多为 $n-2$,加上最开始获取全集最小值和最大值的两次询问,总询问次数不超过
$$2+2(n-2)=2n-2.$$自适应交互器也不会影响这个过程. 对于询问 $c$ 和回答 $r$,元素 $r\oplus c$ 必须存在于任何与全部历史回答相容的集合中,所以已经发现的元素不会在之后被交互器换掉. 当收集到 $n$ 个互异元素时,任意合法的相容集合都只能恰好由它们组成.
K
前面的建模比较平凡. 一次操作只会交换两个元素,所以若最后两个序列相等,每个数在 $a,b$ 中的总出现次数一定是偶数. 反过来,跨行交换足以实现所有位置之间的任意排列:跨行的两个位置可以直接交换,同一行内的两个位置则可以借另一行的任意位置中转,用三次操作完成交换. 因此每个数的总出现次数均为偶数也是有解的充分条件.
另外,交换 $a_i,b_i$ 的代价为 $|i-i|=0$,所以同一列中的上下顺序可以免费调整. 若一开始就有 $a_i=b_i=x$,则可以钦定一个最优方案始终不操作这一列. 从同值元素的位置匹配来看,若两个位置 $i,i$ 原本分别与 $L,R$ 配对,将 $(L,i),(i,R)$ 改成 $(L,R),(i,i)$ 后距离和仍然是 $R-L$. 因而总能让这两个 $x$ 在距离 $0$ 处直接配对,之后将所有初始相等的列删去即可.
这个题真正关键的就是下面的结论.
对于每个数值 $v$,将它在剩余两行中的全部出现下标按照非降序排列为
$$p_{v,1}\le p_{v,2}\le\cdots\le p_{v,2k_v}.$$那么最小总代价恰好为
$$\frac12\sum_v\sum_{t=1}^{k_v} \left(p_{v,2t}-p_{v,2t-1}\right).$$首先证明下界. 最终每两个相同的数都要在同一列汇合. 对于同一个数值,数轴上的最小权完美匹配一定是将排序后相邻的出现位置配对,所以令
$$D=\sum_v\sum_{t=1}^{k_v} \left(p_{v,2t}-p_{v,2t-1}\right),$$则所有元素的总水平移动距离至少为 $D$. 一次代价为 $|i-j|$ 的交换会让两个元素各自移动 $|i-j|$,所以元素总移动距离等于总代价的两倍. 因此任意方案都满足
$$\operatorname{cost}\ge\frac D2.$$接下来说明这个下界可以取到. 每次取当前最靠左的未解决列 $i$,记 $x=a_i,y=b_i$. 由于剩余部分中每个数仍然出现偶数次,在 $i$ 右侧一定还能找到 $x,y$. 令 $p$ 为 $x$ 下一次出现的位置,$q$ 为 $y$ 下一次出现的位置.
若 $p\le q$,先通过一次可能需要的同列免费交换把位置 $p$ 的 $x$ 放到 $a_p$,再交换 $a_p,b_i$,代价为 $p-i$. 这样第 $i$ 列就变成 $(x,x)$,而原来位于 $i$ 的 $y$ 被移动到了 $p$. 操作前,$x,y$ 的第一对分别贡献 $p-i,q-i$;操作后 $x$ 的这一对已经解决,$y$ 的第一对则变成 $(p,q)$,贡献 $q-p$. 因而势能的下降量为
$$(p-i)+(q-i)-(q-p)=2(p-i),$$恰好是本次代价的两倍. 若 $q<p$,对称地把位置 $q$ 的 $y$ 换到第 $i$ 列,同样会以代价 $q-i$ 消去 $2(q-i)$ 的势能. $p=q$ 时任取一种操作即可,并且会同时解决两列.
所以每一步的实际代价都恰好等于 $D$ 的下降量的一半. 最后所有列均相等且 $D=0$,总代价便恰好等于初始的 $D/2$,从而达到下界. 每轮至多使用一次同列免费交换和一次有代价交换,并且至少永久解决一列,所以操作次数至多为 $2n$,自然满足 $3n$ 的限制.
B
比较自然的 2-SAT,不过直接建图显然会炸,真正需要做的是长链剖分优化建图. 令布尔变量 $X_u$ 表示是否在节点 $u$ 安装基站. 对于每条树边 $(u,v)$,至少选择一个端点,所以有子句
$$X_u\lor X_v,$$在蕴含图中加入
$$\neg X_u\to X_v,\qquad \neg X_v\to X_u.$$对于一次故障 $(x,y)$,定义
$$S(x,y)=\{z\mid z\in subtree(x),\operatorname{dep}(z)-\operatorname{dep}(x)=y\}.$$如果选择了 $x$,那么 $S(x,y)$ 中的所有节点都不能选择. 也就是说,对于每个 $z\in S(x,y)$ 都需要加入
$$\neg X_x\lor\neg X_z,$$也就是
$$X_x\to\neg X_z,\qquad X_z\to\neg X_x.$$若直接枚举集合中的所有点,最坏复杂度会达到 $O(nm)$. 因此接下来考虑用一个虚点代表整个集合. 令 id[u][d] 表示集合 $S(u,d)$ 的代表文字,它为真时能够推出这个集合中所有的 $\neg X_z$. 单点集合直接令
若已有两个集合的代表文字 $r_1,r_2$,新建辅助变量的一对文字 $g,\neg g$,并加入
$$g\to r_1,\qquad g\to r_2,$$以及对应的逆否边
$$\neg r_1\to\neg g,\qquad \neg r_2\to\neg g.$$于是 $g$ 就可以作为两个集合并集的代表. 对于故障 $(x,y)$,若 $S(x,y)$ 非空,记 $r=id[x][y]$,只需要加入
$$X_x\to r,\qquad \neg r\to\neg X_x.$$这样对于每个 $z\in S(x,y)$,图中都存在路径
$$X_x\to r\to\neg X_z, \qquad X_z\to\neg r\to\neg X_x,$$正好等价于逐个加入原来的限制. 这里引入辅助变量不会改变原问题的可满足性:任取一组满足原约束的赋值,将每个集合虚点赋成其所有叶子文字 $\neg X_z$ 的合取,就能扩展成新图的一组合法赋值;反过来,$X_x\to id[x][y]$ 又会强迫集合中的所有 $\neg X_z$ 成立.
剩下的问题就是如何建立全部 id. 令 $h(u)$ 表示以 $u$ 为根的子树高度,选取高度最大的儿子 $son_u$ 作为重儿子. 由于
可以先将重儿子的数组错开一位直接复用:
$$id[u][d+1]\gets id[son_u][d].$$之后枚举每个轻儿子 $v$ 和 $0\le d\le h(v)$,用上面的方式新建一个虚点,合并当前的 id[u][d+1] 与 id[v][d],再把 id[u][d+1] 更新成这个新虚点. 这和长链剖分优化 DP 时重儿子继承数组,轻儿子逐层合并是完全一样的.
看上去这里仍然枚举了很多深度,但总合并次数实际上只有 $O(n)$. 每个轻儿子都是一条重链的链头,而 $h(v)+1$ 恰好等于从 $v$ 沿重边一直走到叶子的链长. 所有重链两两不交,所以
$$\sum_{v\text{ is a light child}}(h(v)+1)\le n.$$每次合并只新建一对辅助文字并加入常数条边,故集合虚点及其边数都是 $O(n)$. 树边限制需要 $O(n)$ 条边,每个故障只需要常数条边,最终蕴含图的点数和边数均为 $O(n+m)$. 对整张图跑 SCC 即可判断是否有解,但不仅原变量,每个辅助变量也都需要检查正负文字是否落在同一个 SCC 中. 有解时按照 SCC 的拓扑序赋值,最后只输出取真的原变量.
实现时还有一个比较阴间的细节. 如果像长剖优化 DP 一样真正让 id[u] 与重儿子的数组共享内存,那么父亲合并轻儿子时会覆盖重儿子原来的代表编号. 因此需要先按照起点 $x$ 将所有故障分组. 后序 DFS 完成节点 $u$ 的全部合并以后,立刻使用当前的 id[u][y] 加入所有以 $u$ 为起点的故障边,然后才能返回父亲并允许这段数组被覆盖. 若 $y>h(x)$,则 $S(x,y)$ 为空,这条故障没有产生任何限制,直接忽略即可.