chxD
普通的 DP 题,不过需要稍微考虑一下实现,不然复杂度很容易写假. 将 0,1,? 分别编码成三进制位 $0,1,2$,并令 $f_s$ 表示三进制状态 $s$ 对应的广义子集和. 对于不含问号的状态,其每一位已经唯一确定了一个二进制下标 $j$,边界就是
如果状态 $s$ 的第 $i$ 位是问号,那么按照这一位最终填入 $0$ 或 $1$ 分类即可得到
$$f_s=f_{s-2\cdot3^i}+f_{s-3^i}.$$直接枚举状态中的任意一个问号会让转移顺序比较混乱,而每轮扫描全部 $3^n$ 个状态又会写成 $O(n3^n)$. 这里采用和 $O(k2^k)$ 实现子集和类似的枚举方式,总共进行 $n$ 轮. 第 $i$ 轮只计算最高的问号恰好位于第 $i$ 位的所有状态. 当第 $i$ 位分别改成 $0$ 和 $1$ 后,剩余问号只可能位于 $0\sim i-1$ 中,所以这两个子状态都已经在前面的轮次计算完毕.
具体地,第 $i$ 位以下的三进制位可以任取,共有 $3^i$ 种;第 $i$ 位固定为 ?;第 $i$ 位以上不能再出现问号,所以共有 $2^{n-i-1}$ 种. 因此所有转移的总数为
每个含问号的状态恰好被计算一次,总复杂度就是 $O(3^n)$.
实现时可以预处理 binToTer[mask],表示把二进制 mask 的每一位原样放进三进制后得到的编号. 枚举第 $i$ 轮的高位二进制状态 high 与低位三进制状态 low,当前状态可以直接写成
这样内层的 low 连续递增,访问也比较连续,足以应付 $1$ 秒的时限. 由于任意广义子集和至多为 $9\cdot2^{16}$,使用 32 位整数存储 dp 即可,空间复杂度为 $O(3^n)$. 初始化和每次转移完成时顺手把对应的 $f_s$ 异或进答案,最后直接输出即可.
G
首先考虑直接不分组,也就是把所有宝石都放进同一个组. 记全体元素的异或和为
$$T=a_1\oplus a_2\oplus\cdots\oplus a_n,$$此时方案的价值就是 $T$.
接下来考虑组数不少于 $2$ 的情况. 感性上组数应该不会太多,事实上任意三个组都可以直接合并,并且答案一定不会变差. 假设这三个组的亮度分别为 $B_1,B_2,B_3$,合并后的新组亮度为
$$B'=B_1\oplus B_2\oplus B_3.$$逐位考虑原方案的答案. 若某一位为 $1$,说明所有组的亮度在这一位都为 $1$,于是
$$(B')_k=1\oplus1\oplus1=1,$$合并以后不会丢掉这一位. 若原答案的某一位为 $0$,那么合并后它既可能仍为 $0$,也可能变成 $1$,同样不可能让答案变差. 因此每次都可以把三个组压成一个组,使组数减少 $2$. 如法炮制,奇数组最终可以压成一个组,偶数组最终可以压成两个组,所以一定存在一个最优方案只使用一个组或两个组.
现在只需要求分成两个组时的最优答案. 设第一组的异或和为 $S$,那么第二组的异或和就是 $T\oplus S$,方案价值为
$$S\mathbin{\&}(T\oplus S).$$若 $T$ 的某一位为 $1$,那么 $S$ 与 $T\oplus S$ 在这一位必然相反,所以答案的这一位不可能为 $1$. 若 $T$ 的某一位为 $0$,二者在这一位相同,答案的这一位就等于 $S$ 的这一位. 因此有
$$S\mathbin{\&}(T\oplus S)=S\mathbin{\&}\neg T.$$也就是说,$T$ 中为 $1$ 的位全部没有贡献,只需要屏蔽这些位以后最大化第一组的异或和. 令
$$b_i=a_i\mathbin{\&}\neg T,$$那么任取一组宝石后得到的有效部分,就是对应若干个 $b_i$ 的异或和. 将所有 $b_i$ 扔进线性基,再从高位到低位贪心维护答案 $S$:若 $S$ 的第 $i$ 位已经为 $1$ 就跳过,否则当第 $i$ 位存在基向量时令 $S$ 异或上它. 最后得到的就是两组情形的最大价值.
分组非空的限制也不会产生问题. 若线性基求出的答案大于 $0$,对应子集显然非空,同时它也不可能包含全部元素,因为全部 $b_i$ 的异或和为
$$T\mathbin{\&}\neg T=0.$$若线性基答案为 $0$,在 $n\ge2$ 时任意拆成两个非空组即可. 因此最终答案就是单组方案 $T$ 与线性基求出的双组方案二者的最大值. 线性基维护 $60$ 个二进制位,时间复杂度为 $O(60n)$.
J
由于比较的是权值序列的字典序,这个递归结构天然适合 DFS. 若两个序列在某一位第一次不同,那么这一位较小的序列无论怎样向后拓展,仍然小于另一条序列的任意拓展;若一个序列是另一个序列的前缀,则较短的序列排在前面. 因此可以把所有可能的权值序列看成一棵字符集为 $1\sim8$ 的隐式 Trie,在每个节点先输出当前序列,再按照 $1,2,\ldots,8$ 的顺序递归儿子,恰好就是字典序.
不过题目区分具体经过的边,所以 DFS 状态不能只记录当前路径末尾节点构成的普通集合. 对于当前权值前缀 $p$,令
$$cnt_u=\#\{\text{权值序列为 }p\text{ 且终点为 }u\text{ 的路径}\}.$$也就是说,状态实际保存的是一个带重数的末尾节点集合. 当前权值序列对应的不同路径总数为
$$C=\sum_u cnt_u.$$进入这个状态时,应当先向答案中加入 $C$ 个当前长度 $len$. 这些路径虽然使用的边不同,但是权值序列完全相同,所以长度也完全相同. 若答案数量已经达到 $k$,就立刻结束整个搜索,不再考虑任何拓展.
之后依次枚举下一条边的权值 $w=1,2,\ldots,8$. 对于所有当前可能的末尾节点,沿权值为 $w$ 的边转移,得到
$$cnt'_v= \sum_u cnt_u\cdot \#\{u\to v\text{ 且边权为 }w\}.$$若新的带重集合非空,就递归进入长度为 $len+1$ 的状态. 这一层递归全部结束以后,才继续考虑下一个权值 $w+1$,从而保证搜索顺序就是权值序列的字典序.
初始状态可以看成每个顶点上各有一条空路径,也就是所有 $cnt_u=1$,这样第一次转移会把每一条边恰好变成一条长度为 $1$ 的路径. 不过空路径并不属于题目要求的路径,所以根状态本身不能加入答案,只能从它的八个儿子开始正常 DFS.
实现时将邻边按照起点与权值分类,状态只存储 $cnt_u>0$ 的 (u,cnt_u) 对,并用时间戳数组合并转移到相同终点的计数. 所有数量都只需截断到当前还缺少的答案数. 构造某个儿子时一旦路径数量已经达到这个上限,就可以立刻用 $len+1$ 填满剩余答案并结束,不必继续计算它的终点分布.
最后考虑复杂度. 每个真正进入的非根 Trie 节点都至少向答案中贡献一条路径,所以访问的状态数不超过 $k$. 一个状态的非零末尾节点数量不超过它对应的路径数,而枚举八种边权的额外开销也就可以摊到这些路径上. 再加上读入和分类全部边,总复杂度为
$$O(n+m+8k),$$所有计数与状态也只需保留到 $k$. 概念上这是一个 DFS,但最坏情况下字典序最小的权值可能沿环连续拓展 $k$ 次,递归深度达到 $k$. 实现时最好使用显式栈模拟递归,避免系统栈直接爆掉.
I
首先观察每个位置只有修改和不修改两种状态,同一个位置操作多次显然没有意义. 固定所有不修改的位置以后,它们按照原来的顺序构成一个子序列,而相邻两个保留位置之间的元素都可以随意修改.
对于两端值分别为 $x,y$ 的一段,异或距离满足三角不等式,所以无论在中间填入多少个数,这段相邻异或之和都至少为 $x\oplus y$. 这个下界一定可以取到:让修改过的元素先全部等于左端点,再在某处切换成右端点即可. 因此每段修改区间只需要贡献两侧保留元素的异或值.
为了把原式中的 $a_1+a_n$ 一起处理,添加两个虚拟位置
$$a_0=a_{n+1}=0,$$并钦定它们始终保留. 设最终保留的原位置为
$$0=i_0<i_1<\cdots<i_k<i_{k+1}=n+1,$$那么方案代价就是
$$\sum_{t=0}^{k} (a_{i_t}\oplus a_{i_{t+1}}) +(n-k)C.$$其中两端的 $0\oplus a_{i_1}$ 与 $a_{i_k}\oplus0$ 正好对应原式中的首尾两项. 若一个原位置都不保留,就相当于把所有数改成 $0$,代价为 $nC$.
于是可以先写出一个朴素 DP. 令 $f_i$ 表示处理到位置 $i$,并且位置 $i$ 一定被保留时的最小代价. 若上一个保留的位置为 $j<i$,那么中间的 $i-j-1$ 个位置全部被修改,因此
$$f_i= \min_{0\le j<i} \left\{ f_j+(i-j-1)C+(a_i\oplus a_j) \right\},$$边界为 $f_0=0$,最终答案就是 $f_{n+1}$. 不过直接枚举上一个位置的复杂度为 $O(n^2)$.
将与 $i,j$ 有关的线性项分离,可以得到
$$f_i-iC= \min_{0\le j<i} \left\{ (f_j-jC)+(a_i\oplus a_j) \right\}-C.$$令
$$g_i=f_i-iC,$$转移就变成
$$g_i= \min_{0\le j<i} \left\{ g_j+(a_i\oplus a_j) \right\}-C.$$若若干个 $a_j$ 完全相同,那么异或部分也完全相同,只需要留下其中最小的 $g_j$. 剩下的问题就是动态维护一个带附加权值的异或最小值,但这个东西并没有特别直接的数据结构,所以考虑平衡规划.
由于 $a_i<2^{18}$,将每个数拆成高低各 $9$ 位. 记
$$H(x)=x\mathbin{>>}9, \qquad L(x)=x\bmod2^9.$$从一个历史值 $a_j$ 转移到当前值 $a_i$ 时,构造中间值 $b$,令它的高 $9$ 位与 $a_i$ 相同,低 $9$ 位与 $a_j$ 相同. 两次改变涉及的数位互不相交,所以
$$a_j\oplus a_i=(a_j\oplus b)+(b\oplus a_i).$$接下来把前一半的变化分配给推送,后一半的变化分配给拉取. 维护
$$mn[p][q]= \min_{\substack{j<i\\L(a_j)=q}} \left\{ g_j+\bigl(H(a_j)\oplus p\bigr)2^9 \right\}.$$每次计算完 $g_j$ 后,枚举未来目标值的高 $9$ 位 $p$,执行
$$mn[p][L(a_j)]\gets \min\left\{ mn[p][L(a_j)], g_j+\bigl(H(a_j)\oplus p\bigr)2^9 \right\}.$$这一步相当于提前完成 $a_j\to b$ 的高位变化. 计算当前 $g_i$ 时,高位已经确定为 $H(a_i)$,只需枚举中间值的低 $9$ 位 $q$,补上剩余的低位贡献:
$$g_i= \min_{0\le q<2^9} \left\{ mn[H(a_i)][q]+(q\oplus L(a_i)) \right\}-C.$$先将虚拟状态 $a_0=0,g_0=0$ 推入 mn,再依次查询并推入 $1\sim n$ 的状态,最后只查询虚拟右端点 $a_{n+1}=0$. 答案通过
还原. 每个位置的推送和拉取都只枚举 $2^9$ 种情况,总复杂度为 $O(n2^9+2^{18})$,空间复杂度为 $O(2^{18})$. 由于 $g_i$ 可能为负数,所有 DP 值都需要使用 64 位有符号整数.
H
这个题一眼看上去完全没什么思路,不过既然是一个博弈论题,那么大概率会存在一个可以直接判断胜负的结论. 于是考虑把值域限制在 $[0,31]$ 内打表找规律,不得不说打表太强大了.
对于每个数 $x$,记它的出现次数为 $c_x$. 首先将所有相同的数两两配对,一共可以得到 $\lfloor c_x/2\rfloor$ 对. 如果 $c_x$ 是奇数,则还会额外剩下一个没有配对的 $x$. 记所有没有配对的数构成的集合为
$$O=\{x\mid c_x\equiv1\pmod 2\},$$并令 $q=|O|$. 由于原序列的长度为 $2n$,所以 $q$ 也一定是偶数. 再记所有已配对元素对 Menji 的异或贡献为
$$H= \bigoplus_x \underbrace{x\oplus x\oplus\cdots\oplus x}_{\lfloor c_x/2\rfloor\text{ 次}}.$$也就是说,每一对相同的数向 $H$ 贡献一次 $x$.
首先看看双方分别能对这些数对做什么. Bot 可以预先固定所有配对,每当 Menji 从某一对中取走一个数时,Bot 就立即取走它的同值配偶. 这样 Menji 最终一定从每一对中恰好得到一个数,异或和也就被固定为 $H$.
反过来,Menji 也有办法保证自己从每一对中恰好得到一个数. 她先从任意一对中取走一个,将这一对视为当前尚未闭合的数对. 之后如果 Bot 从一对尚未动过的数对中取数,Menji 就立即取走它的配偶. 如果 Bot 取走了当前未闭合数对中的另一个数,Menji 就从另一对尚未动过的数对中任取一个,把它当作新的未闭合数对. 不断重复这个过程,最终 Menji 同样会从每一对中恰好得到一个数.
于是只需要按照 $q$ 分类讨论.
$q=0$
此时所有数都已经被两两配对. 如果 $H=0$,Menji 使用上面的未闭合数对策略,就能保证最终异或和为 $H=0$. 如果 $H\ne0$,Bot 使用同值配偶回应策略,就能强制 Menji 的最终异或和为 $H\ne0$. 因此这种情况下 Menji 当且仅当 $H=0$ 时获胜.
$q=2$
设两个没有配对的数分别为 $x,y$. 如果 $H=x$,Menji 第一轮直接选择 $x$. 此后如果 Bot 从某个普通数对中取数,Menji 就取走它的配偶. 如果 Bot 提前取走了 $y$,那么剩下的局面只包含普通数对,Menji 再改用未闭合数对策略即可. 如果 Bot 一直不取 $y$,那么最后 $y$ 也只会留给 Bot. 因此 Menji 最终得到了 $x$ 以及每个普通数对中的一个数,她的异或和为
$$x\oplus H=0.$$当 $H=y$ 时完全同理. 如果 $H$ 既不等于 $x$ 也不等于 $y$,Bot 就将 $x,y$ 视作一对,并将其余相同数照常配对. 每当 Menji 从某一对中取数,Bot 立即取走另一个. 这样 Menji 从 $x,y$ 中只能得到一个,最终异或和只可能是
$$H\oplus x$$或 $H\oplus y$,二者均不为 $0$. 因此这种情况下 Menji 当且仅当 $H\in\{x,y\}$ 时获胜.
$q\ge4$
此时 Bot 一定必胜. Bot 可以继续对所有普通数对使用同值配偶回应策略,于是这些数对对 Menji 的贡献被固定为 $H$. 问题就可以抽象为:有 $q$ 个两两不同的数,Menji 和 Bot 每轮分别删除一个,Menji 希望自己取得的所有数的异或和恰好为某个目标值 $T$. 在原问题中这个目标就是 $T=H$.
先看 $q=4$ 的情况. 假设 Menji 第一次选择了 $z$,那么能够与 $z$ 凑出目标 $T$ 的数唯一确定为
$$z\oplus T.$$如果 $z\oplus T$ 在剩余三个数中,Bot 立即将它删除. 如果它并不存在,Bot 随便删除一个数即可. 这样 Menji 第二次无论选择什么,两次所选数的异或和都不可能等于 $T$.
这个结论可以对 $q$ 直接归纳. 当 $q\ge6$ 时,Menji 先选择一个数 $z$,Bot 再删除另一个数,剩下仍然有至少 $4$ 个两两不同的数. 此时只需要让 Menji 后续取得的数的异或和不等于 $T\oplus z$. 根据归纳假设,Bot 一定可以做到. 因此只要 $q\ge4$,无论目标 $T$ 是什么,Bot 都必胜.
综上,完整的判定就是:
- 若 $q=0$,Menji 当且仅当 $H=0$ 时获胜.
- 若 $q=2$,设 $O=\{x,y\}$,Menji 当且仅当 $H=x$ 或 $H=y$ 时获胜.
- 若 $q\ge4$,Bot 一定获胜.