master_rat1 edited 3 年,3 月前
本次 EOJ 月赛由华东师范大学 ACM 团队与华东师大二附中信息学竞赛组联合举办。
感谢华东师范大学肖春芸老师、华东师范大学第二附属中学金靖老师周密的组织策划,使得 EOJ 月赛能够圆满完成。此外,感谢 EOJ 运维团队为月赛提供了重要的技术支持。
也感谢各位出题人对月赛作出的贡献,感谢所有选手的参与!祝大家假期愉快!
令 $X=A_1~|~A_2~|\cdots|~A_N$,$Y=B_1~\&~B_2~\&\cdots\&~B_M$,下面证明 $X\subseteq Y$(即只要 $X$ 的某个二进制位是 $1$,则 $Y$ 的该二进制位也为 $1$)是 $(A,B)$ 合法的充要条件。
先证明必要性,假设存在一个二进制位使得 $X$ 是 $1$ 而 $Y$ 是 $0$,则 $\exists 1\le j\le M$ 使 $B_j$ 的该二进制位为 $0$,所以 $\forall ~1\le i\le N$ 都有 $a_{i,j}$ 的该二进制位为 $0$,因此 $\forall~1\le i\le N,A_i$ 的该二进制位都为 $0$,$X$ 的该二进制位不可能为 $1$,矛盾。
再证明充分性, 可以通过如下方法构造出一个符合条件的表格:
由于 $\forall 1\le i\le N,1\le j\le M$ 有 $A_i\subseteq X\subseteq Y\subseteq B_j$,所以该表格合法。
可以枚举 $X$,设其中有 $c$ 个二进制位为 $1$,则 $A$ 的个数为 $(2^N-1)^c$,容易用数位dp计算 $B$ 的个数。时间复杂度为 $O(K\log N)$。
credit: ix35
暴力枚举 $2^h-1$ 个非叶结点的开关状态,再暴力计算每个点的球数。
时间复杂度为 $O(2^h\times nh)$,期望得分 $10$ 分。
我们将最后构造出的树上每个点开关状况记为 $S$,而初始时所有点的开关都朝左的状况为 $T$。
我们首先证明一个引理:
引理 $1$:对于任何初始状况对应的 $S$,存在唯一的叶结点重标号方案,使得它等价于 $T$。
证明:考虑从根结点出发,每遇到一个开关朝右的点,就将其左右子树的叶子编号对应交换,最后得到了 $T$。
在证明中可以发现,$S$ 中的一个子树总是和 $T$ 中的一个子树一一对应。
于是我们可以设计 DP,令 $dp(i,j)$ 表示将 $S$ 中以 $i$ 为根的子树对应 $T$ 中以 $j$ 为根的子树时,这个子树内所有关键点的球数之和的最大值,这里要求 $i,j$ 深度相同。
转移是简单的:$dp(i,j)=\max(dp(l_i,l_j)+dp(r_i,r_j),dp(l_i,r_j)+dp(r_i,l_j))$。
边界即叶结点,我们对每个 $T$ 中的叶结点先计算出 $w_i$ 表示它最终的球数,那么当 $j$ 是叶子时 $dp(i,j)=w_j$。
时间复杂度为 $O(2^{2h})$,期望得分 $30$ 分。
我们考虑再证明一个引理:
引理 $2$:在连续投出 $2^h$ 个球后,每个叶子恰有一个球。
在证明这个引理的同时,我们将归纳给出在 $T$ 中最初 $2^h$ 个球流向何方。
令 $A_{h,j}$ 是高度为 $h$ 的树 $T$ 中第 $j$ 个球落到的叶子,下面我们递归证明:$A_h$ 是由 $A_{h-1}$ 和 $A_{h-1}+2^{h-1}$(这表示其中每个元素都加上 $2^{h-1}$) 交替连接得到的,形式化地,有:
$$
A_{h,2j-1}=A_{h-1,j},\ \ \ \ A_{h,2j}=A_{h-1,j}+2^{h-1}
$$
这一点只通过模拟根结点的开关变化即可发现,可以发现第奇数次球会到左边子树,而第偶数次球会到右边子树,这已经证明了上面的引理。
由此可以得到简单推论:
引理 $2$ 推论:在连续投出 $2^h$ 个球后,所有点的开关状态与最初相同。
证明:由于每个叶子都恰好有一个球,所以每个点被经过了其子树内叶子结点个数这么多次,这是一个偶数,所以开关状态和最初相同。
这告诉我们:每 $2^h$ 个球为一组,叶结点求出分布呈现周期性。
由引理 $2$,我们可以简单地知道 $m=1$ 时的答案:令唯一的关键点对应 $T$ 中的点 $1$,那么一定是每一周期中第一个有球经过的点,所以答案就是 $\lceil \dfrac{n}{2^q}\rceil$。
时间复杂度为 $O(1)$,期望得分 $10$ 分,结合 $\text{Algorithm 2}$ 可获得 $40$ 分。
尝试优化 $\text{Algorithm 2}$ 中的 DP,我们需要进一步观察 $T$ 和 $A_h$ 序列的性质。
我们称两个 $T$ 中子树是 $i\text{-}$本质不同的,当且仅当在扔下 $i$ 个球后两个子树中所有球数非零的叶结点不同构(即不能通过重标号使得两个子树中球数非零的叶结点完全重合)。
引理 $3$:对于任意 $i\leq 2^h$ 和任意深度 $h_0$,深度为 $h_0$ 的子树中 $i\text{-}$本质不同的至多有两种。
证明:(深度是到根结点的边数)考虑之前所述 $A_h$ 序列的生成过程,不难发现:考虑所有深度为 $h_0$ 的子树,可以将它们视作整体,将整个扔球操作看成 $2^{h-h_0}$ 个周期,每个周期内 $2^{h_0}$ 个球被扔到每个子树中各一个,而且每个子树内同一周期内球进到的叶子的相对位置是相同的,所以在一个周期进行到第 $x$ 个球时,只会有前 $x$ 个子树和后 $2^{h_0}-x$ 个子树这两种本质不同的子树。
于是原本状态 $dp(i,j)$ 中的第二维 $j$ 只有两种不同情况了,我们只需用 $dp(i,0)$ 和 $dp(i,1)$ 来代替。
转移时,我们需要知道两种深度为 $i$ 的本质不同子树的两个儿子各是哪一种深度为 $i+1$ 的子树,我们可以令 $S(i,0),S(i,1)$ 分别表示大小为 $i$ 的两种本质不同子树的球数非零的叶结点数量,容易发现 $|S(i,0)-S(i,1)|\leq 1$,我们只需要根据这个大小就可以判断是由哪两个子树相加得到的了。
时间复杂度为 $O(2^h)$,期望得分 $40$ 分,结合 $\text{Algorithm 3}$ 可获得 $50$ 分。
当 $h$ 较大时,我们发现只要取所有关键点的祖先结点进行 DP 即可,其余点的 DP 值一定是 $0$。
如果不显式建树,那么需要查询一个点子树内是否有关键点,稍微麻烦点,我们可以选择仿照 Trie 的方式建树,直接得到有效的二叉树结构。
credit: ix35
暴力枚举所有可能的串询问,询问次数约为 $3^R$。
首先确定 $a$ 的个数,只要二分即可。
然后确定 $b$,在任意相邻两个 $a$ 之间二分即可。
然后确定 $c$,在任意相邻两个 $a,b$ 之间二分即可。
询问次数约为 $2n\log R$。
发现上面的二分还不如直接枚举 $a,b,c$ 的个数并检验。
例如确定 $b$ 时,只需要在从小到大枚举相邻两个 $a$ 中有几个 $b$。
询问次数约为 $3n$。
虽然询问 $b,c$ 时枚举比较好,但是询问 $a$ 时还是二分更优。
询问次数约为 $2n+\log R$。
首先确定 $a,b,c$ 的数量,分别设为 $x,y,z$。
不妨设 $x\leq y\leq z$,然后套用上一个做法即可。
来分析一下询问次数:
由于 $x\leq y\leq z$,所以 $x+y\leq \dfrac{2}{3}n$,所以总询问次数约为 $\dfrac{5}{3}n+3\log R$。
时间复杂度为 $O(mh)$,期望得分 $100$ 分。
credit: ix35
$S$ 的后缀自动机上的结点和其反串 $S’$ 的后缀树的结点是对应的,下面考虑计算一个串 $S$ 的后缀树的期望结点数量。
利用字符集大小为 $2$ 的特殊性,我们可知后缀树是一棵二叉树,且可以将结点分成三类(这里不算终止符对应的结点):
将这三类结点的数量分别设为 $a,b,c$,所求即 $a+b+c$ 的期望。
如果只考虑 A,C 两类结点,根据二叉树的性质易知 $a+c=2a-1$,所以 $a+b+c=2a+b-1$,只需要分别求 $a,b$ 的期望即可,下面以求 $a$ 的期望为例。
枚举以 $i$ 开头的后缀 $Suf(i)$,计算它在全串中仅出现一次的概率 $P(i)$,则 $E(a)=\sum\limits_{i=1}^n P(i)$。
考虑容斥,枚举 $[i-1]={1,2,\ldots,i-1}$ 的子集 $A$,钦定 $Suf(i)$ 是所有 $Suf(j)\ (j\in A)$ 的前缀,设此概率为 $Pr(A)$,则:
$$
P(i)=\sum \limits_{A\subseteq [i-1]} (-1)^{|A|}\times Pr(A)
$$
下面考虑用两种方法计算上式:
暴力枚举 $A$,然后可以建出一张表示某些位置上字符相等的图,数一下连通块,再结合给定的字符就可以方便地得到 $Pr(A)$。
复杂度为 $O(n^2\times 2^{i})$。
令 $len=n-i+1$。
枚举 $Suf(i)$,然后对 $A$ 的容斥系数进行 DP,令 $f(x)$ 表示考虑了 $Suf(1),\ldots,Suf(x)$,且 $Suf(x)$ 以 $Suf(i)$ 为前缀时,$x$ 之前的这些后缀在 $A$ 中部分的贡献,考虑转移 $dp(x)\times w(x,y)\to dp(y)$,则:
先对枚举的 $Suf(i)$ 进行一下 KMP 求出所有 Border,然后 $O(n^2)$ DP。
复杂度为 $O(n^2\times 2^{n-i})$。
结合以上两个算法,当 $i\leq \dfrac{n}{2}$ 时采用法一,当 $i>\dfrac{n}{2}$ 时采用法二,总复杂度 $O(n^2\times 2^{\frac{n}{2}})$。
这是计算 $E(a)$ 的,而 $E(b)$ 基本是一样的,只是在 $Suf(i)$ 后加上一个 $0$ 和加上一个 $1$ 后执行上面算法得到的结果(分别记作 $P_0(i)$ 和 $P_1(i)$),则:
$$
Ans=2E(a)+E(b)-1=\sum\limits_{i=1}^n \Big(2P(i)+(P_0(i)-P(i)+P_1(i)-P(i))\Big)-1=\sum\limits_{i=1}^n \Big(P_0(i)+P_1(i)\Big)-1
$$
所以实际上只要算 $P_0,P_1$ 就可以了,砍掉了 $\dfrac{1}{3}$ 的常数。
此外注意一下根结点只有一个儿子的情况(本质上是空后缀作为 B 类结点,此时 $S$ 为全 $0$ 或全 $1$ 串),要么枚举 $i$ 的时候算上空后缀,要么根据 $S$ 是否可能全 $0$ 和全 $1$ 特殊处理一下。
时间复杂度 $O(n^2\times 2^{\frac{n}{2}})$,可以通过本题。