T1 挤压
概率期望,二进制拆位
看到异或想到拆位算贡献
\[\begin{aligned} ans&=\sum_xx^2P(x)\\ &=\sum_x(b_1+b_2+...+b_{30})^2P(x)\ \ \ (b_i表示\ x\ 二进制下\ i\ 位的值)\\ &=\sum_x(b_1b_1+b_1b_2+. . .b_{30}b_{29}+b_{30}b_{30})P(x)\\ &=\sum_i^{30}\sum_j^{30}b_ib_j\sum_{b_i\in x\ and\ b_j\in x}P(x) \end{aligned}\]后面一部分直接简单 \(DP\) 计算即可
时间复杂度瓶颈在 \(DP\) ,为 \(O(nlog^2n)\)
T2 工地难题
计数题,排列组合,容斥
发现最大恰好这一限制不好满足,考虑对答案做个前缀和,即计算最大不超过这一限制。
问题转移到计算最大不超过的方案
考虑到 \(0\) 的个数是固定的为 \(n-m\) 个,它把 \(1\) 分成了 \(n-m+1\) 个连续段(可能长度为 \(0\) )。
记限制最大不超过的值为 \(k\) ,\(1\) 的个数为 \(n\),连续段的个数为 \(m\)。
当抛弃限制 \(k\) 的时候答案显然为 \(\dbinom{n+m-1}{m-1}\)
思考怎么处理限制 \(k\),发现抛弃限制 \(k\) 时算出的答案就是连续段的长度超过 \(k\) 至少有 \(0\) 个的个数,即等于 \(\sum_{i=0} cnt_{连续段长度超过\ k\ 恰好为 i 的个数}\) 如果能算出连续段的长度超过 \(k\) 至少有 \(1\) 个的个数,直接作差就算完了,但发现这个东西同样不好求。
我们可以钦定出多少个大于 \(k\) 的个数 \(i\),即从总数 \(n\) 中取出 \(i(k+1)\) 个来,再从剩下的 \(n-i(k+1)\) 个中做抛弃限制 \(k\) 的计算,再在其基础上塞入这 \(i\) 个长为 \((k+1)\) 的连续段即乘上 \(\dbinom{m}{i}\),但是这样计算会算重,举个例子在计算长度超过 \(k\) 至少有 \(1\) 个的个数时它会将 \(cnt_{连续段长度超过\ k\ 恰好为 2 的个数}\) 多算一遍,即会在这两个连续段中都插入一次。
考虑容斥去重,下表中至少的个数是以上述方案计算的,其中第 \(i\) 行 \(j\) 列是以至少有 \(0\) 个中恰有 \(i\) 个超过的个数为单位 \(1\) 所算的系数。
恰有 \(i\) 个超过\ 至少有 \(i\) 个超过 | \(0\) | \(1\) | \(2\) | \(3\) | \(4\) | ... |
---|---|---|---|---|---|---|
\(1\) | \(\binom{1}{0}\) | \(\binom{1}{1}\) | \(0\) | \(0\) | \(0\) | |
\(2\) | \(\binom{2}{0}\) | \(\binom{2}{1}\) | \(\binom{2}{2}\) | \(0\) | \(0\) | |
\(3\) | \(\binom{3}{0}\) | \(\binom{3}{1}\) | \(\binom{3}{2}\) | \(\binom{3}{3}\) | \(0\) | |
\(4\) | \(\binom{4}{0}\) | \(\binom{4}{1}\) | \(\binom{4}{2}\) | \(\binom{4}{3}\) | \(\binom{4}{4}\) | |
... |
目的是为了清除上表中所有的个数,由 \(\sum_{i=0}^{n}(-1)^i\dbinom{n}{i}=0\) 注意到上表每行满足这样一个式子,直接做即可。
时间复杂度分析,对于给定 \(k\) ,最多能有 \(\dfrac{n}{k}\) 个连续段的长度超过 \(k\),所以时间复杂度是调和级数为 \(O(nlogn)\)。
T3 星空遗迹
特殊性质,栈,线段树
性质1:对于连续一段操作其实本质有用的只有一个
性质2:若一段操作两边的操作都能赢它,则可将这一段变为两边的操作
证明可以考虑操作 \(f\) 本质上是获胜者蔓延的过程
考虑询问,可以用一个单调栈去维护这样的性质,即从栈顶的第 \(i+1\) 个操作赢第 \(i\) 个操作,每次对于一个新的操作入栈时,如果相同则 \(pop\) 栈顶将自己放入,如果赢了栈顶则 \(pop\) 两次栈顶将自己放入,如果输给了栈顶则直接放入。这样是满足以上的性质,则最后的答案就是栈底元素,这样就得到了查询 \(O(n)\) 的做法。
发现不用真的去维护这样一个栈,只需要记录栈的 \(size\) 即可,记 \(f\) 为栈的 \(size\) 则得到式子
\[f_{i+1}= \begin{cases} f_i+1&win(s_i,s_{i+1})=s_i\\ f_i&s_i=s_{i+1}\\ max(f_i-1,1)&win(s_i,s_{i+1})=s_{i+1} \end{cases} \]答案即为最后一个 \(f=1\) 时的栈中的元素,但情况 \(3\) 中对 \(1\) 取 \(\max\) 并不好维护,发现不对 \(1\) 取 \(\max\) 直接减到负的答案是最后一个 \(f\) 最小时的操作,但其实任意一个最小都是相同的,证明考虑 \(f\) 本质上是一个前缀和的形式
简单转化,用线段树维护即可
时间复杂度 \(O(nlogn)\)
T4 纽带
析合树
不会