一场难度略高于普及组的 $Div.2$ .
CF1151C Problem for Nazar
二分.
转化成求前缀和 $sum(r)-sum(l-1)$ .算每个前缀和的时候二分出整的前 $2^k$ 个数,剩下的单独算就好了.
CF1151D Stas and the Queue at the Buffet
贪心.
考虑当前的两个位置 $i,j\ (i<j)$ , 有 $x,y$ 两个元素,若交换这两个元素,对答案的影响.
化简出来发现只需要将所有元素按 $a_i-b_i$ 从大到小排序就好了.
这种判定贪心的可行性及怎样贪心的方法很常见,就是考虑交换两个元素对答案的影响.
CF1151E Number of Components
构造.
考虑若当前计算的权值区间是 $(l,r)$ ,那么把在这个范围内的点权值赋为 $1$ ,否则赋为 $0$.
- 再在位置 $0$ 处补上一个权值 $0$ ,可以发现此时对于这对 $(l,r)$ 的答案就是相邻的 $(0,1)$ 对数.
- 那么我们直接来算每两个相邻位置的贡献,即 $a_i,a_{i+1}$ 在多少组 $(l,r)$ 中被赋的权值不同就好了.
CF1153F Sonya and Informatics
概率+矩阵快速幂.
设 $f(i,j)$ 表示操作了 $j$ 次,当前最后一个 $1$ 在位置 $i$ 的概率.
每次 $j\rightarrow j+1$ 转移的时候分类讨论一下选了哪两个位置,写出转移矩阵,转移 $k$ 次,矩阵快速幂加速即可.
时间复杂度 $O(n^3logk)$ .