9.7-9.13 学习记录

发表于 2026-09-07 更新于 2026-09-15 分类于学习记录

训练量很饱和啊。

9.7

VP CF 1116 Div.2

A

题意

三个非负整数 $a$，$b$，$c$，操作可以将其中一个整数替换为另外两个整数之和，问最小极差。

思考

极差最小，也就是三个数尽可能一样大。
操作能生成的数只会越来越大。$a$，$b$，$a+b$ 不管怎么操作，极差都比原来大，因此只会操作一次。
答案就是，$\min(\text{原极差}, \max(a,b), \max(b,c), \max(a,c))$
用时 $14$ 分钟

B

题意

替换 ?，变成 $0/1$，使得对于每一个 $1 < i < n$，都有 $s_{i-1} \neq s_{i+1}$。

求替换方案数。

赛时思路

如果出现形如 0?0 就输出 $0$
形如 ????，第一个填什么，第三个填相反的，第二个和第四个同理。这里又着急了，往后多想一个 ? 就想到正解了
先把能确定的 ? 确定下来，例如 10?，此时 ? 一定是 $0$
剩下的就按连续 ? 处理，扫一遍就好了。
交上去 WA 了？？用时 $30$ 分钟。

正确思路

可恶，多考虑一步就做出来了。

对于 ?????，第五个也会被第一项确定，误以为它是自由的。

因此分成奇偶两条链考虑，交替相等。

还有一种做法是 dp。

C

$2n$ 个人围成圈，奇数称为红组，偶数称为蓝组。有一些人拿着炸弹，每个拿着炸弹的人可以执行以下操作之一：

保留炸弹
传递给下一个人，前提是那个人没有炸弹（顺时针）

如果下一个人有炸弹，则无法传递。

游戏进行 $k$ 轮，问最终分数。

赛时思路

考虑简单的情况，只有一个炸弹。若 $k = 0$ 是必败态，$k = 1$ 是必胜态，$k = 2$ 是必胜态，$k = 3$ 是必胜态。。。不要看到博弈题就去推必胜/必败态，感觉无论是什么题目，起点都是要去理解感受这个问题。可能不同题型确实存在一些技巧，但是不要一上来就套技巧。
两个炸弹？$k = 0$ 必败，$k = 1$ 且下一个人没有炸弹，必胜，否则必败。$k = 2$ 且下一个人没有炸弹，必胜，否则，有可能胜有可能败。
没思路了。用时 $20$ 分钟。

正确思路

对于每个人来说，保证自己存活且淘汰别人，是最优的。
考虑每个人的决策，对于拿炸弹的人来说，直到最后一轮再抛出去，可以同时满足上述两个目的。因此一定是最后一轮才抛。
邪门思路：$k$ 很大，肯定与 $k$ 无关（

D

题意

长度为 $n$ 的 $01$ 串，每次操作可以选定两个 $l \le r$ 且 $s_l = s_r$，然后让 $[l+1, r-1]$ 区间内的数翻转，问能形成多少种 $01$ 串。

赛时思路

对形如 $0110$ 等对称区间的操作是无用的。
经典结论：翻转 $[1,l]$，$[l+1,r]$，$[1, r]$ = 交换 $[1,l]$ 与 $[l+1,r]$ 的位置
没有思路啊。用时 $8$ 分钟。

正确思考

操作题，思考哪些东西不会被操作改变。
$01$ 串能考虑的东西不多，直接考虑相邻两项 $00/01/10/11$ 翻转之后的样子好像不好做。
先把 $01$ 串缩成极大连续段，此时考虑操作，发现不会改变 $01010$ 或 $10101$ 的结构，而且段内 $1$ 或 $0$ 的数量可以通过操作任意改变（不能变成 $0$）。
那就把多出来的 $0$ 和 $1$ 抽出来，隔板法算方案，各自之间是独立的。

VP CF Educational 193

A

题意

判断 $[2, n+1]$ 中是否存在一个数 $x$，使得 $< x$ 的数都不是他的因子，且 $> x$ 的数都是它的倍数。

思考

只有最后一个数有可能，遍历一遍即可。
用时 $7$ 分钟。

B

题意

删除序列中的一些元素，之后再交换一次相邻元素（可以不交换）。

问使得序列中不存在相邻相同元素的最小删除次数。

赛时思路

交换操作最理想的情况是 $1122 \rightarrow 1212$
交换操作只适用于 $(!x)xxyy(!y)$ 或 $(!x)xxy(!x)$ 或 $(!x)yxx(!x)$ 这三种情况。这里情况太复杂了，如果缩成连续段就好写很多，感觉是缺了个技巧，相邻相同缩成段这个还是很常见的。
全部删除后再反悔即可。
交上去又 WA 了？？用时 $26$ 分钟。

正确思路

缩成连续段后考虑三种情况：
1. 左右长度大于 $1$：交换后少 $2$ 次操作。
2. 左长度大于 $1$，右长度等于 $1$：判断 $i+2$ 与 $i$ 的颜色是否相同，交换后少 $1$ 次操作。
3. 左长度等于 $1$，右长度大于 $1$：判断 $i-1$ 与 $i+1$ 的颜色是否相同，交换后少 $1$ 次操作。

C

题意

给定长度分别为 $x$，$y$ 的严格增序列 $a$，$b$ 和一个 $n \times m$ 的矩阵，初始全 $0$。

操作可以用 $a$ 中的元素填充矩阵的 $i$ 行，可以用 $b$ 中元素填充矩阵的 $j$ 列。

最大化矩阵中出现了至少一次的数字之和。

$n,m \le 10^5$，$x,y,a_i,b_i \le n+m$

赛时思路

发现看错题了，耗时 $34$ 分钟（悲）读完题之后看样例验证一下理解啊。
把样例都算一遍好像就找到构造方法了。
简单来说，选 $n-1$ 个 $a$，$m-1$ 个 $b$，最后一个在 $a$，$b$ 中选就好了
但是有一个问题：出现重复的时候，选择 $a$ 和选择 $b$ 是不同的。
想不出来补丁，失败了，用时 $12$ 分钟。

正确思考

一个显然的想法是用前 $n$ 个 $a$ 填，前 $m$ 个 $b$ 填。
细想之后发现，要么填 $n-1$ 个 $a$ 和 $m$ 个 $b$，要么填 $n$ 个 $a$ 和 $m-1$ 个 $b$，所以一共填 $n+m-1$ 个数。记填的总数 $S=\min(n+m-1,\min(x,n)+\min(y,m))$
难点在于如何处理重复的数字，它既可以放在 $a$ 也可以放在 $b$，但是在当时并不知道放 $a$ 好还是放 $b$ 好。
那我们就把它拿了再说，先不纠结它到底拿了哪个。某种意义上是一种 延迟决策。
那如何判断合法性呢？发现只要拿的总数 $\le S$，就一定合法。因为总可以把都有的全分配到 $a$ 和 $b$ 里，但不超过 $a$，$b$ 的数量限制。相当于在最后再判断它放在哪里。
具体做法是处理出：只在 $a$ 中出现的数 $A$（取前 $n$ 个），只在 $b$ 中出现的数 $B$（取前 $m$ 个），在 $a$，$b$ 中都出现的数 $C$，然后合并，取前 $S$ 个。

贪心专题训练

Monsters And Spells

题意

$n$ 个怪兽，每个怪兽有出现时间 $k_i$ 和生命值 $h_i$。

你有一个攻击力 $x$，如果上一秒没有攻击，这一秒的攻击力就是 $x$，否则就是 $x+1$。

为了让每个怪兽出现即死亡，计算最少魔力花费（攻击之和）。

$n \le 10^4$

思考

一个比较 naive 的做法是从 $k_i - h_i + 1$ 时开始蓄力，这样的花费显然最小。
把这视作一个区间，发现区间有交，之后合并。
最后统计无交区间就好了，等差数列求和。

Vasya And Array

题意

给定 $m$ 条信息，告诉你 $[l, r]$ 区间是/不是不降序列，构造一个长度为 $n$ 的数组满足条件。

$n, m \le 10^3$

思考

数据范围很小，一开始的想法是图论建模暴力连边，但无法处理 $t = 0$ 约束。
考虑到这是贪心专题。显然两个相交的不降区间可以合并，先处理所有不降区间，再处理非不降区间。
如果后者会被不降区间包含则无解，否则，就说明左边界或者右边界存在 $a_i < a_{i+1}$。时间复杂度 $O(nm)$。

Stall Reservations S

区间调度板子。

Coffee Break

题意

给定 $n$ 个点，值域 $m$ 和一个 $d$。

定义偏序 $a \preceq b$ 为 $b > a + d$，问最小链划分数量，以及每个点在哪个链划分内。

思考

根据 Dilworth 定理，偏序集的最小链划分数量等于最大反链集合大小。这题的反链集合内的元素，任意两点之间的大小不超过 $d$，也就是最大值 $-$ 最小值 $\le d$。
排序后双指针找出最大反链集合即可。
但是这题需要输出方案！！
考虑选择 $a$ 之后，$[a, a+d]$ 区间内的数都无法和他处于同一条链上。将每个点视作区间，区间不能重叠，且要分组，那么问题就转化为了一个区间调度问题。妙啊。
实际上因为区间长度固定，所以有一种二分贪心写法，但是时间复杂度是一样的，感觉还不是很好写，作罢。

9.8

补题

[CF Educational 193] D

题意

维护 $a,b$。每次移动需要令 $a \leftarrow a+1$ 或 $b \leftarrow b+1$，每次可以跳到 $(p+a,q+b)$ 的位置。

飞船必须处于 $(x,y)$ 内，求一个操作序列 $s$，使得它到 $(x,y)$ 的欧几里得距离最小。

$s$ 的长度不超过 $2 \times 10^4$。题面有说的，一开始没注意到，一定要通读题面啊。

正确思路

应该注意到 $s$ 的长度不大。因为 $p,q$ 的增加是类似等差数列的，所以是根号级别的长度。当然题目也有提示。实际上就算没发现这点，也需要想到要将移动总距离拆出来，拆给每种取值的 $a$ 和 $b$。动机就是，如果按照题目的方法算移动距离的话，很不优雅。具体来讲，就是将“这一步可以将 $p$ 增加 $a$，$q$ 增加 $b$”，转化为“这一步可以将 $p$ 或 $q$ 增加 $T-i+1$。”
所以我们就去考虑 $s$ 每一位的影响，尝试把这个影响独立出来。
假设我们已经确定了 $s$ 的长度为 $T$，那么如果在第 $i$ 位令 $a$ 增加 $1$，整体来看，$x$ 坐标向右移动了 $T-i+1$ 格。所以在第 $i$ 位，可以使飞船向右或向上移动 $T-i+1$ 格，尽可能接近但不超过 $(x,y)$。
此时就可以把 $T$ 算出来了，因为这个等差数列的和一定 $\le x+y$，且越大越好。
知道了 $T$ 之后，$p+q$ 实际上也知道了，现在就要让 $(p-x)^2+(q-y)^2$ 最小。
在 $p+q$ 固定的情况下，显然让 $p-x=q-y$ 最好。因此我们可以直接解出 $p,q$ 的值。
因为取的是一个等差数列，所以一定能取出 $p$，又因为 $p+q=$ 等差数列的和，所以剩下的一定组成 $q$。
具体流程是算出 $T$，算出 $p$，再等差数列取数。

[CF 1118 Div.2] C

题意

交互题，需要找到直径长度，以及直径端点。

最多 $3n$ 次询问，每次询问可以知道 $\operatorname{dist}(u,v)$ 是否大于等于 $d$。

正确思考

找直径两种方法，两次 dfs 和树形 DP。这题显然是两次 dfs。
维护一个 $d$，直径是 $d-1$，钦定一个起点，枚举其他点，更新 $d$。
再用最远点跑一边。总共询问最多 $3n$。$d$ 最多增加 $n$ 次，两个循环用掉 $2n$ 次询问。

VP CF 1115 Div.2

A

题意

长度为 $n$ 的序列，排序，出现了连续两个相同数之后不能累加。

思考

构造一个形如：$1234\ 1234\ 123\ 22$ 的序列就好了。
找到出现次数最多的那一个，用它减去第二多，剩下的只能贡献两个。
用时 $10$ 分钟。交上去 WA 了？？？
不对，发现剩下多的可以插到前面去。
换一种思路，先把最大的那个平铺，然后往里面插空。只有当所有其他数字的出现次数 $<$ 空的时候，会出现相邻相同，分类讨论即可。
终于对了，耗时 $25$ 分钟。

B

题意

给你一个长度为 $n$ 的 $01$ 串，可以用 $010101\ldots$ 或 $101010\ldots$ 删除一些项，使得最终序列没有相邻相同的元素，问最少操作次数。

思考

需要删除的 $01$ 数量可以计算，最终删除的 $01$ 数量只差 $1$。
统计出需要删除的数量之后，如果差值 $>1$，就要多删小的那个。
但是删除小的那一个，会让另一个需要删除的数量至少增加 $1$（两个块合并了），达不到效果。
因此只能多删头尾元素。
不好想，换种思路。首先删 $0$ 或 $1$ 是独立的，可以先把需要删的删掉，现在的序列变成 $0101$ 或 $1010$。
此时再补上需要多删的 $0$ 或 $1$。删除任意一个中间的元素，都会使相邻合并，需要多删一次。
所以只能删除头尾元素。
用时 $16$ 分钟。

C

题意

$n \times m$ 的网格，初始每个点有 $a_{i,j}$，每行有 $v_i$。每当移除一个点，会使得这一行及上方所有行 $v_k \leftarrow v_k-a_{i,u}$。

当 $v_i \le 0$ 或同一行的点都被移除后，游戏结束。

要使得游戏结束，最少进行几轮？

$n\times m \le 10^6$

思考

首先 $m$ 轮是下界。
然后思考如何让某一层 $v_i \le 0$。找到当前层以及下方所有层数中，$a_{i,j}$ 最大的 $k$ 个（$k\le m$），扫一遍就好了。时间复杂度 $O(nm \log m)$，归并排序，每次合并两行。
用时 $28$ 分钟，代码调了 $10$ 分钟（悲

D

题意

长度为 $n$ 的序列，可以选定一个 $2 \le i \le n-1$，要求 $a_{i-1}$ 和 $a_{i+1}$ 同奇偶，然后让 $a_i \leftarrow a_{i-1}+a_{i+1}-a_i$。

问，进行若干次操作之后，字典序最小的序列长什么样。

$n \le 10^5$

赛时思路

这种操作次数不限的问题，要去考虑操作不能改变的东西是什么。这里其实范围可以扩大，操作次数不限的问题要去考虑操作的性质，不变性只是其中一种。
显然操作不会改变 $a_i$ 的奇偶性，因此，能操作的项是确定的。这在这题里只能算小性质吧。
既然是字典序贪心，那就从第一个可以操作的项开始考虑。如果右边那一项不可操作，那就看操作一次之后会不会让当前项变小就好了。
右边那一项可操作怎么办呢？那就循环依赖寄了啊。发现不可做要及时回溯。
感觉想不出来了，用时 $9$ 分钟。

正确思路

序列上操作，一个常见的思路是将操作映射到差分/前缀和数组上。
题目的操作会让人联想到差分，于是我们考虑操作一次对差分数组有何影响。
发现操作 $i$ 相当于交换 $d_i$ 和 $d_{i+1}$，操作的前提是 $a_{i-1}$ 和 $a_{i+1}$ 同奇偶，同奇偶的数差是偶数，所以约束等价于 $d_i = d_{i+1}$。
所以操作就变成差分数组上同奇偶的数可以任意交换，缩成极大连续段，然后让小的数排前面。
注意第 $1$ 项不可以操作。

正确思路

VP CF 1113 Div.2

A

题意

A，B 博弈，A 可以删除一个 $0$，B 可以删除一个 $1$，A 先手。

A 希望最终序列字典序最大，B 相反。输出最终序列

思考

B 会删除第一个 $1$。
A 删除第一个 $0$。
用时 $4$ 分钟。

B

题意

大小为 $n$ 的初始集合 $a$，以及大小为 $m$ 的目标集合 $b$。

每次操作选择 $a$ 中的两个数，删除他们，插入一个他们之间的数进入 $a$。

问能否通过若干次操作使得集合 $a$ 等于集合 $b$。

集合 $a$，$b$ 中的数两两不同。

$n,m \le 2\times10^5$

思考

首先 $n < 2m$ 一定不行。
考虑将 $a$，$b$ 排序。
$a$ 不能生成比 $\max a$ 大或比 $\min a$ 小的数，因此若 $\max b > \max a$ 或 $\min b < \min a$，则一定不行。
否则就一定可以？看眼样例。发现不对。
如果不删除，那就一定可以。为什么删除了不行呢？因为大的数可能不够吧。
首先每次操作生成一个 $b$ 集合的数肯定不劣。尝试从小到大生成咯。
排序后双指针，合着这是模拟题啊。
不对啊，做法假了，没过样例。
换一种思路。把 $b$ 的数放入 $a$ 中，能生成 $b$ 的，只有它左右两边各取一个才行。
把 $a$ 的数视作 $1$，$b$ 的数视作 $-1$，前后扫一遍，如果 $<0$，那就不行。类似括号序列？
交上去居然 AC 了，用时 $25$ 分钟。好神秘。

C

题意

长度为 $2n$ 的序列，$x \in [1,n]$ 在 $a$ 中出现了两次。

每次操作选择一个数 $x$，找到它在 $a$ 中出现的下标，$l$ 和 $r$，删除 $a[l\ldots r]$，收获 $(r-l+1)^2$ 的价值。

问序列为空之后能得到的最大价值。

$n \le 2\times 10^5$

正确思路

如果 $[l,r]$ 区间内已经有数被删掉了，那么它一定是被内部消化了，可以证明这个一定不优于不删除。
所以最优删除一定是多个紧密相贴的块。
DP 做。

D

题意

$2$ 个长度为 $n$ 的 $01$ 串 $s,t$，$q$ 组询问，每一组询问给定 $l$，$r$，问 $s[l\ldots r]$ 和 $t[l\ldots r]$ 是不是合法对。

合法对 $a,b$ 定义为，可以通过不断选择一组 $i_1 < i_2 < \ldots < i_k$，使得 $a_i$ 与 $b_i$ 中的众数是一样的，然后删除这些项，直到 $a,b$ 为空。

正确思路

$2$ 个 $01$ 串，考虑 $00/01/10/11$ 这几种情况。
$00/11$ 这两种情况对约束是比较友好的，虽然能改变相对大小，但不会使得 $a$，$b$ 的众数从相同变不同，只可能使众数从不同变相同。
$10/01$ 两个组合在一起也可以达到相同的效果，不会改变相对大小，所以能消掉的就消掉。
所以考虑只剩下 $01/10$ 的情况，他们会改变众数。此时就需要一个 $00/11$ 来弥补。
统计 $01/10$ 的个数，$00/11$ 的个数就好了。

贪心专题训练

Packing Under Range Regulations

题意

$n$ 个数，每个数的取值范围是 $[l_i,r_i]$。$n$ 个数要求两两不同，问能不能做到。

$n \le 2\times 10^5$

思考

题目给到区间约束。一个比较 naive 的想法是按区间左端点排序，每次选区间左端点。
但是这样会出现多个区间共用左端点的情况。不难发现，占用了左端点后，其余区间的可选范围减少 $1$，把他们归到下一个左端点考虑就好了。
相同左端点，优先满足 $r$ 小的那一个区间。

01Sequence

题意

构造一个长度为 $n$ 且 $1$ 的数量最少的 $01$ 序列，使其满足 $m$ 个约束，每个约束 $l,r,x$ 表示 $[l,r]$ 中至少有 $x$ 个 $1$。

$n,m \le 2\times 10^5$

思考

在前缀和数组的视角下看约束，$s_r - s_{l-1} \ge x$，感觉没啥用。
考虑简化问题，$x = 1$ 时退化为区间选点，那这题就相当于区间选多个点。
沿用区间选点的贪心思路，如果区间内点不够，就从右端点开始加。
需要动态维护区间和，单点加，并查集处理“左边第一个 $0$”，时间复杂度 $O(m \log n + n \log n)$

后话

瞄了一眼题解，直接用 set 维护就好了，不需要上并查集。
有差分约束的做法，我就说这个约束怎么这么像差分约束。然后这题的约束还有 $0 \le s_i-s_{i-1} \le 1$，边权有 $-1$，跑 SPFA 会被卡。转而考虑 $s_i$ 记录 $0$ 的数量就可以跑 dij 做了。好题！

Case of Fugitive

题意

$n$ 个不交区间，$m$ 条线段，长度为 $a_i$。一条线段可以将其左右端点的相邻区间联通。问能否使得所有区间联通。

$n,m \le 2 \times 10^5$

思考

将 $a_i$ 排序，那么，相邻两个区间能选择的线段构成一个区间。
对于这新的 $n-1$ 个区间，每个区间要选出一个数，一个数不能被重复选。这不就是 Packing Under Range Regulations 吗？秒了。
既然出现得这么频繁，不妨起个名字，就叫点选区间问题吧。

9.9

VP CF Educational 194

A

太简单就懒得写了，用时 $4$ 分钟。

B

题意

求 $\sum\limits_{i=0}^{k-1} (y+i) \bmod (x+i)$

$x,y \le 10^6$，$k \le 10^{12}$，$\sum y\le 10^6$ 对于这个 $y$ 的范围要很敏感

赛时思路

推式子题，拆成 $y \bmod (x+i)+i\bmod (x+i)$。式子推错了，外面还要套一层取模的。
先看第一项，注意到 $y$ 很小，所以当 $x+i > y$ 之后，都贡献 $y$。可以暴力枚举。
再看第二项，一直贡献 $i$ 啊，等差数列求个和就好了。
要开 int128 吧。
过不了样例。突然发现这个式子外面还要再套一层 $\bmod (x+i)$。
啊啊，重新来一遍。
如果 $y > x$，问题就是一个等差数列求和。
如果 $y\le x$，变成 $(y+i)-\lfloor \frac{y+i}{x+i} \rfloor \times(x+i)$，考虑用 $\lfloor \frac{y+i}{x+i} \rfloor$ 的值分组。这里出现误判了，我当时以为这个会越加越大，实际上这是假分数，所以越加越小，最终趋近 $1$，所以可以暴力枚举的，$i=y$ 的时候就是 $1$ 了。
当 $\lfloor \frac{y+i}{x+i} \rfloor = p$ 时，有：$(y+i)-p(x+i) = y+i-px-pi=y-px+(1-p)i$
感觉太复杂了啊，推不下去了。用时 $46$ 分钟。

正确思路

看到式子之后先想一下，再尝试变化。
如果 $y < x$ 那就等差数列求和。
如果 $y > x$，这个式子很像糖水原理，所以将取模转化为 $(y+i)-\lfloor \frac{y+i}{x+i} \rfloor \times(x+i)$。当 $i=y$ 时就变成了 $y-x$。暴力枚举 $y$ 就好了。

C

题意

给定 $x,y$，一次操作可以将 $x \leftarrow x-1,y\leftarrow y+1$，使得 $x \oplus y$ 最大的同时需要操作次数最小。

$x,y \le 2^{29}$

赛时思路

考虑从高向低位贪心，每次 check 当前位能不能贡献 $1$，如果可以，那就选。这里又急了，感觉还是那个问题，在没有理解题目的情况下贸然行动了。应该要注意到 $x \oplus y$ 一定可以取到最大值 $x+y$ 的。对位运算的最大值缺乏积累吧，不够敏感。
当前位的操作不能影响到前面数字，因此，lowbit(x) > 当前位则无法操作（xxxx00000），lowzero(y) > 当前位则无法操作(xxxx11111)。可以计算出此时最大操作数。
从当前位看，$x$ 不能从 $0$ 变 $1$，$y$ 不能从 $1$ 变 $0$，因此，记录这两位第一次变化所需的操作次数，取较大值即可。
$x$ 从 $1$ 变 $0$ 好计算（xxxx011111），$y$ 从 $0$ 变 $1$ 也好计算 (xxxx10000)。
这样子 $x \oplus y$ 确实最大，但是操作次数最小吗？的确吧。
代码没调出来（悲。用时 $40$ 分钟。

正确思路

对位运算的最大/最小值应该很敏感才行：
1. xor：最大值是 $a+b$，最小值是 $0$
2. or：最大值是 $a+b$，最小值是 $\max(a,b)$
3. and：最大值是 $\max(a,b)$，最小值是 $0$
然后注意到这题 $x=0$ 时一定能取到最大值 $x+y$，考虑最小化操作次数就好了。
令 $n=x+y$，$x \oplus y=n$ 意味着 $x,y$ 在一些位上不能相同，相当于让 $n$ 把一些 $1$ 分给 $x$，然后不能超过 $x$ 的同时越大越好。这就是一个用二进制来拼数的过程了，从高往低贪心。

D

题意

已知这个序列的前缀和的每一项的正负性，构造一个无元素 $0$ 的序列 $a$，它的代价是所有元素绝对值的最大值。

求最小代价。

$n \le 3\times 10^5$

赛时思路

考虑构造前缀和数组，它做差分就是原数组，代价就是相邻两项差的最大值，约束是不能出现相邻相同，以及每一位的正负性。
出现连续 $0$ 或开头 $0$ 无解。
拆成加号段和减号段。直观理解一下，每一段里，走势都是像个山峰一样的。这里应该要去尝试构造反例的，样例 hack 了这个理解。但实际上也接近了。
加号段的开头必为 $1$，长度为奇数时结尾为 $1$，否则是 $2$。
减号段开头必为 $-1$，长度为奇数时结尾为 $-1$，否则是 $-2$。
扫一遍就好了？
做法假了。。用时 $20$ 分钟。

正确思路

考虑构造前缀和数组，要求相邻两项尽可能紧密。
可以通过“抖动”的策略控制大小。然后感觉这个答案其实很小。把样例都看一遍，发现答案只可能是 $1/2/3$.
把玩一下样例发现只有出现 -++- 或 +--+ 的时候答案才会等于 $3$
所以按照加号段以 $1$ 开头，减号段以 $-1$ 开头的策略做一遍，如果答案是 $1$ 或 $2$ 直接输出，是 $3$ 的话再判断一下有没有 -++- 或 +--+，没有也输出 $2$.

VP CF 1112 Div.2

A

题意

长度为 $n$ 的 $w$ 数组，选择一个 $k$。

所有大于 $k$ 的元素右移，小于 $k$ 的元素左移，不能出现等于 $k$ 的元素。

问选择 $k$ 之后能否使得 $[1,n]$ 中每一位恰好有一个元素。

思考

每个元素都要移动，并且只移动一次。那么，第一项和第二项应该交换位置。第三项和第四项应该交换位置。奇数一定无解。
所以，$k$ < 奇数项，大于偶数项。比较奇数项最小值和偶数项最大值即可。
用时 $12$ 分钟。

B

题意

构造一个长度为 $n$ 的 $01$ 串，要求有恰好 $k$ 个相邻相等，并且 $01$ 数量只差最多为 $1$。

思考

考虑合并相同项。长度为 $x$ 的项可以贡献 $x-1$ 个相邻相等。
先把 $k$ 的约束满足了，再用 $0101$ 填到长度为 $n$。
判断 $k$ 的奇偶性，如果是偶数，$01$ 各自贡献 $\frac{k}{2}$，形如 $000011110101$
如果是奇数，$0$ 贡献 $\lfloor \frac{k}{2} \rfloor$。形如 $000111101010$。
用时 $12$ 分钟。

C

题意

给你一个长度为 $n$ 的序列 $a$，从中找到一个最长子序列。

约束是，第 $i$ 项不能是子序列里正着数 $[l_i,r_i]$ 项，也不能是倒着数 $[u_i,v_i]$ 项。

$n \le 5\times 10^3$

赛时思路

这个倒着数需要提前知道序列长度才行啊。二分？前面那一句是对的，后面这里错了，没有单调性，而且这个数据范围也不像是二分的样子啊（
二分之后就可以确定出子序列每一项可以填哪些数。这里细想一步就会发现非常复杂，不可做，应该及时跳出换思路。
这个区间的性质好像没用上啊。放弃了。用时 $21$ 分钟。

正确思路

枚举序列长度，考虑子序列每一项可以填哪些数，发现不可做。
那就依次考虑原序列的数，看它能不能填进子序列里。
如果当前项能填，我们猜测，此时填一定最优 [感觉这里很难想]。可以用调整法证明。如果最优解不是这样的，那就把第一个出现不同的位置调整，不会影响答案。

D

题意

给你一个长度为 $n-1$ 的数组 $a$。

对于一个长度为 $n$ 的排列，定义 $v_i$ ($1\le i \le n-1$) 为：将这个排列从 $i$ 处断开，左右段最大值的较小值。

计算有多少个 $v_i = a_i$ 的排列 $p$。

$n \le 10^6,a_i \le n$

赛时思路

感觉要跑个 dp 啊。感觉应该先理解题目才是，不要上来就 dp 吧。

正确思路

观察 $v$ 的形状，$n$ 将左右劈成两个坡，分别为前缀最大值与后缀最大值。这是一个单峰序列，且峰顶是 $n-1$。
此时考虑填数使得 $v_i=a_i$。如果 $a_i$ 不是一个以 $n-1$ 为峰的单峰序列，那就无解。
考虑 $n$ 个数可以填在哪里。首先 $a_i$ 只能填在固定位置，且它拥有一个平台，这个平台一定放比它小的数。$n$ 比较特殊，不能放入任何一个平台，但是能放在 $n-1$ 的左右两侧。
每个平台只能容纳 $\le v_i$ 的数，对于点 $i$，只能填在 $v_i\ge i$ 的平台里里。这是一个经典计数模型，从大往小填数，维护当前空位数就不会有问题。因为当前填的一定会占用后面填的一个空位。如果从小到大填，当前填的就不一定占用后面的空位，所以就不能做。
判断无解，开个桶记录记录连续段长度，从大到小填数，维护一个可填空位，如果这个数不是 $a_i$ 就填，空位 $-1$.

贪心专题训练

超速检测

梦回 CSP-S2024，终于把当年的正解补上了。

找出每个车的超速时所在的位置，第一问做个前缀和，第二问是个区间选点。对于每个区间，如果没有点覆盖，找到最后一个 $\le r$ 的点选就好了。

细节好多。。。

拼数

拼数类贪心，之前还在 ABC 上做到过。

国王游戏

这种需要确定顺序的排序题，一种方法是邻项交换确定排序规则。

假设现在交换 $i,j$。设 $s$ 是 $i-1$ 及之前的 $a$ 乘积。

交换前：$\max(\lfloor \frac{s}{b_i} \rfloor, \lfloor \frac{s\times a_i}{b_j} \rfloor)$

交换后：$\max(\lfloor \frac{s}{b_j} \rfloor, \lfloor \frac{s\times a_j}{b_i} \rfloor)$

交换之后更优，即：$\max(\lfloor \frac{s}{b_i} \rfloor, \lfloor \frac{s\times a_i}{b_j} \rfloor) \le \max(\lfloor \frac{s}{b_j} \rfloor, \lfloor \frac{s\times a_j}{b_i} \rfloor)$。

两边同时除以 $s$ ，乘以 $b_ib_j$，则有：$\max(b_j,a_ib_i) \le \max(b_i,a_jb_j)$。

分两种情况讨论：

$b_j \ge a_ib_i$，此时 $\max$ 可以消掉，$b_j \le a_jb_j$，为假。
$a_ib_i > b_j$，又有 $a_ib_i \ge b_i$，所有左边取的一定是 $a_jb_j$，所以 $a_ib_i \le a_jb_j$。

Buy low sell high

在当前这一天卖出，需要在之前找到一个最小的买入价格。

但是当前决策可能和之前冲突。决策的时候加入一个反悔代价，就可以了。

先前决策价值：$a_j-a_i$
当前决策，反悔先前决策价值：$a_k-a_i - (a_j-a_i) = a_k - a_j$

Olympiad in Programming and Sports

双队伍选择，尝试反悔贪心。

先把其中一队选满，再考虑另一对。

如果 $i$ 没选过，贡献 $b_i$，否则，贡献 $b_i-a_i+a_j$。

开三个优先队列，看看是哪种情况收益大就好了。

感觉比较难理解。

拯救小矮人

首先要确定逃出顺序，使用我们的邻项交换法。

交换操作只会对当前这两人产生影响。看这两人能否逃出就好了。

交换前：$i$ 先 $j$ 后

$i$ 逃出时人梯高度：$s+a_j+a_i+b_i$

$j$ 逃出时人梯高度：$s+a_j+b_j$

交换后：$j$ 先 $i$ 后

$j$ 逃出时人梯高度：$s+a_i+a_j+b_j$

$i$ 逃出时人梯高度：$s+a_i+b_i$

交换后更优，条件是：$\min(a_i+a_j+b_j,a_i+b_i) \ge \min(a_j+a_i+b_i,a_j+b_j)$。

推导一下有：$a_i+\min(a_j+b_j,b_i) \ge a_j+\min(a_i+b_i,b_j)$

分类讨论一下：

$a_j+b_j > b_i$，此时 $a_i+b_i \ge a_j+b_j$，因为 $a_i+b_i$ 不可能大于 $a_i+b_i+a_j$。
$a_j+b_j \le b_i$，此时 $a_i+a_j+b_j \ge a_j+b_j$，理由同上，将 $b_i$ 代入左式不等号不变，所以当 $a_i+b_i \ge a_j+b_j$ 时，交换不劣。

尽可能让 $a_i+b_i$ 小的排在前面。

确定顺序之后，如果当前人逃不出去了，那就在逃出去的人里面拉那个 $a_i$ 最大的来垫背。

反悔贪心捏。

建筑抢修

这种决策的顺序对答案有影响的题目，通常都需要去考虑排序。

考虑邻项交换确定排序规则。交换顺序只对这两项产生影响。

设修理完前面的建筑需要 $s$ 秒。

交换前：先 $i$ 后 $j$

$i$ 建筑：$s+T_i \le L_i$

$j$ 建筑：$s+T_i+T_j \le L_j$

交换后：先 $j$ 后 $i$

$j$ 建筑：$s+T_j \le L_j$

$i$ 建筑：$s+T_i+T_j \le L_i$

交换后更优，猜测排序规则是 $L_i \le L_j$，带入验证，成立。

先选，发现不行就找到之前的建筑，删掉它。

9.10

VP CF 1111 Div.2

B

题意

构造一个长度为 $n$ 的正整数序列 $a$，使得其有一个长度为 $k$ 的连续子序列的和是 $m$ 的倍数，且不存在长度 $< k$ 的和是 $m$ 倍数的连续子序列。

思考

如果 $m<k$ 无解。
先构造出一个长度为 $k$，和等于 $m$ 的子序列。前 $k-1$ 项是 $1$，第 $k$ 项是 $m-k$。
然后选一个 $kx$ 不能整除 $m$ 的数 $x$。发现找不到。
那就一直构造长度为 $k-1$ 的子序列，使他的和 $= m-1$。
这样子除了前 $k$ 项，后面的长度为 $k$ 的区间和都 $< m$。
WA 了两发。。。哦会有 $0$ 的问题，那就使他的和 $= m$ 就好了。
用时 $27$ 分钟（

笔记

区间和考虑前缀和数组，按余数分组。

C

题意

给你一个初始 $01$ 串 $a$ 和目标 $01$ 串 $b$，操作可以选择 $a$ 的一个子序列，要求子序列存在奇数个 $1$，然后将这个子序列取反。问从 $a$ 到 $b$ 最小操作次数。

思考

需要从 $0$ 变 $1$ 的项非常好考虑，所以只需要考虑从 $1$ 变 $0$ 的项就好了。
如果从 $1$ 变 $0$ 的个数刚好是奇数，操作 $1$ 次。从 $1$ 变 $0$ 的个数是偶数且大于 $0$？单独选择一个 $1$ 操作一次，使数量变成奇数。
没有从 $1$ 变 $0$ 的个数呢？此时 $a$ 中的所有 $1$ 都与 $b$ 中的 $1$ 对应。也就是无论怎么调整，都无法生成出一个需要从 $1$ 变 $0$ 的数。无解。
交上去 WA 了？？
哦无解判错了。可以通过献祭一个 $a$ 中的 $1$，使它变成从 $0$ 变 $1$，同时献祭一个 $a$ 中的 $0$，使它变成从 $1$ 到 $0$。
用时 $28$ 分钟。

笔记

双 $01$ 串考虑 $00/01/10/11$ 四种情况

D

题意

$0$-based.

给你一个长度为 $n$ 的正整数序列 $b$。找到一个最小的 $k$，只需要交换 $i \oplus j \le k$ 的数，就可以将其排成一个不降的序列。

Hard version 则需要处理多个单点修改和查询。

$n \le 10^6$

赛时思路

对于一个固定的 $k$，能交换的下标是固定的。
尝试将下标按照二进制最高位分组，同组之间的交换不需要用到最高位，不同组则需要。对于这种直觉出来的东西不要太过信任，如果发现不行应该果断放弃。分组的思路是对的，位运算问题里分组还是很常见的技巧。
发现样例的 $k$ 好像都是 $2$ 的幂？居然猜对了。
如果解锁了当前组，前面的组也会被解锁。
等等，这个是 $0$-based，$0$ 和任何数的异或不是等于它本身吗？那就可以用 $0$ 作为跳板啊。但是用 $0$ 不一定是 $k$ 最小的。用 $0$ 作为跳板这个技巧应该挺常见的来着
解锁了当前组之后，组间可以任意交换，组中第一个数可以和 $0$ 交换，也就是组内任意数都可以和 $0$ 交换。
排序一遍，找到不合理的位置中，下标最大的那个数的二进制最高位就好了。也就是求 $\log$ 向下取整。
WA 了。。。看来还是太 naive 了。
同组交换不需要用到最高位啊，和 $0$ 交换才需要。先把组内的顺序排好，再考虑和组外的交换。感觉可做啊。
$x-1 \oplus x = 2^{lowbti_x}-1$，组内交换可以用 lowbit 做到？假了。。

Eazy version 正确思路

首先固定 $k$，考虑哪些下标可以交换。
小于等于 $k$ 的下标显然可以交换，大于 $k$ 的下标中，如果它们大于 $k$ 的最高位部分相同，那么它们也可以交换。因此发现 $k$ 只有最高位有用，所以 $k$ 是 $2$ 的次幂。
为了描述这种关系，我们将下标按照 $k$ 分组，同一组之间可以任意交换，不同组之间则不行。
所以枚举 $k$，判断不同组之间是不是排好序的就行了。判断方法就是找出组内最大最小值，如果当前组的最小值小于前一组最大值就不行。这个可以 $O(n)$ 做到。时间复杂度 $O(n \log V)$.

Hard version 正确思路

根据 Eazy version，我们开 $k$ 个线段树，维护相邻的逆序对数量，就可以判断区间是否有序，时间复杂度 $O(n\log n\log V)$。
开动一下人类智慧，发现线段树的结构和我们分组的形状很类似。
把数组的长度填成 $2$ 的次幂，那么线段树每一层就对应一个 $k$。堆式存储的线段树上的节点 $u$，它左边的节点是 $u-1$，如果 $u$ 是 $2$ 的次幂，那么它就是最左节点。
维护每一层的相邻节点逆序对数，修改只会影响一条链。于是我们得到了一个 $O(n+n \log n)$ 做法。

贪心专题训练

种树

一个 naive 的做法是把 $a$ 升序排序，取前 $m$ 个，但是可能会取到相邻的。在取的时候加入反悔选项，即 $a_{i-1}+a_{i+1}-a_i$ 即可。需要用链表维护一下左右项。

感觉非常巧妙。

Least Cost Bracket Sequence

先全选右括号，再扫一遍，根据括号序列的前缀约束，在每个不满足约束的位置进行反悔。

Minimize The Integer

题意

$n$ 位的大整数 $a$，只要 $a$ 的相邻两项相同，就可以交换 $a$ 的相邻两项。

求最小 $a$。

思考

和数位有关的，最小的，是个字典序贪心。
按位考虑，一个数只能和右边第一个和它不同奇偶的数交换。
预处理出右边第一个不同奇偶的数，扫一遍就好了。
需要套个并查集维护右边第一个不同奇偶的数。

正确思路

瞄了眼题解，思路比我简洁一万倍啊（
奇偶性相同的点无法改变次序，不同则可以任意改变。
抽成两个序列，搞个类归并就 ok 了。

删数问题

题意

$n$ 位大整数 $a$，从中删除 $k$ 位，求最小 $a$。

思考

数位，最小，字典序贪心。
按位考虑，第一次在 $[n-k,n]$ 中选最靠右的最小值，第二次在 $[n-k-1,$ 上一次选的位置 $-1]$ 中选最靠右的最小值。
暴力即可。线段树也可以做到 $O(n \log n)$。

正确思路

这题解法感觉有很多，挑一个最优雅的学下吧。
只要当 $s_i \ge s_{i+1}$ 时删除 $i$ 是有用的。
维护一个单调栈，如果栈顶元素 $>$ push 的元素，弹掉它。
如果最后 $k$ 还没有用完，弹掉栈顶 $k$ 个即可。
注意前导 $0$ 和 $0$ 的细节。

长野原龙势流星群

题意

$n$ 个节点，以 $1$ 为根的有根树。对于每个 $u$ 找到一个平均值最大的连通块，输出这个平均值。

$n \le 2\times 10^5$

思考

这种平均值问题，很难让人不去二分啊。
二分一下均值，问题就变成，存不存在一个点权和 $> 0$ 的连通块。好像不可做就是了（
点 $u$ 的最大均值和它的子节点有什么关系吗？换根 DP 也未尝不可。好像也不可做就是了（
标签里有二分欸，那再想想。上面两个思路结合起来好像就可做了？
dp[$v$] 表示以 $v$ 为根的子树中，和最大是多少。
如果 dp[root] $> 0$ 则说明二分可行。转移的时候自己一定要选，再选所有 $> 0$ 的子节点就好了。
于是得到了一个 $O(n^2\log V)$ 的做法。
没思路了，开题解！

正确思路

9.11

把前面欠的 $14$ 道题全补了，累死我了。整理了一下笔记。

9.12

VP CF 1108 Div.2

C

题意

给你一个不降的序列 $a$，它的取值要么是 $-1$，要么是正整数。

定义序列 $b$ 的价值为：$b_1-b_2+b_3-b_4…$，问 $a$ 有多少个子序列的价值是 $0$。

$n \le 2\times 10^5$，$a_i = -1\ or\ 1 \le 10^9$

赛时思路

这个 $-1$ 非常奇怪啊，考虑将 $-1$ 和正整数部分分开考虑。
$-1$ 这里可以通过选两个抵消掉价值，也可以通过选一个使价值 $-1$。这里没想清楚啊浪费了时间，以后多想一会儿
所以就是要在正整数部分找到，价值 $= 0$ 和价值 $= 1$ 的序列个数。注意不降性质。
感觉这样不太好考虑，将价值变形一下，$b_1+b_3+b_5…-(b_2+b_4+b_6…)$。
用函数图像感受一下价值，它是一个幅度越来越大折线，和 $0$ 的差距只会越来越大。
所以想让它的价值 $= 0$，就必须是偶数个相同的+偶数个相同的…
想让它的价值 $= 1$，在 $0$ 的基础上偏移一个 $1$ 就好了，开头加上奇数个 $1$。
看眼样例，不对啊。哦选奇数个 $-1$ 的情况会先使价值取相反数再 $-1$。所以需要价值 $= -1$ 的序列。早该看了（
如果想让它的价值 $= -1$，用一个 $x,x+1$ 扰动，那就需要前面有多少个价值 $= 0$ 的，后面有多少个价值 $= 0$ 的，相当于让 $x,x+1$ 选奇数个，其余选偶数个。
具体解法就是，相邻相同段合并，忽略 $-1$ 段，$f[i]$ 表示前 $i$ 项有多少个价值为 $0$ 的子序列，$g[i]$ 表示后 $i$ 项有多少个价值为 $0$ 的子序列。这是好做的。因为 ${i \choose 0} + {i \choose 2} + +… = 2^{i-1}$，递推就好了。
然后处理价值为 $1$ 的子序列个数。如果右边是 $x+1$，那么新增：$f_{i-1}\times g_{i+2}\times 2^{len_i-1}2^{len_{i+1}-1}$ 个。推出来的数学式子要尤其注意能不能化简
然后处理 $-1$ 也是选奇数个还是偶数个的区别了，非常好算。
仔细想想不用处理 $f$，$g$ 数组，因为这个是可以用前后缀和把 $2$ 的指数累加起来的。
再仔细想想发现这个式子的值就等于价值 $= 0$ 的序列个数。
用时 $59$ 分钟，极限。

D

题意

博弈，A 在开始前执行了 $C$ 次 $a_i \leftarrow a_i-1$。

游戏开始， B 先手，每次交换 $a$ 中的任意两个元素。此时若 $a_1$ 是偶数，令开头极大偶数段除以 $2$；若是奇数，令 $a_i \leftarrow a_i-1$。若 $a_i=0$ 就删除它。

B 想要最大化步数，A 想要最小化步数。问最终步数。

$n,a_i \le 10^5$

赛时思路

A 肯定希望 $a_1$ 是偶数，B 相反。$-1$ 操作会使 $1$ 被删除，奇数变偶数。
假如序列已经确定，B 会如何操作呢？看看样例吧。
没找到什么有用的东西啊。放弃了，用时 $20$ 分钟。

正确思路

博弈题先考虑好考虑的策略，这题里面是后手。
序列确定时后手如何操作？自然想到用一个奇数去“卡”掉连续偶数 ÷2。至于为什么不用奇数去换 -1 操作，是因为奇数也会变成偶数，而且偶数的 ÷2 是必然的，区别只是一起 ÷ 还是单独 ÷。
于是先手的策略就是尽可能让奇数晚出现，奇数出现的时刻就是 $a$ 中二进制的最低的 1 的位置。$\log V$ 的循环去枚举这个奇数的位置，计算修改代价。
之后每个数的代价就是，最高位 $1$ 的位数（代表要 ÷ 几次 $2$）+ $1$ 的个数（代表要 - 几次 $1$）。发现还可以通过给每个数进行“微调”以缩小代价，这个微调的量最多到 $2\log V$，总时间复杂度 $O(n \log^2 V)$。

贪心专题训练

Color a Tree

题意

给定一棵有 $N$ 个节点的树，树根为 $R$ ，要给这棵树的所有节点染色。

给点 $i$ 染色的代价为 $t\cdot a_i$，其中 $t$ 代表这是第几次染色，$a_i$ 是给定的权值。

此外，染一个点前，它的父节点必须已染好色（所以根节点 $R$ 一定最先被染色）。求染完这棵树最小的代价。

$1\leq R \leq N\leq 10^3$，$1\leq a_i\leq 500$。

思考

首先想贪心地将权值大的先染色，但是加上了树的结构约束之后就有问题了。
对于权值最大的点 $i$，如果它的父节点被染色了，那么它也一定会在下一步被染色，所以可以把打包成一个节点，节点权值的含义就是：从根节点开始染，需要多少花费。这里还是要想一下对不对的
优先队列存储所有块，如果当前点是连通块的根，就合并它与父节点，如果是树的根则跳过。

正确思考

居然是按照平均值排序。？
这题本质上是在求一个染色的顺序。对于 $x,y,z$，已知 $x,y$ 一定会连续染色，先染哪个比较好呢？（感觉很像邻项交换确定排序规则）
1. 先染 $z$：$z + 2x + 3y$
2. 先染 $x,y$：$x + 2y + 3z$
要比较两式的大小关系，将式子同时加上 $z-y$ 再除以 $2$ 得到：
1. $\frac{2z + 2x + 2y}{2} = z + 2\times(\frac{x+y}{2})$
2. $\frac{x+y}{2}+2z$
所以按照平均值比较。

消防局的设立

题意

$n$ 个节点的树，要在上面选一些特殊点，覆盖整棵树。每个特殊点的覆盖范围是与它距离 $\le 2$ 的点。

至少要多少个特殊点？

$n \le 10^3$

思考

感觉没啥好的直觉。
每个点是不是只会被覆盖一次呢？假了。
想要贪心的话会怎么贪呢？如果这个点能覆盖的点多就优先选它？感觉不是很好。
树的问题考虑链和菊花的情况。
1. 链：在链上 $3$，$8$，$13$ 的位置放最好。
2. 菊花：复杂起来了，得根据链的长度分类讨论了。
要不试试 DP？
$dp[u]$ 表示，以 $u$ 为根的子树全覆盖，最少需要多少个点。要么在点 $u$ 上取一个，要么在 $son[u]$ 取，要么在 $son[son[v]]$ 取。时间复杂度非常充足啊，$O(n^2)$ 肯定可做。
假设在点 $v$ 取，给所有步数为 $2$ 能到达的点打上标记，然后从 $u$ 出发，遇到没打上标记的点，说明这颗子树没有覆盖成功，加上它的覆盖贡献就 ok 了。
然而这个思路是错误的（悲

正确思考

从下往上贪心。
贪心策略是在最深节点的爷爷处放消防站。因为这样不会有浪费。

As far as possible

题意

$n$ 个点的树，边有边权。A，B 博弈，A 选 $k$ 个不同的点，B 要选择一条贯穿这 $k$ 个点的路径，起点终点都是 $1$，可以重复经过某个点，代价定义为边权之和。

A 希望最大化权值，B 希望最小化权值。对于每一个 $k\in [1,n]$ 都输出一个答案。

$n \le 2\times 10^5$。

思考

B 的策略首先是好确定的，先把子树内的处理完，再跳出去处理子树外的。这里方向是对的，再考虑一下下界的话就能得出结论了
这种博弈题一点思考的方向都没有啊（

正确思路

树上回路，回路的边一定走偶数次。
考虑下界，对于点集 $S$，需要经过的路径至少是 $Path(1,v)$ 的并集长度乘 $2$，且一定存在一种方案可以达到下界。
所以选叶子一定不劣。问题转化为：选 $k$ 个叶子，使得 $Path(1,k)$ 的并集最大。
这个问题可以转化为选 $k$ 条不相交的最长链。

总结

博弈题先确定好确定的策略，一般都是先确定后手的。

Mafia

题意

长度为 $n$ 的序列 $a$，每次可以选择一个长度为 $n-1$ 的子序列，使子序列内所有数 $-1$。

问使得序列所有数 $\le 0$ 的最小操作次数。

$n \le 10^5$

思考

直观上感觉与最大值有关，显然最少进行最大值轮。
但是每次还会漏掉一个，漏掉的那个应当是最小值。
每次操作，$n-1$ 个数的相对大小不变，触及到最小值后，次小值和最小值开始轮换。
不太行啊。

正确思考

第一个下界是最大值，找到了。第二个下界是 $\frac{\sum a_i}{n-1}$。
只要满足这两个下界就一定行。证明如下：
合法的方案等价于，每轮分配一个监督者，一共分配 $T$ 个，且每个人最多分配 $T-a_i$ 次。
因为 $T \ge \max a_i$，所以 $T-a_i\ge 0$
因为 $(n-1)T \ge \sum a_i$，所以，$\sum (T-a_i) = nT - \sum a_i \ge T$。

总结

这种取多个下界的最大值，来满足约束的题目还挺常见的来着。

摸鱼

ABC 474 D

题意

给定两个长度为 $n$ 的序列 $a,b$，构造一个 $w$ 序列（$w_i \le 10^{18}$），使得 $\sum\limits_{i=1}^n (a_i-b_i)w_i > 0$。

思考

让 $a_i > b_i$ 的位置填最大的，否则填 $1$。
存在一个大于就可以了，好唐的题（

ABC 474 E

题意

$n$ 个商品，原价 $a_i$，优惠后 $b_i$，原价买可以获得一张优惠卷，优惠买减少一张优惠卷。每种商品至少买一次，问最低金额。

$n \le 2\times 10^5$

思考

感觉能贪心也能 dp。
有优惠肯定会用优惠的，所以就变成了，一半的商品原价，另一半优惠，如果是奇数原价的数量 $+1$。
反悔贪心？先全部原价购买，然后反悔退掉一半，用优惠。
不对哦，一个商品可以买很多次，所以不一定是一半一半的。
那也可以贪啊，要攒优惠券的话一定是买原价最小的那个商品捏。
如果一个商品的优惠价格 $>$ 最小原价商品，那么一定用优惠。
怎么有点像股票买卖？这题就是贪心不用想。

反悔贪心 1

比较 naive 的想法是，一定用优惠的买最小。那么，将先前决策入堆，如果当前优惠劵不够了，那就退掉前面一个用优惠的，或者买一个最小原价商品。
1. 原价：$a$ 并且优惠券 $+1$，$b-a$ 入原价堆
2. 退掉前面：$b + q.top()$，$a-b$ 入堆
3. 买一个最小原价：$mn+b$
优先用 $2$，$3$，如果 $2$，$3$ 代价 $> a$ 那就用 $a$。
最后如果有剩下的优惠券，就退掉原价堆最小的几个。
但是这里有个问题，就是最小原价商品实际上可以不单独买。感觉绝对想复杂了。

反悔贪心 2

如果一个商品只能买一次很好做，只有原价最少商品会买多次。它最多被买 $n$ 次啊。
所以先假设它没有被买多次做一遍反悔贪心，然后，在原价堆里，一直用它最小商品替换。
AC 了好玩好玩。

总结

关键洞察：刷票一定用原价最少的那个刷，其他都只买一次。
之后的贪心就很自然了。

然后打了一场 ABC 475，切掉 F 了嘿嘿。

9.13

VP CF 1106 Div.2

C

题意

$n$ 个节点的有根树，定义点集 $G(u,h)$ 表示，以 $u$ 为根的子树中，距离等于 $h$ 的点的集合。

问有多少个不同的非空 $G$。

$n \le 2\times 10^5$

赛时思路

感觉和层数，分叉数有点关系。先把单独的每个点算上。
试想，如果点 $u$ 只有 $v$ 一个儿子，那它能造成的贡献和 $v$ 完全一致。没啥用啊感觉。
按层数考虑。这一层的节点能被划分为多少个不同点集？要看节点 $1$ 的子节点有多少个深度大于 $h$ 的子树。要跑一个深搜才能算出来总个数啊。这里本质在拆贡献，直接按照层数发现不好拆，就应该换了。
好像跑一遍深搜就好了。维护 $ans[u]$ 表示深度为 $u$ 的节点能被划分为多少个不同点集，初始 $ans[0]$ 为 $1$。遇到一颗子树，如果它有两条以上的深度 $\ge h$ 的分支，那么就对 $h$ 层贡献：$ans[h] \leftarrow ans[h]+$ 分支数，对 $ans$ 做个前缀和就可以了。这里没考虑清楚啊，有点乱了。
再做一遍累加。
好像假了。放弃了，$60$ 分钟。

正确思路

考虑每个节点能产生多少新贡献。
如果没有重复，那么会产生 $(\max dep_v)-d+1$ 的贡献，其中 $dep_v$ 是子树 $v$ 向下最深层。
但是这样会有重复。考虑重复如何发生。对于某一层 $h$，如果 $G(u,h)$ 与 $u$ 的父亲的 $G(p,k)$ 相同，那就发生了重复。重复的原因在于，$p$ 没有除了 $u$ 以外的第二个深度 $\ge h$ 的子树。如果有两颗以上的子树，那么就一定不会发生重复。
因此每个点的贡献可表达为 $次大深度-d+1$。

总结

感觉拆贡献的时候还是先从平凡的角度拆。点，边啊之类的。不行了再去拆特别的，比如层数之类的。
当然也不是绝对吧，感觉哪个可做就先试哪个了就肯定是先想好有大概很多个方向可以尝试，再去深度搜索。贸然推进风险很大的。有了一个方向之后，再好好想想，能不能想到另一个，花几分钟时间思考一下别的大方向还是很有益处的。慢即快。

D

题意

将 $n$ 的因子分成最小的层数，满足以下条件：

若 $x$ 是 $y$ 的因子，那么 $x$ 必须在 $y$ 这一层之前出现
同一层之间，相邻两个数的 $\gcd > 1$。

求最小层数。$n \le 10^6$。

赛时思路

先从简单的情况考虑，$n$ 一定在最后独占一层。
然后考虑前一层，将 $n$ 的所有因子质因数分解，同一层的因子的指数最多比上一层 $-1$（$-2$ 的话 $-1$ 的那个因子就无处安放了），并且同一层之间，每个因数最多只有一个指数 $-1$，否则的话就会成为另一个因数的因数。
所以每一层只能使指数 $-1$，并且每个质因子只能单独放一层，最少指数和 $+$ 质因子个数层。

VP CF 1105 Div.2

B

题意

构造一个 $n \times m$ 的 $01$ 矩阵，要求其中所有的 $r \times c$ 的子矩阵，满足矩阵异或和等于 $0$。

求这样的 $01$ 矩阵有多少个。

$n,m,r,c \le 10^9$

赛时思路

矩阵异或和等于 $0$ 等价于矩阵内有偶数个 $1$。
瞄一眼样例，答案和 $2$ 的次幂有关。
没思路了啊。用时 $16$ 分钟。

正确思路

发现对于一个 $r \times c$ 的矩阵，可以通过一项决定矩阵的异或和，其他都可以随便选。
因此能够随便选的点的个数就是 $nm-(n-r+1)(m-c+1)$。

总结

感觉还是对于这种，只需要一个项就可以决定位运算的模型不熟悉，记下吧。

C

题意

博弈题。初始时有一个长度为 $n$ 的序列 $a$。

A 先手，每一回合里需要选择一个长度为 $n$ 的序列 $b$，满足：

$b_i \le a_i$
$b$ 不能全是 $0$.
$b$ 的异或和是 $0$. 对这个约束有误解。这并不意味着数需要成对出现，只需要二进制的每一位是偶数个就可以了。

选不出序列就输了。选出序列之后，令 $a_i \leftarrow a_i - b_i$。

第一回合里，A 有多少种序列，可以让他必胜？

$n \le 10^6$。

赛时思路

考虑什么样才是输的局面。$a$ 全 $0$ 显然输，只有 $1$ 个非 $0$ 显然输。
这时候发现进行的轮数其实很少？每次可以让非 $0$ 个数至少减半。
考虑简单的情况？如果序列长度是 $1$，A 必输；序列长度是 $2$，A 此时只能令 $b_1=b_2=$ 最小值，否则 $B$ 就可以赢。序列长度是 $3$，A 不希望 $B$ 有 $2$ 个非 $0$ 元素，所以要么此时存在一组相同的数，要么？
想不出来可以一步逼死对方的策略啊，想出来这个这题就结束了。
首先长度为 $2$ 时策略是固定的。长度为 $3$ 时，如果 $a$ 是 $123$，下一步必然会使得 $a$ 的长度变成 $2$，也就是必败，但是不存在什么一步策略使序列变成这样啊。放弃了。用时 $29$ 分钟。

正确思路

问有多少种必胜序列，考虑必胜/必败态。如果单纯只是问能不能必胜，那就不一定需要考虑。
研究一下什么样的序列是必败的。要么全 $0$ 序列，要么只剩下一个非 $0$ 元素。现在要证明，不是这种情况就是必胜的，这个命题等价于找到一个 $X \oplus a_i \le a_i$，其中 $X=a_1\oplus a_2…a_n$。
找到 $X$ 的最高位 $h$，必然存在一个 $a_i$ 第 $h$ 位是 1，此时 $X\oplus a_i \le a_i$ 必然成立。因此 A 必须也只需要生成一个全 $0$ 序列或者存在一个非 $0$ 元素的序列就能取胜。
找到有多少个 $a_i$ 满足条件即可。

D

题意

$n$ 个人围成一圈，每个人可以看到左边 $d$ 个人和右边 $d$ 个人。

现在要给这些人发礼物。

如果它收到了礼物，并且它视野中有 $x$ 个人没收到，增加 $x\times a_i$ 的幸福度。

如果它没收到礼物，并且它视野中有 $x$ 个人收到了，减少 $x\times a_i$ 的幸福度。

要最大化幸福度。$n \le 2\times 10^5$。

赛时思路

我怎么感觉这题我做过。现在每个人的贡献和其他人有关，我们要把它独立出来。
假设一开始没有人拿到礼物，现在第 $i$ 个人拿到了，造成的影响是：
1. 对于视野范围内拿到了礼物的人，减少了 $a_j$，增加了 $a_i$，总共变化 $\sum a_i-a_j$
2. 对于视野范围内没有拿到礼物的人，减少了 $a_j$ 增加了 $a_i$，总共变化 $\sum a_i-a_j$
3. 求和一下，发现式子只与区间权值和和当前点权值有关。
给 $i$ 点的人发礼物，造成的贡献是：$2d\times a_i-(sum[i+d]-sum[i-d-1])+a_i = (2d+1)a_i-sum[i+d]+sum[i-d-1]$，记得扩环成链。

总结

本质 01 串问题，这题其实就是把贡献都拆到了 1 上面。

树论专题训练

知识积累

重心的定义

删去重心后，剩下连通块的最大大小不超过总结点数的一半
删去重心后，得到的最大联通分量最小
树中节点到重心的距离和最小

重心的性质

树的最多有两个重心，且相邻。
给树添加/删除一个叶子，重心至多移动一条边。
两颗树连在一起，新重心在原重心的路径上。
重心在从根开始的重链上。

重心的求法

dfs 统计所有子树的 $sz$，遍历每个点根据定义 $1$ 找重心。
跑一遍 dfs 找到当前点到所有其他点的距离和，然后换根。

医院设置

题意

给你一颗 $n$ 个点的带权树，找一个点 $u$，使 $\sum\limits a_i\times dist(i,u)$ 最小。

正确思考

大胆猜测 $u$ 点就是树的重心，考虑调整法证明。
假设最优的点是 $u$ 且 $u$ 不是树的重心，那么，$u$ 必然存在一个子节点，使得 $sz[v] \ge \frac{S}{2}$，其中 $S$ 是总权值和。将 $u$ 调整到这个 $v$ 上面，增加了 $S-sz[v]-sz[v]=S-2sz[v] \le 0$，调整后不劣，且最终一定调整到重心的位置上。
然后求一个带权树重心。稍微归纳一下，这类问题就叫做 “树上货舱选址”？

Link Cut Centroids

题意

给定一棵节点数为 n 的树，删一条边然后加上一条边，使得该树的重心唯一。（删掉的边和加上的边可以是同一条。）

$n \le 10^5$。

正确思考

只有一个重心的时候随便弄。
两个重心的时候，两个重心各自的子树大小等于 $\frac{n}{2}$，所以让它们的大小不等就好了，具体方法就是移动一个重心的子节点给另一个重心。

树的重心

题意

$n$ 个节点的树，定义边 $(u,v)$ 的价值为：去掉边 $(u,v)$ 后，形成的两颗子树的重心编号之和。

$n \le 10^6$

思考

要么把贡献拆到边上，要么拆到点上嘛。
把贡献拆到边上，本质上还是把贡献拆到子树上。
深搜其中一颗子树的根节点，考虑在深搜过程中维护这个子树的重心。维护两个东西，$child[u]$ 表示 $u$ 的子节点中的最大 $sz$；$rest[u]$ 表示，$子树节点总数-\sum\limits_{v\in G[u]}sz[v]$。这个可以通过 dfs 序+线段树维护。然后找到其中 $\max(child[u],rest[u]) \le \frac{节点总数}{2}$ 的 $u$ 的编号，这个可以通过查询区间最小值得到，检查一下与 $u$ 相邻的点，这个是常数级别的，做到这里大概是 $O(n \log n)$。
考虑维护外面那颗子树的重心。本质是一样的，不过一边是不断加，另一边是不断减罢了，是对称的。于是得到一个 $O(n \log n+常数\log n)$ 的算法，不知道能不能乱搞过去（

正解

求所有子树的重心可以 $O(n)$ 做，详见 CF685B。
难点在于另一个部分的重心怎么求。分类讨论一下：
1. 倘若我们遍历到的 $u$ 点不在原树的重链上，那么另一部分的重心还在原来的重链上，直接倍增就可以了，因为 $n-sz[v]$ 和 $sz[son[v]]$ 具有单调性。
2. 倘若 $u$ 点在原树的重链上，那么另一部分的重链可能发生变化。
  1. 原重儿子—>重儿子–>…–> 次重儿子 ($u$ 造成的影响) --> 重儿子…
  2. 原次重儿子–>重儿子–>…
对于情况 2，无法确定在什么时候转向次重儿子，所以不好考虑。如果我们钦定这个“拐点”就是根这里呢？
直观理解一下，这就是让所有儿子的 $sz$ 尽可能接近，这不就是重心的性质嘛。
所以我们钦定原树的重心为根，若 $u$ 在原树的重链上，则重儿子会少掉一部分，此时的重心要么还是原来的根，要么往次重儿子移动，倍增即可。
实现细节：
1. 封装两个函数：
  1. 根据一个重心找另一个重心
  2. 从重链的叶子出发，倍增找子树 $u$ 的重心。

逃学的小孩 / 数据生成器

题意

$n$ 个节点的带权树，找到三个点 $A,B,C$，满足 $dist(C,A) \le dist(C,B)$ 且使得 $dist(C,A)+dist(A,B)$ 最大。

$n \le 2\times 10^5$.

思考

根据式子可以得到：$dist(C,B) \le dist(C,A)+dist(A,B)$。好像没啥用。
仔细考虑这个过程，从 $C$ 出发走到 $A$，如果 $A$ 回头走，就有 $dist(C,A) > dist(C,B)$ 的风险，如果 $A$ 往外走，就没有这个风险。整个过程和找直径很像啊。
如果 $A$ 没有往回走，那么答案显然是 $dist(C,A)+直径长度$，$A,B$ 是直径端点。
如果 $A$ 往回走走到了 $B$，且 $dist(C,B) > dist(C,A)$，那么此时交换 $A,B$ 的顺序，也是合法答案。
大概理解了这个过程，对于一个点 $C$，从它出发的最大值怎么找呢？首先随便找一条路径 $dist(A,B)$，然后再加上 $\min(dist(C,A),dist(C,B))$。
感觉没啥进展啊，开题解吧。

正解

求式子：$ans=dist(A,B)+\max\min(dist(A,C),dist(B,C))$ 的最大值。
考虑当 $dist(A,B)$ 取到最大值时，另一项能否取到最大值。证明很麻烦，直接猜测结果是对的吧（
大不了打个拍。

总结

感觉还是少了点贪心直觉吧。这种式子应该反应过来，取一边最大值时，另一边也能达到最大。