Codeforces Round #800 (Div. 2)

C. Directional Increase
题目大意，一开始给你一个长度为 nn 的数组，最开始的元素都只有 00，指针指在第 11 个位置
两种操作任意次
第一种，如果指针不在 nn，可以将当前指针指向的元素 +1+1，然后指针移动到下一个位置
第二种，如果指针不在 11，可以将当前指针指向的元素 −1-1，然后指针移动到前一个位置
给你一个数组 aa，判断 aa 能不能由任意次两种操作其中一种，变换而成
注意变换完成之后，指针必须重新指向 11 这个位置

算法分析
从后往前贪心，将 aa 数组的后缀 00 去掉，得到 bb 数组，令此时 bb 数组长度为 nn

很关键的是，变换完之后指针必须重新指向 11 这个位置，由此出发，我们考虑从 bb 数组能不能逆变换成 <0,0⋯ ,0>\left<0,0\cdots, 0 \right>
突破口不难想到，必须有 bn<0b_n < 0，因为指针要回退到 11 这个位置，所以 bnb_n 只能往前走若干次
bnb_n 初始时候是 00，构造 bnb_n 之后指针回退到位置 11，所以 bnb_n 只会不断减小

下面考虑构造，(bn−1−∣bn∣,0)→(bn−1,0)→(bn−1,−∣bn∣)(b_{n-1}-|b_n|, 0) \to (b_{n-1}, 0) \to (b_{n-1}, -|b_n|)
上面的过程是指针从 n−1n-1 处向右移动 11 个单位，移动 ∣bn∣|b_n| 次，这样指针移动完在 nn 位置
然后再从 nn 位置向左移动，回退 ∣bn∣|b_n| 次，指针又回到 n−1n-1，恰好是一次合法的构造

也就是说，从后往前贪心，如果遇到 bi+1<0b_{i+1} < 0，逆变换 bi=bi−∣bi+1∣b_{i} = b_{i} - |b_{i+1}|，使得 bi+1b_{i+1} 这一位为 00
并且 bib_i 形成新的后缀，并且 bi<0b_i < 0 才能继续做下去

注意到 bi=0b_i = 0 只有当 i=1i = 1 时候成立才可以继续做，因为你指针必须回退到 11
最后当指针回退到 11 的时候判一下 b[1]b[1] 是否为 00 即可

AtCoder Beginner Contest 256

I like Query Problem
题目大意，给你长度为 nn 的序列和 qq 个询问
(1,l,r,x)(1, l, r, x) 表示将 [l,r][l, r] 的数都改成 ⌊aix⌋\displaystyle \left\lfloor \frac{a_i}{x} \right\rfloor
(2,l,r,y)(2, l, r, y) 将 [l,r][l, r] 的数都改成 yy
(3,l,r)(3, l, r) 求 [l,r][l, r] 的和

算法分析
首先对于区间赋值，[l,r]←v[l, r] \leftarrow v 很简单，就是标准的线段树操作

难点是在于 ⌊aid⌋\displaystyle\left\lfloor \frac{a_i}{d} \right\rfloor

对于这种修改，最坏情况可能有 22 种

  • [l,k],[k+1,r][l, k], [k+1, r] 两个区间的值可能不同
  • [l,k][l, k] 可能执行了 22 次，⌊aid2⌋\displaystyle \left\lfloor \frac{a_i}{d^2} \right\rfloor
    [k+1,r][k+1, r] 可能执行了 33 次，⌊aid3⌋\displaystyle \left\lfloor \frac{a_i}{d^3} \right\rfloor

不论哪种情况，对第一种操作而言，都可能存在 [l,r][l, r] 区间值不统一的情况
对于这种情况，可以用 segment tree beats 来实现，具体来说

  • 对于 [l,r][l, r] 执行 ai←ai/xa_i \leftarrow a_i / x 的操作，如果 [l,r][l, r] 中的所有元素都相同，不妨设都是 vv
    此时相当于区间赋值操作，直接给区间打赋值标记 v/xv / x
  • 否则的话，暴力递归所有子节点，直到找到满足所有数都相同的区间，打标记 v/xv / x
    然后回溯的时候，更新路径上的值
  • 至于一个区间是否所有数都相同？可以维护一个最大值 mxmx，一个最小值 mnmn，当 mx=mnmx = mn 时候区间所有数都相同
    另外还需要维护区间的 sum,szsum, sz

segment tree beats 的时间复杂度平均是 O((n+q)log⁡n)O((n+q) \log n)

E - Takahashi’s Anguish
题目大意，给你 1→n1 \to n 的排列，表示小孩的编号，每一个小孩都会讨厌另一个小孩
(i,x(i))(i, x(i)) 表示小孩 ii 讨厌小孩 x(i)x(i)，并且 ii 有怨气值 C(i)C(i)，如果 x(i)x(i) 在 ii 之前先得到糖果
那么就会产生 C(i)C(i) 的怨气值，现在问一个方案使得怨气值最小

思路分析
首先对于 (i,x(i),x(x(i)),⋯ )(i, x(i), x(x(i)), \cdots) 如果张成一条链，那么顺着这条链时间顺序发糖果，不会产生怨气值
但是注意到，可以考虑建一条有向边 (i,x(i))(i, x(i))，对应的图有如下性质
该图是 Functional Graph，即每一个点都只有一个出度，Functional Graph 有如下性质
假设该图 GG 包含 KK 个连通分量 C1,C2,⋯ ,CkC_1, C_2, \cdots, C_k，每一个连通分量有且仅有一个环

证明
如果每一个点的入度也都是 11，那么这个图对应的是置换图，有 (k+1)(k+1) 个节点，并且仅有一个简单环
否则的话，一定可以找到一个点入度为 00，删除这个点，和它的出边，类似拓扑排序，可以不断执行这个过程
直到剩下的图构成一个置换图

根据Functional Graph的性质，就可以想到用并查集维护连通分量和环
具体来说，沿着 (u,x(u))(u, x(u)) 路径走，边走边执行并查集合并，当遇到 (u,x(u))(u, x(u)) 在同一个并查集中的时候
那就说明沿着 (u,x(u))(u, x(u)) 往前走是在一个简单环上绕行，记一下环的起点 s←u,j=x(s)s \leftarrow u, j = x(s)，令 j=x(j)j = x(j) 遍历环
找到 min⁡(C(j))\min(C(j)) 即可

F - Cumulative Cumulative Cumulative Sum
根据题中给出的表达式，不难推出

Cx=xA1+(x−1)A2+⋯1Ax\displaystyle C_x = xA_1 + (x-1)A_2 + \cdots 1A_x
Dx=(1+2+⋯x)A1+(1+2+⋯x−1)A2+⋯+1Ax\displaystyle D_x = (1+2+\cdots x)A_1 + (1+2+\cdots x-1)A_2 + \cdots + 1A_x，令 f(x)=1+2+⋯+xf(x) = 1+2+\cdots + x，那么
Dx=f(x)A1+f(x−1)A2+⋯+f(1)Ax\displaystyle D_x = f(x)A_1 + f(x-1)A_2 + \cdots + f(1)A_x

也就是说，Dx=∑i=1x(x−i+1)(x−i+2)2Ai\displaystyle D_x = \sum_{i = 1}^{x} \frac{(x-i+1)(x-i+2)}{2}A_i

(x+1)(x+2)2∑i=1xAi+12∑i=1xi2Ai−2x+32∑i=1xiAi\displaystyle \frac{(x+1)(x+2)}{2} \sum_{i = 1}^{x} A_i + \frac{1}{2} \sum_{i = 1}^{x} i^2A_i - \frac{2x+3}{2} \sum_{i = 1}^{x}iA_i

要维护三个部分前缀和，并且支持单点修改，用树状数组就可以做到

G - Black and White Stones
题目大意，一个 nn 边形，边长都相等，每一条边的边长为 dd，按边长一个单位一个单位来看
一条边就有 d+1d+1 个点，现在给每一个点染色，可以染成黑白两种颜色，要求染完之后
每条边白色的点数相同，问染色的方案

思路分析
一开始比较难想，先来看一个类似的问题，不相邻的组合数个数，这个问题的解决思想
核心是所有的方案数可以分为两种，包含第一个球和不包含第一个球，从这里出发考虑
本题的方案数也可以分为 22 类，即第一个点染白色或者是黑色

以边作为 dp\text{dp} 的阶段，假设当前考虑第 ii 条边，第一个点的颜色是 cc
c=0c = 0 表示白色，c=1c = 1 表示黑色，我们还需要记一下一条边最后一个点的颜色 jj
因为对于第 nn 条边，必须首尾相接，也就是说 j=cj = c，所以状态函数定义如下
dp(c,i,j)dp(c, i, j) 表示当前考虑第 ii 条边，并且第一个点染色成 cc，最后一个点染色成 jj，此时的方案数

这样我们可以枚举每一条边白色节点的个数 k=0,1,2,⋯ ,d+1k = 0, 1, 2, \cdots, d+1，接下来考虑状态转移方程
对于每一条边，我们 dpdp 状态表示的时候，边的第一个点和最后一个点，用状态维度加以限制
中间的 d−1d-1 个点是没有限制的，不难写出状态转移方程

dp(c,i,0)=dp(c,i−1,0)⋅(d−1k−2)+dp(c,i−1,1)⋅(d−1k−1)\displaystyle dp(c, i, 0) = dp(c, i-1, 0) \cdot \binom{d-1}{k-2} + dp(c, i-1, 1) \cdot \binom{d-1}{k-1}

dp(c,i,1)=dp(c,i−1,0)⋅(d−1k−1)+dp(c,i−1,1)⋅(d−1k)\displaystyle dp(c, i, 1) = dp(c, i-1, 0) \cdot \binom{d-1}{k-1} + dp(c, i-1, 1) \cdot \binom{d-1}{k}

枚举 kk，然后计算 ii，这样的复杂度是 O(n2)O(n^2) 的，这里用矩阵快速幂优化

不妨用 b(k)b(k) 表示 (d−1k)\displaystyle \binom{d-1}{k}，整理状态转移方程，可以得到

(b(k−2)b(k−1)b(k−1)b(k))(dp(c,i−1,0)dp(c,i−1,1))=(dp(c,i,0)dp(c,i,1))\begin{pmatrix} b(k-2) & b(k-1) \\ b(k-1) & b(k) \end{pmatrix} \begin{pmatrix} dp(c, i-1, 0) \\ dp(c, i-1, 1) \end{pmatrix} = \begin{pmatrix} dp(c, i, 0) \\ dp(c, i, 1) \end{pmatrix}

这是可以用矩阵快速幂来做的

(b(k−2)b(k−1)b(k−1)b(k))n(dp(c,0,0)dp(c,0,1))=(dp(c,n,0)dp(c,n,1))\begin{pmatrix} b(k-2) & b(k-1) \\ b(k-1) & b(k) \end{pmatrix}^n \begin{pmatrix} dp(c, 0, 0) \\ dp(c, 0, 1) \end{pmatrix} = \begin{pmatrix} dp(c, n, 0) \\ dp(c, n, 1) \end{pmatrix}

值得注意的是，dp(0,n,1),dp(1,n,0)dp(0, n, 1), dp(1, n, 0) 并不合法，同理，dp(0,0,1)dp(0, 0, 1) 不合法，dp(1,0,0)dp(1, 0, 0) 也不合法

(b(k−2)b(k−1)b(k−1)b(k))n(dp(0,0,0)=10)=(dp(0,n,0)dp(0,n,1)=0)\begin{pmatrix} b(k-2) & b(k-1) \\ b(k-1) & b(k) \end{pmatrix}^n \begin{pmatrix} dp(0, 0, 0) = 1 \\ 0 \end{pmatrix} = \begin{pmatrix} dp(0, n, 0) \\ dp(0, n, 1) = 0 \end{pmatrix}

(b(k−2)b(k−1)b(k−1)b(k))n(0dp(1,0,1)=1)=(dp(1,n,0)=0dp(1,n,1))\begin{pmatrix} b(k-2) & b(k-1) \\ b(k-1) & b(k) \end{pmatrix}^n \begin{pmatrix} 0 \\ dp(1, 0, 1) = 1 \end{pmatrix} = \begin{pmatrix} dp(1, n, 0) = 0 \\ dp(1, n, 1) \end{pmatrix}

综上所述，假设 Bn\bm{B}^n 矩阵快速幂求出来的结果是 A\bm{A}
那么 dp(0,n,0)=A(0,0), dp(1,n,1)=A(1,1)dp(0, n, 0) = \bm{A}(0, 0), \ dp(1, n, 1) = \bm{A}(1, 1)，二者相加就是答案

Codeforces Round 773 (Div. 2)

E. Anonymity Is Important

Codeforces Round #789 (Div. 2)

C. Tokitsukaze and Strange Inequality

D. Tokitsukaze and Meeting

E. Tokitsukaze and Two Colorful Tapes

一些组合问题

不相邻的组合数个数
从 nn 个球中选出 rr 个不相邻的球的方案

  • n<2r−1n < 2r -1 不存在这样的方案，答案是 00
  • n⩾2r−1n \geqslant 2r-1 时候，取法是 (n−r+1r)\displaystyle \binom{n-r+1}{r}
    这怎么来理解呢？
    首先有 rr 个球，中间有 r−1r-1 个空格，这 r−1r-1 个数只能看成是空格而不是球
    于是我们取的球只能从 n−r+1n-r+1 个里面取，任意取 rr 个，然后将之前的空格插入到 r−1r-1 个空位中
    (n−r+1r)\displaystyle \binom{n-r+1}{r} 种方案数

那么 nn 个球围成一圈呢？

  • 注意到一个球周围至少要有 22 个空格，所以 n<2rn < 2r 时无解
  • n⩾2rn \geqslant 2r，对球进行编号，对于所有可能的组合，都只有 22 种情况
    包含 11 号球和不包含 11 号球
    如果包含 11 号球，那么 (n−1,1,2)(n-1, 1, 2) 这 33 个位置不能选，所以只能从 n−3n-3 个球中选
    从 n−3n-3 个球中选出 r−1r-1 个不相邻的球的方案数是 ((n−3)−(r−1)+1r−1)=(n−r−1r−1)\displaystyle \binom{(n-3)-(r-1) + 1}{r-1} = \binom{n-r-1}{r-1}
    如果不包含 11 号球，可以从 n−1n-1 个数中任选 rr 个不相邻的球，方案数是 ((n−1)−r+1r)=(n−rr)\displaystyle \binom{(n-1)-r+1}{r} = \binom{n-r}{r}
  • 综上，(n−r−1r−1)+(n−rr)\displaystyle \binom{n-r-1}{r-1} + \binom{n-r}{r}