Solution Set #3

整理了 \(3\) 月的做题。

30. AT_arc106_e

想到二分图就好做了吧/youl

二分答案 \(mid\)，上界显然为 \(2nk\)，考虑网络流模型：右部图 \((i,j)\) 表示第 \(i\) 个人第 \(j\) 次颁奖，左部图表示 \([1,mid]\) 的所有天，每个人往能跑到的天连边，判断是否存在右部图的匹配即可。

\(n\leq 18\) 明示状态压缩。

考虑，预处理出每一天来家的朋友的状态 \(t_i\)。

判断是否存在完美匹配，考虑 Hall 定理：\(\forall S,|N(S)|\ge |S|\)。考虑左部图点集的子集 \(S\)，\(N(S)\) 是什么东西：所有右边的人，与天数集合 \(S\) 有交集的人数量 \(\times k\)。

有交集容斥成总数减不交。处理 \(f_S\) 表示被 \(S\) 完全包含，进行高维前缀和即可。

31. P10200

注意到结论 \(\min(a\oplus b,b\oplus c)\leq a\oplus c\)，所以两个集合分别排序之后，我们只需要考虑相邻两个数的异或和。

朴素的 dp 是，仅考虑前 \(i\) 个数，\(f_{i,j,0/1}\)，\(a_i\) 被放入第 \(1/2\) 个集合，第 \(2/1\) 个集合的最后一个是 \(j\) 的合法集合对 \((S_1,S_2)\) 方案数。

考虑 \(i+1\) 放入第 \(1\) 个集合中，若 \(a_{i}\oplus a_{i+1}\ge k_1\)，那么可以直接先继承 \(f_{i,?,0}\)，同理有 \(f_{i,?,1}\) 的继承。

考虑当前结尾 \(i\) 是集合 \(1\)，\(i+1\) 是集合 \(2\)，那么我们可以考虑对于 \(a_{i+1}\oplus a_j\ge k_2\)，继承所有 \(f_{i,j,0}\)。

注意到 \(i\) 在扫描线过程中可以略去，将 \(f_{j,0/1}\) 分别放在两棵字典树上，下标放在 \(a_j\) 上，模拟所有合法的 \(j\) 的求和过程即可。

32. P9200

主动弱化限制条件。直接上手做不了一点。

考虑确定下来 \(n+1\) 插入到哪里怎么做，显然有 \(n\) 种选择（插入到 \(i=1,2,\cdots,n\) 的后面）

记录此时的长度为 \(n+1\) 的数列 \(e_i\) 的前缀和为 \(pre_i\)。

对于一个起点 \(i\)，移动到 \(j\) 的电荷量，考虑断环成链，将数列 \(e_i\) 复制一份到后面，如果有 \(i\le j\)，那么有到达 \(j\) 的电荷量为 \(pre_j-pre_{i-1}\)，意义是求出区间和。否则，对于 \(i>j\) 的情况，有到达 \(j\) 的电荷量为 \(pre_{j+n+1}-pre_{i-1}\)，也就是环上的区间和。

注意到 \(\sum e_i=0\)，即 \(pre_{n+1}\) 恒等于 \(0\)，显然有 \(pre_{j+n+1}=pre_{j}\)，那么到达 \(j\) 的电荷量就等于 \(pre_{j}-pre_{i-1}\)，与 \(i\leq j\) 没有任何区别，因此可以不考虑位置关系。

考虑记 \(f(x,i)=\sum_{j=1}^{n+1}|pre_j-pre_{i-1}|\times c_j\)。\(x\) 是枚举 \(n+1\) 的插入的位置是 \((x,x+1)\) 之间（对于 \(x=n\) 是 \((n,1)\) 之间），\(i\) 是枚举粒子环游的起点，有 \(1\leq x\leq n,1\leq i\leq n+1\)。\(x\) 是我们最开始就在枚举的东西，考虑从 \(i\) 入手做。

因为 \(pre_{n+1}=pre_0=0\)，所以，对全体的 \(i\in [0,n]\) 扫一遍取 \(\min\) 就等价于对 \(i\in[1,n+1]\) 扫一遍。式子可以改写为 \(f(x,i)=\sum_{j=1}^{n+1}|pre_j-pre_i|\times c_i\)。

考虑 \(i\) 取在什么时可以取到 \(\min\)。这显然是一个带权中位数的形式。就是考虑，有一个 \(\sum c_i\) 个数的序列，对于每个 \(j\)，在这个序列中有 \(c_j\) 个 \(pre_j\)。对这个排序之后，中位数的值就是我们想要的 \(i\)。证明的话，调整法或者交换法随便证下就好了。

注意到这个形式不要求对 \((pre_i,c_i)\) 具体的下标做出要求，考虑以 \(pre_i\) 为值域的下标进行维护。

注意到 \(\sum c_i\) 是定值，那么找出来的中位数 \(x\) 就是满足，下标 \(\leq x\)（也就是所有 \(pre_j\leq x\) 的 \(j\)），对于 \(c_i\) 前缀和第一个 \(\ge \lceil \dfrac{\sum_{i=1}^{n+1} c_i}{2}\rceil\) 的 \(x\)。因为前缀和会变，考虑用权值线段树维护，下标为 \(pre_{i}\)，存的值为 \(c_i\)，直接在线段树二分就可以处理。

现在考虑移动 \(n+1\) 插入的位置。
考虑操作的序列，现在 \(n+1\) 在整个序列第 \(i\) 个，移动到第 \(i-1\) 个。

注意到每次只会影响前一个位置的前缀和值，直接模拟即可。具体的，考虑初始状态是放在 \(n\) 之后，也就是
\(\lbrace1,2,\cdots,n,n+1\rbrace\)，然后把 \(n+1\) 逐个往前移动。

每次移动形如将：

\(\lbrace1,2,\cdots,i-2,i-1,n+1,i,i+1,\cdots,n\rbrace\)

更改为：

\(\lbrace1,2,\cdots,i-2,n+1,i-1,i,i+1,\cdots,n\rbrace\)

直接对这两个位置进行修改即可。

因为直接在数据结构上二分，所以时间复杂度 \(O(n\log n)\)。

33. LOJ4040

一眼出了特殊性质 B 的做法。考虑 \(R=n\) 的部分分，显然只需要考虑对于剩下未确定的，（左部图）行往（右部图）值连边。然后找出 \((n-C)\) 组二分图完美匹配即可。断言一定有解。

二分图两侧均有 \(n\) 个点，每个点度数为 \(k\)，为正则二分图。由 Hall 定理每次都有完美匹配。

考虑 \(R\ne n\)，想了半天。结果是把右上角补了，然后再跑性质 B，注意若存在某个数的出现次数 \(>n-R\) 就是无解。此时是（左部图）列往（右部图）值连边。

直接跑若干轮完美匹配显然会似，无论是匈牙利还是 dinic，考虑换一种描述：二分图的边染色，使得任意两条相邻（有公共顶点）的边颜色不同。

怎么做呢？考虑添加一条边 \((u,v)\)，与 \(u\) 相邻的边颜色集合为 \(S_u\)，同理有 \(S_v\)，强制将 \(col_{u,v}\) 染成 \(\text{mex}(S_u)\)，然后循环找冲突，这个过程是链，由二分图的性质是有解的。

时间复杂度从 \(O(Tn^3\sqrt n)\) 变成了 \(O(Tn^2)\)。

34. LOJ4122

对 \(R\) 状压，考虑最后的机器人的相对关系，容易想到 dp 的一个维度必然是 \(f_S\) 表示集合 \(S\) 中的已经染色的最小时间。机器人一直在动，很难保持相对关系。考虑给所有东西扔一个顺时针 \(\dfrac{1}{k}\) 单位每秒的速度，然后机器人就不动了。人的顺逆速度会有两种，激活点也只以这个速度在转。

回到那个 dp，容易发现还需要扔一个 \(f_{S,i}\) 表示 \(i\in S\) 是最后一个染色的，然后就枚举 \(j\not\in S\) 进行转移。注意到每次转移的形式是，先求出来 当前时间 + 人的时间，然后再等激活点转过来。人走过来的时间小一定不劣，所以可以先求 当前时间 + 人的时间 的 \(\min\)，访问那个 dp 值向外转移时再去更新激活点转过来的时间，可以二分找。

时间复杂度 \(O(R^22^R+R2^R\log n)\)，不知道为啥过去了。

35. LOJ4121

显然就是只考虑差值 \(x\)，若 \(x\leq 0,x\to x+v\)，否则 \(x\to x-v\)。

注意到真正有用的值域只有 \(O(a_1)\)，我们只关心 \(x\) 在一定值域内的变化。考虑从左到右扫描线。当前考虑的区间是 \([-x,x)\)（容易发现左右的限制的绝对值都是相等的）

一次变换过后，\([-x,0]\to [-x+v,v]\)，\((0,x)\to (-v,x-v)\)，然后有用的区间就是这俩东西取并集，注意到 \(v\) 递减，这个东西只会越变越小。考虑中间的交集 \((-v,v]\) 是干啥的，容易发现就是将两个变换前的数，让他们在这次变换后的值是相等的，暴力将重合的位置的并查集合并。这个东西可以并查集套 treap 维护。

然后把交集的区间只保留一个，treap 维护分裂合并就行，复杂度 \(O(n\log n)\)。

36. LOJ3481

CF1864F。

每种颜色每个位置可以少一次操作当且仅当两个相邻位置中间的 \(\min\) 大于他们。随便扫描线加树状数组维护下就过了。

37. 「联合省选 2023」过河卒

注意到 \(n,m\leq 10\)，考虑将三个棋子的位置关系以及先后手直接设为状态。即考虑有向图，点 \(((a,b),(c,d),(e,f)),0/1\) 代表红棋子 \(1\) 的坐标为 \((a,b)\)，红棋子 \(2\) 的坐标为 \((c,d)\)，黑棋子为 \((e,f)\)，当前是 红方/黑方 作为先手。

注意：状态合法要求红棋子不重合。

考虑将问题抽象成：对于一张有向图，初始位于状态 \(s\)，每次可以向点的后继移动一步，不能移动者输。

可以先把图建出来，这个可以用 BFS，建出来一张大小为 \(2(nm)^3\) 的有向图。

那么我们需要最先判断的事情是，谁是 winner。因此考虑对每个点设上 \(N/P/T\) 态表示 必败点 / 必胜点 / 平局点，然后将第二属性设为 \(\text{dist}\) 表示达到必胜策略的最优步数。

注意到无出度的状态是 \(N\) 态。考虑：

• 若后继存在 \(N\) 态，则该点为 \(P\) 态。
• 若后继全部为 \(P\) 态，则该点为 \(N\) 态。
• 否则该点为 \(T\) 态。

考虑用另外一个 BFS 来求 \(\text{dist}\)。注意到终态的 \(N/P/T\) 态已知，均为 \(N\)，所以可以从终止状态倒序转移，直接建立反图。

考虑，对于一个点 \(u\)，如果出现在队列中，代表它的 \(N/P/T\) 以及 \(\text{dist}\) 已经完全确定。注意到 \(T\) 态没有太大存在的必要，因此考虑队列只加入 \(N/P\) 态的点。

将上述讨论的分讨改到反图上，就是向后转移。考虑队列中的点 \(u\) 向 \(v\) 转移：

• 若 \(u\) 为 \(P\) 态，则 \(v\) 可能为 \(N\) 态，此时 \(v\) 的后继都被加入过队列时，那么 \(v\) 就确定是 \(N\) 态，同时更新 \(\text{dist}\) 即可。
• 我们限定队列中的点只能是 \(N/P\) 态，因此 \(u\) 在剩余情况只会是 \(N\) 态，向后继转移时，若 \(v\) 的 \(N/P\) 态未完全确定，那么可以直接确定 \(v\) 是 \(P\) 态，若未加入队列，加入队列；并且更新 \(\text{dist}\)。

不知道为什么洛谷 \(\text{TLE}\) 了一个点。