Codeforces Round #800 (Div. 2)
C. Directional Increase
题目大意,一开始给你一个长度为 n 的数组,最开始的元素都只有 0,指针指在第 1 个位置
两种操作任意次
第一种,如果指针不在 n,可以将当前指针指向的元素 +1,然后指针移动到下一个位置
第二种,如果指针不在 1,可以将当前指针指向的元素 −1,然后指针移动到前一个位置
给你一个数组 a,判断 a 能不能由任意次两种操作其中一种,变换而成
注意变换完成之后,指针必须重新指向 1 这个位置
算法分析
从后往前贪心,将 a 数组的后缀 0 去掉,得到 b 数组,令此时 b 数组长度为 n
很关键的是,变换完之后指针必须重新指向 1 这个位置,由此出发,我们考虑从 b 数组能不能逆变换成 ⟨0,0⋯,0⟩
突破口不难想到,必须有 bn<0,因为指针要回退到 1 这个位置,所以 bn 只能往前走若干次
bn 初始时候是 0,构造 bn 之后指针回退到位置 1,所以 bn 只会不断减小
下面考虑构造,(bn−1−∣bn∣,0)→(bn−1,0)→(bn−1,−∣bn∣)
上面的过程是指针从 n−1 处向右移动 1 个单位,移动 ∣bn∣ 次,这样指针移动完在 n 位置
然后再从 n 位置向左移动,回退 ∣bn∣ 次,指针又回到 n−1,恰好是一次合法的构造
也就是说,从后往前贪心,如果遇到 bi+1<0,逆变换 bi=bi−∣bi+1∣,使得 bi+1 这一位为 0
并且 bi 形成新的后缀,并且 bi<0 才能继续做下去
注意到 bi=0 只有当 i=1 时候成立才可以继续做,因为你指针必须回退到 1
最后当指针回退到 1 的时候判一下 b[1] 是否为 0 即可
AtCoder Beginner Contest 256
I like Query Problem
题目大意,给你长度为 n 的序列和 q 个询问
(1,l,r,x) 表示将 [l,r] 的数都改成 ⌊xai⌋
(2,l,r,y) 将 [l,r] 的数都改成 y
(3,l,r) 求 [l,r] 的和
算法分析
首先对于区间赋值,[l,r]←v 很简单,就是标准的线段树操作
难点是在于 ⌊dai⌋
对于这种修改,最坏情况可能有 2 种
- [l,k],[k+1,r] 两个区间的值可能不同
- [l,k] 可能执行了 2 次,⌊d2ai⌋
[k+1,r] 可能执行了 3 次,⌊d3ai⌋
不论哪种情况,对第一种操作而言,都可能存在 [l,r] 区间值不统一的情况
对于这种情况,可以用 segment tree beats 来实现,具体来说
- 对于 [l,r] 执行 ai←ai/x 的操作,如果 [l,r] 中的所有元素都相同,不妨设都是 v
此时相当于区间赋值操作,直接给区间打赋值标记 v/x
- 否则的话,暴力递归所有子节点,直到找到满足所有数都相同的区间,打标记 v/x
然后回溯的时候,更新路径上的值
- 至于一个区间是否所有数都相同?可以维护一个最大值 mx,一个最小值 mn,当 mx=mn 时候区间所有数都相同
另外还需要维护区间的 sum,sz
segment tree beats 的时间复杂度平均是 O((n+q)logn)
E - Takahashi’s Anguish
题目大意,给你 1→n 的排列,表示小孩的编号,每一个小孩都会讨厌另一个小孩
(i,x(i)) 表示小孩 i 讨厌小孩 x(i),并且 i 有怨气值 C(i),如果 x(i) 在 i 之前先得到糖果
那么就会产生 C(i) 的怨气值,现在问一个方案使得怨气值最小
思路分析
首先对于 (i,x(i),x(x(i)),⋯) 如果张成一条链,那么顺着这条链时间顺序发糖果,不会产生怨气值
但是注意到,可以考虑建一条有向边 (i,x(i)),对应的图有如下性质
该图是 Functional Graph,即每一个点都只有一个出度,Functional Graph 有如下性质
假设该图 G 包含 K 个连通分量 C1,C2,⋯,Ck,每一个连通分量有且仅有一个环
证明
如果每一个点的入度也都是 1,那么这个图对应的是置换图,有 (k+1) 个节点,并且仅有一个简单环
否则的话,一定可以找到一个点入度为 0,删除这个点,和它的出边,类似拓扑排序,可以不断执行这个过程
直到剩下的图构成一个置换图
根据Functional Graph的性质,就可以想到用并查集维护连通分量和环
具体来说,沿着 (u,x(u)) 路径走,边走边执行并查集合并,当遇到 (u,x(u)) 在同一个并查集中的时候
那就说明沿着 (u,x(u)) 往前走是在一个简单环上绕行,记一下环的起点 s←u,j=x(s),令 j=x(j) 遍历环
找到 min(C(j)) 即可
F - Cumulative Cumulative Cumulative Sum
根据题中给出的表达式,不难推出
Cx=xA1+(x−1)A2+⋯1Ax
Dx=(1+2+⋯x)A1+(1+2+⋯x−1)A2+⋯+1Ax,令 f(x)=1+2+⋯+x,那么
Dx=f(x)A1+f(x−1)A2+⋯+f(1)Ax
也就是说,Dx=i=1∑x2(x−i+1)(x−i+2)Ai
2(x+1)(x+2)i=1∑xAi+21i=1∑xi2Ai−22x+3i=1∑xiAi
要维护三个部分前缀和,并且支持单点修改,用树状数组就可以做到
G - Black and White Stones
题目大意,一个 n 边形,边长都相等,每一条边的边长为 d,按边长一个单位一个单位来看
一条边就有 d+1 个点,现在给每一个点染色,可以染成黑白两种颜色,要求染完之后
每条边白色的点数相同,问染色的方案
思路分析
一开始比较难想,先来看一个类似的问题,不相邻的组合数个数,这个问题的解决思想
核心是所有的方案数可以分为两种,包含第一个球和不包含第一个球,从这里出发考虑
本题的方案数也可以分为 2 类,即第一个点染白色或者是黑色
以边作为 dp 的阶段,假设当前考虑第 i 条边,第一个点的颜色是 c
c=0 表示白色,c=1 表示黑色,我们还需要记一下一条边最后一个点的颜色 j
因为对于第 n 条边,必须首尾相接,也就是说 j=c,所以状态函数定义如下
dp(c,i,j) 表示当前考虑第 i 条边,并且第一个点染色成 c,最后一个点染色成 j,此时的方案数
这样我们可以枚举每一条边白色节点的个数 k=0,1,2,⋯,d+1,接下来考虑状态转移方程
对于每一条边,我们 dp 状态表示的时候,边的第一个点和最后一个点,用状态维度加以限制
中间的 d−1 个点是没有限制的,不难写出状态转移方程
dp(c,i,0)=dp(c,i−1,0)⋅(k−2d−1)+dp(c,i−1,1)⋅(k−1d−1)
dp(c,i,1)=dp(c,i−1,0)⋅(k−1d−1)+dp(c,i−1,1)⋅(kd−1)
枚举 k,然后计算 i,这样的复杂度是 O(n2) 的,这里用矩阵快速幂优化
不妨用 b(k) 表示 (kd−1),整理状态转移方程,可以得到
(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))
这是可以用矩阵快速幂来做的
(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))
值得注意的是,dp(0,n,1),dp(1,n,0) 并不合法,同理,dp(0,0,1) 不合法,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)
(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))
综上所述,假设 Bn 矩阵快速幂求出来的结果是 A
那么 dp(0,n,0)=A(0,0), dp(1,n,1)=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
一些组合问题
不相邻的组合数个数
从 n 个球中选出 r 个不相邻的球的方案
- n<2r−1 不存在这样的方案,答案是 0
- n⩾2r−1 时候,取法是 (rn−r+1)
这怎么来理解呢?
首先有 r 个球,中间有 r−1 个空格,这 r−1 个数只能看成是空格而不是球
于是我们取的球只能从 n−r+1 个里面取,任意取 r 个,然后将之前的空格插入到 r−1 个空位中
(rn−r+1) 种方案数
那么 n 个球围成一圈呢?
- 注意到一个球周围至少要有 2 个空格,所以 n<2r 时无解
- n⩾2r,对球进行编号,对于所有可能的组合,都只有 2 种情况
包含 1 号球和不包含 1 号球
如果包含 1 号球,那么 (n−1,1,2) 这 3 个位置不能选,所以只能从 n−3 个球中选
从 n−3 个球中选出 r−1 个不相邻的球的方案数是 (r−1(n−3)−(r−1)+1)=(r−1n−r−1)
如果不包含 1 号球,可以从 n−1 个数中任选 r 个不相邻的球,方案数是 (r(n−1)−r+1)=(rn−r)
- 综上,(r−1n−r−1)+(rn−r)