Codeforces Round 924 (Div. 2)

比赛链接，官方题解

ID	Difficulty (0-5)	Topic	Status	Code
A	0	Brute Force	Solved	A.cpp
B	0	Two Pointers	Solved	B.cpp
C	1	Math	Solved	C.cpp
D	1	Greedy	Solved	D.cpp
E	3	Dynamic Programming	Upsolved	E.cpp
F	4	Combinatorics, Segment Tree	Upsolved	F.cpp

E. Modular Sequence

给定 $n,x,y,s$ ，问是否能构造以恶搞长度为 $n$ 的数列 $a$ ，满足：

• $a_1=x$
• $a_i=a_{i-1}+y$ 或 $a_i=a_{i-1}\mod y$
• $\sum_{i=1}^n a_i= s$

令 $r=x\mod y$，不妨令 $s’=(s-nr)/y, x’=(x-r)/y$ ，选择改成置为 $0$ 或加 $1$ 。

我们称连续增长的为一段。则答案中除了第一段都是从 $0$ 开始的。

因为求和增长的速度是平方级别的，所以每一段连续的长度不会超过 $O(\sqrt{s})$ 。

把这 $O(\sqrt{s})$ 中不同的段按照长度拿出来做个完全背包，求出凑出某个数所需的最小长度。

然后枚举第一个 $0$ 的位置即可。复杂度 $O(s\sqrt{s}+\sum n)$ 。

F. Digital Patterns

给两个数列 $a_1,a_2,\dots,a_n$ 和 $b_1,b_2,\dots,b_m$ ，生成一个 $n\times m$ 的矩阵 $c_{i,j}=a_i+b_j$ 。

查询 $c$ 有多少个子正方形满足范围内上下左右相邻的数字里没有相同的。

支持对 $a,b$ 进行区间加，查询符合条件的子正方形数量。