CF Round 1053(2150 & 2151) 总结
Div2 A
若存在 \(a_i\ge a_i+1\) 那么只出现一次,否则出现 \(n-a_m+1\) 次。
A
我们不能每次从头开始走,考虑怎么利用上一轮的信息。
假设我们要求第 \(k\) 轮的终点,由于第 \(k-1\) 轮的终点可能被覆盖了,所以考虑从第 \(k-1\) 轮的 \(k-2\) 步的位置往后走两步。所以记录上一步的位置即可。
找白点用一个 set
初始把所有白点放进去即可。
Div2 C
当 \(k=1\) 时,每个间隔的系数为 1 0 1 0 1 0 1 0 1
。
当 \(k=2\) 时,每个间隔的系数为 1 2 1 2 1 2 1 2 1
。
当 \(k=3\) 时,每个间隔的系数为 1 2 3 2 3 2 3 2 1
。
当 \(k=4\) 时,每个间隔的系数为 1 2 3 4 3 4 3 2 1
。
当 \(k=5\) 时,每个间隔的系数为 1 2 3 4 5 4 3 2 1
。
可以看出只需分别维护奇数位和偶数位的前缀和即可。
B
首先左上角、右上角一定为黑色。于是可知第一列只有第一行为黑,那么第二列前两行有且只有一个黑,同时可知第二列有且只有前两行存在黑。同理对于 \(i\le \lceil \frac n 2\rceil\) 的第 \(i\) 列,前 \(i\) 行有且只有一个黑,有且只有前 \(i\) 行存在黑。对于右半边的列同理。
那么每一列可以对一个前缀的行产生贡献。于是倒着枚举行,累加 \(res\) 为当前还有几个列没有被匹配,答案每次乘上 \(\binom {res}{a_i}\) 即可。
C
假设 \(t_i=1/0\) 表示 Alice 是否选择物品 \(a_i\)。记物品 \(i\) 在 \(b\) 中的位置为 \(p_i\),那么 \(t\) 数组合法的条件为,对于任意 \(i<j\) 满足 \(t_i=0,t_j=1\) 的 \(i,j\),有 \(p_{a_j}<p_{a_i}\)。不然 Bob 选 \(a_i\) 的时候就会先把 \(a_j\) 选了,Alice 就不可能选到了。
于是维护 DP,设 \(f_{i,j}\) 表示考虑完 Alice 的前 \(i\) 个物品,且 Bob 选择的物品的最大位置为 \(j\)。用线段树转移是容易的,复杂度 \(O(n\log n)\)。
D
记 \(f_i\) 为最终 \(i\) 位置上的人数,那么 \(f_i\) 一定形成恰好一个非 \(0\) 连续段 \([l,r]\),且 \(\forall l<j<r\) 有 \(f_j\) 为奇数。
把 \(f_l,f_r\) 也变成和中间部分类似的约束条件,枚举 \(x,y\in \{1,2\}\),令 \(f_l=x+2g_l,f_r=y+2g_r,f_j=1+2g_j(l<j<r)\)。
若 \(r-l+1=K\),则合法的条件为 \(S=n-x-y-(K-2)\) 为偶数,且 \(\sum g=S/2\)。由于上述分配方式是对称的,所以任意 \(2g_i\) 的期望值都为 \(\frac SK\)。所以对答案的贡献为 \(\sum a_i\times \frac SK\times ways\),其中 \(ways\) 为分配的方案数,可以用插板法简单地得到。
对于一个 \(K\),有多个 \([l,r]\),它们 \(a\) 的和的总和可以由前缀和的前缀和计算。答案记得加上基础的 \(1,x,y\) 的贡献以及 \(l=r\) 时的贡献。
E1 & E2
考虑一种分治算法,首先将 \(a\) 随机打乱,维护一个只在当前区间 \([l,r]\) 出现的数集合 \(S\),对每个数用最多两次询问把它删掉或放进一个子区间,询问次数 \(O(n\log n)\)。
考虑再维护一个区间内与区间外都出现的数集合 \(T\),即已知这些数在区间内出现恰好一次,那么所求数在当前区间内的充要为 \(2|S|+|T|\ne r-l+1\)。这样可以通过 E1。
考虑另一种确定一个数是否是所求数的方法,可以二分,记期望询问次数为 \(X\),那么有 \(\frac 12\) 的概率在 \([l,mid],[mid+1,r]\) 都出现过,询问两次;有 \(\frac 14\) 的概率递归右边,询问一次;有 \(\frac 14\) 的概率递归左边,询问两次。则 \(X=\frac 22+\frac 14(1+X)+\frac 14(2+X)\),解得 \(X=\frac 72\)。
这个二分法不能直接用,考虑结合前面的算法,第一层采用前面的算法,然后就能确定所求数可能是哪些并且在哪一边。可以通过 E2。
F
首先找出一棵生成树,第一步操作可以把树上所有距离为 2 的点对连起来。
考虑第二步操作,我们找到树上直径,若其长为 \(len\),那么令 \(K-1=\lceil \frac {len}2\rceil\)。此时对于树上距离大于 \(len\) 的点对,每次可以把两条边换成一条长为 2 的边,使得步数减一,直到为 \(len\)。
而对于树上距离小于 \(len\) 的点对,可以考虑从 \(\text {lca}(x,y)\) 处往父亲方向补充需要的点,假设 \(\text{lca(x,y)}\) 的 \(x\) 方向儿子为 \(z\),\(\text{lca}(x,y)\) 的父亲依次是 \(a_1,a_2,a_3,a_4,a_5\),那么我们可以连出 \(z\to a_1\to a_3\to a_5\to a_4\to a_2\to \text{lca(x,y)}\),对于偶数长度有一点小变化。但这要求 \(\text{lca(x,y)}\) 往上的父亲要足够多,考虑依次把两个直径端点作为根跑这个过程,那么至少有一个是能满足的。
复杂度 \(O(n^3)\)。