Creator's World

凡事总须研究，才会明白。古来时常 偷学，我也还记得，可是不甚清楚。我翻开历史一查，这历史没有年代，歪歪斜斜的每叶上都写着“颓废划水”几个字。我横竖睡不着，仔细看了半夜，才从字缝里看出字来，满本都写着两个字是“偷学”！

6.25

CF1526C2 Potions (Hard Version)

反悔贪心。

一开始没考虑单调性直接二分结果伪了。正解是反悔贪心，我们用一个 $sum$ 值存当前的总和，一个小根堆存序列，每当 $sum<0$ 的时候就让 $sum$ 减去堆顶元素，答案减一。

CF1526B I Hate 1111

最后我们发现每个全部为 $1$ 的数都可以表示为 $11\times x + 111\times y$，$111 = 10\times 11 + 1$，那么原式化为 $11\times x + (10\times 11 + 1)\times y=11\times(x+10\times y)+y$，那么 $n$ 取余后乘上 $111$ 判断是否小于 $n$。

CF1526A Mean Inequality

我们为了保证不会出现题目中的情况，我们按照最大、最小、次大、次小 $\cdots$ 来排，就不会出现。

CF1409E Two Platforms

dp。

首先一个平台从每个点开始最多能接到的点可以通过移动指针 $O(n)$ 求出来，然后考虑两个平台怎么接到最多的点，若第一个平台范围是 $[l,r]$，那么第二个平台就是 $[r+1,n]$ 中的最大值，那么求一个后缀最大值就可以了。

CF1413C Perform Easily

双指针。

首先直接暴力求出所有可能，然后从小到大排序，再用双指针，当 $[l,r]$ 所有编号都出现了，那么说明是合法的，更新答案。

CF1537E2 Erase and Extend (Hard Version)

贪心。

思路同下，但我们需要线性的算法。考虑当前答案长度为 $ans$，枚举到第 $i$ 位，我们分类讨论：

若 $s_i>s_{i\mod ans}$，那么后面不可能成为答案，直接退出；

若 $s_i<s_{i\mod ans}$，那么 $ans = i$。

CF1537E1 Erase and Extend (Easy Version)

贪心。

首先一定是先用操作一再用操作二的，因为若 $s'>s$，那么 $s's'>ss'$。因此我们直接枚举前缀，找将其复制后字典序最大的即可。

6.24

CF1537D Deleting Divisors

博弈论。

打表找规律是非常好用的考场策略，可以发现先手必败情况如下：

• $n$ 为奇数；

• $n = 2^{k}$，$k$ 为奇数。

否则一定必胜。证明见 题解。

CF1537C Challenging Cliffs

贪心。

考虑什么时候 $h_i\leq h_{i+1}$ 的个数最多，显然将 $h$ 从小到大排序后最多。然后再找高度差最小的地方，以此为断点。

CF1537B Bad Boy

走最多距离显然走一圈外圈，那么放在 $(1,1),(n,m)$ 即可。

CF1415D XOR-gun

暴力、鸽巢定理。

考虑三个数 $1$ 的最高位都是同一位，那么异或前两个一定会破坏序列的不降。若不存在一次就破坏的情况，那说明 $1$ 的最高位是同一位的最多 $2$ 个，根据鸽巢原理，由于 $a_i\leq 1e9$，所以这种情况 $n\leq 60$，所以直接暴力做就好了。

CF1426E Rock, Paper, Scissors

贪心、性质。

首先最大胜场很好考虑，显然是 $\min(a_1,b_2) + \min(a_2,b_3)+ \min(a_3,b_1)$。然后考虑最小胜场，显然是 $n-\text{最多非胜场}$，而最多非胜场的话为 $\min(a_1,n-b_2)+\min(a_2,n-b_3)+\min(a_3,n-b_1)$。

CF1427C The Hard Work of Paparazzi

dp。

首先有个很显然的 $n^2$ 暴力 dp，然后考虑怎么优化，这个 $r\leq 500$ 肯定不对劲，一定是 $r$ 为突破口来优化的，想到这里就没想法了。但其实我们再深入思考一下，我们发现用 $2\times r$ 的时间是可以从一个地方走到另一个任何地方的，那么我们只要枚举每个状态的前 $2\times r$ 个转移即可，至于小于 $2\times r$ 的话，那再开个变量存一下就好了。

CF1427D Unshuffling a Deck

构造、贪心。

感觉 cf 挺多构造题的。既然题目都告诉你做多操作 $n$ 次，那么我们就去想怎么用 $n$ 次将卡牌排好序。我们发现可以根据排序次数的奇偶性来操作，奇数时我们让数列尽量升序，偶数时尽量降序，那么这样每次操作都会产生至少一点贡献，最多 $n$ 次完成。

CF1428D Bouncing Boomerangs

构造、贪心。

其实自己想了一会之后有想法的：直接按 $a_i$ 分类讨论：

• $a_i=1$ 的话直接开一行就行了，优先和前面 $a_i=2$ 的情况配对。

• $a_i=2$ 的话要占一整行。

• $a_i=3$ 的话要占一整行，同时还要占一整列。

但是实现上有些问题。其实直接用一个 $h$ 表示现在在第几行了，$last$ 表示上一次 $a_i$ 是几，用个队列存一下 $a_i=2$ 时要占的行就可以了。还是要多熟悉熟悉构造题。

6.23

CF1454E Number of Simple Paths

dfs、容斥、基环树。

我们可以知道若在同一个环中答案是 $\frac{n\times (n-1)}{2} \times 2 = n\times (n - 1)$，那么只要减去只有一条简单路径的条数就可以了。显然是环上每个点和它的子树中的点构成的简单路径只有一条。

CF1442A Extreme Subtraction

差分。

考虑差分，$1\sim k$ 都加上 $-1$，相当于 $diff_1-1,diff_{k+1}+1$。$k\sim n$ 都加上 $-1$，相当于 $diff_k-1,diff_{n+1}+1$。那么第二个操作可以让所有大于 $0$ 的变成 $0$，只要考虑能否让小于 $0$ 的变成 $0$ 即可，只要判断所有小于 $0$ 的绝对值和 $diif_1$ 的大小关系就好了。

CF1437C Chef Monocarp

dp。

可以想象成一个背包问题，$T$ 是物品，菜品是体积，每个物品都会占用一个体积，其价值为 $\operatorname{abs}(T-t_i)$，然后跑 01 背包就好了。

CF1430E String Reversal

逆序对。

首先有个套路：这种求交换相邻元素次数的一般就是求逆序对个数。那么我们有个想法：生成原字符串的目标序列，然后求逆序对即可。关键是本题有相同元素，我们为了让逆序对更少，尽量让序列升序，可以用个二维数组存。

CF1439A2 Binary Table (Hard Version)

构造、模拟。

对于前 $n-2$ 行，我们考虑对于每一个 $1$ 把它变成 $0$ 且不要影响前面的，那么就把它变成 $0$ 然后后面随便变就行了。对于 $n-1$ 和 $n$，因为后面没有可以变了，所以对于每一列若它们都是 $1$ 就把它变成 $0$。然后对于最后的 $2\times 2$ 矩阵，可以用最多四步把它全变为 $0$。

CF1452B Toy Blocks

要 $n-1$ 个盒子都相等，那么总和一定是 $n-1$ 的倍数，这是第一个限制条件。然后考虑怎么让 $n-1$ 个盒子都相等，那么最坏就是剩下最大值的情况，那么就是要让所有都变成最大值，取个 $\max$ 即可。

CF1452D Radio Towers

递推、找规律。

首先这种期望的题目显然是 $\frac{\text{合法方案}}{\text{总方案}}$，那么这里总方案就是 $2^n$，考虑合法方案个数，先手玩一下小数据发现似乎满足斐波那契数列的规律，那么就直接求就好了。不过找规律还是有点不靠谱的。

6.22

CF1468J Road Reform

最小生成树。

首先我们分两种情况考虑：一是生成树中有边大于 $k$，它们的边权都是 $w - k$，那么小于 $k$ 的边都相当于 $0$，跑最小生成树就好了；二是生成树没有边大于 $k$，那么就加上最小的 $k - w$ 即可。

CF1475D Cleaning the Phone

二分。

一眼就是个背包，但是看数据范围就知道一定不可能，那么一定有什么特殊条件来帮助我们解题。体积只有 $1$ 和 $2$ 两种可能，本来想的是直接二分，但是因为奇数偶数不同所以没有单调性。因此我们考虑枚举选几个 $2$，然后再二分选满足条件且最小的 $1$。

CF1466E Apollo versus Pan

二进制。

按位考虑经典题型。一开始推出来了式子，将题目转化为怎么快速求 $\sum_{i=1}^na_x \& a_i$ 和 $\sum_{i=1}^na_x \operatorname{|} a_i$，然后思考位运算的本质，考虑按位计算。每一位的 $1$ 都会对 & 的总和产生这一位 $1$ 的个数的贡献，对 | 的总和产生 $n$ 的贡献；每一位的 $0$ 都会对 | 的总和产生这一位 $1$ 的个数的贡献。

CF1462F The Treasure of The Segments

二分。

有个很显然的想法，枚举每一条线段然后钦定它为满足条件的线段，然后再二分求出没有覆盖的线段取最小值就好了。至于没有覆盖的，就是 $l$ 比 $r$ 大，或是 $r$ 比 $l$ 小。

6.20

P4101 [HEOI2014]人人尽说江南好

博弈论。

可以证明一定会拖到最后，那么只要计算最多的合并次数，再判断奇偶就行了。至于最多合并次数的话，显然最后会变成形如 $\{m,m,m,m,\cdots,n\%m\}$，合并成 $x$ 需要 $x-1$ 次，那么次数就是 $(n/m)\times (m-1)+\max(n\%m-1,0)$

P4136 谁能赢呢？

博弈论。

显然要走完所有格子，那么判断奇偶行即可。

CF1475G Strange Beauty

dp。

从小到大排，然后对于每个数枚举它的因子，求最长的满足条件的序列即可。

CF1475F Unusual Matrix

根据异或的性质，我们考虑将两个矩阵异或起来，然后就是要让产生的矩阵全变为 $0$。那就很简单了，先第一行垂直异或全变为 $0$，然后判断每一行是不是都是 $0$ 或 $1$ 即可。

6.19

CF1038C Gambling

博弈论。

两个序列，每个序列从大到小排。然后根据奇偶行判断现在是谁的回合，接着判断两个序列中队首的大小来计算是要选自己的还是让对面选下一个。

P2210 Haywire

模拟退火。

直接模拟退火，没什么好说的。

P3936 Coloring

模拟退火。

直接模拟退火随机化格子就好了，贡献很容易算。本题不一样的是记录了三个值：现在的值、旧的值、答案。每次求差值都是和旧的值取，同时每次退火旧的值都要取答案，我就是这里没写一直 $99$ 分的。

P2985 [USACO10FEB]Chocolate Eating S

二分。

求最小值的最大值，显然用二分。check 的话就贪心地每天选到最低值。输出方案的话就和 check 类似。

6.18

P1199 [NOIP2010 普及组] 三国游戏

博弈论、贪心。

显然当小涵选了一个武将后他一定选不到最大默契值，那就选次大默契值。然后到了电脑一样，它也选不到它的最大默契值，只能选次大默契值，那么一定会小于小涵的。

6.17

P3951 [NOIP2017 提高组] 小凯的疑惑 / [蓝桥杯 2013 省] 买不到的数目

数论。

直接打表找规律也可以找到，严格的证明看题解。

CF1535D Playoff Tournament

两支队伍 $i$ 和 $j$（设 $i<j$） 在第 $k$ 张比赛相遇，若 $s_k$ 为 "0"，$f_k=f_i$；若 $s_k$ 为 "1"，$f_k=f_j$；若 $s_k$ 为 "?"，$f_k=f_i+f_j$。然后用线段树维护即可。

CF1536D Omkar and Medians

set、二分。

首先一个数 $x$ 是 $2\times i - 1$ 个数的中位数，需要满足有 $i-1$ 个数比 $x$ 大，$i-1$ 个数比 $x$ 小。

然后我们考虑 $b_i$ 和 $b_{i-1}$ 的关系，根据关系维护 set 来判断。

P2538 [SCOI2008]城堡

模拟退火。

先预处理出每两个点间的最短路，然后直接随机序列，前 $k$ 个城市要修城堡。

P3391 【模板】文艺平衡树

splay。

AT5294 [ABC151F] Enclose All

最小覆盖圆。

[SP18185 GIVEAWAY - Give Away](https://www.luogu.com.cn/problem/SP18185)

分块。

基础题。

P5544 [JSOI2016]炸弹攻击1

模拟退火。

像这种坐标系上求最优解，没想法直接考虑模拟退火。随机生成点，然后半径要取 $R$ 和点到房子圆心的距离减去半径的最小值，保证不会接触建筑，然后再求消灭多少敌人。

UVA11020 Efficient Solutions

用 multiset 维护，每次新加入一个点判断他是否优势，有的话还要删去没有优势的点。

6.16

CF1503A Balance the Bits

构造。

首先考虑显然的无解情况：两端不是 $1$；$1$ 的个数不是偶数。然后有解的话为了满足两个括号序列都合法，我们让左半部分的 $1$ 都是 (，右半部分的 $1$ 都是 )，然后 $0$ 的话 ( 和 ) 交替进行。

CF1504B Flip the Bits

首先容易发现相同的要进行偶数次操作，不同的要进行奇数次操作。不过每次操作都是 $1\sim i$，正着做我们不知道后面有哪些操作，因此我们考虑反着做。

CF1504A Déjà Vu

显然找到一个不是 a 的放在它的相对位置即可。

CF1477B Nezzar and Binary String

线段树。

本题最重要的就是逆向思维。我们发现正着做非常困难，因为每次操作都要考虑后面的情况，不可做不可做……等等，都要考虑后面的情况……那不是到着做就好做了吗？因此我们考虑从后往前操作，尝试将目标串变会原始串，那么这样每次操作都是唯一的。通过线段树维护区间 $1$ 的个数，然后判断其和区间长度一半的大小关系，等于一半的话没法修改，否则的话修改小的那个。

6.15

CF802B Heidi and Library (medium)

堆优化贪心。

感觉贪心还是很好想到的：考虑扔掉那本书收益更大，显然是扔下一次出现在比较后面的那本。但是我只会感性理解，证明还是不会。然后就可以堆优化贪心，但是本题中相同元素的 $nxt$ 是要更新的，一开始不知道怎么做，后来发现其实每次都加进堆里即可，不会对答案产生影响，因为相同元素在前面的 $nxt$ 肯定小，肯定会一直在后面。

CF1479B2 Painting the Array II

贪心。

求最大值，本质和下面还是一样的。

CF1479B1 Painting the Array I

贪心。

我们按照下面两个原则进行贪心：

1. 若 $a_{x}$ 和 $a_{y}$ 中有一个和 $a_i$ 相同，则放在另一端。（都相同随便放）。

   因为这样不会对后面答案产生影响，同时使答案避免减 $1$。

2. 若 $a_x$ 和 $a_y$ 都不等于 $a_i$，设 $nxt_i$ 为 $a_i$ 下一次出现位置，放在 $nxt$ 较小的那一段。

   感性认知一下，我们要避免相同的放在一起，$nxt$ 小的说明要尽快用不同元素将它们隔开，大的后面有更多其他可能。

CF1481D AB Graph

构造。

像这种构造题我们就大力分类讨论。首先若 $m$ 是奇数的话，直接在一条边上来回走即可。若 $m$ 是偶数，有相同的边来回走即可；若 $n=2$ 无解；否则的话我们考虑构造一个三元环上走，发现满足回文的话只要出现两个字符相同即可，而三元环根据鸽巢定理，一定可以找到，然后构造即可。

P1337 [JSOI2004]平衡点 / 吊打XXX

模拟退火。

学了下模拟退火，发现还是挺好理解的，就是随机化然后找最优解，不过要注意一些特殊的东西：比如初温、降温等。不过不知道为什么多跑几遍就会超时，只跑一遍居然对了，有些神奇。

CF1404B Tree Tag

博弈论、搜索、树的直径。

博弈论上手两步：一手玩样例；二考虑极端情况。考虑一下发现，若是每次 B 都能逃脱 A 的范围，那么 A 就永远抓不到 B，否则的话可以抓到。那么很容易考虑极端情况：A 下一步就可以到达 B，有以下两种可能

1. $2\times da \geq \min(db,len)$

   $len$ 为树的直径，$\min(db,len)$ 是 B 一步最多走的距离。那么 A 先手走一步，B 不管怎么走，A 下一步都可以到达 B。

2. $da\geq \operatorname{dis}(a,b)$

    也就是走一步就到了。
   

P2503 [HAOI2006]均分数据

模拟退火、dp。

发现模拟退火真是个好东西，这道题目若要求直接用 dp 求很麻烦，因为其要求的是任意排列中的最小值，若只要求一个固定序列的连续值的话很好求。方法在 P2217 [HAOI2007]分割矩阵 中见过，直接 dp 转移即可。因此我们考虑随机化，用模拟退火来随机生成序列。

P3878 [TJOI2010]分金币

模拟退火。

感觉题意不是很清楚，提议明确后还是很简单的，直接分为两个部分，然后模拟退火随机化序列即可。

6.14

P1742 最小圆覆盖

计算几何。

最小圆覆盖也还好理解，关键思想是三点确定一个圆。不过我用的是解析几何的方法求圆心坐标的（也就是解方程）而不是计算几何（也就是什么旋转什么的），因为自己旋转这方面没去看懂，还是要都会才行。还有时间复杂度为什么是 $O(n)$ 的也没有搞懂，还要去看。

6.10

[CF380C Sereja and Brackets](CF380C Sereja and Brackets)

线段树。

要求一个区间所有 子序列 中最长的合法括号序列长度。发现直接维护区间最长合法括号序列长度非常难，正难则反，我们发现维护区间不匹配的左右括号很好做，直接用线段树做。用左右子树更新父亲的时候，失配的左右括号要减去左子树失配的左括号和右子树失配的右括号个数中的最小值，因为这是匹配上的括号个数。

6.8

CF13E Holes

分块。

弹飞绵羊的双倍经验。

6.7

CF1493C K-beautiful Strings

因为字典序又要比原字符大又要尽量小，那么从后面枚举变哪位。同时开桶记录出现次数即可。

6.6

CF1509C The Sports Festival

区间 dp。

首先容易发现大的区间的值是可以确定的，然后放最后一位的一定是最大的或最小的，那么数学归纳法我们可以得出结论：每次新加一个新的数一定是最大的或最小的数。因此我们将数组从小到大排序，然后就可以区间 dp。

CF1508B Almost Sorted

递归、二分。

先观察一下发现一些性质，然后这种求第 $k$ 字典序的可以考虑递归 $+$ 二分。

CF1493C K-beautiful Strings

直接从后往前枚举，然后考虑将当前这位变大，然后判断。

6.5

CF1513D GCD and MST

其实还是简单的。自己有了思路，但是却缺乏将思路实践的能力，这个还是很重要的。首先一段数的 $\gcd$ 等于这段数的最小值，那么显然这段数每个数都是最小数的倍数。因此从小到大排序，然后双指针向两边扩展即可。

CF1514D Cut and Stick

众数。

首先根据题意发现只跟出现次数最多的数，也就是众数相关。然后我们发现，若一个区间满足条件，设其有 $a_i$ 个众数，则区间一定要有 $a_i-1$ 个非众数。设总共有 $x$ 个众数，有 $n-x$ 个非众数，分成 $t$ 组，每组有 $a_i$ 个众数，那么有 $\sum_{i=1}^t a_i=x,\sum_{i=1}^t a_i-1\leq n-x$，那么有 $t\geq 2\times x - n$。众数直接用分块来求。还有 $1$ 的情况。

CF1525C Robot Collisions

栈。

首先有个很显然的性质：只有奇偶性相同的才有可能撞到一起。我们再观察一下，发现若不考虑反弹，那这不就是括号匹配吗？直接用栈来做。最后再处理反弹的情况。

CF1525D Armchairs

线性 dp。

首先我们思考性质：对于两个人 $a\leq b$，有两个椅子 $c\leq d$，那么 $a\rightarrow c$ 和 $b\rightarrow d$ 一定不劣。因此我们可以设 $f_{i,j}$ 表示前 $i$ 个人做前 $j$ 个椅子的最小移动距离，那么转移式子很显然

$f_{i,j}=\min(f_{i-1,j},f_{i-1,j-1}+\operatorname{abs}(pos_i-pos_j))$

P1606 [USACO07FEB]Lilypad Pond G

最短路计数。

首先容易将题目转化为最短路计数问题：将和 $0$ 的连边权值为 $1$，与 $1$ 的连边权值为 $0$，然后跑最短路，同时开个 $f$ 数组计数。不过本题有个很值得思考的细节，那就是 dijkstra 最短路计数边权不能为 $0$！因为这样会出现计数不完整。而若是正边权，那么在优先队列中前面的点一定在前面，一定会更新完全。

UVA11270 Tiling Dominoes

状压 dp。

状压 dp 的经典模型（或者说是轮廓线 dp 的模板）。首先考虑无解的情况，显然 $n,m$ 都是奇数的时候无解。数据范围 $n\times m \leq 100$，显然 $n,m$ 中小的那个不超过 $10$，考虑对小的那个进行状压。然后我们发现只要确定了竖放的情况剩下的都要用横放来补满，因此我们只考虑竖放。设 $f_{i,S}$ 表示第 $i$ 行竖放的状态为 $S$ 的方案，$1$ 表示放，$0$ 表示不放。然后得到转移 $f_{i,S}+=f_{i-1,S_{last}}$。

当然不可能这样直接转移，我们还要考虑转移是否合法。首先这一行和上一行不能有重叠，即 $S$ & $S_{last}$ 为 $0$。同时这一行填满后应该可以用竖放来填满，这个我们可以预处理出每个状态是否合法，然后只要判断 $S$ $|$ $S_{last}$ 是否合法即可。

6.4

CF1520D Same Differences

偶然找到了之前模拟赛的题目。移动式子，然后直接用 map 存即可。

CF1500A Going Home

鸽巢原理。

直接暴力枚举即可，但时间复杂度并不是 $O(n^2)$ 的，而是 $O(n^2,n+C)$，$C$ 是 $a_i+a_j$ 的值域。为什么呢？因为根据鸽巢原理原理，$a_i+a_j$ 最大才 $5\times 10^6$，那么最多枚举 $5\times 10^6$ 就可以找到了。

P2938 [USACO09FEB]Stock Market G

背包。

普及组原题。对于每一天都进行一次背包，将价格视为代价，将赚到的钱视为价值。

CF1494E A-Z Graph

思维。

其实想想还是很简单的。首先对于奇数很简单，构造一个形如 $[a,b,a,\ldots,a,b,a]$ 的序列即可，因此需要有 $a\leftarrow b$ 和 $b\leftarrow a$ 的边。再思考偶数的，其实也是类似的，不过变成了 $[a,b,a,\ldots,a,b]$，因此及需要满足上面的条件，还要边的字母相同。因此维护这两个东西就好了。

CF1508A Binary Literature

构造。

一开始以为是子串，结果是子序列。那就简单了，直接拼起来是 $4\times n$ 的，考虑怎么减少 $1$ 个 $n$。$3$ 个字符串一定会有两个字符串出现 $0/1$ 的次数都超过 $n$，拼起来就好了。

P1470 [USACO2.3]最长前缀 Longest Prefix

dp、哈希。

直接枚举每一位若当前位置的字符串相同，就从前面的状态转移来即可。判断字符串是否相同可以用哈希 $O(1)$ 做。不过不知道因为什么玄学原因 TLE。

P2375 [NOI2014] 动物园

kmp。

是个 kmp 的好题。增加了我对 kmp 的理解。其实自己差不多都想到了，但就差那么一步啊……手玩一下有个思路：先求出 nxt 数组，然后对于每一位都去跳它的 nxt 数组，若满足 $nxt < i - nxt + 1$ 的话答案加 $1$，这样时间复杂度太大，只能得 $50$ 分。思考问题的本质，每一个 $i$ 对答案的贡献就是满足上面条件的 nxt 个数，而就在这里我没想清楚，乱写了错误的东西。其实非常简单，先递推求出每一位的 nxt 的个数（这里也想到了），然后就像求 nxt 一样，枚举一个指针 $j$，保证其满足 kmp 和上面的条件，然后更新答案即可。

CF1461B Find the Spruce

暴力。

其实一开始就想到暴力，但是以为时间复杂度是 $500^3$ 就没有写。但其实是自己时间复杂度算错了，因为并不会跑满，会在不行的时候 break，因此是可以过的。

6.3

CF1461C Random Events

期望。

首先我们发现不是所有操作都有用的，从后往前扫，第一个 $a_i\ne i$ 的就是关键位，只有大于等于关键位的才有用。然后求所有元素都被升序排列的几率，正难则反，我们先算不被升序排列的概率，即 $\prod 1-p_i$，最后再用 $1$ 减去即可。

CF1461D Divide and Summarize

递归、二分。

真没想到就是个暴力，直接 dfs 然后二分位置，递归即可，时间复杂度为 $O(n\log n)$。

5.31

P7469 [NOI Online 2021 提高组] 积木小赛

哈希。

P6033 [NOIP2004 提高组] 合并果子 加强版

贪心、队列。

$O(n\log n)$ 显然过不了这题。那么快排、优先队列都用不了。$a_i\leq 10^5$，快排可以用桶排代替。而优先队列又该用什么代替呢？联想到蚯蚓那题，我们发现可以用两个队列，一个放排序结果，另一个放合并结果，每次合并从两个队列队首选最小的合并即可。

P2633 Count on a tree

主席树。

静态区间第 $k$ 小值是主席树的经典题型，考虑放到树上怎么做。想到主席树本来就是用差分的思想，那么 $[u,v]$ 的权值也可以用差分来求：即 $sum_u+sum_v-sum_{lca(u,v)}-sum_{fa_{lca(u,v)}}$。

5.30

CF484E Sign on Fence

可持久化线段树。

首先对于求区间最小值我们可以很套路地想到二分区间最小值，那么怎么 check 呢？还是很经典的套路，$x$ 是区间最小值说明区间所有数都大于等于 $x$，那么将大于等于 $x$ 的数设为 $1$，那么题目也就变成了 $[l,r]$ 间的最长连续为 $1$ 的区间长度是否大于等于 $k$，而这又是线段树的经典模型。但二分有那么多个，线段树要支持不同版本的，因此用可持久化线段树。

P2839 [国家集训队]middle

可持久化线段树。

求中位数和上面的方法差不多，将小于 $x$ 的设作 $-1$，否则设为 $1$，那么满足条件的话就是区间最大的连续和是否大于 $0$。

不过本题连区间都不是固定的，该怎么做呢？首先，当 $b+1\leq c-1$ 的话，区间 $[b+1,c-1]$ 是一定要选的，那么直接加上区间和即可，然后再加上 $[a,b]$ 的最大后缀和和 $[c,d]$ 的最大前缀和即可。

注意初始化。

P4211 [LNOI2014]LCA

树链剖分、差分。

首先暴力显然过不了，考虑根到 $x$ 和 $y$ 的 lca 的就是两个点的公共路径长度，那么我们就有了个想法：每次都将 $i$ 到 $1$ 的路径权值加 $1$，每次查询 $z$ 到 $1$ 的路径权值和，而我们可以用树链剖分来做。但这样时间复杂度还是没变，对于一个 $[l,r]$ 的查询我们可以想到差分，我们可以用 $[1,r]$ 的答案减去 $[1,l-1]$ 的答案。还要再优化，我们发现 $[1,4]$ 和 $[1,5]$ 只不过多了 $5$ 因此离线询问，在按位置排序来做。

5.29

P6166 [IOI2012]scrivener

主席树。

下面那题的双倍经验。

P1383 高级打字机

主席树。

如果没有撤销操作就是普通的线段树，但有了撤销操作就成了主席树。首先考虑普通的线段树怎么做：线段树维护字符长度；修改操作的话就判断当前节点的左子树是否等于区间的一半，是的话往右子树走，否则的话往左子树走；查询的话就线段树二分，判断左子树的大小即可。

5.28

P3567 [POI2014]KUR-Couriers

主席树。

SP11470 TTM - To the moon

区间修改可持久化线段树。

记得标记永久化。

P3919 【模板】可持久化线段树 1（可持久化数组

主席树。

CF1527B2 Palindrome Game (hard version)

博弈论。

首先回文的情况下面已经讨论过了，然后是非回文的情况。还是分奇偶讨论，我们发现 $A$ 占有主动权，他可以一直翻转，而 $B$ 一定要快地让串回文，而 $A$ 只要成为最后一个让串回文的那个人，那他就是后手，转化为上面的必胜状态。不过还要判一下平局的情况：只有 $2$ 个 $0$，且 $n$ 为奇数，且 $a_{(n+1)/2}$ 为 $0$。

CF1527B1 Palindrome Game (easy version)

博弈论。

博弈论可以往奇偶性上考虑。若 $0$ 的个数为偶数，那么 $A$ 变一个 $0$ $B$ 就变和它对称的 $0$，那么最后剩下 $2$ 个 $0$，$A$ 变一下 $B$ 翻一下 $B$ 就赢了。至于 $0$ 为奇数 $A$ 拿中间一个就变成了 $A$ 必胜的局面。记得特判平局和 $0$ 只有一个的情况。

P3901 数列找不同

莫队。

莫队经典应用：数颜色。

5.27

P3203 [HNOI2010]弹飞绵羊

分块。

CF1397B Power Sequence

很恶心，几天前就做了，直接暴力枚举即可，为了防止爆 long long 我还写了特判，但本地能过但在 cf 死活过不了，太恶心了，最后一定要让你保证不会爆 long long 才能过。

P5047 [Ynoi2019 模拟赛] Yuno loves sqrt technology II

二次离线莫队。

SP3946 MKTHNUM - K-th Number

主席树模板。

求区间 $k$ 小值。

P4396 [AHOI2013]作业

下面的双倍经验。

P4867 Gty的二逼妹子序列

莫队、权值分块。

P4462 [CQOI2018]异或序列

莫队、异或。

主要还是异或的神奇性质：具有前缀性，可以先做一下前缀和，然后就可以求区间异或值。

P4137 Rmq Problem / mex

回滚莫队。

5.26

AT4866 [ABC155E] Payment

很快想到每一位都有两种抉择：通过加上一位再减；直接自己加。但后面就没搞清楚，其实这种两种抉择，没有后效性，求最优解，可以直接 dp。

AT5300 [ABC154D] Dice in Line

太水了。直接上期望的定义即可。

AT5295 [ABC154F] Many Many Paths

组合计数。

发现自己组合计数太弱了。组合计数的恒等式都挺重要的，应该要记下来。事实上考场上就没想到组合数，其实从 $(0,0)$ 走到 $(n,m)$ 的路径数就是 $\binom{n+m}{n}$，连这点都没想到。然后根据组合恒等式压掉一维，然后 $O(n)$ 做。具体看题解吧。题解。

AT1219 歴史の研究

回滚莫队。

CF86D Powerful array

普通莫队。

只要考虑转移时的变化即可。

CF375D Tree and Queries

树上莫队。

CF940F Machine Learning

带修莫队。

5.25

SP3266 KQUERY - K-query

分块。

CF1393A Rainbow Dash, Fluttershy and Chess Coloring

模拟一下发现规律：答案是 $\frac{n}{2}+1$。

CF1393B Applejack and Storages

显然这跟 $2$ 根木棍的数量和 $4$ 根木棍的数量有关，因此我们考虑维护这两个值。

CF1393C Pinkie Pie Eats Patty-cakes

显然本题的关键在出现次数最多的数身上，因为其他数跟在出现最多的数后面一定不会影响答案，因此求出出现次数最多的数的个数 $num$，则答案为 \frac{n-sum\times num}{sum-1。

P3709 大爷的字符串题

分块。

就是求区间众数出现次数，不过题意写的完全看不懂。直接用分块求。

P1997 faebdc 的烦恼

分块。

区间众数。

P4074 [WC2013] 糖果公园

做了我整整两个小时，不过最后还是做出来了。这说明我的代码能力和思维严谨性还不行，不过相比之前肯定有进步，但这还不够，一定做到更好。

SP10707 COT2 - Count on a tree II

树上莫队。

5.24

P5048 [Ynoi2019 模拟赛] Yuno loves sqrt technology III

分块。

这题和蒲公英非常相似（几乎一样），都是求区间众数。不过蒲公英要求的众数，而这题求的是众数出现次数，因此要减去一些没必要的计算。

和那题一样，先离散化，再预处理出两两块之间的众数出现次数以及用 vector 存每个数值出现位置，然后对于询问，在同一块直接暴力算；否则的话先有前面预处理的答案，然后对于不完整块的元素，左端的我们直接对于每个元素从它在 vector 出现位置 $pos$ 再加上 $maxn$ 开始，若 $pos + maxn \leq r$，那么众数出现次数加 $1$，右段的同理。时间复杂度为 $O(n\sqrt{n})$，比每次二分要优。

为什么这样是对的呢？因为若 $pos + maxn$ 还满足在 vector 中的话，那么说明 $a_i$ 出现次数起码等于中间块的答案，直接用即可。

CF455D Serega and Fun

分块。

一开始不知道怎么处理移动操作，然后才知道直接对每个块都建一个 deque 即可，然后就好做了，不过有些细节。

CF551E GukiZ and GukiZiana

分块。

区间修改加上奇怪的查询，想到了分块。我们可以将每个块排序，然后在每个块中二分查找，然后计算答案。查询时间复杂度为 $O(mn\log\sqrt{n})$，时限为 $10$ 秒，能过。

P1903 [国家集训队]数颜色 / 维护队列

带修莫队。

5.23

AtCoder Regular Contest 120

A - Max Add

显然不可能每次重算，肯定是从前面的答案转移而来，从这个思路出发就能想到。

B - Uniformly Distributed

对于所有的 $i+j$，有三种情况：

1. 都是 "."，答案乘 $2$；

2. 两个不同，答案为 $0$；

3. 两个相同，答案乘 $1$。

CF865D Buy Low Sell High

反悔贪心、优先队列。

首先有个贪心想法：每次选最小的价格买入，然后在后面可以获得收益的时候买出。但这样显然不对，因为可能后面有可以获得更多收益的时候。因此我们需要加入反悔的操作，当进行在第 $i$ 天买入在第 $j$ 天卖出的操作时，假想一个价值为 $val$ 的物品，买这个物品的时候，抵消了上面的操作而变为了在第 $i$ 天买入在第 $j$ 天迈出的操作。$val$ 等于多少呢？$a_j-a_i+a_k-val=a_k-a_i$，$val=a_j$。因此我们对于每个 $a_i$ 将其塞入小根堆两次，一次是开始的贪心策略，另一次是提供反悔的操作。

CF1517C Fillomino 2

贪心。

很容易就猜到结论了：能往左就往左，否则往下。

CF617E XOR and Favorite Number

异或、莫队。

SP3267 DQUERY - D-query

莫队。

P2709 小B的询问

莫队。

P1494 [国家集训队]小Z的袜子

莫队。

#6282. 数列分块入门 6

分块：单点插入、单点查询

5.22

实际：$11$

AISing Programming Contest 2021（AtCoder Beginner Contest 202）

做了四题。

D - aab aba baa

P4168 [Violet]蒲公英

分块：求众数。

CF425A Sereja and Swaps

贪心、枚举。

CF1517D Explorer Space

记忆化搜索。

CF725F Family Photos

贪心、排序。

CF1081B Farewell Party

思维。

首先很显然有 $k$ 个人和它不一样，就有 $n-k$ 个人和它一样。但是对于 $2,2,2,2$ 这组数据就不行（这个 hack 数据是 cf 的，并不是自己想的，之后还是要自己造数据 hack 自己）。

#6281. 数列分块入门 5

分块。

P3157 [CQOI2011]动态逆序对

分块。

5.21

实际：$8$

#6279. 数列分块入门 3

分块。

UVA12003 Array Transformer

分块。

和数列分块入门 2 几乎一样。不过一开始竟然连 build 函数都没调用……结果 TLE 了……之后还是要先静态挑错，否则太浪费时间了。

#6278. 数列分块入门 2

分块。

洛谷类似题目 P2801 教主的魔法 的数据太水了，查询时我把原始数组 $a_i$ 写成 辅助数组 $b_i$ 都能过，导致一直看不出这道题的问题。显然查询时应该用原始数组 $a_i$，因为 $b_i$ 排序过了，只有在整块时二分用。

#6277. 数列分块入门 1

分块、区间修改、单点查询。

P1627 [CQOI2009]中位数

中位数。

CF1396B Stoned Game

博弈论。

若最大的那堆石子比其他石子的和都要大，那么先手只要一直拿第一堆就一定胜利。否则的话每个人一定不会让另一个人出现上面的情况，否则必败，按照这个策略，每个人都会拿当前能拿的最大的那一堆，因此一定会取完所有石子，只要判断奇偶性即可。

CF1396A Multiples of Length

构造。

考虑特殊的操作，猜测会有一次 $1\sim n$ 的操作，且在最后进行，那么就转化为用两次操作将所有数变为 $n$ 的倍数。再考虑 $n-1$ 的特殊性，显然对于 $a_i$ 来说，$a_i+a_i\times (n - 1) = a_i\times n$，可以将其转化为 $n$ 的倍数。因此第一次改变 $1\sim n - 1$，第二次改变 $n$，最后改变 $1\sim n$。

CF1397A Juggling Letters

5.20

目标：$17$

实际：$7$

P2801 教主的魔法

分块、二分。

❗️P3803 【模板】多项式乘法（FFT）

FFT。

P2513 [HAOI2009]逆序对数列

dp。

P1521 求逆序对

dp。

P1018 [NOIP2000 提高组] 乘积最大

dp、高精度。

CF1478C Nezzar and Symmetric Array

思维。

一开始没有想法，但考虑绝对值可以转化到数轴上，数形结合很快就发现了性质，但死活过不了，发现漏了个原本发现但没有重视的性质。之后一定要仔细把性质都记在纸上。

5.19

目标：$13$

实际：$6$

P2308 添加括号

区间 dp、恶心人的输出细节（或者说是错误的题意）。

P3047 [USACO12FEB]Nearby Cows G

换根 dp。

CF1324F Maximum White Subtree

换根 dp。

P2986 [USACO10MAR]Great Cow Gathering G

换根 dp。

CF1478A Nezzar and Colorful Balls

CF1478B Nezzar and Lucky Number

5.18

目标：$10$

实际：$7$

CF1474E What Is It?

构造。

P2293 [HNOI2004]高精度开根

二分、高精度。

P1726 上白泽慧音

tarjan、强连通分量。

U135365 A+B Problem 整数版

高精。

CF1474D Cleaning

思维。

CF1474C Array Destruction

思维。

5.17

目标：$10$

实际：$10$

SP16409 LOPOV - Lopov

贪心。

P2005 A/B Problem II

高精度除法。

CF1474B Different Divisors

素数筛、思维、找规律。

CF1474A Puzzle From the Future

贪心。

P1932 A+B A-B A*B A/B A%B Problem

高精度全家桶。

P1604 B进制星球

高精度加法、进制。

P1480 A/B Problem

高精度除法。

P1131 [ZJOI2007] 时态同步

树形 dp。

P2055 [ZJOI2009]假期的宿舍

二分图的最大匹配。

P1262 间谍网络

强连通分量、缩点。

5.15

P5018 [NOIP2018 普及组] 对称二叉树

树形结构、递归。

其实直接暴力递归判断即可，若以 $u$ 为根的子树满足条件，那么它的两个儿子权值要相等，且以它们为根的子树也要满足条件。

P4408 [NOI2003] 逃学的小孩

树的直径、LCA。

很显然最坏的情况就是 A 和 B 在直径的两端，然后枚举每个点计算答案即可（用 LCA 做）。

5.8

P3080 [USACO13MAR]The Cow Run G/S

区间 dp。

区间 dp 的经典模型，和关路灯、上次模拟赛题目都很像。与模拟赛题目的唯一区别就是这题要求全部取完，而模拟赛却不一定，所以它还要枚举要选多少个。根据贪心的思想，一定会在一个区间的左或右，设状态转移即可。

5.6

P3155 [CQOI2009]叶子的染色

树形 dp。

自己想的状态和转移都差不多，但就是没有坚持想下去。设 $f_{u,0 / 1}$ 表示 $u$ 这个点涂黑 $/$ 白的最小涂色数，显然若 $u$ 涂了颜色，那么可以直接继承 $v$ 涂该色的情况，只要 $-1$ 即可。

5.5

#10027. 「一本通 1.4 例 2」魔板

广搜。

其实就是经典的广搜，不过对于这类题目判重可以用 map，好处是好写，坏处是常数大。

不过这道题问题很大，对于 string 函数的一些莫名其妙的错误，调了一下午，还是要搞清楚到底是什么情况。

#10029. 「一本通 1.4 练习 1」棋盘游戏

广搜。

和上题类似，用 map 判重，然后暴力 bfs 即可。

#10155. 「一本通 5.2 例 3」数字转换

树的直径。

很显然的一题，先连边，再求树的直径即可。

#10024. 「一本通 1.3 练习 3」质数方阵

搜索。

一开始打了个暴力的 dfs，只拿了 20 分。结果看了 Acfboy 的，发现确实是暴力的 dfs，只不过暴力也有优劣之分，dfs 也需要巧妙地实现。一开始直接以一位一位的去填肯定不行，可以先预处理出所有符合条件的素数，再预处理出每个数下一位可行的填数选项，然后 dfs 即可。

学到了：要充分利用题目的要求，写暴力也要有好的思想。

#10249. 「一本通 1.3 例 5」weight

搜索。

这道题目的搜索比较特殊，甚至初看之下不知道怎么搜索。既然给出了前缀和与后缀和，那么我们肯定要根据这点来搜索。先将给出的数列从小到大排序，搜索时维护两个指针，一左一右，同时维护已知的前后缀，若当前的前后缀减去已知的前后缀在 $S$ 中出现过了，就继续搜，最后一定左右指针一定会汇合。

学到了：这种奇特的搜索方法。

VP Codeforces Round #683 (Div. 2, by Meet IT)

CF1447A Add Candies

思维题。

除自己之外的数都加 $j$，相当于自己减 $j$，然后就好了（手玩也可以发现）。

CF1447B Numbers Box

思维题。

也是道思维题，但却没有想出来。其实自己看出来一点，但想歪了。可以发现任意两个点都可以一起改变符号，然后统计负数个数就行了。

CF1446A Knapsack

贪心。

一下就想到了从小到大排序，注意细节就好了。

CF1446B Catching Cheaters

dp。

显然是最长公共子序列的变形题。一开始没有头绪，连状态都设不出来。原因是没有加限制条件，给状态加上限制以便于转移，这是常见的方法。设 $f_{i,j}$ 表示以 $i$ 和 $j$ 结尾的最大值，转移就很好写了。

5.4

P3802 小魔女帕琪

期望 $+$ 组合计数。

P2217 [HAOI2007]分割矩阵

记忆化搜索。

这题给出了新的记搜方法：一种是思考普通的 dfs 再优化，而这种则是思考 dp，再用 dfs 的形式的方式呈现。

P1283 平板涂色

搜索。

就是最简单的搜索，只是自己根本没有思考。一定要思考起码三十分钟，不要追求快。

$4.29$

P6155 修改

栈 $+$ 贪心。

其实这个贪心是很 naive 的，关键是如何快速的求通过给一个数加一使得所有数都不相同的最小加的次数（之前 ABC 也见过这种题），通过栈可以做到 $O(n\log n)$（因为还要排序）。 具体实现是维护一个数值，如果数列中的数等于该数值，就将其加入栈中，每次在去除栈顶，其修改值就是当前数值减去数列值。

P5181 [COCI 2009] GENIJALAC

思维。

思考问题的本质。会发现一列的出现位置会出现循环节，求出每一列的循环节取 $\operatorname{LCM}$ 即可，一定要注意特殊的情况，多造数据卡死自己。

$4.28$

P4362 [NOI2002] 贪吃的九头龙

树上背包。

首先要发现一个性质：若 $m>3$ 那么就不可能有一条边两个端点都是小头的情况，因为一定可以相交放，那么只要关注大头的限制就好了，设 $f_{u,j,0 / 1}$ 表示以 $u$ 为根的子树放了 $i$ 个大头，$u$ 不放 $/$ 放大头的最小难受，然后转移也很转移。注意细节：倒序枚举；父节点一定要先选一个子节点；还有初始值。

P5562 [Celeste-B]Center of the Earth

非常神奇的 构造题。

首先有个显然的做法：只要两个相同即可，那么 $n^2$ 枚举前两个即可，第三个随便。但这样显然不是最优的，因为完全没有考虑到第三位。发现 $n$ 为偶数，而三位数一定会有两位同奇偶，因此我们分奇偶讨论。$k=\frac{n^2}{2}$，具体的证明。

$4.18$

P5664 [CSP-S2019] Emiya 家今天的饭

容斥、dp。

P1450 [HAOI2008]硬币购物

容斥、dp。

P3216 [HNOI2011]数学作业

递推、矩阵加速。

$4.17$

Japanese Student Championship 2021

A - Competition

显然是求满足 $\frac{ans}{z} <\frac{y}{z}$ 的最大的 $ans$，因为精度问题，将式子转化为 $ans\times z<y\times z$，直接枚举即可。

B - Xor of Sequences

直接记录每个数在 $A$ 和 $B$ 的出现次数。

C - Max GCD 2

暴力枚举显然不行，换个角度思考。$\gcd$ 其实就是在 $x$ 和 $y$ 间出现两次及以上的因数，因此直接枚举即可。

D - Nowhere P

只要画出答案树就很容易猜出结论，对于 $n$ 和 $p$，答案为 $(p-1)\times (p-2)^{n-1}$

$4.16$

CF1470B Strange Definition

数学 $+$ 思维。

推式子。

$\operatorname{lcm}(x,y)=x\times y /\gcd(x,y)$

$\frac{\operatorname{lcm}(x,y)}{\gcd(x,y)}=\frac{x\times y }{\gcd(x,y)^2}$

显然要让 $x\times y$ 为完全平方数，考虑 唯一分解定理，要让次数为偶数，再考虑性质即可。

$4.15$

P4826 [USACO15FEB]Superbull S

最小生成树。

转换题意。这种题目挺常见的，$n$ 个人打 $n-1$ 场比赛，其实就是 树形结构。然后就是普通的最小生成树。

注意最小生成树空间要开大（应该开 $n^2$）。

P5596 【XR-4】题

数学。

首先有显然的 inf 的情况，$\frac{a^2}{4}=b$，为了避免精度问题，转化为 $a^2=4\times b$。

然后怒推一波式子，左边的显然是平方差公式，转化得

$(y-x)(y+x)=ax+b$

设 $t=y-x$，则 $y+x=t+2x$

$t(t+2x)=ax+b$

$t^2+2x\times t=ax+b$

$x=\frac{b-t^2}{2t-a}$

直接枚举 $t$ 即可，上下都有单调性，上面的 $>0$ 下面的 $<0$ 退出即可。

P1655 小朋友的球

dp。

设 $f_{i,j}$ 表示 $i$ 个球放在 $j$ 个盒子里的不同方案数，考虑第 $i$ 个球放在哪个盒子里。分两类：

1. 重新放一个盒子里，对答案贡献为 $f_{i-1,j-1}$；

2. 和前面的某个盒子放在一起，对答案贡献为 $j \times f_{i-1,j}$。

因此 $f_{i,j}=f_{i-1,j-1} + j \times f_{i-1,j}$。恭喜你，手推出了 第二类斯特林数 的递推式。

然后本题要高精，建议结构体封装函数，重载运算符，好写不易错。

P2532 [AHOI2012]树屋阶梯

卡特兰数。

如何看出本题是卡特兰数呢？题解里讲的很清楚了。其实我们也可以通过找规律的方法发现，当看到 $C_1=1,C_2=2,C_3=5,\ldots$ 时就可以猜测是卡特兰数了。