2025省选集训Day1 略解

前言

且视他人之疑目如盏盏鬼火，大胆地去走你的夜路。

先做的前天的 DP 套 DP，可能浪费了一个上午在麻将这个题上，感觉今天的题做不完了。

A

略

B

TZL 说很简单，我信了，然后想了 40 多分钟都没搞明白简单在哪里。

然后他又说随便找规律，然后完全不知道怎么找。

简称太菜了。

我们发现，先建完一颗 \(\texttt{01 Trie}\) 树，那么我们每次选择一个点对应的就是这个点的子树和其到根节点路径上所有的点都不能选择了。

发现输入完之后，能选的点会构成若干棵满二叉树。

由于是博弈，考虑从 \(\text{SG}\) 函数入手，求出深度为 \(i\) 的满二叉树的 \(\text{SG}\) 值。

考虑观察一下我们是如何操作的：

• 删掉根节点，那么这棵树直接没了。

• 删掉一个深度为 \(1\) 的节点，剩下一颗深度为 \(i-1\) 的满二叉树。

• 删掉一个深度为 \(2\) 的节点，剩下一颗深度为 \(i-1\) 和一颗 \(i-2\) 的二叉树。

• 以此类推，删掉一个深度为 \(i\) 的节点，剩下深度为 \(i-1,i-2,.....,1\) 的二叉树。

简而言之，\(\text{SG}(i)=\text{mex}_{j=1}^i (\oplus_{k=j}^{i-1} \space \text{SG}(k))\)

然后由于 \(L\) 太大，考虑简单的对每个 \(i\) 的 \(\text{SG}\) 打个表，发现 \(\text{SG}(i)=\text{lowbit}(i)\)（这里指的不是二进制位，\(\text{lowbit}(4)=4\)。）， 然后直接对于输入完后构成的每个满二叉树的 \(\text{SG}\) 异或起来正常博弈论判断就做完了。