有一棵\(n\)个点的树，\(m\)个叶子，编号为\(1～m\)。两人在树上博弈，均从根出发，轮流行动，每次走向一个当前所在节点的子节点，如果在叶子就不移动。最终如果两人所在叶子编号一个是另一个\(+1\)（\(\bmodm\)意义下），则\(+1\)的一方获胜。\(m 首先后手是一定不败的，因为后手可以始终跟着先手，最终达到相同的叶子节点。 那么现在考虑什么样的情况下后手必胜。记\(S_x\)代表\(x\)子树内叶子节点的集合，\(T_x\)代表\(x\)子树内叶子节点\(+1\)的集合。假设先手在\(x\)，后手在\(y\)，且\(dep[x]=dep[y]\)，其中\(dep[x]\)代表\(x\)的深度。 如果\(T_x\nsubseteqS_y\)，则先手一定可以一直向不存在于\(S_y\)中的叶子节点移动，因为\(y\)也只能往下移动到\(y'\)，并且\(S_y'\subseteqS_y\)，所以后手永远无法移动到获胜的叶子节点处。 所以后手的移动要始终保证\(T_x\subseteqS_y\)，也就是说，当先手从\(x\)移动到其儿子时，对于\(x\)的每个儿子\(x'\)一定存在唯一的\(y\)的儿子\(y'\)，使得\(T_{x'}\subseteqS_{y'}\)。根据该性质，定义\(dfs(x,y,fx,fy)\)代表先手在\(x\)，后手在\(y\)，且\(x\)的父亲为\(fx\)，\(y\)的父亲为\(fy\)时，后手是否必胜。枚举所有合法的\(x'\)和\(y'\)递归解决即可。因为如果后手必胜，每个\(x'\)一定存在唯一的\(y\)的儿子\(y'\)，所以只有\(O(m)\)种结果，所以复杂度为\(O(m\logn)\)，其中的\(\logn\)是通过map来确定与\(x'\)对应的\(y'\)。注意当某个人已经到叶子节点的时候，直接退出即可。至于为什么\(x'\)一定存在唯一的\(y\)的儿子\(y'\)，下面的方法可以回答。 不妨考虑在\([1,n]\)中选择两种颜色，若选择的两种颜色的出现次数分别为\(x,y\)，存在以下\(2\)种情况： 若\(\text{highbit}(x)=\text{highbit}(y)\)，其中\(\text{highbit}(x)\)代表\(x\)在二进制下最高的\(1\)所在位，记\(t=\text{highbit}(x)\)。 不难证明，在区间\([1,n]\)不断缩减的过程中（要么\(x\)减少\(1\)，要么\(y\)减少\(1\)），一定存在某个时刻，使得在当前区间中某一个颜色的出现次数的\(\text{highbit}\)仍为\(t\)，而另一个颜色的出现次数恰好为\(2^t-1\)。此时两种颜色的出现次数的二进制或最大，等于\(2^{t+1}-1\)。 贪心的，只需要选择\([1,n]\)中出现次数最多、次多的两种颜色即可。 若\(\text{highbit}(x)\neq\text{highbit}(y)\)，记\(t=\text{highbit}(x\\&\y)\)。 不难证明，在区间\([1,n]\)不断缩减的过程中（要么\(x\)减少\(1\)，要么\(y\)减少\(1\)），一定存在某个时刻，使得在当前区间中某一个颜色的出现次数仍\(\geq2^t\)，而另一个颜色的出现次数恰好为\(2^t-1\)，并且\(x,y\)高于\(t\)位的二进制不会改变。此时两种颜色的出现次数的二进制或最大，等于\(x\midy\mid2^{\text{highbit}(x\\&\y)}-1\)。 综上，假设\([1,n]\)中出现次数最多、次多的颜色出现次数分别为\(x,y\)，则答案一定为\(x\midy\mid2^{\text{highbit}(x\\&\y)}-1\)，注意特判\(\text{highbit}(x\\&\y)=0\)的情况。 #include 双方只从序列开头拿数字，假设序列\(a,b\)首元素分别为\(x,y\)，则： 重复该过程，直到存在一方序列为空。 如果双方序列最终都为空，则平局，否则仍有剩余元素的一方获胜。 存在\(q\)次询问，每次单点修改后，询问最后结果是否平局。 \(|a|,|b|,q\leq10^5,a_i,b_i\leq10^5\)。 显然我们只关心最大值，并且如果平局，则两个序列最大值必须相同，记\(a\)中最大值第一次出现位置为\(x\)，\(b\)中为\(y\)，则\(a[1,x]\)和\(b[1,y]\)最后一定会平局，我们不必关心淘汰的过程，因为\(a_x\)和\(b_y\)都是最大值且相同，所以结果是固定的。然后我们继续找\(a[x+1,|a|]\)和\(b[y+1,|b|]\)中的最大值，判断是否相同，然后重复该过程即可判断\(a[1,|a|]\)和\(b[1,|b|]\)是否平局。 不难发现，我们寻找的位置一定是后缀最大值的位置，即令\(sufMax[i]\)代表序列\(a[i,n]\)中的最大值，则我们关心的位置一定是\(a_i=sufMax_i\)的位置。 并且最终平局的话，\(a_{|a|},b_{|b|}\)一定是必选的，观察后发现选择的位置一定是以序列末尾为起点的单调不减的子序列，记作\(T\)。例如\(\{2,3,5,4,1,2,1\}\)，则选择的位置构成的子序列为\(\{5,4,2,1\}\)，从右往左看单调不减。那么若最终平局，当且仅当\(T_a=T_b\)成立。 因为存在单点修改，我们只需要通过线段树分别维护子序列\(T_a,T_b\)的异或哈希即可，具体的： 以序列\(a\)为例，假设线段树上节点\(i\)所代表区间为\(a[l,r]\)，则该节点维护的信息为以\(a[r]\)为起点的\(a[l,r]\)中单调不减的子序列的哈希值，即\(T_{a[l,r]}\)所代表的哈希值，记作\(shs[i]\)；同时维护区间最大值\(mx\)。 考虑左右儿子如何合并，即如何合并\(T_{a[l,mid]}\)和\(T_{a[mid+1,r]}\)成\(T_{a[l,r]}\)，定义\(ls\)代表节点\(i\)的左儿子，\(rs\)代表节点\(i\)的右儿子，则有： 如果\(mx[ls] 如果\(mx[ls]\geqmx[rs]\)，则\(T_{a[l,r]}\)中仍有部分元素在\(T_{a[l,r]}\)中，需要找到\(a[l,mid]\)中从右数起第一个\(\geqmx[rs]\)的位置\(x\)，则\(T_{a[l,r]}=T_{a[l,x]}+T_{a[mid+1,r]}\)，即\(shs[i]=\text{qry}(l,mid,mx[rs])+shs[rs],mx[i]=mx[ls]\)。 其中\(\text{qry}(l,r,k)\)代表\(T_{a[l,x]}\)的哈希值，其中\(x\)为\(a[l,r]\)中从右数起第一个\(\geqk\)的位置，具体的实现类似P4198楼房重建通过线段树上二分实现： 由于合并的复杂度为\(O(\logn)\)，则总复杂度为\(O(n\log^2n)\)。 根据期望的线性性，定义\(T_i\)代表第\(i\)次操作新增的叶子节点的集合，\(T\)代表操作完\(K\)次后的节点集合，即\(T=\{1\}+T_1+T_2+\dots+T_K\)，则有： 定义\(ans(i)\)代表第\(i\)次操作新增的叶子节点的深度和的期望，即\(ans(i)=E(\sum_{v\inT_i}dep(v))\)。 定义\(cnt(i)\)代表第\(i\)次操作后叶子节点个数，则有\(cnt(i)=(M-1)\timesi+1\)，\(cnt(0)=1\). 定义\(f(i)\)代表第\(i\)次操作后叶子节点的深度和的期望，即\(f(i)=\sum_{j=1}^{cnt_i}E(dep(v_j))\)，其中\(v_j\)是第\(i\)次操作后的叶子节点，显然\(f(0)=0\)。 \(ans(i)\)可以根据第\(i-1\)次操作之后的叶子节点的深度得到，即： \(f(i)\)等于\(f(i-1)\)加上新增的\(ans(i)\)，然后再减去减少的叶子节点的深度的期望和，即： \(O(K+\logV)\)预处理所有\(cnt(i)\)的逆元即可。 简单的来说令\(prod[i]=\prod_{j=1}^icnt(j),iprod[i]=(\prod_{j=1}^icnt(j))^{-1}\)。 先\(O(K)\)得到\(prod\)后，通过快速幂得到\(iprod[K]\)后，根据\(iprod[i]=iprod[i+1]\timescnt(i+1)\)，可以\(O(K)\)递推出\(iprod\)。所以\((cnt(i))^{-1}=prod[i-1]\timesiprod[i]\)。 不难发现\(M\)与复杂度没有关系，本质上\(M\leq100\)用来保证\(cnt(i)\)在模\(10^9+9\)意义下存在逆元。
2023CCPC深圳Zeoykkk
2024-11-27 22:46:00
THE END