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 只会不断减小

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

也就是说,从后往前贪心,如果遇到 bi+1<0b_{i+1} < 0逆变换 bi=bibi+1b_{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] 执行 aiai/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)logn)O((n+q) \log n)

E - Takahashi’s Anguish
题目大意,给你 1n1 \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)) 往前走是在一个简单环上绕行,记一下环的起点 su,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+(x1)A2+1Ax\displaystyle C_x = xA_1 + (x-1)A_2 + \cdots 1A_x
Dx=(1+2+x)A1+(1+2+x1)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(x1)A2++f(1)Ax\displaystyle D_x = f(x)A_1 + f(x-1)A_2 + \cdots + f(1)A_x

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

(x+1)(x+2)2i=1xAi+12i=1xi2Ai2x+32i=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 状态表示的时候,边的第一个点和最后一个点,用状态维度加以限制
中间的 d1d-1 个点是没有限制的,不难写出状态转移方程

dp(c,i,0)=dp(c,i1,0)(d1k2)+dp(c,i1,1)(d1k1)\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,i1,0)(d1k1)+dp(c,i1,1)(d1k)\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) 表示 (d1k)\displaystyle \binom{d-1}{k},整理状态转移方程,可以得到

(b(k2)b(k1)b(k1)b(k))(dp(c,i1,0)dp(c,i1,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(k2)b(k1)b(k1)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(k2)b(k1)b(k1)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(k2)b(k1)b(k1)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<2r1n < 2r -1 不存在这样的方案,答案是 00
  • n2r1n \geqslant 2r-1 时候,取法是 (nr+1r)\displaystyle \binom{n-r+1}{r}
    这怎么来理解呢?
    首先有 rr 个球,中间有 r1r-1空格,这 r1r-1 个数只能看成是空格而不是球
    于是我们取的球只能从 nr+1n-r+1 个里面取,任意取 rr 个,然后将之前的空格插入到 r1r-1 个空位中
    (nr+1r)\displaystyle \binom{n-r+1}{r} 种方案数

那么 nn 个球围成一圈呢?

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