VP

pointfish / 2025-02-18 / 原文

Educational Codeforces Round 161 (Rated for Div. 2)

D

$n$ 个怪物站成一个序列，有防御值和攻击值，每个怪物会受到来自左右两个怪兽的攻击，如果防御值小于两边攻击值之和则怪物死亡，从序列中移除，求每次移除的怪物。

暴力做第一次，发现每次可能被移除的怪物一定是上一次被移除的怪物的旁边。

E

构造长度小于等于 $200$ 的序列 $a$，使得 $a$ 中严格上升序列为 $x$，$x\le10^{18}$，包含空串。

首先构造出一组 $1,2,3\dots n$，发现序列数为 $2^n$（包含空串），如果在后面添加一个数 $x$，则序列数增加 $2^{(x-1)}$，将需要加入的数倒序添加就互不影响。

F

长度为 $n$ 的序列 $a$，值域为 $[1,x]$，每次选定一个区间，将这个区间全部赋值为任意一个在这个区间内没有出现过的数，求将整个区间赋为同一个值得最小操作数，$n\le100,x\le100$。

观察数据范围考虑 $dp$，令 $f_{i,j,k}$ 为区间 $[i,j]$ 全部赋值为 $k$ 的最小操作数，$g_{i,j,k}$ 为区间 $[i,j]$ 赋值为不出现 $k$ 的最小操作数。

可得状态转移方程：

\[f_{i,j,k}=f_{i,mid,k}+f_{mid+1,r,k} \]

\[f_{i,j,k}=g_{i,j,k}+1 \]

\[g_{i,j,k}=g_{i,mid,k}+g_{mid+1,r,k} \]

\[g_{i,j,k}=g_{i,j,l}+1,(k\not = l) \]

注意转移顺序，答案为 $\min f_{1,n,i}$

Codeforces Round 926 (Div. 2)

评分不高，但是极度困难。

C

奇怪赌场，设每次赌 $y$ 元，赢一次获得 $k\times y$，最开始有 $a$ 元，赌场选择你是否获胜，但最多连续 $x$ 次选择你输，判断是否能获得无限钱。

\[x\le 100,k\le 30,a\le 10^9 \]

如果连输 $x$ 把，剩下的钱就可以 $allin$，如果钱比原来多就可以获得无限钱。显然，在前 $x$ 轮中任意一次赌场让他赢都会获得比原来更多的钱，才能使赌场一直让他输。

令之前投入了 $sum$ 元，假设这一次投入 $x$ 元，那么 $sum+x<k\times x$，转化一下就可以优化了。

啊啊啊，被 C 题爆了。

D

给一颗 $n$ 个点的树，求有多少个选点的集合使得集合中任意三个点不在同一简单路径上。

\[n\le 3 \times 10^5 \]

$三个点不在同一路径，以该点为根向下到叶子节点最多有两个选点，考虑树形 $dp$，令 $f_{u,0/1/2}$ 表示以该点为根到该子树的叶子节点最多有 $0/1/2$ 个选点，显然 $f_{u,0}=1$，对于每个儿子，都可以自由选择零或一个点，乘法原理：

\[f_{u,1}=\prod(f_{v,0}+f_{v,1}) \]

如果儿子选择两个点，则其他儿子和根都只能有 $0$ 个选点，如果选择儿子一个点，加法原理：

\[f_{u,2}=\sum(f_{v,1}+f_{v,2}) \]

E

给定 $n$ 个点的树，再给定 $k$ 条路径，对树边染色，求最小染色边数使得每条路径都被染色。

\[n \le 10^5,k \le 20 \]

从 $k$ 的数据范围中可以猜测到复杂度中包含一个 $2^{20}$，对于一个路径，以 $lca$ 为界限分为两条向下的路径，枚举每条路径是哪条链被染色。

然后现在有 $k$ 条祖孙链，按深度大到小排序，如果该链已被染色就跳过，否则就染该链最上面的边。

这里是一个单点加路径和，可以转化成子树加单点查：修改边就修改整个子树，路径和就是转化为两个点值是否一样，如果不一样就代表路径内有染色边。

F

给定一颗大小为 $n$ 二叉查找树，点权值为 $c$，其中有一些点的权值缺失，求树有多少种权值方案。

中序遍历转化为序列，为单调不降序列，对于一个未填的块，长度为 $len$，可填值域为 $x$，则填数方案为 $\dbinom{len+x-1}{len}$。

推导一下：设 $f_{i,j}$ 表示长度为 $i$ 值域为 $j$ 的方案数，转移为 $f_{i,j}=\sum_{k=1}^{j}f{i-1,k}$，发现这是一个前缀和，容易发现这就是一个杨辉三角。

1	1	1	1	1
1	2	3	4	5
1	3	6	10	15
1	4	10	20	35
1	5	15	35	70

Codeforces Round 936 (Div. 2)

D

有点难度。

长度为 $n$ 的序列，和 $x$ 求最多能把这个序列分成多少段使得每一段的异或和或起来小于等于 $x$。

\[n\le10^5,x,a_i\le2^{30} \]

从大到小枚举 $x$ 的二进制。

该位为 $1$ ：这一位可以填 $1$ 也可以填 $0$ 填零可以直接统计答案与最后答案取 $\max$ 因为后面填什么都可以。

该位为 $0$ ：这一位必须填 $0$，在 $a$ 中扫一遍，发现第一个该位为 $1$ 的数一定是和第二个异或掉，如果做不了就直接结束。

把已经被异或的 $a$ 赋值为 $-1$，最后记录有多少个不为 $-1$ 的。

E

长度为 $n$ 的排列，给出前缀最大值的位置和后缀最大值的位置。

\[n\le2\times 10 ^ 5 \]

比 $D$ 简单。

分别排序，特判掉最小前缀值不是 $1$，最大后缀值不是 $n$ 的情况。

然后发现前缀最大值和后缀最小值相同，不相同也特判掉。

显然这个位置是最大值，那么剩下 $n-1$ 个数，分成了两部分，到底是那个不重要，只在乎大小关系，乘上一个组合数 $\dbinom{n-1}{a_r-1}$，紧接着看左边那部分，很明显最后一个前缀最大值是，左边那部分的最大值，然后选 $a_r-a_{r-1}-1$ 个数。差不多就这样，反正很好想的。

F

一个长度为 $n$ 的排列 $a_{1...n}$。有 $q$ 次询问，每次给出 $l,r$，求有多少个子序列 $i_{1...k}$ 满足：

$l\le i_1,\space i_k\le r$
$\forall j\in [1,k-1],a_{i_j}|a_{i_{j+1}}$

$n\le10^6$

先扫描线把答案离线，注意到是一个排列，所以枚举所有数的倍数是 $n\log n$ 的，考虑贡献，加入一个数 $x$，之前的数 $z$ 如果有贡献，有两种方式，以 $z|x$ 直接贡献，或者 $z|y,y|x$ 贡献，这个地方可以 dp，每次加进来都做一遍就好了。

AtCoder Regular Contest 187

不是vp，赛时只会A。

A

长度为 $n$ 的序列 $a$ 和一个 $k$。$n,a_i,k\le 50$

定义一次操作为 $a_i=a_{i+1}+k,a_{i+1}=a_i$，后面那次赋值 $a_i$ 是前面未赋值前的值。

发现操作两次可以让两个数都加 $k$，容易把前 $n-1$ 个数变有序，可以把这些数都变很大，然后从倒数第二个开始操作，把最后一个数往前挪。

B

有一张图，编号为 $1$ 到 $n$，$n\le2000$，每个点有权值。对于 $\forall i<j,a_i\ge a_j$ 把 $i$ 和 $j$ 连边。现在给定一个有残缺的权值，残缺的位置可以随便填，求所有情况图联通块的数量和。

找充要条件，发现当前 $i$ 个的最小值大于后 $n-i$ 的最大值时，前 $i$ 个和后 $n-i$ 是断开的，然后计数即可，算一个前缀 $i$ 或后缀 $i$ 大于或小于的 $j$ 数量即可。

C

长度为 $n$ 的排列 $p$，$n\le5000$。给定目标排列 $q$，可能有残缺，求有多少个排列经过一轮冒泡可以变为目标排列。我们称一轮冒泡为对于 $i=1,2,...n-1$，如果 $p_i>p_{i+1}$，交换两个数。

同样找充要条件，考虑固定排列 $q$，观察发现，若前缀最大值的个数为 $x$，通过手玩发现通过一轮冒泡变成排列 $q$ 的排列有 $2^q$ 种。

可以设计 dp。设 $f_{i,j}$ 为前 $i$ 位中，前缀最大值为 $j$ 的答案，设排列中已经给出的数的集合为 $S$。

如果给一个 $x\in S$。那么 $f_{i,x}=2\times\sum_{k=0}^{x-1}f_{i-1,k}$ ，$f_{i,j}=f_{i-1,j} (j>x)$

如果是 $ -1$ 。$f_{i,j}=\sum_{k=i-1}^{j-1}{f_{i-1,k}\times[k\notin S]}+f_{i-1,j}\times d$ 其中 $d$ 是小于 $j$ 且没有确定出现过的数。

D

给定长度为 $n$ 的序列 $A$ 和序列 $B$，令序列 $C_i=A_i$ 或 $C_i=B_i$

对于每一个 $i$，最小化 $C$ 序列的最大值与最小值的差。

\[n\le5\times10^5,A_i,B_i\le10^9 \]

先离散化，然后设一个 $f$ ，$f_i$ 表示最小的数为 $\ge i$ 时的差，对于第 $i$ 位的选择，不妨设 $A_i\le B_i$,则 $A_i$ 在在 $f$ 上的修改区间为 $[1,A_i]$， $B_i$ 的修改区间为 $(A_i,B_i]$，取 $\max$ 因为单调上升实际上就是一个区间推平操作。