CodeForces 2100-2300 – hydd's blog

Greedy

1472F

从左到右考虑每一列，确定了前 $i-1$ 列，那么现在的第 $i$ 列哪些被覆盖就确定了。
可以求出第 $i$ 列覆盖的方案：如果没有空格/只有一个空格，则只能放横的；否则两个都是空格，一种是放两个横的，一种是放一个竖的，可以发现放两个横的和放两个竖的等价，不如变成放竖的，其它的之后再决策。
所以就变成，只要这一列没满，就横着放，否则竖着放。
有一种离谱情况，它是第一行放(1,2),(3,4),...，第二行放的是(2,3),(4,5),...，类似于这种就必须横着放。
那么你就可以 O(m)模拟，你这一列覆盖完之后就知道后面的是上下两行差 1 的情况还是可以直接竖着放。
从有障碍的一列到后一个有障碍的一列，中间快速跳。

1367F

我们直接来做 F2。首先可以离散化，然后发现每个数最多操作一次，不然你可以只操作最后的那一次。
根据经典套路，你把不动的拿出来，一定是个递增序列，剩下的也得能归位（比最小值小或比最大值大，也就是>最小<最大的必须本身在序列内）。
直接设 $dp[i]$ 表示 $i$ 选了且是最大的最长长度，$a[i]=x$。一种从之前的最后一个 $x$ 转移过来；一种是选所有的 $x-1$（必须在 $i$ 前面），再从第一个 $x-1$ 转移过来；还有一种是选之前所有的 $x-1$。
分别求出来转移即可。

1373E（#）

考虑 $x+k$ 进没进位。
如果没进位，枚举最后一位，之前的位贪心（尽量填 9）。
如果进位了，枚举最后一位和之前连续的 9 的长度，计算一下，再贪心（先填一个 8，再尽量填 9）。

1530E（#）

如果只有一种字符，那只有一种方法，直接结束。
f 为 0：如果有某种字符只出现一次，那么拿最小的只出现一次的字符当开头，其它的从小到大往后排（不可能拿出现果不止一次的字符，那会使得 f 至少为 1；也不可能取更大的字符，那字典序更大）。
f 为 1：现在所有字符都出现至少两次（这种情况答案一定不为 0，不妨假设 a 出现了），想让字典序尽量小，先考虑有没有可能是以 aa 开头，那么之后就不能有两个相邻的 a（否则 f 至少为 2），只能形如 aababa…ca…。可以发现 a 的个数最多为其它数字个数+2，即 cnt>=n-cnt+2，cnt>=n/2+1。
如果不满足条件（不妨假设 b 出现了），考虑开头为 ab，那么之后就不能再出现 ab，如果只有两种字符，那么 b 一定要出现在 a 前面，即 abbb…baa…a；如果有更多字符（不妨假设 c 出现了），那么可以为 abaaa…acbbb...bccc…c…，即 ab 之后填所有的 a，再填 c，剩下的从小到大填。

1254B2（#）

只需要考虑 $k$ 是质数的情况。
其实 $a_i$ 和 $a_i \bmod k$ 是完全等价的（不会出现负数啥的情况），那么前面往后移和后面往前移也是等价的，计算一下答案即可。

576C（#）

按照莫队的方法奇偶排序即可。

547A（#）

你先暴力跳，把第一个跳满足，如果跳了 $m$ 次还不满足就无解。
如果此时第二个也满足就直接结束。
否则你让第一个就再跳一个环回，跳回来，记录此时第二个乘的 x 和加的 y。
之后再跳第一个就不变了，依旧暴力跳，不超过 m 次。

1253E

对于原问题，可以加入一个 [0,0] 的区间，这样不会影响答案（可以把第二个区间多扩展这个区间的范围）。
设 $dp_i$ 表示只用中心不超过 $i$，覆盖 $1..i$ 的最小代价。有了 $[0,0]$ 就不存在不能覆盖的问题了。
如果原先覆盖了 $i
$ 那么从之前没覆盖的第一个位置转移，否则直接考虑之前的某一个扩展到 $i$，再从左端点之前转移过来。
但是你可以扩展得更长，多覆盖左边的一点，这样就很麻烦了。但是 $dp_{i+1}\leq dp_i+1$，你可以把之前的区间增加 $1$。

1316E

排序，变成 $a_i$ 从大到小排序。
范围很小，直接状压 $dp$ 记录到哪一个，之前队伍有了哪几个位置（状态），有多少名观众。
如果当前放进队伍就枚举放哪个位置，不放进队伍如果观众不够就当观众，否则就不参加。

1296F（#）

显然要满足 $u,v$ 路径上的边权都 $\geq w$。
路径取 $\max$ 后判断是否合法即可。

1334E（#）

考虑路径会长成什么样，直观的想法是先除后乘一定严格比先乘后除优，不妨反证。考虑从 x 到 x*p/q。
设 p,q 为两个不等质数，先乘后除：-d(x)+d(xp)+d(xp)-d(xp/q)，先除后乘：d(x)-d(x/q)-d(x/q)+d(xp/q)
要求-d(x)+d(xp)+d(xp)-d(xp/q)<=d(x)-d(x/q)-d(x/q)+d(xp/q)，整理得 2d(x)-2d(xp)+2d(xp/q)-2d(x/q)>0.
都除以 2，移项变成 d((x/q)p)-d(x/q)>=d(xp)-d(x)，可以知道，*p 之后增加量应该数字除去所有 p 之后，剩下的因子数，(x/q)|x，这个式子一定不成立。（为啥不考虑 p=q 呢，因为边权一定为正，没必要从 x 到 x）。
所以一定会先除后乘，否则可以交换顺序。那么可以变成 x 一直除，y 一直除，到达同一个点。
由于你只是除，那么路径上的中间点的权值都会删去，所以路径长度一定是 d(x)-d(目标点)。
那么答案是 d(x)+d(y)-2d(目标点)，x,y 都能到达的点只能是 g=gcd(x,y)的约数，可以发现 g 的约数中，g 本身的 d(g)是严格最大的，所以目标点也固定为 g。答案就是 x 到 g 的方案数*y 到 g 的方案数。
相当于要求一个数 x，每次除一个质因数，有多少种不同的方法，那么就用 tot!/(p1!p2!...pk!)算算多重组合。
由于题目说了给的都是 D 的约数，先求出 D 的所有质因子，询问的时候就可以 O(log V)解决。

1384B2（#）

称无论什么时候在当前位置都是安全的点为安全点，否则为不安全点。显然不安全点能走的时间是一些区间。
若当前点为安全点且下一个点也是安全点，直接走过去即可；
若当前点为安全点且下一个点不是安全点，则在最优的时间走过去（递减且正好能走过去）。
若当前点不为安全点且下一个点是安全点，直接走过去即可；
若当前点不为安全点且下一个点不是安全点，则只要能走过去且不死就走过去，一直不走必定会死，能跑路就赶紧跑路。

549G（#）

继续寻找不变量，$a_i+i$ 总是不变的。
初始的 $a_i+=i$，条件变为：$a_{i-1}\geq a_i$ 的话交换 $a_{i-1},a_i$。
如果有相等的显然最后会一直交换，否则最后会排序，再 $-i$ 输出即可。

825E（#）

你直接按照顺序拓扑排序，把小的给编号小的，求出的是答案对应的逆排列最小。（编号小的其实是越早经过越优）。
非常有意思的一点是，你如果建反图，尽量把大的给编号大的，这样求出的就是答案最小。（现在越早经过反而变成越劣，反过来了）。

1411D（#）

把贡献分成几种情况，0 和 1，?和 1，0 和?，?和?。
可以知道，把序列分成若干部分，它们之间形成的 01/10 子序列和内部顺序无关。
考虑?...?，它们和外部的贡献和顺序无关，和 0,1 出现次数有关。如果?替换从 0,0 或 1,1 的出现次数不同。
替换成 0,1 和 1,0 出现次数相同，内部的贡献比较变为 0...1 和 1...0 哪个大，设中间的...有 a 个 0，b 个 1，那么 0,1 的贡献是(a+b+1)x，1,0 的贡献是(a+b+1)y，看 x,y 哪个大变成哪个即可。
不妨设 x 比较大，所以?填的一定是前面若干个 0，后面若干个 1，枚举前面多少个填 0，可以计算出?和?，而其它三种预处理即可。

1154F

可以发现一定选最便宜的 $k$ 双，因为如果选了 $x$ 有一个更小的 $y$ 没选，那么如果本身 $x$ 被免费，那么换成 $y$ 之后一定也免费；如果 $x$ 不免费，一种是换成 $y$ 之后也不免费，一种是换了变免费了，那么有一个变收费了，变收费的一定比 $x$ 小，总代价也变小。
排序。总和固定，你希望免费的鞋的钱的价格尽量高，所以你会成段成段的买。
然后 dp，枚举最后一次买了多少双鞋，计算一下代价。

1535E

这题关键在于：
保证 $c_i>c_{p_{i}}$，所以删的一定是到根路径上的前缀；
操作是有后效性的（永久的）。
删的一定是到根路径上的一个前缀，删除的时间可以均摊。
怎么找最上面的点？考虑倍增（主要是方便在线加点），找到最上面没被删的点即可。

1154G（#）

拿个桶记录每个数有没有出现过。
lcm 可能很大，但 lcm(a,b)=ab/gcd(a,b)，考虑枚举 gcd 和它的倍数，求两个最小的出现过的更新答案即可。

1556E

可以发现，设 $c_i=b_i-a_i$，那么就变成选出下标递增的 $k$ 个位置
$-1,+1,-1,+1,...,-1,+1$，要求所有数都是 $0$。
显然和不变，所以和必为 $0$ 才有解。根据经典套路，做个前缀和还是要求所有数都是 $0$，就变成区间 $-1$（最后一个数不能动，也说明和必须为 $0$），如果原先有负数显然无解。
由于每次可以任意选区间，所以答案就是最大值。
先全局做一次，维护一下区间最大最小值，再都减去 $l-1$ 的前缀和，如果最小值 $<0$ 则无解，再判断 $r$，如果是 $0$ 也无解，最后再输出最大值。

1494D（#）

LCA 的权值为最大值的，说明它们 LCA 为根。
LCA 的权值不为最大值的，说明它们在根节点同一子树。
递归下去即可。

1557D

设 $f_i$ 表示 $1..i$ 行能选出多少行使得选出的数量最多（第 $i$ 行必选）。
如果第 $i$ 行和第 $j(j<i)$ 行能相邻，$f_i$ 就可以从 $f_j+1$ 转移。
判相邻就看是否有一列相交，不妨转变思路，直接把有第 $x$ 列的放到线段树上取最大值，求 $f_i$ 就在 $i$ 有的区间上取最大值即可。
答案是 $n-\max f_i$。

1605D

首先看条件 $u \oplus v\leq min(u,v)$，不妨设 $u<v$，如果 $u,v$ 最高位不同，那么 $u\oplus v$ 的最高位就是 $v$ 的最高位，比 $u$ 大，矛盾。如果最高位相同，直接异或掉了，一定满足。
所以条件就变为 $u,v$ 最高位相同。由于是轮流操作，你还可以把树黑白染色。
显然所有点都不能动的构造最大。看黑白两边的节点个数 $x,y$，不妨设 $x\leq y$。
最高位不同的数之间相互独立，把 $x$ 二进制分解，最高位是那些的都放到 $x$，剩下的都放到 $y$。
那么所有点相邻的都没有同最高位的，所以都不能走。

1175E

用一个区间覆盖第 $i$ 个点，假设之前都覆盖了，那么右端点一定越靠右越好。
求出覆盖第 $i$ 个点的右端点最右的区间，扫一遍取 $\max$，建边指向右端点右边那个点。
现在变成一个森林，从 $l$ 开始跳几步才能 $\geq r$，倍增即可。

1271D

对于一个城堡，你一定尽量晚的放士兵，因为如果你之前不放后来放，影响是中间那一段时间军中的人数增加 $1$，不会更劣。
由于你会走过每一个城堡，记录哪些是在这个城堡才会选的驻守方案，如果不往那些驻守之后就守不了了。
直接二维 $dp$ 记到哪一个还有多少人是一定可以的。不这么做，考虑带悔贪心。
因为你必须走到底，所以你可以先在最后能驻守的时候先驻守，行军人数不够就反悔把之前的抽出来，但是你走过去之后，就不能把这些人放回去了（他们必须跟过来），所以复杂度是对的。

1220E（#）

因为保证了图连通，考虑拓扑排序。
排序完之后剩下的还在图中的，它们一定可以一次走完并且停在任何一个点。
就分进入环还是不进入环的情况，可以（对被删去的点）处理一个 f 数组表示从度数为 0 的点开始到这个点的最大权值，同时更新不经过环的答案，最后把不删的点之和+f 的最大权值。

1404C（#）

如果询问的是整个序列，那么每次删除最后一个满足 $a_i=i$ 的位置即可，把删除顺序记作 $b_i$。
询问的不是整个序列，找第一个 $b_i<x$，在之前的 $b_i\leq y$ 的都对答案产生了 $1$ 的贡献，计算即可。

1511E

横着的和竖着的是独立的，横/竖的极长连续段之间也是独立的。
如果有一段长度为 $x$ 的横/竖的极长连续段，设它的答案为 $f[x]$，那么对应的贡献为 $f[x]*2^{tot-x}$（$tot$ 是总白色格子数量，即剩下可以任意选）。
考虑 $f[i]$ 的转移：
$i$ 位置是另一种颜色，从 $f[i-1]$ 转移过来；
$i$ 位置是这种颜色，$i-1$ 不是这种颜色，从 $f[i-2]$ 转移过来；
$i$ 位置是这种颜色，$i-1$ 也是这种颜色，从 $f[i-2]+2^{i-2}$ 转移过来（后面加的是之前的方案数）。
横竖都算一边加起来即可。

1029E（#）

看上去比较像贪心，首先新的边一定一端是 1，否则不优（你是要减小最短路，看减小的是哪边，不妨把另一边换成 1）。考虑哪些点的策略一定是固定的。
考虑一个还不满足条件的叶子节点，那么一定要把它或它的父亲和 1 连边，连谁比较优呢。
发现一定会连它的父亲，它父亲会使得满足条件的更多，且除了它本身以外其它点的最短路更小。
对于满足条件的叶子节点，可以发现能把其删掉，选它也不如选它的父亲。
所以你每次选一个深度最深的叶子节点做，然后删去，更新它父亲的深度。

767B

你考虑，如果你要在前面一些老哥之后，这个老哥之前，那么你在之前的任何时间点来和后面这个老哥来的前一秒来是没区别的。
所以你就对于每个老哥，看在这个老哥前一秒来要等多少时间（等不等得到，$now+m>T_e$ 就等不到了）。之前要占多少时间可以直接拿个数字记录，即之前的人都走完需要多久，减一下更新答案。

1415E（#）

相当于分成最多 k+1 个序列，每个序列再按照顺序计算。
可以贪心考虑，显然分出的每个序列都是从大到小排序最好。
用堆维护每个序列当前的和，找到最大的序列加上当前的数。

679B

考虑能不能变成规模更小的子问题。
求出最大的 $x$ 满足 $x^3\leq n$，那么最后答案中，第一步取的一定不超过 $x$。
如果第一步取 $x$，那么剩下的可以是 $[0,n-x^3]$ 中的任何数（初始在 $[x^3,n]$）。
如果第一步取 $x-1$，那么剩下的可以是 $[0,x^3-1-(x-1)^3]$ 中的任何数（初始在 $[(x-1)^3,x^3-1]$）。
初始取比 $x-1$ 更小的一定不如取 $x-1$，剩下的范围更大。
那么也就是说能递归到 $\max(n-x^3,x^3-1-(x-1)^3)$ 的子问题，$n$ 的答案是它的答案 $+1$。
不过比较低素质的是相同的情况下让体积最大，所以你求出答案之后还得看到底取哪边可以，都可以就尽量取大的。
这个递归复杂度是 $O(n^{\frac 13})$。

1528C

可以发现，第一棵树取得一定是祖孙链。
在两棵树上都保证了 $fa_i<i$，所以你枚举第一棵树的祖孙链的时候，如果第二棵树的这个点和之前的点（最多只有一个）有祖孙关系，一定用这个点替代之前的点（$dfs$ 序的区间严格被之前的包含）。

1396C

由于 $r_1\leq r_2\leq r_3$，而手枪和 AWP 都只能打一只怪物，所以 AWP 只可能用来打 BOSS。
如果用手枪一只一只打小怪，最后一定是一起把 BOSS 一起解决了（不解决放着之后需要的时间不会更少）。
如果用激光枪，那么打完一定要走，如果之前 $i-1$ BOSS 也没死，就去打 $i-1$，否则打 $i+1$（你之后还得打 $i-1$ 的 BOSS，不如现在先去了）。
不过即使你用手枪打，如果 $i-1$ 的 BOSS 没死，你打完后一定也是先去 $i-1$，之后再折返一定不优。
所以说，假设 $i$ 之前的怪全都死了，一种是你用手枪+AWP 解决，到 $i+1$；另一种是用激光枪/手枪给每个打一枪，然后到 $i+1$，再用任意方法（都打一枪或直接解决），再回到 $i$，手枪一枪打死 BOSS，又到 $i+1$，如果 BOSS 没死也一枪打死，最后到 $i+2$。
所以一种是新增 $a_i\times r_1+r_3+d$ 的代价走到 $i+1$，一种是新增 $\min((a_i+1)\times r_1,r_3)+r_1+\min(\min((a_{i+1}+1)\times r_1,r_3)+r_1,a_{i+1}\times r_1+r_3)+4d$走到 $i+2$。
dp 即可。

675E

从后往前维护后缀最大值（是指 $i..j-1$ 中的所有值都比 $a[j]$ 小）。
那么你从这个点开始，走到的点一定在这个点开始的后缀最大值的集合内。
而且，后缀最大值也不一定会出现，如果这个点能直接走到下下个点，那么下一个点也没用了。
用单调栈维护这个集合，同时维护这个集合中的位置之和来计算答案。

1202C

行列独立，分别处理，以行为例：先求不操作得到的最小/最大值。
现在要让最大值-1（或最小值+1）,显然当当前值第一次等于最大值（最小值）的时候必须是有-1（+1）。
然后更新操作后的最小最大值，列同理。再计算一下。

1203F2

同 F1，加血的没区别（按照 $a_i$），扣血的你利用调整法，发现也差不多，按照 $a_i+b_i$ 的顺序从大到小。
加血显然能加就加，扣血的现在可以选择扣不扣，跑个背包即可。

1108F（#）

和 MST 有关的，很多贪心都是对的。。。
随便取一棵生成树，不妨假设最后留下的就是这棵生成树。
那么你对于剩下的非树边，和树边一定形成了一个环，它不能替换环上的其它边，即要比其它边都严格大。
考虑边 kruskal 边计算答案，发现后面加入的边如果需要增加当且仅当在加入同权值的边之前是不连通的，加了同权值的边后连通，为了不让自己替换那条边所以要+1。
同权值的一起计算即可。

754D

按照左端点从小到大排序。
把右端点加入小根堆，每次弹堆顶保证不超过 k 个数。
如果有 k 个那么用最小值-当前左端点+1 更新答案。

1152D

你考虑类似二分图匹配，左部是深度为奇数的点，右部为深度为偶数的点。
答案不超过两部大小较小值。容易构造出答案为左部大小的答案，即每个深度为奇数的点选一个儿子（一定能选出）。
按照左端点从小到大排序。
把右端点加入小根堆，每次弹堆顶保证不超过 k 个数。
如果有 k 个那么用最小值-当前左端点+1 更新答案。

976E

明显*2 只给同一个人最优。
剩下的一定是选替换掉新增的贡献最大的若干个。
排序求一下即可。

1398E（#）

设电的数量为 x。可以发现，理想的情况是你给最大的 x 个翻倍。
但是有可能不行，因为可能最大的 x 个都是电，这样一定有一个翻不了，可以发现一定不翻最小的。
而且，如果最大的 x 个中有火，你就从一个不用翻的电开始就可以了，此时一定没有最小的电。
所以无论什么情况，都不会翻最小的电。你要求的是答案尽量大。
如果 x 大有火则为 S+S1，否则为 S+S2-M（S 为所有和，S1 为前 x 大和，S2 为前 x+1 大和，M 为最小的电）。
可以用 set 维护前 x+1 大，相同的认为火更大。

708C（#）

以你要的点为根，你要让所有子树都<=n/2，如果本身满足就不用操作，否则你需要在>n/2 的子树里找到一个<=n/2 的最大子树拿出来直接接到根上，如果拿出了这个子树之后就<=n/2 了的话就 OK。
考虑固定了根怎么求，可以 dp，设 dp[u]表示 u 子树里最大的<=n/2 的子树，转移就是看所有儿子，如果 size 不超过 n/2 就用 size 转移，否则用 dp 转移，取个最大值。
只记最大的其实也不行，因为你要换根，换根了之后就要把某个儿子的贡献去掉，所以记最大的和次大的，如果往最大的子树换根则这个点的值变为次大的，否则就是最大的。

767D

一组牛奶可以当且仅当 $i$ 天内过期的牛奶不超过 $k\times i$ 瓶。
一定会买保质期最长的若干瓶，把商店里的牛奶按保质期从大到小排序。
现在考虑到第 $x$ 瓶牛奶，维护后面前缀和-$k\times i$ 的最小值，就能知道这瓶牛奶放不放的下，放不下就结束，否则就放，最小值-1，到下一瓶牛奶更新中间的最小值。

1537F（#）

这种就考虑生成树或二分图。按照经典套路，每次加或减的都是一个偶数，所以如果和的奇偶性不对显然无解。
可以发现，能把两个距离为奇数的位置一个+1 一个-1，能把两个距离为偶数的位置都+1/-1。
如果有奇环，因为原图连通，故任意两点都存在长度为奇数/偶数的路径，故一定有解。
如果没有奇环，那么是二分图，那么左部之和减右部之和不变，判断一下即可。

1213F（#）

如果 $p_{l..r}$ 形成的可重集= $q_{l..r}$ 形成的可重集，那么可以使用同一种字符来填。
固定了 $l$，那么尽量选最小的 $r$，直接贪心往后选，如果相同就分段。
这样可能使得字母不够用，那么把字母比较大的都变成 $z$ 即可。

1461E（#）

开始的时候 k 在[l,r]内。分类讨论。
如果 x>=y，一天过后水不会变多，第一天特殊考虑，剩下每一天一定会加水（尽量大，一定不会超过 r）。
如果 x<y，那么就是一直倒水直到再倒要 $<l$ 了，就加水。看上去这种复杂度很高，不过可以发现，再倒要 $<l$ 的状态只有 x 种，即 l,l+1,…,l+x-1，如果出现环（即状态重复出现）那么就一定能无限进行下去，否则每个状态最多遍历一次，复杂度 O(x)。

1477C（#）

如果构造的方案存在钝角 ∠ABC，那么根据大边对大角，AC 一定严格比 AB 和 BC 长。
所以如果 AB 比 AC 长就不存在这个问题，每次取离 A 最远的 B 即可。

1201D

可以发现，最后一定是在一行了里面走，然后向上，再走，再向上。
可以发现一行里停的一定是当前行最左/最右的障碍，你没有必要取完最后一个障碍后还移动，这不如走上去后再移动。
把中间空余的行删去，然后从下一行到上一行，一种是先往左后往右，一种是先往右后往左，都计算一下即可。
方便起见在第一行加 $(1,1)$ 当宝藏。

990E

枚举第 $i$ 种用来 power。
那么你每次为了尽量不重复，一定会选择不超过 $now+i$ 的尽量靠后的非障碍位置。
先判断最长的连续障碍段长度，否则你每个障碍最多回退一步，相当于每次不超过 $(n+m)/i$，可以通过。

1216F

设 $dp_i$ 表示恰好覆盖了不超过 $i$ 的最小代价。
那么覆盖 $i$ 应该从 $i-k$，求 $[i-2k-1,i-1]$ 的 $dp$ 最小值转移过来即可（单调队列）。
注意需要 $dp$ 到 $n+k$。

1385F

你找到深度最深的（叶子）节点，看它的父亲，如果为叶子的儿子个数 $\geq k$，就删。
如果没有 $k$ 个，那么它的父亲就没救了，包括所有儿子无论如何都不行。

1166D（#）

你考虑前缀和，$x_i=S_{i-1}+r_i$，那么 $S_i=2S_{i-1}+r_i$。
那么你要 $S_{n-1}+1<=b<=S_{n-1}+m$。
你先让 $S$ 尽量小，然后再反过来加大，先给 $S_{n-1}$ 加大同时满足条件，把剩下的给 $S_{n-2}$，再不停的往前推。

1583E（#）

根据经典套路先求一棵生成树。询问给路径上的边都+1，这个和路径具体是什么有关系。
考虑设 f[u]表示 u 相邻的边之和的奇偶性，这个和路径具体使什么没关系，一次操作给两端点都异或 1。
如果最后存在 f 是奇数显然无解，否则叶子节点的那些边已经合法，那么推到他们父亲连到父亲的边也合法，一直推可以说明所有的边都合法，即只需要取一棵生成树，合法的依旧合法。

1335F（#）

如果两个机器人走到某一步在同一个格子，那么继续走下去还会在同一个格子。
它要求一直走下去，而走 nm 步后一定会进入环，所以只需要要求走 nm 步之后不在同一个格子即可。
现在要求走 nm 后到哪个位置，这个可以用倍增（也可以对于每个环倒着处理到这个环的点，不带 log）。
能到达某个格子的多个位置，如果有黑色尽量选黑色，否则任意选。

1453E

观察一下它走的路径，容易发现进了一棵子树一定是走完了再出来，这个容易归纳证明。
你最后退出时走的那个子树，要增加一些从当前根出去的距离，所以一定是 $dp$ 最小的子树，子树之间走的一定是最大的。而根节点需要特判，你可以只走次大的，最大的走完直接结束。

650C（#）

同行/同列值相同的位置最终值也会相同，先用并查集并起来形成一个等价类。
现在一行里等价类按照权值小向大连单向边，代表大小关系，可以发现只需要连大小顺序相邻的。
最后需要的步数至少是 DAG 最长链长度，可以构造每个点的权值为 0 度点到当前点的最长链的长度达到下界。

623B（#）

还是一样，考虑最后的素因子（每个数都是它的倍数）。
如果一个数不变,+1 或-1 都不是它的倍数，那么就必须在区间内。
如果有必须在区间内的数，求它们最小和最大的位置，它们之前的一个后缀，之后的一个前缀也可以在区间内，计算一下。否则任意一个数都能在区间内，一个前缀和一个后缀不在区间内，计算一下前缀后缀。
对于原问题，由于不能删完，所以第一个数或最后一个数一定保留，它必须是它们不变,+1,-1 中某个的素因子，这样只有两位数种方案，分别判断即可。

1413E（#）

发现如果 a>bc，那么他无论怎么恢复都不如减的多，答案是无穷大。
否则 a<=bc，不妨假设 0 时刻你就攻击，到 a/b 上取整时刻，减的就比加的多了，不如第一个不做。
所以只需要考虑到[(a-1)/b]时刻，那么你一定是能攻击就攻击，在[[(a-1)/b]/d]次操作后达到最大值。
计算一下答案即可。

748D（#）

一定是中间一个回文串（或者没有），然后左边是若干个 s，右边是若干个 rev(s)。
对于代价和为正的非回文原串和反串一定选，代价和为正的回文原串和反串先选。
最后看看要不要拿掉选的回文串对中的较小值或加入未选回文串的最大值。

912D（#）

显然期望可以拆开，变成期望最大的 k 个位置的和。
对于(x,y)，能覆盖它的渔网数量=(min(x+r-1,m)-max(x,r)+1)*(min(y+r-1,m)-max(y,r)+1)。
那么两维相对独立，求出(min(x+r-1,m)-max(x,r)+1)的所有 x 的取值从大到小排，对于 y 同理。
然后可以使用堆贪心，因为 u[1]v[1]>u[2]v[1],u[1]v[1]>u[1]v[2]，取出前 k 个即可。

486E（#）

判断一个数能不能在 LIS 上：求出以每个数为开头/结尾的 LIS 长度，看看加起来-1 是否等于最长的 LIS 长度。如果等于，那么说明它在 LIS 上，且位置固定（它一定是 LIS 上第 x 个位置）。
判断一个数是不是必须在 LIS 上：看 LIS 第 x 个位置有没有多种选法，如果有就不必须在，否则必须在。

884D

倒过来变成合并，每次把两堆或三堆合并成一堆。
显然合并三堆是更优的（类似三叉哈夫曼树），但是可能合并不完，因为每次是 3->1，减少两个，如果初始有偶数堆最后会剩两堆。
发现不如初始先合并最小的两堆，再做。

1292C

推式子，它这个是个排列，

$$
\begin{aligned}
&\sum_{1\leq u\lt v\leq n} \operatorname{mex}(u \rightarrow v)\
=&\sum_{1\leq u\lt v\leq n} \sum_{i\geq 1} [\operatorname{mex}(u\rightarrow v)\geq i]\
=&\sum_{i\geq 1} \sum_{1\leq u\lt v\leq n} [\operatorname{mex}(u\rightarrow v)\geq i]
\end{aligned}
$$

也就是有多少 $(u,v)$，使得路径上包含 $0..i-1$ 的所有数。

那么首先 $0..i-1$ 要在同一条路径上 $i$ 才可能计算答案。
其次如果固定 $i$ 满足条件（$0..i-1$ 在同一条路径上），那么最理想的方案是两端有一个 $i-1$，这样到 $i-1$ 可以删去一个数。所以一定是初始有一个 $0$，然后从小到大，往链两端加入一条权值为 $i$ 的边，贡献是两端子树大小乘积。
求出这个子树大小，然后倒过来递归，每次删去两端的一端，递归下去。
状态数 $\mathcal{O}(n^2)$，转移 $\mathcal{O}(1)$，记忆化搜索即可。

1251E1

直接来做 E2。
按照 $m_i$ 从小到大排序，有个朴素的想法是设 $dp[i][j]$ 表示考虑完前 $i$ 个，$i+1..n$ 还有 $j$ 个被贿赂的最小代价。
转移第一种是 $i+1$ 被贿赂，就转移到 $dp[i+1][j-1]+q_{i+1}$；第二种是没被贿赂，那么要求 $i+j\geq m_{i+1}$，转移到 $dp[i+1][j]$。这足以通过 E1。
发现 $i+j\geq m_{i+1}$ 可以移项成为 $j\geq m_{i+1}-i$，也就是一个人跟风为你投票当且仅当后面被贿赂的人数 $\geq m_i-i+1$。
把 $m_i$ 相同的放在一起，倒过来考虑，设当前 $\geq m_i$ 被贿赂的人数为 $cnt1$，$<m_i$ 的人数为 $cnt2$，相当于现在一定有 $cnt1+cnt2$ 个人投票，如果够了，那么能全部都选；否则不够，就需要在 $\geq m_i$ 里的再贿赂一些，显然贿赂的越少越好（如果不够之后可以再贿赂），就贿赂直到 $cnt1+cnt2$ 足够，拿个小根堆存一下。

723E（#）

显然度数是奇数的永远不可能合法。
如果只有度数为偶数的点，根据套路，可以考虑欧拉路，恰好有 n 次进入 n 次退出。
如果有部分度数为奇数的点，考虑把它们度数也变成偶数，即加一个新点连向所有度数为奇数的点。这样所有度数为偶数的点都合法。

1236D

它的起点在左上角，所以你一定是越绕越小的螺旋形。假如你直走也可以走，右转也可以走，此时你必须直走，因为如果你转弯了，你就再也绕不出来了。
暴力复杂度一定是对的，你每转 2 次两维必定都减少 1。维护一下四个方向的边界，不能超出。最后为了防止不出现没走到的，判断一下走过的格子数量是否为非障碍格子数量。
你找下一个停下的位置，需要二分下一个障碍的左端和方向边界取较小值。

1028D

保证数字互不相同，ACCEPT 给你提供了一些信息，即 $x$ 的都在 $B$。
维护一定在 $A$ 中数字的最大值 $u$ 和一定在 $B$ 中数字的最小值 $v$，和所有数的 $set$。
如果 ACCEPT 的时候问的值比 $u$ 小或比 $v$ 大，就挂了，没有方案。否则如果这个数 $>u$ 且 $<v$ 那么不确定在哪个集合，方案数 $\times 2$。现在就能更新 $u,v$ 了，$u$ 是 $x$ 的最小的数。
结束时还要乘上 $u,v$ 之间的数字个数+1，可以选一个前缀给 $A$，剩下的给 $B$。

618D

从简单的入手讨论。
如果 $y\leq x$，那肯定尽量走 $y$ 边。你发现除了菊花图比较憨憨删去之后直接不连通了，其它情况一定可以都走 $y$。因为你考虑生成树是一个二分图，你如果两部有连边 $(u,v)$，你可以在左边乱跳，然后停在 $u$，再到 $v$，最后在右边乱跳。

所以如果树不是菊花，那么答案是 $(n-1)y$，否则是 $(n-2)y+x$。

如果 $x>y$，如果你选了 $a$ 条 $x$ 的路径，那么需要 $a$ 条 $y$ 把它们接起来。相当于要求树的最小（点）路径覆盖，树形 dp 即可。

242D（#）

这什么垃圾翻译。。。
和某题差不多，你每次找到一个 cnt_i=a_i 的，点一下，那么它以后再也不会不合法。
你最多把每个都点一次，所以一定有解。

804C（#）

先给 1 号点上的所有种类染色。考虑现在到点 u，这个点上还有些种类没被染过色。
这些没被染过色的，可以给它们分配和 u 中染过色不同的，且两两不同的颜色。
尽量分配编号小的颜色，种类数应该是每个点上种类数 max，可以发现没有比这样更少的方案。

980E

从大到小贪心，$n$ 必须要选。
其它的从大到小贪心，能保留就保留。
保留即路径上的都得保留，判断一下路径上点的数量。
树状数组维护 dfs 序，删点就直接暴力，树状数组给子树-1。

732E

把电脑扔进 multiset，把适配器排序贪心。
具体来说就是枚举除多少次，如果有就和 multiset 里的配对，删除。

1179C（#）

从大到小枚举最后剩下来的值 x 看看可不可行，可行当且仅当 a_i>=x 的个数严格大于 b_i>=x 的个数。
现在你要带修改，且要快速询问，保存 a_i>=x 的个数-b_i>=x 的个数，求最靠右的>0 的位置。
维护线段树，每次看右儿子的最大值，如果<=0 就到左儿子，否则到右儿子。

520D

维护一个大根堆一个小根堆，里面是能拆的方块。
拆了之后向四周扩展，把那些能拆的也加进去。取了的用 map 标记一下。

1616E

这题在现场。先求 LCP，如果有前面大于后面就直接输出 1.
否则你一定是两种情况之一：替换一个比它小的；替换一个和它一样的。
比它小的直接计算即可，维护后面每种字符的位置；一样的要移过来，维护个 vector 即可。

1498D（#）

相当于要维护这次操作过后哪些位置能到达。记 f[i]为答案。
记 g[i]表示这次操作选的 a 为多少才能到达 i，对于之前能到达的 i（之后可以一直 a=0），g[i]=0。
然后更新，从小到大，g[i]+1->g[calc(i)]，最后将 g[i]<=y 的且之前不能到达的 i，f[i]更新为当前操作的编号。

622E

显然根的不同子树独立，分开考虑。
如果两个点深度不同，它们是不影响的。
两个深度相同的有交必定会完蛋，所以一定要一个等一秒，相当于深度+1。
所以现在就变成可以给若干个数增加，问全部互不相同时和最小为多少。
排序之后贪心即可。

1190C

先手如果一步就赢那么显然先手必胜。
不能一步就赢，那么后手可以重复先手的操作使局面不变，也可以正常操作，所以要么是平局要么是后手必胜。问题的关键就看后手能不能一步就赢。
枚举先手取的区间，如果左右都相同，那么就可以必胜；否则如果两边都不完全相同，后手一定不可以获胜。如果先手不能必胜且不存在后手不可以必胜，就后手必胜。

1552E（#）

记 c=⌈n/(k−1)⌉。
考虑先取出第二次出现位置最小的 c 个区间，将[第一次,第二次]做为它们的区间。
考虑从剩下的取出第三次出现位置最小的 c 个区间，将[第二次,第三次]做为它们的区间。
以此类推共取 k-1 次。可以发现不同组的区间显然两两不交，故一个位置被覆盖的次数最多为 c。

1132D

答案显然有可二分性。
你每次一定给最邻近关机的电脑充电，因为你要求所有电脑都不能关机。
用优先队列维护电脑的关机时间，每次给最小的加，如果取出来的时候已经小于当前时间了说明它已经关机了，这个 mid 不行。

1534E（#）

假设第 i 个位置在异或中出现了 c_i 次（c_i 必须是奇数）。令 sum=Σc_i，则 k|sum，c_i<=sum/k。
满足这个当然有解，可以考虑看成矩阵（一行有 k 个，一列有 sum/k 个）以列为优先填。
在 sum 固定的情况下一定是让 max{c_i}尽量小，可以变成初始 c_i 都为 1，每次给最小的 c_i+=2，看是否满足条件。它说答案不超过 500 次，最多也就 500*k 次操作，可以通过。

1148E（#）

首先总和不变。可以把操作看成对于 s_j-s_i>=1（=1 相当于交换顺序，无关紧要）的两个数，s_j--，s_i++。
对 s_i++，s_j--，只要对值相同的取最后/最前的一个，相对顺序就不会改变，说明存在操作使相对顺序不变。
将 s,t 排序，设 a_i=t_i-s_i。现在要把前面的某个-1，后面的某个+1。可以发现有解相当于要求前缀和>0。
具体的构造方法类似于括号序，看栈底和当前数的大小关系即可。

909D

直接暴力复杂度是平方的。容易想到把同颜色当成一个同色段。
左右的同色段每次长度减少 1，中间的同色段每次长度减少 2（左右都没了）。
可以暴力，因为每个点只会消失一次，所以可以直接暴力给每个段长度 $-1/-2$，如果减没了直接暴力合并，复杂度为 $O(n)$。

576B（#）

首先树相同必须重心相同，一棵树最多有两个重心，说明必须存在一个<=2 的循环。
如果存在不动点即 p_i=i，可以造一个以 i 为根的菊花。
否则存在对换 p_a=b,p_b=a，考虑断开 a,b 的边，那么发现两部分排列后将会变成对方。
所以如果存在长度为奇数的循环则无解。否则将循环上奇数位置连 a，偶数位置连 b 即可。

496E

由于 $a_j\leq b_j$，所以可以把条件改为 $-a_j\leq -c_i,b_j\leq d_i$。
把演奏家按照 $(-c_i,d_i)$ 的二元组排序，按照顺序，你一定是取 $-a_j\leq -c_i,b_j\leq d_i$ 中 $b_j$ 最大的，因为之后的 $-c_i$ 都不比当前的小，所以你只需要尽量的取 $b_i$ 大的。

229D

题目相当于分成若干个段，使得每段和不降，问 n-最小段数。
设 $f_i$ 为 $1..i$ 不降的最少段数，$h_i$ 为此时最后一个塔的最小高度。
有一个直观的想法：存在一种答案最小的方案，最后一个数也是最小的。
这个怎么证明呢，假设 $1..i-1$ 都满足，那么 $h$ 存的就是可能的最小高度。$f_i$ 的转移即为

$$
f_i=\min_{j<i,h_j\leq sum(j+1,i)} {f_j-j}+i-1
$$

这个形式不好看，设 $g_i$ 为 $f_i-i$。

$$
g_i=\min_{j<i,h_j\leq sum(j+1,i)} {g_j}-1
$$

由于 $g_{i-1}$ 可以转移的 $j$ 在 $g_i$ 也可以转移，所以 $g_{i-1}\geq g_i$。所以你找到最大的满足条件的 $j$，它的 $g$ 一定是最小的，同时 $h$ 也是 $sum(j+1,i)$，即证明了 $i$ 也满足条件。
问题变成怎么找这个 $j$，$j<i,h_j+pre_j\leq pre_i$，而这个 $pre_i$ 也是单调递增的，故可以维护一个单调（$h_j+pre_j$ 递增）队列。

269C（#）

非源非汇的点流量平衡。
由于最后是 DAG，考虑一个类似于拓扑排序的做法。
首先入度为 0 的应该是 1 号点和无边相连的点。
那么加入队列的，没访问的邻边都是出边，更新一下，看看另一端能不能加入队列。

1603C

如果你知道一个数最后分成了 x 个，那么一定是尽量平均的分配（设 y=val mod x，则有 x-y 个 u 和 y 个 u+1，其中 u=[val/x]，无论怎么调整都不能使最大值减小或最小值增大）。
考虑怎么求整个序列的值，这就显而易见了，你从右往左，每次求最少操作几次，使得值不超过右边的数的值即可。
但是，你一个数拆分是整除的形式，即这个 u 只有 sqrt V 种，当前数尽量大，转移一下即可。

995C（#）

原来每个不超过 1e6，最后要求和不超过 1.5e6。
向量相加显然和夹角有关系，考虑哪些夹角可以。
$c^2=a^2+b^2-2ab\cos C$，不妨设 $a\leq b$，那么 $c^2\leq a^2(1-2\cos C)+b^2$，当 $cosC\leq 1/2$ 时 $c^2\leq b^2$。
（这个是把两个向量首尾相接，形成三角形两条边）。
拿出三个向量，正反有 6 个向量，一定有两个夹角 $\leq pi/3$，满足条件。
到最后只剩下两个向量时，夹角之间 $\leq pi/2$，这样长度可能乘上 $\sqrt 2$，也不超过 1.5e6。

1217E（#）

有个简单的思路，平衡的是不是每一位最多只有一个数非 0。
思考一下，发现如果有多个数某位都非 0，且还要满足条件，那么一定需要进位。
对于前面的位，如果后面有进位，要满足条件自己也要进位。
到最后会进到一个没有数出现过的位，就 gg 了。
那么不平衡的一定有两个数在某一位都非 0，要求最小就是这一位非 0 的最小的两个数之和。
线段树记录一下区间每一位非 0 的数中，最小和次小的值即可。

1158C（#）

先考虑没有-1 的情况，存在 i,j，i<j<nxt_i<nxt_j 一定无解。否则可以构造出解。
对于后缀最大值（nxt_i=n+1），它们之间的小区间又是独立的（nxt_j<=i），递归下去做。
具体实现可以类似于建树，i 的父亲是 nxt_i，层数低的比层数高的值大，同层编号小的比编号大的值大。
nxt_i=-1 的情况，直接取 nxt_i=i+1 即可，这样不会使得原来有解的变成无解。

808E

这题比较特殊的在于 $w_i$ 不超过 3。
只有两种比较经典，先从大到小排序，一定是要么+1，要么-1 +2。
枚举 3 有多少个，询问 1,2 组成的答案即可。

1468H（#）

首先每次减小 $k-1$ 个，$(n-m) mod (k-1)$ 不为 $0$ 显然无解。
设 $d=(k-1)/2$，考虑最后一步，中心是 $b_x$，删去了中心左边的 $d$ 个数，右边的 $d$ 个数。
如果不存在 $x$ 使得 $b_x$ 左/右边有 $d$ 个非 $b$ 中的数，那么显然无解。
否则你在前面删的时候，$k$ 个数都取要删的数，一定能调整成最后 $b_x$ 左右各 $d$ 个数。

549B（#）

设 b_i 表示当前 i 收到的消息数量，初始 b_i=0。如果不存在 a_i=0 那么直接结束。
每一次找到 a_i=b_i，钦定 i 加入 party，称这个操作为 fix。
那么显然每个点 fix 过后 b_i>a_i，不会再次被 fix。如果某一步找不到就结束。

508E

可以发现，只要在当前时间放右括号合法（和栈底）匹配，那么一定就直接匹配。
因为如果你中间再加点别的，不如在这个右括号后面加，并不影响其他的，只是可能导致当前栈底时间过了。
如果时间没到就加左括号拖时间，然后就可以大力模拟了！

1411E（#）

这种题目（什么能不能达到，能不能凑出来）考虑寻找不变量（输入什么都不会变，或者只和极少输入的数有关）。寻找不变量之后考虑所有能到达的状态。
对于这题，就考虑字符是什么和字符前面的符号无关，考虑哪些符号是可达的。
首先最后一个一定是+号，同样的，倒数第二个一定是-号。
考虑是否满足这个条件就可以了，找到一对+-，那么就可以从减号的位置递归。
这有一种情况可能找不到，就是------…-+，只有最后一个位置是加号，那么取 m=|S|-1 即可。
去除最后两个数的限制，之前的可以直接贪心，从大到小排序，一个一个加入。否则你后面取的一定有一部分是抵消它的（这个是 2 的幂次，一次只能在一位上加），可以全部取反。

748E

记录瓣数为 $i$ 的橘子有多少个。
从大到小枚举答案，那么 $\geq 2i-1$ 的都可以直接分了。如果当前 $\geq i$ 的橘子数量 $\geq k$，那么直接 OK，否则继续往下。

346C（#）

首先相同的 x_i 显然可以删去。2 操作相当于走到左边一个最近的 x_i 的倍数。
如果 2 操作某个 x_i 已经<b，那么之后操作这个 x_i 一定也<b，删去即可。
否则就需要决策怎么走是最优的，发现一定是走 2 操作后最小的 x_i，走到 a-a mod x_i，否则假设走另一个 x_j 更优，那么考虑某一步一定会从>=a-a mod x_i 走到<a-a mod x_i，那么这一步在 a-a mod x_i 开始也一定可以走，步数也不会更多。所以一定走 2 操作最小的。
算一下时间复杂度，你每两步操作就会使答案至少减少当前 x 的最大值，而 x 的最大值>=数字的个数，而你每次操作的复杂度也是数字的个数，所以复杂度和 a-b 是线性关系。

979D（#）

把条件转化为 v<=s-x,k|v,k|x，要求 x xor v 最大。（可以直接判断 k|x 是否满足，不满足则无解）
由于 v<=10^5，如果你知道了所有 k 的倍数建的 trie 树，复杂度为 O(log v)。
所以可以考虑在加入的时候，给所有 k|v 的 trie 插入 v。
询问时只需要对 k 的 trie 查找，trie 每个节点记录子树满足条件的最小的 v 是多少（要满足 v<=s-x），看往哪个子树走。

1601C

很容易想到，$b$ 应该是按照递增的顺序插入$a$ 的。
证明很简单，如果有相邻两个 $b$ 中的数按 $x>y$ 插入，换成 $y,x$ 一定不劣。
再想，是不是 $x<y$，$x$ 在 $a$ 中第一个最优的位置 <= $y$ 在 $a$ 中第一个最优的位置。
这个其实也好证明，设 $p$ 为 $x$ 插入到第 1 个位置前的逆序对数，$v_i=-1/0/1$（分别对应 $a_i$ 比 $x$ 小，相等，比 $x$ 大），那么 $x$ 插入到第 $i$ 个位置后有 $p+v_1+v_2+\cdots+v_i$ 个逆序对，所以第一个最优的位置为 $v$ 的前缀和最小值第一次出现的位置。
那么当 $x$ 增大时，有些 $v_i$ 减少了 $1$，对应到前缀和上是某些后缀减少了 $1$，最小值不可能前移。
一种可以用线段树维护最小值和出现位置，还有一种是用分治，求出 $mid$ 的第一个最优位置，那么左边和右边就完全没有关系了（它们之间的逆序对数是固定的），递归做即可。

552E（#）

如果把括号加在两个之间，对答案没有影响。如果加在一个 $+$ 一个 $\times$ 之间，那么在 $+$ 那段扩展，答案一定也不会变劣。
所以只有可能在两个 $\times$ 之间或一个端点一个 $\times$ 之间加，枚举一下，然后暴力计算表达式即可。

550E（#）

特判 n=1。如果最后一个数是 1，那么无论怎么操作，最后一个数的值一定是 1，无解。
如果倒数第二个是 1，那么前面怎么合并都是 1，最后和 0 合并即可。
000 可以变成 10，即只要最后 0 的个数=1 或>=3 都一定有解。
考虑最后 0 的个数为 2，即 xxx…1..100。如果之前还有 0，那么可以把 1..10 合并成 0，那么最后就有 3 个 0，有解；否则只能是 1..100，不能操作 00（最后一个数会变成 1），操作 11 或 10 都是减少 1 个 1，最后只能变成 00，00 显然没有合法方案。

1098B（#）

一种是隔行相同，隔列字符集合相同；一种是隔列相同，隔行字符集合相同。（或两者都有）
枚举一下是第一种还是第二种（2），枚举隔行/列相同的集合和顺序（4*3），枚举另一种的顺序（2），枚举另一种隔列/行变不变（2），然后算一下即可。

1062E

LCA 为 $x$，一定满足所有点的 dfs 序都在 $[dfn_x,dfn_x+siz_x-1]$。
所以如果删去的不是 dfs 序最小或最大的，并不会影响 LCA。
所以就删去 dfs 序最小的和最大的，求出剩下的 dfs 序最小的和最大的，求它们的 LCA 即可。

584E（#）

将 $p$ 变成 $1,2,…,n$，变成将 $s$ 交换成升序的最小代价。
答案的下界是 $\frac{\sum |i-p_i|}{2}$，达到下界必须每次交换都没有浪费。
考虑从大到小确定数的位置，枚举 $i$ 表示 $>i$ 的数都归位了，现在要将 i 归位。
找到 i 右边第一个 $j$ 使得 $p_j\leq pos_i$ 的位置，交换。这样显然不存在浪费，最后也一定会归位。（没归位前右边一定有 $\leq pos_i$的数）

266C（#）

递归，首先保证最后一列无 1，那么再交换有 1 的行和最后一行。
可以去掉最后一行，最后一列，再重复上面的步骤。

723F（#）

把和 s,t 不相连的边先搞出若干棵生成树。
考虑每个生成树，如果只和 s,t 中其中一个相连，那么必须要连（否则不连通）；如果都相连，可以任意选择；最后要把 s,t 连通，就选一个都相连的两边都连起来或 s,t 有边直接连起来（尽量选前者，对度数贡献小）。
所以就看都相连的个数，如果为 0 就把 s,t 连起来看看度数行不行，如果不为 0 就选一个和 s,t 都连，剩下的贪心尽量不超过上界，如果还是超就无解。

1283F（#）

每个数出现次数为儿子个数，父亲出现的一定比儿子早，没有出现的点即为叶子节点。
第一个数就是根节点，接下来考虑连边情况。
将叶子节点加入小根堆，从后往前枚举 i，弹出堆顶 u，将 a_i 和 u 连边，如果 a_i 的儿子已经连完了就加入堆。
注意到最大值只和二进制数最高位有关（最高位显然两两不同），所以维护子树里的最大值即可。

1276C（#）

不妨假设 R<=C。那么选进来的数出现次数都不超过 R。
固定了 R 之后，每种数就尽量选，看最多能选多少，再确定 C。
构造的方法是不停地往右下走，如果走过了就再往右。

286C

很容易有一种贪心的想法，就是和栈顶能匹配就匹配。
但是题目规定了某些一定为右括号，这样不好办，前面左括号数量可能不够。但是相反左括号就没有这个问题。
所以把序列倒过来，就变成钦定某些是左括号了！为什么能匹配就匹配是对的呢？
可以调整，你一定能把(())调整成()()，因为当时能是右括号你填了左括号，中间的限制都一样，所以一定能改。

1468A

容易发现，$\min(b_1,b_2)\leq \min(b_2,b_3) \Leftrightarrow b_1\leq b_3\ or\ b_2\leq b_3$。
从后往前考虑，如果 $b_{k-1}\leq b_k$ 则 $b_k$ 满足，考虑 $k-1$；否则 $b_{k-1}\gt b_k,b_{k-2}\leq b_k$ （$b_{k-2}\leq b_k\lt b_{k-1}$），那么 $b_{k-1}$ 和 $b_k$ 都满足，考虑 $k-2$。
所以就可以 dp 了。设 $dp_i$ 表示以 $i$ 结尾的答案，则 $dp_i=\min_{j<i,b_j\leq b_i}{dp_j+1},\min_{j<x<i, b_j\leq b_i\lt b_x}{dp_j+2}$。
找到每个 $i$ 之前最近的位置使得 $b_x\gt b_i$，所有数按照 $b_i$ 排序后更新 $dp$，树状数组查询，$x$ 之前的 $+2$ 转移，$x$ 及之后 $+1$ 转移即可。

1593G（#）

考虑哪些中括号一定要变成小括号，可以发现奇偶性相同的位置，不能有一对匹配的括号。
设有 a 个奇数位置的中括号，b 个偶数位置的中括号，那么至少要|a-b|个中括号要变成小括号。
将相邻的奇偶性不同的一一匹配后删去，剩下的转为小括号。
可以发现小括号一定有合法的匹配方案（中括号区间内，把更小中括号包含的删掉，剩下的长度还为偶数）。

765E

对每条边，以它为根分成两部分，求出每个儿子合并出的长度，看有几种不同的，0 种说明是叶子，1 种说明 OK，其它情况都不行。这个可以直接 dfs。
枚举根看一下儿子是否合法即可，这时候有 2 种也是可以的。

425B

分析题目给的这个条件。如果你确定了前 $i$ 行都是矩阵，那么考虑 $i+1$ 行。
考虑第 $i$ 行的某个矩形，一种是它直接封口了，就是 $i+1$ 行就不是同一个矩形了；另一种是没封口，$i+1$ 行和它是一个矩形。可以发现，下一行的对应位置，要么全部相同（同一个），要么全部相反（封口）。
但是，如果出现相邻两个一个封口一个不封，那么就连在一起了（颜色相同），而上一行不是同一个，不合法。
所以这一行要么给所有的都封口（即取反），要么都不封（和上一行相同）。
由于最多翻 $k$ 行，所以前 $k+1$ 行一定有一行没有翻，枚举那一行，bitset 求其它行的方案。

1607G

设第 $i$ 道食物吃了 $x_i$ 单位鱼肉，要满足 $\max(m-b_i,0)\leq x_i\leq min(a_i,m)$
推式子，x 之和前面系数带个 2，要求 $|S-2\sum x_i|$ 尽量小，如果都取最小/最大都不够小/不够大那么就直接取，否则就按照 S 奇偶性，最多相差 1.

356C（#）

设为 1,2,3,4 的个数分别为 a,b,c,d。最后的目标是 a,b 清零。
首先一定是 12 变成 3，现在 a,b 最多有一个非零。
如果 a 非零尽量 111 变成 3（2 次），b 非零尽量 222 变成 33（2 次），比从 4 移出来要优。现在 a,b<3。
如果 a=1，c>=1 则 13 变成 4（1 次），d>=2 则 144 变成 333（2 次），否则无解。
如果 a=2，c>=2 则 1313 变成 44（2 次），d>=1 则 114 变成 33（2 次），否则无解。
如果 b=1，d>=1 则 24 变成 33（1 次），c>=2 则 233 变成 44（2 次），否则无解。
如果 b=2，则 22 变成 4（2 次）。
发现上面产生的无解情况即总和为 1,2,5 的情况，并不会把有解判成无解。

1610E（#）

先思考如何快速判断一个不降序列是不是好的，拿出一个子序列，如果最小值=最大值则显然是好的。
如果不相等，如果存在 x,y,z(x<=y,y<=z,x(x+y+z)/3，即 2y>x+z。
会发现 x 一定取序列的最小值，y,z 会取两个相邻的值。
看是否满足这个条件就行了，因为假设是可怕的，>avg 的最小值是 y，那么你剩下的平均值要越小越好，且<avg 的个数<=除了这个数外>avg 的个数，那只会取 x,z。
枚举最小值，那么有 2(y-x)<=(z-x)，每次取的数字至少*2，可以发现能贪心的往后取第一个最小的，而且每次都至少乘 2，所以只会做 log 次，可以直接暴力二分，复杂度两个 log。

1239C

这个题意很绕，是有一个队列和一些在等待状态的人。时间到了且他前面没人在排队他就会去排。
所以维护一个事件序列，用优先队列。维护一个当前的时间，对一个到时间的人，如果前面没人排，他就加入排队队列（queue），否则他进入等待状态，由于出等待状态时按照从小到大的顺序，所以可以拿个优先队列维护。
如果队列空了就从等待状态拿最小的过来。求下一个时间点，一种是队列里有人，那么就+p，即他接水的时间；如果没人，那么就从下一个事件的时间开始。

260D（#）

把黑和白的分开，每次选出黑和白最小的两个权值，在它们之间连它们最小值的边，然后删掉一个点。
这样显然不会产生环，权值也符合条件，但是不一定连通。
找到最大的那个块（大小显然>=2），里面一定有黑点和白点，将其它的块都连权值为 0 的边上去即可。

762D

可以发现，只能在第二行后退，否则之前经过的相当于把你限制住了，你出不去。第二行后退也只能第一行/第三行前进 - 第二行后退 - 第三行/第一行前进。
这就比较憨了，因为你知道你也可以通过上下右走，使得中间有奇数列时从第一行->第三行，有偶数列时从第三行到第一行，而你这个操作是无论如何都从第一行到第三行。
你不妨只加入中间有两列的，即 $(1,x)\rightarrow (3,x+3)$，这样相当于只有上/下/右/跨两列三一互换，直接 dp 即可。

1131E（#）

对不同的字母分开来讨论。枚举字母 c。
现在有一个新的字符串 s，l,r,m 分别表示 s 左边，右边，所有的极长 c 串长度。
如果 s 所有字母都是 c，那么现在的答案就变为 m+(m+1)*|s|。
如果不是，且原先答案为 0，说明答案就是 m；否则答案为 max(l+r+1,m)即包含原先的 c 和不包含两种。

627C

把起点和终点看作代价为 0 的加油站。
到达一个加油站时，一定会加到至少能到下一个代价不比它大的加油站的油，如果加满也到不了就加满。
直接模拟即可。

731D

观察到：相同的数字永远是相同的，不同的数字永远是不同的。
两个串，除去它们的 LCP（永远相同），看下一个位置，一定得一个小于另一个（一个为空直接 OK）。
所有 $>c$ 的数之间， $>c$ 的和 $\leq c$ 的大小关系都是不变的，所以只要考虑 $\leq c$ 的数之间的大小关系。
设第 $i$ 小的数为 $p_i$，初始 $p_i=i$，一次操作把 $p_c$ 移到开头。所以你做 $c$ 次操作就会变成原序列。
操作 $x(1\leq x\lt c)$ 次相当于把最后的 $x$ 个数移到开头，即 $c-x+1,c-x+2,\cdots c,1,2,\cdots,c-x$。
如果两个数 $a,b$，本身 $ab$，那么要求 $a$ 移到开头，$b$ 没移到开头。
对于合法的区间，做个区间加。最后看最小的 $x$ 使得和为总条件数（不一定是 $n-1$，因为可能本身相邻的有一个为空）即可。

364B

它那个换过去和换回来的不能一样的限制没什么用，因为你直接不换这个就行了。
那么你每次显然希望能换到的尽量大，对后面的限制也越松（$\leq cost+d$）。
暴力的思路是每次暴力跑 01 背包，上界是当前的 $cost+d$，如果跑出来能比原来的 $cost$ 大就更新继续跑。
不过这个太傻了，背包时只有上界在变。不如刚开始跑一遍 01 背包，然后每次找当前不超过 $cost+d$ 最大的可以凑出来的位置。

1252E

字典序一般就从前往后逐位确定，需要判断这一位填 $x$ 可不可行，可行再考虑下一位。
是否可行是和后面的有关的，从后往前处理。
只有最后一位填 $[L,R]$ 都可行，其它位要满足：和某个后一位的数差的绝对值不超过 $k$；满足大小关系。大小关系是一个区间，最后一位的填法也是一个区间，所以从后往前都是两个区间的交。
初始最后一位的合法区间为 $[L,R]$，前面的位是后面 $[L-k,R+k]$ 和当前大小关系 and 之后的结果。如果某一位合法区间为空显然无解。
否则就可以从前往后贪心，第一位取最小值，然后再求个交，求交里第二位的最小值，以此类推。

1132E

求出 $\operatorname{lcm}{1,2,3,4,5,6,7,8}=840$，设它为 $L$。
那么，把 $cnt_i$ 分解成 $cnt_i=\frac{L}{i} \times p_i+q_i(0\leq q_i\lt \frac{L}{i})$。如果 $p_i$ 为 $0$ 那么直接全部加入，否则加入 $p_i-1$ 个 $L$ 和剩下的 $\frac{L}{i}+q_i$ 个，可以发现这一定能表示出原先所有的（和二进制分组类似的思想）。
现在 $i$ 只有 $<2\times \frac{L}{i}$ 个，写个暴力看看大概背包复杂度是 1e7 级别的。
最后再暴力枚举每个位置，看能加多少个 $L$，更新答案即可。

965E（#）

建出 trie 树，把树上字符串的点标记。
你现在可以把一个标记点上移，要求没有一个点有多个标记。
容易想到贪心，对于每个子树，把最深的点移到当前点，每个点维护一个堆，启发式合并。

962E（#）

显然没必要给 BR 连边。
考虑 BR 会不会和左/右方向上第一个 P 之后的位置连边，发现肯定不如连到第一个 P，第一个 P 再连出去。
同理可以证明两个 P 中间的连边是 PRR…RP，PBB…BP 的形式。

1584E

操作显然和顺序无关。先考虑整个序列。
由于 $1$ 只有一个相邻的，所以 $(1,2)$ 一定被减了恰好 $a_1$ 次，然后 $(2,3)$ 一定被减了恰好 $a_2-a_1$ 次，$(3,4)$ 一定被减了恰好 $a_3-a_2+a_1$ 次，以此类推。
现在 $1,2,\cdots, n-1$ 已经满足，而 $(n-1,n)$ 被减了 $a_{n-1}-a_{n-2}+a_{n-3}-\cdots$ 次，要求和 $a_n$ 相等，即 $a_n-a_{n-1}+a_{n-2}-\cdots=0$。
次数必须 $\geq 0$，否则不合法。
对于 $r$ 维护合法的 $l$，$r$ 变成 $r+1$ 就是给所有的都取反然后加上 $a_{r+1}$，此时新变成不满足的那些，把它们删去。再加上现在和为 $0$ 的还满足的个数。

524D

把题目写的按秒表示，就变成一个顺序的时间序列。
如果当前还在线的人数 $<M$，你就新加一个人。否则还认为是最后一次操作的人（使得不同人数尽量多）。
过程中到 $M$ 就合法，否则不合法。

238C

$u,v$ 的链上（包括 $u,v$）所有点伸出去的子树都是外向的，链上必定前缀指向 $u$ 后缀指向 $v$。
先根据每条边预处理两端为根时子树的答案，那么链上某个点的贡献可以通过相减得到。
枚举 $u$，dfs 的过程中看 $v$，外向的累加，链上的记一下方向，当前是指向 $u$ 还是指向 $v$ 即可。

575F

维护当前代价最小的区间。
如果第 $i$ 秒的区间和当前区间有交集，那么可以直接求交（不在区间内的不小于最小答案加上到区间的距离）。
没交集，不妨设当前区间在左边，那么中间（当前区间右端点-最小区间左端点）之间答案都一样。
说白了就是两个开始斜率是-1，中间斜率为 0，最后斜率为 1 的函数加起来，再把斜率>1 或<-1 的变成 1 或-1。

946E

所谓排列后能回文即最多一个字符出现奇数次，而长度为偶数，说明都出现偶数次。
枚举 lcp（越长越好），看出现奇数次的数，判断一下可不可能，可能就递归解决。

553D（#）

最小的尽量大，考虑二分答案 $mid$。
设 $i$ 周围选了 $a_i$ 个，那么 $a_i/d_i\geq mid$，即 $a_i\geq mid*d_i$。
先假设所有点都能选，$a_i=d_i$。然后把那些不能选的 $k$ 个删去，更新周围的 $a$。
之后再找到 $a_i<mid*d_i$ 的点，删去，更新周围的 $a$。
如果最后还有点就合法，否则不合法。

773C（#）

最后答案一定是一个区间，考虑如果求出了最小值，那么把那些 $r=1$ 的位置的 $r$ 变成上一个数，在把 $1$ 单独当一个数，答案就 $+1$ 了，最大值是 $1$ 的个数。
记 $a_i$ 表示 $2^i$ 的个数，$b_i$ 表示 $(2^i,2^{i+1})$ 中的数的个数。
考虑二分最小值，具体判断方法是，从小到大枚举 $i$，记录还能在后面继续加的数的数量 $x$ 和之前剩余的可以当 $r$ 的个数 $y$，尽量加 $a_i$，如果 $a_i\leq x$，则用完 $a_i$，剩下的尽量用$y$，$x$ 变成 $a_i$；否则将 $a_i$ 多余的给 $y$，$y+=a_i-x$。

1622E

绝对值最大，$n$ 很小，考虑直接枚举绝对值里的正负。
枚举完之后就知道每个 $p_i$ 对答案贡献的系数了，系数越大的分配的值越大，算一下答案，更新即可。

274D（#）

考虑如何判断两列的先后顺序。
如果有一行两列中有-1 或这两列的这一行相同，这一行就不管；否则就固定了两个的大小关系。
但是你这样暴力枚举两列再枚举每行复杂度太高。
固定某一行，现在要连这一行的边。-1 的直接不考虑，发现只需要连大小相邻的不同的。
对这一行每种权值建一个特殊点，特殊点连向这一行这种权值的点，这种权值的点又连向下一个特殊点。
现在就看建出的图有没有环，有环则无解，否则跑个拓扑序即可。

226D（#）

和 272E 类似，每次选择和为负数的一行/一列的翻转，使矩阵总和至少+2。
由于绝对值之和 mx<=1e6，且达到 mx 后一定合法，所以可以直接暴力翻。

847D（#）

枚举 i，表示必须要走到位置 i 后直接结束。拿一个堆维护之前的狗粮能吃到的最早出发时间。
那么堆里>=T-i 的就可以弹掉了，想要吃它们走不到 i。
如果当前位置本身就走不到就直接退出。否则加入当前狗粮的出发时间 T-i，判断堆的大小即可。

518E（#）

把式子重复项删去，变成 a1<a{k+1},a2<a{k+2},…,a_{n-k}<a_k。
即 a1<a{k+1}<a{2k+1}<…，a_2<a{k+2}<a{2k+2}<…，…，a_k<a{2k}<a_{3k}<…。
这个要求绝对值之和尽量小，就不能用经典套路了。不过还是可以对两个固定位置之间的取值分类讨论。
如果两个固定的都是负的，中间的数尽量往大取。如果两个固定的数都是正的，中间的数尽量往小取。否则要使得绝对值之和尽量小，中间的数正负的个数尽量平均。
为了方便起见，可以认为每个这样的下标差为 k 的序列中，开头有个负无穷，结尾有个正无穷。

1607H

操作后两个数的和为 $a_i+b_i-m$，和不同的两个数一定不同。
现在这个 $b$ 就没啥用了，存 $a$ 可能的范围（区间，注意要 $a,b$ 都非负），两个数要相同必须区间有交。
现在问题就变为数轴上有一大堆的线段，取若干个点覆盖到每一条线段。
贪心，按照右端点排序，如果当前区间没被覆盖，那么覆盖右端点是最优的，排序做一遍即可。

332C

假设确定了学生选了哪些，那么主席首先要让不满意度尽量小，所以一定会取不满意度最大的若干个。
其次要让白头发尽量少，那么就可以按照 $(-b_i,a_i)$从小到大排序，取前 $k$ 个，也就是说后面 $p-k$ 个不会被取。
那么整个序列的最后 $p-k$ 个都不会被取，剩下的学生会取 $(a_i,-b_i)$ 最大的若干个给主席，再塞上最后的 $p-k$ 个，就达到学生期望了。

19C

判断长度为 $L$ 的有没有出现，有个 NOI 题的经典套路：每 $L$ 个位置设一个关键点，那么两个相邻相同的串中关键点的位置相同，求个 LCP/LCS 就可以了，这样套个后缀数组 ST 表查询，是 $O(n\log n)$ 的（调和级数）。
不过好像可以直接暴力枚举，因为每种只出现 $10$ 次，暴力枚举开头判断 LCP 应该也行。

77C

考虑树形 dp，设 $dp[u]$ 表示考虑 $u$ 的子树，从 $u$ 出发回到 $u$ 的最大答案。
有没有可能第一次走到某个 $v$ 然后下去走了一圈，第二次再走到某个 $v$ 下去走一圈呢？发现这和第一次到 $v$ 然后两圈绕完，再 $v,u$ 之间走一次是等价的。
所以每个子树绕圈只有一次，转移考虑首先是尽量希望走到某个子树走一圈再上来，如果还有剩余，就走到某个儿子再走上来。
绕一圈的按照 dp 值从大到小取，还有多就把儿子剩下的加起来，和当前剩下的取 $\min$，能取多少取多少。

1085E（#）

对于 a,b 相等的前缀，s 也必须和它们相等。
对于不等的第一个位置，看能不能介于它们之间。
如果不行之后就只有压下界或压上界，你就一位一位往后枚举，再枚举填什么，看是否可行，如果不行看能不能压界，还不行就没办法了。

847F

显然 2 不好判，1,3 相对来说都还好。
1 操作，把初始的所有人按照(票数,最后一票时间)排序，枚举 $i$ 为结束，那么 $i$ 之前的都不用操作，后面的从前往后尽量加到比 $i$ 的票数恰好多 1，看 $i$ 还在不在里面，如果在说明无论如何都能选中。
3 操作，如果加上所有的票都选不上，那么就一定选不上了（特判 a=m，剩下的情况他一定是时间最晚的）。

429C（#）

每个点的儿子个数为 0 或 2 的图有个重要的性质：设叶子节点个数为 x，那么 1+2(n-x)=n，x=(n+1)/2。
儿子个数可以>2 的话叶子节点数可能更多。由于非叶子节点两两等价，设 f(s)表示 s 集合的点是否能构成一棵树（非叶子节点数为|s|，总点数为 s 中 c_i 的最大值）。
转移的时候需要用 g(s,i)表示选了 s 的点，为若干个森林（至少 2 个），叶子节点个数为 i 是否可行。
注意特判叶子节点数>12 和 n=1。

1425E

$k=0$，不能操作，你只会激活一个点，选后缀和-代价最小的。
$k>=2$，如果 $k=2$ 你可以把任意一个点移到链的左端，激活它，即只需要花最小原子的代价就可以得到所有（或只激活最后一个），$k>2$ 我在移到左端的过程中先把要移的点的出边乱接几次，最后再接到正确的。
$k=1$，是最麻烦的。考虑修改的是 $i$ 的出边，一种是变成往前，一种是变成往 $i+1$ 后，往前一定连到 $1$，连 $1$ 的话就变成环和链，环一定选最小的（可能不选），链就选后缀和-代价最小的（可能不选）；往后就连到 $i+2$，选 $1..i$ 最小的/$i+1$或之后的后缀和-代价最小的/都选。

1387B1

贪心。由深到浅考虑每个点。
对于一个点，把它和它的父亲节点交换，答案+2，再把两个点都打上标记。
每次取最深的点时如果被标记那么就跳过。
最后根节点可能没打标记，那么它和任意儿子也交换一下，答案+2。

475C（#）

注意到每次只能向下或向右，所以路径长度是 O(n+m)的。
找到最靠上其次最靠左的 X，它横向的连续 X 有 x 个，纵向的连续 X 有 y 个。
那么考虑第一步如果往右说明纵向的必须为 y 个，往下说明横向的必须为 x 个。
可以直接暴力枚举另一个方向的长度，然后暴力判断是否合法。复杂度为 O((n+m)^2)。

1070G

枚举集合点，如果集合点不是怪的话两边就直接独立了，否则需要枚举两边哪边先移动。
现在把两边分开，不妨只考虑左边。
你从右往左，如果这个点能移动到集合点就移动（因为它会把它到集合点路径上所有的东西清空，在它左边的能走到它后面的就可以直接走过去了）。
如果最左边的不能移动那么就不行，否则你把原来不能移动的最后再移动即可（所有的都清空了，一定能走）。
判断能不能移动可以从每个点开始预处理，类似右端点固定求后缀和最小值。

949D

先思考如果只有一端有宿管怎么做。
可以发现，假设马上要查寝室 $i$，那么所有人都移动到 $\max(pos-d,i)$，再把 $i$ 位置上多余的人移动到 $i+1$。特别的，如果这样移动位置 $i$ 人数还不到 $b$ 个，那么全部移到 $i+1$。
可以发现两端的也差不多，你先用同样的方法，求出宿管只在左边/右边时哪些寝室人数能达到 $b$ 个，假设左边有 $x$ 个寝室，那么把前 $xb$ 个人当作左边的，其它当成右边的，分别做结果不会改变。
所以就看现在两边不能满足条件的人数的较大值即可。

1618G

考虑固定了 $k$ 怎么做，有一种贪心的想法是你每次能换多大换多大，一直换直到换不了，以任意顺序换即可。
你把相邻的价值差不超过 $k$ 的合并到一个并查集，求出并查集里原本属于自己的物品个数，它们可以被换成并查集里前 $k$ 大的数。
由于并查集对应的是原来物品排序后的一个区间，所以容易求出前 $k$ 大的数之和（原物品序列做一遍前缀和就好了）。
维护并查集里原本属于自己的物品数量，最右边的数的位置即可。
对于多个 $k$，把相邻物品差从小到大排序，把 $k$ 也从小到大排序，每次把差值 $\leq$ 当前 $k$ 的都合并即可。

1039A（#）

题目给定 a_i 是单调递增的，那么 a_i+t 也是单调递增的，且 b_i 是单调递增的，所以 b_i>=a_i+t。
那么说明 xi>=i，否则一定无解。否则若 x_i=c，那么删除 b_c 和 a_i 后对应位置依旧需满足 b>=a+t。即变成 b_i>=a{i+1}+t,b{i+1}>=a{i+2}+t,…,b_{c-1}>=a_c+t。满足条件的情况下要求 b 尽量小（否则 x_i 可能>c）。
最后再判断一下 x_i 是否=c 即可。

542F

贪心，每次取两个时间相等的权值最大的，把它们合并成一个点，时间变成 $i+1$。如果只有一个问题，那么无法合并，也认为时间变成 $i+1$。
对过程中每个点权值求个最大值即可。

522C

如果之前没有人不满意，通过跳过的人数和每盘菜已经用了多少是可以知道有没有可能用完的。
如果有人不满意，说明有一道菜之前就用光了。只有第一个不满意的人有意义，因为后面的可能都是因为和这个人同一道菜没有才难过。
你可以推测，之后别人吃的菜一定不是，前面所有吃这种菜+不知道的数量还不到 $a_i$ 的也一定不是，否则可以是。

594C

原题面写的很离谱，反正意思是删掉 $k$ 个矩形使得包含这些矩形的最小矩形面积最小。
容易想到一定是删除 $x$ 轴最小最大的若干个，$y$ 轴最小最大的若干个。
直接 $O(k^4)$ 枚举，去个重计算一下实际删点个数，如果 $\leq k$ 则更新答案。

846E

把所有 $i$ 和 $x_i$ 连一条边。现在是 $k_i$ 个父亲能变为 $1$ 个儿子，$1$ 个儿子能变为 $1$ 个父亲。
设 $dp[u]$ 表示 $u$ 的子树做完之后，$u$ 点最多剩下多少（负的代表最少还缺多少）。
初值为 $b_i-a_i$，转移就是那些非负的儿子直接把权值给父亲，负的要从父亲里要，计算一下。
最后只要 $dp[1]$ 非负即可，如果要构造方案就考虑从 $1$ 开始，先做正儿子，再把自己多余的贴给负儿子，再做负儿子。

730D（#）

可以贪心，走完第 i 座桥，首先要求喝的饮料数尽量少，其次要求当前饮料剩下来的时间尽量多。
新来了一座桥，如果能直接走过去不超时就直接走，否则先把当前剩下的双倍时间走完，然后看能不能直接走（t>=2l）到下一个，能就走，否则先把能走的 t-l 暴力走（l-x<=t-2x,x<=t-l），接下来必须要一直喝饮料，只要>=r 就开始暴力喝饮料，距离-r（如果 ans 过大直接用除和模代替）。

467E

$ABAB$，可以调整成两个 $A$ 在原序列中相邻（即中间没有其它的 $A$），两个 $B$ 在原序列中相邻（即中间没有其它的 $B$），具体方法是先 fix 第一个 $B$，$A$ 变成它左/右边第一个 $A$，再 fix 第二个 $A$，$B$ 变成它左/右边第一个 $B$。
然后可以贪心，每次取 $ABAB$ 右端点最小的，然后把当前 $pos$ 变为右端点+1。
枚举第二个 $B$ 的位置，看上一个 $B$，如果有两个 $A$ 夹着它，说明就 OK，右端点就是当前位置。两个 $A$ 夹着怎么判断呢？你拿个栈维护，如果它的上一次出现位置被删了直接 OK，否则把被夹着的数全部删了。
总复杂度 $O(n)$。

1250G

如果你每次做都 reset，能赢那么说明一定不是无解，到这一步一定可以；如果到某一步会输，那么一定要在这一步之前结束。
之前只要没分出正负，按一次 reset 和之前一直按 reset 是完全一样的。枚举最后一次 reset 的时间，之前就是分不出胜负就继续，要分出胜负就 reset。之后看哪个赢可以二分时间前缀和判断。

727F

题目等价于每次给定 $a0$，询问删除掉几个数能使得任意前缀和非负。
有一个牛逼的思路，你倒着过来扫，如果是正的就抵消之前的负的，最后那些剩下的就得给 $a[0]$ 抵消。
你把那些没被抵消的拿出来，从大到小（负数）做个前缀和，你可以自己抵消一个前缀，然后把后缀的移除，二分一下即可。

414D

容易想到，比如是第 $x$ 时刻最大，那么其它时刻到的，对应初始的时候就不用放。
现在就是所有的都得在同一时刻到，也就是说在某一时刻所有点在同一深度，然后向上。
如果选择点的深度范围是 $[l,r]$，且深度为 $i$ 的点有 $c[i]$ 个，那么到同一深度需要的代价为：

$$
\sum_{i=l}^r (r-i)*c[i]
$$

原因就是考虑每升水等了多少次，刚开始 $l..r-1$ 深度的水等了一次，再 $l..r-2$ 的水等了一次，以此类推。
把所有点的深度拿出来排序，选出来的一定是一段连续的区间，设最大的深度为 $x$，需要的代价为：

$$
\sum_{i=l}^r (x-dep[i])
$$

现在就可以 two-pointers 来求代价不超过 $p$ 的区间了，注意 $r$ 移动时可能改变 $x$，此时需要加/减区间长度（试写法而定）。

746F

你对于每个 $l$，要求最大的可以听到的 $r$，中间所有的乐趣值都能得到。
显然你尽量会让时间长的只听一半。拿两个 multiset 维护，一个是听一半的歌，一个是剩下的歌。
加入的话就先加到听一半的，如果 $>k$ 首就把最小的移到剩下的歌。
删除的时候，如果在听一半的里删，还有剩下的歌的话从剩下的歌移一首过来。
维护听一半的歌的/2 上取整值之和和剩下的歌的值之和。

432E（#）

刚开始想的是每次找 Up-Left most 的位置，填尽量小的数，然后边长尽量长。
后来发现不对，你填尽量小的数，可能别的数更小但你不能填。
应该改为填尽量小的数，填到一个这一行能填更小字母的位置或不能填的位置。

81D（#）

首先每个数放的次数不能超过[n/2]，所以 a_i 可以和[n/2]取 min。如果 a_i 之和不到 n 那么无解。
如果有一种数的数量是[n/2]，考虑 n 的奇偶性，如果是偶数那么在所有偶数位置放这个数，奇数位置任意放其它数；如果是奇数依旧在所有偶数位置放这个数，剩下必然至少有两种数（否则总和不到），各取一个放 1,n 两位置，剩下随便放。
否则，对于每种数，按照顺序 1,3,5,7,…,2,4,6,8,…放下去即可。

132D（#）

你考虑长为 len 的一段数的表示方法：
给每个 1 的位置+；
（在最后一个位置为 1 的情况下）$+2^{len}$，$-2^0$，再给每个为 0 的位置-。
有一个容易想到的错误贪心：对于每一段 1，如果长度为 1 就直接+，否则在最低位-，最高位+1 的位置+。
很显然第二种表示方法只有第一个位置和最后一个位置都为 1 才有意义，否则你可以删去前后的 0。
继续考虑，发现第二种如果其中有连续的>=2 个 0，你可以把它拆分成前后都用第二种不会更劣。
对于长度 len>=2 的，开头结尾没有 0 的，其中没有连续>=2 个 0 的，且倒数第二个位置是 1，用第二种不比第一种更劣（1 的个数>=0 的个数+2），也不比拆分更劣。
在开头加两个 0，从低位往高位考虑，如果这一位和下一位都是 1，则这一位为第二种的起点，直到出现某一位和它下一位都是 0 结束，否则的话用第一种。

370D（#）

一定有一维卡边界，你可以知道正方形的边长是 max(xmax-xmin,ymax-ymin)。
枚举卡边界的是 x 维还是 y 维，已知边长，看另一维有没有合法方案即可。

958E2

直接 $dp$，设 $dp_{i,j}$ 表示前 $i$ 个时间点选了 $j$ 个区间的最小代价。
而区间只会是相邻端点形成的，非相邻端点形成的区间代价更大。
那么 $dp_{i,j}=\min{dp_{i-1,j},dp_{i-2,j-1}+a[i]-a[i-1]}$。
这个明显是凸的，可以使用 wqs 二分来优化，把每个区间代价减去 $mid$。

123C

对于所有 $(i,j)$，可以发现 $(i-1,j)$ 和 $(i,j-1)$ 必须得相同（都从 $(i-1,j-1)$ 过来）。
那么容易发现，与 $(1,1)$ 距离为 $d$ 的都相同（相当于是个斜角线），那么这条斜角线只需要考虑上面优先级最小的点。
现在就变成一个序列问题，首先得是一个合法序列，然后得满足按照优先级第 $k$ 小。
然后逐位确定，也就是看优先级最小的填左括号的方案数，如果 $\geq k$ 就填左括号，否则填右括号。

1231E（#）

排序后不同显然无解。每个数显然只会被操作一次。
考虑被保留下来的，相当于你要找一个 S 的子序列，T 的子串，使长度尽量长。
枚举 T 中的左端点，枚举 S，看最多能有多长。

353E

考虑那些连续的指向一个方向的段。如果一个点在长度 $\geq 2$ 的段就标记一下。
在长度 $\geq 2$ 的会选非两端的，而交替段（一堆长度为 $1$ 的）只能选一半（(x-1)/2 下取整）。

958B2（#）

选出离某个点最远的点当根，把树长链剖分。
把长链的长度都拿出来，排序，贪心的选即可。
你一定会先选长链，不完整的链一定会后取到。

313E（#）

加起来的和 mod m 只有 $<m$，不用减和 $\geq m$，要减去 m 两种可能。
开个桶记录每个数字出现次数，你显然希望 mod m 和为 m-1 的尽量多，那么只有 b=m-1-a(a+b=m-1)的情况（不存在 a+b=2m-1）。
从小到大枚举 a，如果对于一个 a_i 找不到多余的 b=m-1-a 的话，就先压进栈里，如果之后的 b=m-1-a’多余的话可以和栈里的匹配（b 和更大的 a 匹配然后-m 一定不优，a 和之后更小的 b 匹配也一定不优）。
对于剩下来栈里的 a，和多余的 b 之和一定>m，从大到小枚举 b，弹栈（一定-m 那肯定越大越好）。
最后排序输出即可。

404E

碰不到的墙，你放在那里也没用。
原点两侧只需要考虑第一个墙，之后的墙一定碰不到，也没用。
而如果两边都有墙，你必须两堵墙都撞到一次，那么之后再走任何一个位置（或者不动）都不满足条件了。故最多只有一边有墙。
没有墙的话直接模拟。
有墙的话，最后一步往左一定在右边，反之亦然（如果不在这一边，而墙又撞到了，说明之前一定把墙到原点的都覆盖了，而在原点右边往左一定也不行）。
离原点更近的摆放方案一定越优，它抵消了更多的反向移动。
二分最远的摆放位置即可。

73D

考虑你做完了第一个操作之后怎么做第二个操作。
那么每个连通块具体哪个点连是没有关系的，只需要认为最多连 $\min(tot,k)$ 条边。
每条边都可以连接两个连通块，所以 $\sum min(tot_i,k)\geq 2(m-1)$，$m$ 为连通块数。
尽量使所有的 $tot_i$ 都不超过 $k$，超过 $k$ 就无效了，每次选最小的连通块连，左边计数一下。

1218I

题意是指可以把一行或一列对应位置异或上 $c$ 数组，求一组方案从 $a$ 变成 $b$。
首先求出两个矩阵的异或 $a\oplus b$，现在变成从全 $0$ 矩阵变成 $a\oplus b$ 的解决方案。
也差不多，枚举一下行选不选，列选不选。如果有种情况不合法，即代表两变量不能同时满足。2-SAT 建边输出方案即可。

101D

每条边只能经过两次，那么说明你走进了某个子树，必须走完了再走出来。
设走完 $u$ 子树需要最少的时间为 $f[u]$，那么从 $\sum f[v]$ 转移（和它们的顺序无关）。
和它们的顺序有关的是所谓的平均时间，把那个 $n-1$ 最后再除。设走完 $u$ 子树所有点的答案为 $g[u]$。
考虑两个子树 $x,y$，$x$ 在 $y$ 之前新增的贡献是 $f[y]sz[x]$，$y$ 在 $x$ 之前新增的贡献是 $f[x]sz[y]$，那么如果 $f[y]sz[x]<f[x]sz[y]$ 则说明 $x$ 在 $y$ 之前，排序后更新即可。

858E

记 Sample 为 $A$，Regular 为 $B$。
先求出 $A$ 的个数 $x$，那么 $1,2,\cdots,x$ 都是 $A$，$x+1,x+2,\cdots,n$ 都是 $B$。
如果本身是 $A$ 且在 $A$ 的位置上，本身是 $B$ 且在 $B$ 的位置上，那么删去。
剩下的，再记录占着 $B$ 的位置的 $A$，占着 $A$ 位置的 $B$，占着其它位置的 $A$，占着其它位置的 $B$ 记录。还有 $A,B$ 的空余位置也要记录。
首先尽量让占着位置的赶紧走，所以如果是 $A$ 占 $B$ 且 $A$ 有空位，移过去；$B$ 占 $A$同理。
如果还有占着其它位置的，就把一个占着其它位置的 $A$ 或 $B$ 移过去。
如果以上都不满足，即有占着位置且没有空位，把一个占位置的移到其它位置即可。

144E

相当于你要到 $x+y=n+1$，每次可以 $x--$ 或 $y--$。
只要目标点不重复，过程一定是可以做到不重复的。因为过程重复只有可能是距离相同的点，你一定可以通过调整来做到不重复（起点和终点都按 $x$ 从小到大）。
所以，每个点能到达的最终 $x$ 的范围是一个区间，问题选出若干个点使得每个点和区间一一匹配。
把区间按右端点从小到大排序，相同按左端点从大到小排序，选最左边的没覆盖的点，贪心即可。

491B（#）

把曼哈顿距离的绝对值拆了，分别记录 x+y,x-y,-x+y,-x-y 的最大值。
对于每种方案，算一下四个的最大值是否比当前答案小，小就替换。

134C（#）

拿个堆维护每个人手上还剩的自己的牌的数量。考虑自己的牌最多的人 x，尽量要让自己的牌最多的人牌数最少和剩下的还有牌的人最多，就和剩下的自己的牌的数量从大到小前 x 大的人交换，使它们自己的牌都-1。

76B

和每个老鼠最近的奶酪要么一个要么两个。
把所有只有一个最近的要选的奶酪去掉，这些到底给其中的哪些老鼠其实没啥关系，反正总数是对的（你如果有但是不给，要给有两种选择的老鼠，那么这个老鼠空着还不如交换一下不会更劣）。
对于剩下的两种的老鼠，从左往右扫过去，如果他左边没有覆盖，那么选左边的；否则看右边有没有覆盖，没有的话选右边的；都覆盖了就不选了（反正距离都是一样的）。

248D

先二分答案。然后分情况考虑。
一种是走，直到过程中拿到的糖果数=人数，则回来。
一种是走到底（拿到足够的糖果，且至少到最后一个人）返回。
实际上如果你必须回到开头就没第二种什么事了，第二种省下的是最后一趟回来的时间。

306B

相当于选出尽量少的区间覆盖所有位置。
贪心，维护当前覆盖到的位置 $x$，然后找下一个区间使得满足覆盖的部分连续且右端点尽量大（就是左端点不超过 $x+1$ 的右端点最大是多少），然后覆盖过去即可。

86B（#）

从上到下，从左到右，先用 $12$ 和 $21$ 的来覆盖。剩下的空位找四连通的已经被覆盖的接在一起。
如果没有说明四连通都是障碍物，无解。可以证明每个块大小不超过 $5$。

125D（#）

考虑前三个位置，必有两个在同一等差数列，枚举一下，就知道等差数列的前两项和公差。
由于数字互不相同，直接往后取即可。取完了之后，剩下的给第二个数列。
但是第一个数列可能没有这么长，可能删去了一段后缀。
先特判第一个数列不删，删去最后一个位置，删去最后两个位置可不可行。
否则至少删去三个位置，第二个数列的最后两个数固定了，可以倒推哪些数要在第二个数列，反过来判断第一个数列即可。

120I

经典枚举 lcp。
从后往前枚举 lcp 长度，然后枚举这一位填什么。
那么之后位幸运值最大的填法就是和当前填的一样，计算一下是否合法，合法就往后一位一位算即可。

1431F

先二分答案。
然后从左到右，维护当前块所有数字的优先队列，如果大小为 $m$ 且 $sum$ 满足条件就可以分一块，否则如果大小为 $m$ 看当前的是不是比最大值小，是的话也替换。

1431G（严谨正确性证明？）

先发现一个结论，Alice 选了一个数后，Bob 一定会选比它大的最小的。
把选出的数分成若干段，那么每段一定长度为偶数，而把前一半 Alice 选，后一半 Bob 选一定最大，Alice 从中间开始往左边选。
直接二维 dp，记录当前到 $i$，选了 $j$ 个。转移就枚举当前连续段 $x$ 的长度。

Games

1333D（#）

求最少和最多的次数，中间的都可以求出。
最多的步数是每一次删除一个逆序对，最小的步数可以贪心能翻就翻。
再根据最小步数的方案往大调整。

936B（#）

先做一遍 dfs，记录一下到每个点有没有长度为奇数和偶数的路径。
如果不存在到某个 0 出度点长度为奇数的路径，那么看从 s 开始能不能走到环。
没必要 tarjan，直接从 s 开始 dfs，看有没有后向边即可。
说一下具体原因：前向边显然可以用若干条树边替代，后向边有就一定成环，横边一定是 dfs 序大的连向小的。如果有后向边就成环，没有的话前向边没用，横边也一定不成环。

768E

值域只有 60。拿二进制数记录选过的，暴力跑个求 sg。
然后就把所有 sg 异或起来，为 0 就是 NO，否则是 YES。

1605D（#）

首先看条件 u \oplus v\leq min(u,v)，不妨设 u
所以条件就变为 u,v 最高位相同。由于是轮流操作，你还可以把树黑白染色。
显然所有点都不能动的构造最大。看黑白两边的节点个数 x,y，不妨设 x\leq y。
最高位不同的数之间相互独立，把 x 二进制分解，最高位是那些的都放到 x，剩下的都放到 y。
那么所有点相邻的都没有同最高位的，所以都不能走。

603C（#）

显然不同石子堆是独立的，将 sg 值异或即可。
如果 x 是奇数，sg(x)=mex(sg(x-1))；如果 x 是偶数，sg(x)=mex(sg(x-1),sg’(x/2))。
sg’(x)=sg(x)^sg(x)^…^sg(x)（k 个），即 k 是奇数为 sg(x)，k 是偶数为 0。
k 是奇数则 x 奇数 mex(sg(x-1))，x 偶数 mex(sg(x-1),sg’(x/2))。
k 是偶数则 x 奇数 mex(sg(x-1))，x 偶数 mex(sg(x-1),0)。
推出最前面的几个值，发现 x 是奇数值就是 0，x 是偶数递归即可。

549C

分析一下最后一步能赢的情况。
如果是先手：
全是偶数，后手胜
全是奇数，如果数字个数是偶数，先手胜，否则后手胜
有奇有偶，先手胜
如果是后手：
全是偶数，后手胜
全是奇数，如果数字个数是偶数，先手胜，否则后手胜
有奇有偶，后手胜
具体的方法是：
先手：
后手操作的步数>=奇数数字个数，后手胜
（后手不存在奇数偶数都取不完的情况，此时说明后手能取完所有偶数）
看 k 的奇偶性，奇数先手胜偶数后手胜
后手：
先手操作的步数>=偶数数字个数，看 k 的奇偶性，奇数先手胜偶数后手胜
其它情况都后手胜

520D（#）

维护一个大根堆一个小根堆，里面是能拆的方块。
拆了之后向四周扩展，把那些能拆的也加进去。取了的用 map 标记一下。

1190C（#）

先手如果一步就赢那么显然先手必胜。
不能一步就赢，那么后手可以重复先手的操作使局面不变，也可以正常操作，所以要么是平局要么是后手必胜。问题的关键就看后手能不能一步就赢。
枚举先手取的区间，如果左右都相同，那么就可以必胜；否则如果两边都不完全相同，后手一定不可以获胜。如果先手不能必胜且不存在后手不可以必胜，就后手必胜。

594A

这个题就非常强大。
你先找到一个平衡状态，就是看上去两个人都不亏的状态，保留两个距离为 $n/2$ 的，A 删两边 B 删中间。
由于 A 先操作，你找距离为 $n/2$ 的最近的点对。
首先你看这个能不能达到，你就按照自己的策略删，如果 B 乱删，删了我要删的，那我就跳过，最后只要保证我把想删的都删了，答案一定不比原来的大，那么 B 就亏了。
其次你看能不能比这个更优，考虑最后一步，B 一定会删除它们的中位数。可以发现 B 可以每次在 A 操作完后选择中位数删除，选这个点无论怎样都不会帮 A 的忙（删掉他想删的左边的或右边的），而只要不帮 A 的忙 A 就不可能变得更优。

731E

设 $dp[i]$ 表示考虑完了前 $i$ 个数的最大收益。
如果 $i$ 不选，从 $dp_{i-1}$ 转移。
如果 $i$ 选，前缀和固定为 $pre_i$，那么上一步就是另一个人选，从 $a_i-dp_{i-1}$ 转移过来。
（也可以设 $f[i]$ 表示以 $i$ 结尾，选了 $i$，然后记录前缀最大值转移）。

282D

一个数直接取完，如果初始就为 0 则先手必败，否则先手必胜。
两个数的时候是威佐夫游戏（Wythoff's Game），根据结论，只有任意非负整数 $k$，$([k\varphi],[k\varphi^2])$ 是必败态。不过这个值域可以直接 $O(V^3)$ dp。关于威佐夫游戏：

详见：https://en.wikipedia.org/wiki/Wythoff%27s_game

三个数，结论是它和普通 nim 一样。为什么呢？
如果 $a\oplus b\oplus c\neq 0$，你和普通 nim 一样可以到 $a\oplus b\oplus c=0$ 的。
如果 $a\oplus b\oplus c=0$，你看看能不能翻盘。假如变成 $(a-x)\oplus (b-x)\oplus (c-x)$，考虑 $x$ 的最低位 $k$，所有数 $\bmod 2^{k+1}$，那么原先异或为 $0$ 说明第 $k$ 位有 $0/2$ 个 $1$，减了之后就变成 $3/1$ 个 $1$，一定不为 $0$，不能翻盘。

850C

不同质因子的贡献是独立的，可以用 sg 合并。
分解质因数，对于同一个质因子，求出每个数字中这个质因子出现次数（$0$ 不需要加入），那么现在总数字个数不超过 $9n$（$23571113171923*29>10^9$）。
现在就变成选一个 $x$，把所有 $\geq x$ 的都减去 $x$，问多少步能都变成 $0$。
因为是都变成 $0$，而值相同的数受到的影响是相同的，所以只需要记录每个数是否出现过。状态只有 $30$ 位。
把出现过的位置记录成二进制数 $s$，那么一次选 $x$ 的操作变为 $(s\&(2^x-1))|(s/2^x)$。
这个可以暴力记忆化，分析复杂度可以考虑认为前 $2^{20}$ 个状态是预处理的。

377C

如果操作不是前 $m$ 大的一定不优，
只会操作前 $m$ 大的。
pick 的时候，如果 misspick，还是会随机一个给你，还不如你手动 pick。
ban 的时候，如果你 missban，$m$ 还是会 $-1$，即相当于你 ban 了最小的，还不如你手动 ban。
你直接记录二进制状态表示哪些英雄被 ban/pick 了，当前操作的人在最优策略下的优势。
转移的时候就考虑当前和上一个的人是否相同，不相同前一个系数是负的，相同系数是正的。如果是 ban 不会加上 $a_i$，否则加上 $a_i$。

1584E（#）

操作显然和顺序无关。先考虑整个序列。
由于 $1$ 只有一个相邻的，所以 $(1,2)$ 一定被减了恰好 $a_1$ 次，然后 $(2,3)$ 一定被减了恰好 $a_2-a_1$ 次，$(3,4)$ 一定被减了恰好 $a_3-a_2+a_1$ 次，以此类推。
现在 $1,2,\cdots, n-1$ 已经满足，而 $(n-1,n)$ 被减了 $a_{n-1}-a_{n-2}+a_{n-3}-\cdots$ 次，要求和 $a_n$ 相等，即 $a_n-a_{n-1}+a_{n-2}-\cdots=0$。
次数必须 $\geq 0$，否则不合法。
对于 $r$ 维护合法的 $l$，$r$ 变成 $r+1$ 就是给所有的都取反然后加上 $a_{r+1}$，此时新变成不满足的那些，把它们删去。再加上现在和为 $0$ 的还满足的个数。

317D

对于每个不是别的数的次幂 $x$，你选了个 $x^a$，那么 $x^{2a},x^{3a},\cdots$。
求出最大的 $c$ 满足 $x^c\leq n$，那么每次选一个 $a$ 就是把所有 $a$ 的倍数的位置都标记成不能选。这个可以暴力二进制记录状态计算。
打表打出 sg 值，然后询问对次数可以大于 $1$ 的 sqrt 个暴力异或，>sqrt 的直接求出个数异或。

812E

它给的这个奇偶性相同的条件非常有意思。把一堆石子移到下一层又很像阶梯 nim。
把叶子节点的层当作有效层，往上一层是无效层，以此类推。
那么就和阶梯 nim 完全一样，你从无效层移到有效层另一个人可以复读，所以就是所有有效层上点 $a$ 的异或和。
如果初始异或和就是 $0$，那么要求交换后异或和还是 $0$，满足条件要么是有效层之间交换或无效层之间交换，要么是有效层和无效层两个值相同的交换。
如果初始异或和不是 $0$，那么要求选有效层的一个和无效层的一个要求值异或起来恰好是当前异或和。

255E（#）

sg 打表，从四次根号到二次根号里求个 mex。
x 比较小直接输出 sg 值。
x 比较大，开个根号就足够小了，预处理前缀和计算 sg 为 j 数量，就可以求 mex 了。
可以发现 sg 值不大，所以可以直接暴力。
有另外一种方法是直接打表，sg 值是整段出现的。
<4 的值为 0，<16 的值为 1，<82 的值为 2，<6724 的值为 0，<50626 的值为 3，<2562991876 的值为 1，剩下的值为 2。（大概也能看出来是成段出现的，4 次根号和 2 次根号跨度很大，当 n 很大的时候下界都差不多）。

167C（#）

f(a,0)=0,f(a,1)=1。要求 f(a,b)（a>=b），先考虑 f(b,a mod b)，如果是必败那显然直接取。
如果是必胜，那么考虑做 f(a-b^k,b)，但是你发现还得 a-b^k>=b，否则相当于变成 a mod b 了，而且你无论减多少次 b^k，a mod b 的值还是不变。
将 a-b^k 看成 a-(b^{k-1})b，那么不能减到 a-[a/b]b。所以问题变成，初始是 a/b，每次可以取 b^0,b^1,…，取完的人失败。
这个东西和巴什博弈（减法博弈）比较像，考虑和那个一样每次无论对方做什么操作，都可以把它移到一个必胜态。考虑在 mod (b+1)下，只有取 1 和 b 两种，你可以控制它 mod (b+1)的值不变，同理对面也一样。最后到<b+1 的，胜负就和奇偶性有关（奇败偶胜）。
如果 mod (b+1)是奇数，那么后手直接和你反着来，你去 mod (b+1)为 1 的他取 b，反之亦然，你就输了。否则如果是偶数，如果当前数 mod (b+1)不为 0，你直接取 1，就能使它 mod (b+1)的值减少 1（变成奇数），否则取 b，使得它 mod (b+1)的值为 1（奇数）。
对于原问题，就递归看 f(b,a mod b)是否必败，如果必败那么当前状态必胜，否则就按照上述方法计算。

305E

有个暴力的 $dp$，就是记 $dp_{l,r}$ 表示 $l..r$ 的答案，转移就枚举切分点 $k$ 满足 $a_{k-1}=a_{k+1}$，从它们 $dp_{l,k-1}\oplus dp_{k+1,r}$ 的 $\operatorname{mex}$ 转移即可。
我们称满足 $a_{k-1}=a_{k+1}$ 的点 $k$ 为断点，那么一个（除了两端点）没有断点的段是无法操作的。
考虑断点形成的极长连续段，那么不同的极长连续段，无论怎么操作都是独立的。对于独立的我们可以用 sg 解决。
所以只需要预处理所有极长连续段的 sg 值，现在状态就是一维的了，可以直接暴力枚举分割点的位置 $\operatorname{mex}$ 转移。
它要求输出最小的第一步，枚举第一步判断是否可行即可，总复杂度还是 $O(|s|^2)$ 的。

36D

反过来方便点，记从 $(n,m)$ 开始往左/上/左上 k 步是必胜还是必败，$f(1,1)=0$（必败）。
那么直接转移是 $f(i,j)=\operatorname{not}(f(i-1,j)\operatorname{and}f(i,j-1)\operatorname{and}f(i-k,j-k))$。
没有 $f(i-k,j-k)$，就是普通的黑白染色，$i+j$ 为偶数的为 $0$，其它为 $1$。$i\leq k$ 或 $j\leq k$ 就是这种情况。
否则，考虑 $k+1$ 行剩下的列，那么 $f(i-1,j)$ 和 $f(i-k,j-k)$ 对应的颜色一定不同，所以 $f(i,j)$ 一定是为 $1$。$k+1$ 列同理。
对于 $k+2\cdots 2k$ 行，$k+2\cdots 2k$ 列剩下的，首先可以发现因为 $f(i-k,j-k)=(i+j)\bmod 2$，所以如果 $(i+j)\bmod 2=0$，那么 $f(i,j)=1$，否则 $(i+j)\bmod 2=1$ 的左/上/左上 k 步都是 $1$，$f(i,j)=0$。
对于 $2k+1$ 行剩下的，和 $2k$ 行没啥区别，那些 $(i+j)\bmod 2=0$ 的还是 $1$，剩下的左/上/左上 k 步都是 $1$，$f(i,j)=0$，$2k+1$ 列同理。
对于 $2k+2$ 行剩下的，这就不一样了，它减去 $k$ 是 $k+1$ 行，就已经是和 $(i+j)\bmod 2$ 反过来了，所以 $f(i-1,j)$ 和 $f(i-k,j-k)$ 对应的颜色一定不同，一定都是 $1$，$2k+2$ 列同理。
之后的分析就差不多，$2k+3\cdots 3k+1$ 行又变成正着来了，$3k+2$ 行也依旧同理，$3k+3$ 行依旧是 $1$。
所以就是 $k+1,2k+2,3k+3,\cdots$ 一定都是 $1$，剩下的，$\bmod (2k+2)<k+1$ 的正着来，否则反着来。
当 $n>m$ 交换一下，只考虑 $n/(2k+2)$ 的值，行列减去这么多 $\times (2k+2)$。

335C

如果你放了 $(x,y)$，那么 $(x-1,y\oplus 1),(x,y\oplus 1),(x+1,y\oplus 1)$ 都不能放。
发现之后上下就独立了，考虑设 $dp(l,r,s,t)$ 表示只考虑 $l..r$ 行，$l$ 行状态为 $s$ 的位置不能放，$r$ 行状态为 $t$ 的位置不能放的 $sg$ 值。
然后就枚举在哪里放，还是分成上下两部分，异或起来求 $\operatorname{mex}$ 即可。

48E（#）

bfs，到一个点就枚举怎么打，计算杀龙的最小步数。
如果不行，那就判断是否组成回路。
还是不行那就计算最终成为龙的食物的最大步数。
后面两个可以用 dfs 计算。

38F

先暴力求出所有串的权值，建图，就变成了一个 $DAG$。
现在就是在 DAG 上 $dp$，记录一下每个点的胜负状态，先手取这个点的能得到的双方权值。
如果是必败态，就找后继后手尽量大，其次先手尽量小的。如果是必胜态则额外要求在后继的必败态里找。

1431G（#，严谨正确性证明？）

先发现一个结论，Alice 选了一个数后，Bob 一定会选比它大的最小的。
把选出的数分成若干段，那么每段一定长度为偶数，而把前一半 Alice 选，后一半 Bob 选一定最大，Alice 从中间开始往左边选。
直接二维 dp，记录当前到 $i$，选了 $j$ 个。转移就枚举当前连续段 $x$ 的长度。

Trees

600E

线段树合并模板，直接维护 max 和 sum。
不过应该也可以用 dsu on tree 做，把小的子树先 dfs，大子树 dfs 后不清空，再加入小子树。

208E

可能不连通，不妨加入 $0$ 号点变成一棵树。
相当于求 $p$ 级祖先有多少个 $p$ 的儿子。
先离线求出 $p$ 级祖先是谁，把询问挂到 $p$ 级祖先上。
再把某个点上有的询问，记录进入子树前的值，出来再减去。

620E

变成 dfs 序，区间修改，区间询问数量。
线段树每个区间维护某种颜色的数量即可。

1555E

求 $\max-\min$ 可以枚举其中一个。
假设我枚举 $\min$，就要求最小的 $\max$ 使得只用 $[\min,\max]$ 中的区间可以覆盖每一个位置。
线段树维护区间最小值，区间+1/-1，当最小值非 $0$ 的时候说明所有都被覆盖了。枚举 $\min$，双指针枚举 $\max$ 即可。

1009F

暴力的想法是 dp 来转移子树距离为 $x$ 的数量。
长链剖分，维护 $d$ 最大时最小的深度。先递归轻儿子，清空，再递归重儿子，不清空，再把轻儿子加入。

587C

倍增维护每个点往上的边前 $A=\max{a}$ 小的。
询问的时候也暴力合并这些值，复杂度为 $O(n\log n\times A)$

282E

就算前后缀有交问题也不大，可以调整成没交的。
所以把所有后缀异或和加入 trie，每个前缀在 trie 上找异或它最大的值即可。

540E

求出交换过的关键位置现在的值。
非关键位置之间一定没有，关键位置之间可以用树状数组。
非关键位置和关键位置之间，考虑 $a_x=y$，那么 $y$ 到 $a_x$ 之间的数都有贡献，由于两个一定都是关键点，所以可以轻易求出中间有多少关键点，就能计算了。

1181D

如果初始举办次数都一样，那么会按照 $1,2,\cdots ,m$ 的顺序举办。
现在相当于是，之前某个每举办一次比赛，就删去它第一次出现的位置。
那么你可以求出每次删去的是哪个位置，二分求出现在应该到哪个位置，mod 一下就知道在哪里举办了。

1380E

有一种简单的构造就是 ${1}\rightarrow 2,{1,2}\rightarrow 3,{1,2,3}\rightarrow 4,\cdots$，这样的方案是 $i$ 和 $i+1$ 不在同一堆的个数之和。
而且，$i$ 和 $i+1$ 不在同一堆，一定需要有一次移动，且移动不会同时满足其它的 $i$。
用并查集+启发式来优化合并，把小的集合的贡献和影响重新计算（前一个/后一个在那个塔里，减少答案，vector 维护集合里的点）。

960D

发现无论怎么移动，深度为 $i$ 的（从 $0$ 开始）从左到右一定是 $2^i+x,2^i+x+1,\cdots,2^{i+1}-1,2^i,2^i+1,\cdots,2^i+x-1$。
1 操作就是把一行每个数往右移 $k$，也就是 $x$ 减少 $k$。
2 操作首先把这行每个数往右移 $k$，对于下一行它应该右移 $2k$，再下一行应该右移 $4k$，以此类推（只有 $60$ 层，可以暴力）。
3 操作首先要找到它在那一行的位置，然后不停 $/2$，找到上一行对应位置，输出它的数。

817F

如果只有 1,2 操作可以直接 set 维护线段，因为复杂度是可以均摊的。
不过有 3 操作不行，但是发现还是可以离散化，离散化后就变成区间赋 0/1，区间取反，求全局第一个 0。
线段树维护区间翻和不翻的第一个 0 和标记即可。

1615D

这什么翻译，还以为是点带权，原来是边带权。
那就好做了，先变成两个点到根路径上的异或和，然后就要求两个点值相同或不同，不过不需要 2-SAT，这个是双向的，直接并查集合并（相同合并 (x,y),(x',y')，不同合并 (x,y'),(x',y)）。

165D

相当于询问简单路径上有没有白边，有就是 -1，否则就是两点简单路径长度。
树状数组维护每个点到根路径上白边数量，也就是改成白边的时候给子树 +1，改成黑边给子树 -1。
询问就找到 LCA，query(x)+query(y)-2query(lca)看白边数量，如果非 0 就输出 -1，否则输出 dep[x]+dep[y]-2dep[lca]。

893F

一眼可持久化线段树合并。
每个点维护不超过某个的绝对深度的点权最小值（维护相对深度到上一层合并的时候要移位，不好做）。
询问的时候就在那个点的线段树里询问区间最小值即可。

406D

所谓最右边的一个能到达的山坡就是凸包上下一个点（在它之后都会被它拦住）。
每个点连向右边的这个点，然后能共同到达的就是求 LCA。

894D

每个子树求出到它距离不超过 $x$ 的数量。
然后枚举 LCA，查询子树里贡献即可。

690C3

根据经典套路，新直径端点一定是原来直径的两个点和新的点中选两个点。
把新点加入的时候更新倍增数组，就可以求 LCA 和距离了。

191E

先二分答案，然后判断有多少个区间和 $\geq mid$。
具体的方法是固定一个端点，要求前缀和不超过某个值的个数，可以离散化后树状数组求得。复杂度是 $\log^2$ 的。

1575I

观察式子，发现两个数符号没有关系，$\max(|a_i-a_j|,|a_i+a_j|)=|a_i|+|a_j|$。
那么 $i,j$ 间除了 $i,j$ 其它点都贡献两次，问题就变成路径上的权值之和，维护每个点到根路径和，即修改时给子树加/减（树状数组），询问求 LCA 即可。

85C

只能错恰好一次，你错了之后，如果是 0 走成了 1，那么之后都会走 0；反之是 1 走成了 0，那么之后都会走 1。
怎么找一步不错的叶子节点？在原序列 upper_bound 一下，看这个点的位置，如果是叶子节点说明就是它，如果不是，这一步会左走，而之后就没有比它大的点了，一直往右，记录一下就知道是哪个了。
而确定了目标点后，往上的答案都可以处理出来（还是要记录一直往右和往左走达到的点），从父亲转移过来。

1252B

容易想到设 $dp_{u,0/1}$ 表示 $u$ 的子树覆盖完，有没有路径以 $u$ 为端点的方案数。
但是发现这不行，原因是你有可能子树里原先不合法，现在合法，因为根节点的路径可以接到父亲。
改为设 $dp_{u,0/1/2}$ 表示 $u$ 的子树覆盖完，没有以 $u$ 为端点/有以 $u$ 为端点且不必须和父亲连（子树本身合法）/有以 $u$ 为端点且必须和父亲连（子树在根节点处不合法）的方案数。
$dp_{u,0}$ 要从子树选择两条连上来，那么选择两个 $x,y$，$dp_{x,1/2},dp_{y,1/2}$（能连上来），剩下的就只能是 $dp_{v,0/1}$（能不连上来），乘起来累加。
$dp_{u,1}$ 要从子树选择一条连上来且子树没有其它能连上来的，那么选择一个 $x$，$dp_{x,1/2}$（能连上来），剩下的只能是 $dp_{v,0}$（不能连上来），乘起来累加。
$dp_{u,2}$ 要从子树选择一条连上来且子树没有其它必须连上来的，那么选择一个 $x$，$dp_{x,1/2}$（能连上来），剩下的只能是 $dp_{v,0/1}$（能不连上来），乘起来累加（计算的并不是必须和父亲连的，而是总方案，即有端点在根上的），最后减去 $dp_{u,1}$。
但是 $dp_{u,0}$ 需要枚举两个变量，而其它只需要枚举一个变量，逆元算一下就行。其实也可以做，枚举两个中靠后的一个，维护之前选了另一个的答案，把当前的能不连上来的除掉，乘上能连上来的即可。

916D

可以撤销撤销操作看上去很吓人，不过仔细想一想，撤销了之前的 $k$ 次操作，相当于回到 $k$ 步之前操作后，和前一步的状态并没有关系，到达当前状态的操作已经被撤销了。
所以应该用可持久化数据结构，可以考虑两个线段树，一个权值线段树维护 $a_i$ 的优先级，另一个权值线段树维护优先级小于 $x$ 的数的个数。一个是单点修改单点查询，一个是区间修改单点查询，都可以用可持久化。

1403B

容易想到，对于一个子树，你留下来给父亲匹配的一定不超过两个点，否则你选两个点自行匹配，剩下的留给父亲也可行。留下两个时，到父亲的边会计算两次（你往上保留的奇偶性一定不变，在之后和别的合并一定不如现在就合并）。
发现留下的只和子树里叶子节点的个数的奇偶性有关，也就是子树叶子节点个数是偶数的需要多增加 $1$（边多走了一次）。
树链剖分可以维护，然后再暴力撤销。

Binary Search

1284D

两场讲座要么在 $a,b$ 都不冲突，要么在 $a,b$ 都冲突。
也就是对于某场讲座，在 $a,b$ 中和它不冲突的讲座形成的集合是相同的。
需要一种和顺序无关且能快速计算的判断方法，可以使用随机权值，异或起来判断是否相同。
而不相交的也就是右端点比它左端点小或左端点比它右端点大，存个前后缀异或和即可。
其实还有确定性的算法，就是你考虑和 $a$ 不冲突的中和 $b$ 冲突的，把右端点比它左端点小的区间的 $b$ 在线段树/树状数组（离散化）上覆盖，然后查当前 $b$ 区间上有没有被覆盖，其它的情况同理。

1059D

如果 $x$ 轴上下方都有点，那么一定无解。否则把所有点都放到 $x$ 轴及以上。
半径是有可二分性的，半径大的，圆心依旧在原来的 $x$，能覆盖的只多不少。
二分完半径 $r$，就可以求出它合法的 $x$ 区间，对于每个点 $(a,b)$，求出和它 $x$ 方向上距离的范围，假设 $x$ 方向距离为 $d$，那么 $d^2+(b-r)^2\leq r^2$，可以解出 $d$ 的范围，即 $x$ 要在 $[a-d,a+d]$，求交最后看交是否为空决定二分上下界的变化。

689D

固定了 $l$，$r$ 一定在一个区间，求出合法的第一个 $r$ 和最后一个 $r$。双指针维护两个 $r$。
预处理 ST 表来求区间最大最小值。

1167E

枚举 $l$，对于 $r$ 一定是越大越容易满足。题目相当于是去掉 $[l,r]$ 中的数后不存在逆序对。
比如当前是 $l,r$，变成 $l+1$ 后，有可能出现一些 $l$ 做较大值或较小值的逆序对。- 做较大值就无解，判断方法是可以维护不超过 $l-1$ 的数的最靠后的位置和为 $l$ 的数的最靠前的位置。
做较小值就找为 $l$ 的最靠后的位置，它之前的最大值（如果存在且比它大）就不能出现。
所以只要维护每种数字最靠前/最靠后的位置和前缀最大值即可。

1626D

枚举最小和最大补全到的 2 的次幂，那么不超过枚举的个数时，一定选尽量多的。因为你留下来，最多也就能给中间的少那么多，而放两边是一定会少的。
对于每个 2 的次幂，求出最小和最大不超过 2 的次幂最多能选多少，就可以计算了。

1039B

先二分大概缩小一下范围，每次更新完 $l,r$ 后，$l$ 还要减去 $k$，$r$ 还要加上 $k$。
到某个范围再随便问一个，如果不对再调整上下界，从头开始整个过程。

875D

区间或一定大于等于区间最大值，所以只需要求等于的情况。
or 一定不超过 log 次变化，对每种 or 里二分即可，单调栈维护 or，ST 表查询区间最大值。

333D

这题也太妙了。
最小值最大，先二分答案，把 $\geq mid$ 的都标记。
现在就是看有没有能组成矩形的四个点都被标记。枚举每一行，枚举有数的两列，如果之前出现过这样的两列，则返回 1，否则标记这两列为出现过。
这样每一列最多被标记一次，所以复杂度是 $O(n^2\log n)$。

813E

每个区间同一种数字只考虑最后 $k$ 个，也就是对于区间里的数，如果它之后第 $k$ 次出现还在区间内就不计算贡献。
也就是对于 $[l,r]$ 内的数，把它之后第 $k$ 次出现的位置拿出来，求 $\gt r$ 的数字个数。预处理每个数的这个位置，询问的时候用主席树来查询区间 $\gt r$ 的数字个数。

369E

一眼正难则反，正着一个区间可能包含多个点，而反过来区间只能在相邻点之间。
然后，把询问离线，变成了给你一些 A 区间，给你一些 B 区间，求出每个 B 区间包含了多少 A 区间。
这个就可以右端点从小到大，其次左端点从大到小排序，询问就是问一个后缀数的个数，树状数组即可。

56E

首先先排序，排完之后，考虑这个骨牌推倒了到哪个位置。
那么当前位置到推倒到的这个位置之前的这些都倒了，它们能倒的距离是它们中的权值的最大值，树状数组维护前缀最大值即可。

85D

先离线后离散化。
线段树上维护区间内 $\bmod 5=0,1,2,3,4$ 的答案。
合并从左儿子的 $x$ 和右儿子的 $(sz_{ls}-x)\bmod 5$ 转移过来。
插入一个数，到叶子节点修改一下权值和 $sz$，往上的时候再合并求出其它点的影响。

1268C

由于最后一定会变成连续的，且逆序对至少交换一次，所以不如先把 $1..k$ 放到一起再交换。
放到一起一定尽量靠近最中间的数。$k$ 增加时，新增的逆序对数就是以新的 $k$ 开头的逆序对数，树状数组查询即可。
至于最中间的数 $x$，维护两个 set，一个存 $x$ 及左边的数，一个存 $x$ 右边的数，如果大小差 $>1$ 说明要调整两个 set 的数，同时维护两个 set 的位置之和即可计算移动的贡献。

620D

不交换直接计算答案。
交换一次可以暴力枚举上下交换的是哪两个数。
交换两次可以暴力枚举 $a/b$ 中交换的两个数存到两个数组，然后排序，在上面双指针或二分找使得答案最小的。

809B

数据范围是 $3\log n$ 级别的，考虑二分。
如果你确定 $[l,r]$ 内有，那么询问 $(mid,mid+1)$（$mid$ 为常规的 $\frac{l+r}2$），返回 TAK 说明左边一定有，否则右边一定有。然后就能求出第一个被选中的位置 $x$。
求出第二个也一样，对 $[x+1,n]$ 再做一次即可（$mid$ 为常规的原因就是让左边的区间长度一定不比右边小，不会导致递归到一个区间内没有选中位置的区间）。

425D

什么经典题。
还是分成大行和小行，大行是点数 $\gt \sqrt n$ 的，小行是点数 $\leq \sqrt n$ 的。
有小行的就枚举小行内的两个，四个点坐标都确定，判断一下是否可行。
两个大行就枚举两行，边长就确定。然后枚举每一列，那么四个点的坐标都确定，判断一下是否可行。

862E

$f(j)$ 中 $a$ 的贡献和 $j$无关，预处理出其中 $b$ 的贡献为 $c_i$（$b$ 在后面操作不变），就变为 $f(j)=\mid\sum (-1)^{i-1}a_i+c_j\mid$，维护 $\sum (-1)^{i-1}a_i$。
修改后容易维护这个值 $s$。因为求的是答案最小值所以可以把 $c$ 排序，就变成求和 $s$ 差值最小的数，lower_bound 然后判断即可。

1070E

可以二分答案，也就是至少做的任务数，任务越多时间一定越长。且你做一定会把最小的若干个给做了。
求出做这么多任务最小的难度，然后扫一遍求一下需要的时间，看是否可行即可。
最后输出它的难度。

730C

先二分答案，然后对于距离在答案内的，从小到大购买，如果能在规定的距离内满足数量和总价两个条件，此答案就可行。

1136E

把式子边长 $a_i>a_{i+1}-k_i$，但是两边形式不同，改成 $a_i-\sum_{j=1}^{i-1} k_i>a_{i+1}-\sum_{j=1}^i k_i$。
令 $c_i=\sum_{j=1}^{i-1} k_i,b_i=a_i-c_i$，加操作就先给 $b_i$ 加，然后之后连续一段小于它的数都变成它，询问就把区间 $b,c$ 的和求出来。
再线段树上二分找到之后比它大的第一个数，中间区间赋值即可。区间赋值，求区间和/最大值。

1379D

只需要知道所有 train 的 $m_i$ 对 $\frac{m}{2}$ 取模的结果即可（一天每隔 $\frac{m}{2}$ 分钟就有一辆车）。
现在要在 $0$ 到 $\frac{m}{2}-1$ 的环上取一段长为 m-k+1 的区间，使区间内发车的 train 数量最多。
复制两份，把 train 排序，双指针即可。

762E

把所有电台按照 $r$ 从小到大排序，一对 $(i,j),i<j$ 有贡献当且仅当 $|x_i-x_j| \leq \min(r_i,r_j),|f_i-f_j|\leq k$。
现在就变成静态二维偏序了，CDQ 分治+树状数组即可。

400E

每一位显然是独立的，拆开来。
$s[i][j]=\operatorname{and}_{k=0}^{i-1} a[j+k]$，所以 $\operatorname{and}$ 起来为 $1$ 的必须所有的数字都为 $1$。
维护所在的 1 的段的长度和答案即可。

138C

对于蘑菇，求它不被砸到的概率。
对于每个左区间的数，要乘上不往左边倒的概率；对于每个右区间的数，要乘上不往右边倒的概率。区间乘也可以类似差分在 $l$ 乘在 $r$ 除。
把这样对端点的操作排序。对于每个蘑菇就知道了概率，和它的价值相乘后累加。

65C

你在时刻 $x$ 能抓到，由于你速度不比他慢，之后也能抓到。
所以可以二分，二分完了之后求出它在哪个位置，看我从开始就走到那个位置的时间是否不超过二分的值，如果是就可行。

387E

容易想到建立笛卡尔树，然后那些需要删的点，贡献是它们子树的大小之和。
其实没必要真的把树建出来，求出前后第一个比它小的，就知道它在笛卡尔树上的子树大小。这个可以用 set 解决。

852D

显然可以二分。提前 floyd 预处理任意两点最短路。
人放一边点放一边，把能到达的连边跑二分图匹配。
如果匹配数量够表示当前答案可行。

24E

先把所有子弹按照 $x$ 坐标从小到大排序。如果相撞就是前面往右的子弹和后面往左的子弹相撞。
按照原来的顺序扫，然后维护之前往右的子弹的现在最大的 $x$ 坐标，如果当前是往左的且 $x$ 坐标不比它大那么就相撞，当前答案合法。

883C

枚举其中一种用了多少次，然后另一种如果比直接贵就直接下载。
否则你就尽量用另一种，最后剩下的一小部分可以考虑直接或者用另一种。
两种反过来也要做一下，因为否则枚举不到最后小部分用第一种的情况。

431E

二分答案，那么 $>mid$ 的都不管，不能选进来。
$\leq mid$ 的，每个能加入 $mid-now$。维护 $\leq mid$ 的个数和数字和，线段树上二分即可。

70C

$x$ 增大，满足条件的 $y$ 减小。
双指针维护，条件可以变为 $a/rev(a)=rev(b)/b$。
维护 map 表示已经加入的数的 $rev(b)/b$，加新的数时看一下和 $a/rev(a)$ 相同的个数。

253E

显然是满足可二分性的，如果答案偏小就降低优先级，否则提高优先级。
判断就按照优先级模拟即可。注意它要求优先级互不相同，你可以认为相同情况下它优先，最后在处理一下。

1575B

首先可以二分答案，因为假设半径 $r$ 可以，你选的圆心点为 $A$，那么扩大 $r$ 后，依旧认为线段 $OA$ 在直径上，这样覆盖的一定包含原来覆盖的。
固定了 $r$ 后要判断，具体的方法是，首先圆心里 $O$ 距离为 $r$，说明它要在以 $O$ 为圆心半径为 $r$ 的圆周上。
那么对于其它点，它如果被覆盖说明到圆心距离不超过 $r$，也以它为圆心作一个圆，要在和 $O$ 为圆心的圆相交的弧上（你发现弧一定是劣弧，可以求出交点后判断是哪一边的弧）。
现在只要求交点，这个其实不用解方程。要找到点使得到两个距离都为 $r$，可以先考虑求出两点的中线，在中线上找满足条件的点的度数（弧度制），三角函数解一下即可。
给弧度范围加，左加右减，然后扫一遍即可。

774B

总宽度固定，一种选的多另一种就选的少。
两种价值从大到小排，相同的情况下宽度从小到大排，第一种选一个前缀，第二种就能选多少就选多少，双指针即可。

1488F

每个数维护前一个比它大的时刻。
对于询问，从 $r$ 开始，每次跳到前一个比它大的，中间的收益都在当前位置卖。
可以用倍增在线求出答案，也可以离线，建出森林，维护栈，二分解决。

Data Structures

52C

如果 $l\leq r$ 就直接线段树操作 $[l,r]$
否则操作 $[l,n],[1,r]$。

617E

虽然询问一个区间不太好做，但是加入一个数是好做的，拿个桶记录一下每个数字个数就能计算了。
所以可以改为莫队来离线处理询问。

1418D

显而易见的，一定是前面一段合并成了一个，后面一段合并成了一个。
分成两部分后，一定需要两部分各自的长度才能把它们合并，也就是省了交界处的那一段。
用 multiset 维护相邻两个数的差值，每次输出最大的，修改的时候更新 multiset 即可。

1207F

500000，4s，根号算法是可以跑过的！！！
$x\leq \sqrt n$ 的维护答案，$x\gt \sqrt n$ 的暴力计算答案。
维护答案就是修改后对 $x\bmod v,\forall v\in [1,\sqrt n]$ 给 $v$ 更新，暴力计算就是每次暴力往后跳 $x$ 求和。

703D

出现奇数次的好算，就是区间异或和。
出现偶数次的就是所有的不同数字的异或和再异或上区间异或和。
离线下来，枚举 $r$，让 $r$ 及之前的相同的数字只有最后一个有贡献，就可以树状数组求了。$r$ 增大时把上一个和当前数相同的位置改为 $0$。

1195E

先横向考虑，求出每个数之前 $b$ 个的最小值。再纵向考虑，求出每个数之前 $a$ 个数（刚才横向求出的）的最小值。
具体求前 $k$ 个数最小值的方法就是直接单调队列维护。

915E

区间赋 0/1 区间求和。
线段树，可以离散化也可以动态开点。

1265E

字母对括号序列没有影响，把它当成 0。根据一般做法，(当 1，)当-1。
还是一样，要求前缀和 $\geq 0$ 且总和为 $0$。
维护前缀和序列，修改的时候就对一个后缀做加减操作。询问就判断总和与最小值即可。

707D

它是在某步操作后加，所以可以使用经典维护操作序列树的方法，对状态之间的关系连边，从 $k$ 操作过来的就把 $k$ 和当前连边。
那么，操作时可以轻易回退的，所以可以直接在操作序列树上递归，维护每行反转 tag 和矩阵即可，注意单点操作时如果有 tag 要变成和 tag 相反的。

429D

变成前缀和 $f(i,j)=(i-j)^2+(pre_i-pre_j)^2$。
这个就是 $(i,pre_i)$ 的平面最近点对。
回忆一下，是一个分治算法，假设两边的最近距离为 $d$，选出 x 离中心轴不超过 $d$ 的点，然后在 y 离它不超过 $d$ 的且比它小的点（最多只有 7 个，因为 $d\times d$ 矩形两两距离 $\geq d$ 最多四个点）。

1092D2

容易想到，要先把最小值的段都填高，那么得满足最小值的段的长度都是偶数。
其次为最小值的数都变大了 1，此时又要求原先最小值 +1 的段长度都是偶数。
依次类推，所以只需要判断任意 $x$ 是否满足 $\geq x$ 的形成若干个连续段，并查集合并即可。

1156E

分治，从 $mid$ 分成两半，分别求后/前缀最大值。
然后枚举一个数，看满足条件另一个数的位置，然后判断最大值是否合法。

1295E

最后是第一个序列都 $\leq x$，第二个序列都 $\gt x$。
那第一个序列中 $\gt x$ 的，第二个序列中 $\leq x$ 的都会需要花费对应 $a$ 的贡献。
维护两序列分界点固定时，每个 $x$ 的答案。用线段树维护区间操作即可。

555C

发现无论怎么拆，都是三角形去掉最下面若干行和最右边若干列的形式。
拿 set 维护一下这些形状，每次操作就是一分为二，维护一下即可。

1108E2

因为 $m$ 很小，把区间变成左闭右开的后离散化，只有剩下的两点间的最小最大值才有用。
枚举最小值所在的段，最大值所在的段（有个很好的性质是如果你枚举的不是真正的最小最大值答案只会更加劣）。然后尽量让最小值所在的段尽量小，若既包含最小值也包含最大值这个段选不选都一样。
所以可以发现只需要枚举最小值，然后选所有包含它的段，最后看剩下的最大值，更新一下答案即可。

1208E

设总长为 $n$，这一行长度为 $m$，那么这一行对 $i$ 位置的贡献是 $[\max(1,m-n+i),\min(m,i)]$ 区间内的最大值。
在 $i$ 增大时两端点向右移动，且虽然 $i$ 取值为 $[1,n]$，但总共不同区间数量不超过 $2m$，即刚开始右端点在变化，之后不动，最后左端点在变化。只需要处理前后，中间的区间加即可。

301D

比较经典，因为对数很少（$O(n\log n)$），可以直接把每一对处理出来。
现在就是求第一个数 $\geq l$，第二个数 $\leq r$ 的对数。
询问离线，排序，一个一个加入对，遇到询问树状数组查询即可。

515E

去掉小孩子在的树之后就变成了一条链。
倍长原序列，从右到左移动左端点，每个位置维护 $2*h+i$，维护一个单调栈，询问的时候二分即可。

1194E

枚举矩形上下边界，就要求竖着的满足能覆盖住的拿出来求一下。
枚举下边界的时候加入 y 坐标在下边界以下的竖着的，那么枚举完上边界就可以树状数组询问方案数。

103D

一眼根号分治，小于根号的维护前缀和，大于根号的暴力做。

1093G

曼哈顿距离最大，意味着只要每个维度两个数字的系数（1/-1）不同，求最大值就是答案。
枚举系数（2^k），求这种系数和另一种系数分别的最大值加起来即可。

785E

单点修改，求区间比某个数大（小）的数字个数，应该用树套树（如树状数组套权值线段树）解决。
（其实有一种经典的 $O(n\sqrt{n\log n})$ 的做法是分块，每块从小到大维护值，修改直接类似插入排序，询问就每块二分）。

797D

dfs 一遍，求出如果到当前的点，那么可能的权值区间是什么。
那么当前点的权值能被搜到当且仅当在权值区间内，map 标记一下。
最后输出有多少个点的权值没被标记。

853C

和它不相交当且仅当至少完全在上下左右四个方向之一。
直接算在上下左右的方案会算重完全在左上左下右上右下的，要减去。
这个方案数类似于二维数点，离散化后一维枚举一维树状数组即可。

1627E

从下到上，爬梯子可以直接转移过来。
同层之间的转移，可以从左往右先转移一次，从右往左再转移一次（要么往左要么往右）。
每层有往上/往下的梯子的格子才有用。

461C

如果折过来没有覆盖掉全部，那么直接暴力折（维护当前还存在的左右端点）；如果覆盖了全部，那么暴力复杂度就错了，反过来让短的折过来，再记录一下现在翻转了。
查询区间和可以用树状数组。

1625D

明显先要建 trie 树。
建完后递归，如果当前填 1 没有压下界那么左右子树可以分别递归，如果压了下界那么两个子树里分别最多选一个数，至于能不能选可以直接递归，原因是如果某个点有两个儿子如果都能走那么说明一个一定不压下界；如果只有一个能走那么直接继续递归。

756C

可以认为开始所有位置都是空的，然后每次钦定某个位置是左括号或右括号（左括号有权值），问最后一个没匹配的左括号的权值。
由于括号序列一定合法，那么可以找最后一个位置使得后缀和 $\gt 0$，把单点操作变成前缀操作就可以求最后一个 $\gt 0$ 的数字了。

1580C

直觉就是根号分治，时间短的暴力记录（有多少辆车在 $mod x=y$ 的天维修），时间长的可以直接在需要维修的位置上加（在 $mod x=y$ 的天加）。
删除的时候，时间短的直接在位置上减，时间长的在维修的位置上减。

1250C

枚举 $l$，维护每个 $r$ 的获利加上 $kr$（最后再减去 $k(l-1)$）。
$l$ 往右移动的时候把那些左端点在原先 $l$ 的区间删去即可。

1252G

需要发现的一点是，这个和经典 $\geq x$ 一样，你只要记录有多少人能力值比你小，到某一年不够了那么就 got fired 了。
你知道每一年加入的人中比你小的个数，维护每一年结束前比你小的人数 $-r$，要求每一年都 $\geq 0$。
第一年就是初始比你小的人数 $-r$，之后每一年就是前一年加前一年新增比你小的人数 $-r$。
发现每一年都 $\geq 0$ 的条件等价于最后一年 $\geq 0$。
那么你就知道只需要求比你小的人数，拿个树状数组维护所有人即可。

1045G

强制钦定以 $(r_i,i)$ 排序，然后变成一个静态二维偏序的形式，CDQ 分治套树状数组即可。

558D

求出询问区间对应的叶子节点，如果是 yes 就求个交，是 no 就和补集求个交（具体区间可以简单讨论一下）。
最后看点数，>1 就多解，=1 就输出，=0 就说明被修改了。

877F

关键点是 $k$ 固定，那么对于每个 $r$ 可以求出满足条件的最近的 $l$。
维护之前的前缀和为 $x$ 的最后一个位置，枚举 $r$ 就能知道 $l$。询问的时候就是问有没有二元组被包含。
相当于 $l\leq x,r\geq y$，二维偏序即可。

878B

段内你先消（$\bmod k$），然后中间的就没用了，只有两端的有用。
特判掉只有一种数的情况，此外两段接到一起可能可以合并（但也只限于前一段的右边和后一段的左边），更多的段也是一样，可以求出每加一个段可以合并多少。

220C

这题的关键是它是一个排列。
每个数从距离每次+1 到-1（或-1 到+1）的变化只有一次，而每个数移动到最后也最多只有一次，可以拿 set 维护+1 和-1 的集合，要变化的暴力移动。

803G

转换成左闭右开后离散化，相邻的之间如果包含了全部就是全体最大值，否则可以 ST 表查询。
操作就可以暴力线段树。

895E

期望有线性性，可以直接维护每个数字的期望。
区间里的每个数字有 $\frac{1}{len}$ 的概率选到，然后另外一边选的值也是随机的，可以算另外一遍选过来的期望。
那么就是区间赋值。

628E

考虑 Z 形第一个转折点，两边一个往左，一个往左下。
你求出能往左多少，往左的长度可以为 $i$，往左下的长度可以为 $i$ 且左下往右的长度可以为 $i$ 则合法。
往左往右可以的长度可以预处理，按对角线顺序处理往左下的，每次往右上走一个，一些就不行了（向右长度不够的），剩下的就求出不超过往左能走的长度里有多少个即可，可以维护树状数组。

35E

这个题很诈骗，维护每一段的最大值，如果相邻两段的值不同就会新增两个端点。
离线区间覆盖可以直接离散化后 set 维护。

420D

被移到最前面和最后面的数，你是知道它们的值的。
移动被移动到前面的数，如果值不一样，就无解。后面同理。
移动一个中间的数，相当于你确定了一个值。中间的可以使用树状数组维护还存在的下标然后二分（第一反应是平衡树，但是值域小可以用树状数组代替）。
然后你发现其实可以全部都用树状数组维护，每次把一个数移到开头/结尾就给一个最小/最大的坐标放着，记录一下它的权值，如果权值冲突就无解，否则最后位置还在初始位置的随便填即可。

219E

一眼 set 维护每段左右端点。
注意存一下每一段到最近两点的距离最大值是多少（中间的段是长度/2 下取整，两边的段是长度-1）.
加入点的时候找到所在段，删掉点的时候找到相邻段即可。

38G

建立 splay（维护正确的下标顺序）。
每次把当前 $>i-c[i]-1$ 的这一段（也就是顺序中最后这么多个数）拿出来，在里面插入当前的值（看右子树权值的最大值和当前的关系）。

89C

$nm\leq 5000$，意思是可以暴力模拟，只要能 $O(1)$ 找到下一个标记的位置。
这个可以把每行每列维护一个双向链表，求出下一个标记点就把当前点删除。

1184C2

曼哈顿距离不超过某个值，先转切比雪夫距离。
枚举一维 $x$，用数据结构维护另一维 $y$，$x$ 移动的时候把超过范围的那些点的贡献去掉，加入新的点的贡献。

413E

没有修改，可以不用线段树，倍增可以代替。
设 $f[i][j]$ 表示 $i$ 往右走 $2^j$ 走到的两个位置分别需要的步数。
应该也可以分治，考虑经过中心的，分别求出两边到中心的，更新答案，再递归在两边的。

228D

$z$ 只有 $6$，可以对每个 $z$ 都维护答案。问哪个 $z$ 我就从那个数据结构找即可。
单点修改对所有 $z$ 都暴力修改即可。

926J

在 set 里维护线段。
每次新加入线段的时候，不停的找和它有交的线段，与它合并，直到没有和它有交的线段。
找与它有交的先找 set 里二元组大小比它大的，如果没有交再看这个二元组的前一个。

257E

如果没有“事件”（指有人上下电梯）发生，那么电梯的运行状态（向上/向下/停止）不变。
拿个 set 维护电梯里往上/往下的人，外面在上面/下面等候的人，当前的事件。
就看当前是哪个最早，是上电梯的事件早还是下电梯的事件早还是有人开始等候早。
由于每个人只会开始等候/上/下电梯各一次，所以复杂度是一个 $\log$ 的。

Remain

1372D

如果你把一个已经是多个数合并的数为中心再做，那么你拆开中间的合并（不做那一步），然后做一下拆开的左边和右边，发现次数相同，但总和变大。
你一定不会再选择合并过的数，但是你要合并成一个，所以第一次合并完，之后一定得选择合并和它相邻的，以此类推。最后一定是隔一个选一个，选 $(n+1)/2$ 个数。
答案比较容易算，也就是选相邻两个，然后两边隔一选一。破环为链即可。

1621D

显然目标的格子都得占。
你发现如果把不是同一行的学生并到了同一行，那么再也不能分开了。
所以第一步只能往外移动，如果不是边界行列，那么它必须整行/整列往外移出来再移下去。
发现这一定不如边界往外移一格（恰好占了一格原先没占的），然后把出来的那格移动到对应位置，再重复操作。
只需要考虑移到 $(1,2n),(2n,1),(1,n+1),(n+1,1),(n,n+1),(n+1,n),(n,2n),(2n,n)$（也就是一步能移到的）。取最小值即可。

598C

不同象限直接分象限讨论，同一象限直接 atan 即可。
然后看相邻两个的度数之差。

505D

考虑把要把条件连成边，那么在同一个弱连通块的本身就必须弱连通（传递性），所以其中至少花 $n-1$ 条边。。
如果弱连通块存在拓扑序，可以按照拓扑序从前往后连边；否则说明弱连通块里有环，则必须要多花 $1$ 条边才能连接起来（你可以直接连成一个环，那么两两可达）。

414C

不同段之间的逆序对相互没有关系，反转的内部才会有关系。
考虑建一个类似线段树的东西，那么每次是给某一层往下都反转。
层数很少，不同层也没有关系，记录一下整层反转后的权值和不反转的权值，每次读入时给下面的所有层都暴力反一下（$O(n)$）即可。

1399E2

你可以算出每条边 $/2$ 后会影响多少边，从而算出它操作后减少的贡献。
显然 $c_i=1$ 和 $c_i=2$ 的是互不影响的，知道了 $c_i=2$ 的操作了多少次以及它减少的贡献，就能知道最少的 $c_i=1$ 的操作次数，进一步算出总花费。
$c_i=2$ 和 $c_i=1$ 分别操作若干次减少的贡献都可以用优先队列维护，每次取出贡献最大的，更新答案，然后再修改 $w$，重新计算贡献加入优先队列。
最后双指针，从小到大枚举一个，另一个一定越来越少。

1266E

设有 $cnt_i$ 个成就获得额外的资源是 $i$。
那么存在下界为 $\sum max(a_i-cnt_i,0)$，只做必要的，认为剩下的都能满足。
可以证明这就是答案，因为你可以开始就在每一堆取恰好 $max(a_i-cnt_i,0)$，那么此时一定有条件被满足（因为是 $<a_i$ 且两两不同，应该有没满的个数个），（除非一个满了）每一步都一定新增其它条件满足（也不一定是新增，就是认为之前的奖励还有剩余拿一个出来，）。

510E

由于 $a_i\geq 2$，所以和一定是奇质数，说明两个数必须一奇一偶。
奇数和偶数才能放在一起，把能放在一起的连边，一定是二分图，所以环一定是偶环。
每个点在环上一定有两个不同的相邻点，且每个点满足此条件形成的图都合法。
建图，每个能相邻的点对左向右连单向边，左边点入度为 2，右边点出度为 2，跑网络流即可。

340B

我发现四个点的经常是要么枚举中间两个（链），要么枚举不相邻的两个（环）。
这题就枚举不相邻的两个（类似对角线？），然后在两边各选一个点使得两个三角形的面积都尽量大。两个是独立的，分别枚举即可。

1628C

这个题啊。。。其实有一个直觉，就是第一行无论填什么都是可以的（这个其实是对的）。
很容易想到一种方法，就是只要上面的没填，我就点一下当前的（这个其实也是对的）。
还有一种方法是，考虑经典方法，黑白染色。黑色的值表示一些白色点的异或和，白色的值表示一些黑色点的异或和。黑白染色在图上就是一些斜着向上的段。
你发现同色的一整段的异或和是相邻两段不同色的，你可以解出每一段的异或和，再异或起来就是全部异或和了。

166B

求出 $A$ 的凸包和 $AB$ 的凸包，如果不一样一定无解。
注意由于不能有交，所以可以把凸包边界上的点也加入凸包。

1185F

表示成二进制状态，要求一个人对应的状态包含于两个披萨状态的或。
然后，把人求子集和（FWT），求出两个披萨的或固定时有多少人。
披萨本质不同的状态只有 $2^9$ 个，每种状态取支出的最小值。
枚举两种披萨，求出它们的或、它们的总支出，看或的子集的人数即可。

1178F1

由于你每次只能染某个同色段内的，所以你每次染完之后不同颜色段就独立了，可以分成若干子问题。
这个 F1 初始是一个排列，所以对于每种颜色，只在段内有这种颜色的才计算方案。
记 $dp(l,r)$ 表示区间 $[l,r]$ 的方案数，那么下一个要填的颜色就是区间内的最小值，枚举包含这个最小值的区间 $[x,y]$，分成四部分，$dp(l,x-1)\times dp(x,p-1)\times dp(p+1,y)\times dp(y+1,r)$。
直接这么做是 $O(n^4)$ 的，不过 $x,y$ 的贡献无关，分别计算贡献相乘即可。

1628D1

这个题太哈人。
设 $solve(a,b)$ 表示还有 $a$ 轮，Bob 还可以减 $b$ 次。
对于 alice，如果选择了 $x$，Bob 一定会选 $solve(a-1,b-1)-x$ 和 $solve(a-1,b)+x$ 的最大值（$b=0$ 时不能 $b-1$，所以 $solve(a,b)=solve(a-1,b)+1$）。Alice 会让两个数尽量接近。
直接 dp 就能过 D1。
来做 D2。
这个有个 $x$ 需要讨论一下，不过可以打个表看一下，发现 $solve(a,b-1)-solve(a,b)\leq 2$，那么两个数可以相同，也就是 $solve(a,b)=\frac{solve(a-1,b-1)+solve(a-1,b)}2$，至于证明也很简单，可以对 $a$ 归纳，如果上一层满足条件，这一层一定也满足条件。
这个形式很像组合数，给 $solve(a,b)$ 乘上 $2^a$，那么转移式子就完全是组合数了，只不过初值不一样。这个问题不大，这其实就是每一步可以往上或往左，走到第 0 列的方案数。对每个初值乘上组合数的系数贡献过来即可。

993C

可以枚举两架敌方的飞机，它们互相击落要我方飞机在什么位置。
枚举两个能使得地方飞机击落的位置，看它们击落了多少地方飞机（可以直接用 bitset 异或）。
时间复杂度 $O(n^5/w)$。

821E

如果没有线段的限制那么就可以 $dp[i][j]=dp[i-1][j-1]+dp[i-1][j]+dp[i-1][j+1]$。
纵坐标很小，限制相同的一段边界是一样的，可以一起转移。用矩阵优化一段的转移即可。

585D

每个任务选两个人有三种方案。
直接暴力是 $O(3^n)$ 的，复杂度太高。
这个范围可以折半搜索，那么由于最后的值是一样的，就枚举一边，另一边使得两边和的三个值一样且尽量大。
先把两边的搜出来，求出两两之差，那么两边两两之差恰好都相反，枚举一边，求另一边相反的值最大是多少即可。

1510G

建树，如果有一条往下的长度为 $k$ 的链，那么直接走就可以了。
但是路径上可以往其它方向走下去再走上来，无论怎样都会走两遍，直接算一下就行了。

286B

理论上如果你能快速维护数组把一个数移动到某个位置的操作，那么就可以暴力调和级数 $O(n\log n)$。
怎么快速维护？如果你要求每次操作后每个数字往右移动一格（把第一格空出来），那么每一块只有一个位置动了，且要动的位置是前一个移到后一个，这样容易快速维护。
直接模拟即可。

1623D

这个明显有循环节（本质不同的状态只有 $4nm$，即当前所在的点和方向），暴力求出循环节和循环节内覆盖关键点的可能时间（最多 $4$ 个）。
容易发现，要么是这一轮每一次都没扫掉之后还得扫，要么就是扫掉了。
就设答案是 $ans$，$ans=t_1+(1-p)(t_2-t_1+(1-p)(t_3-t_2+(1-p)(t_4-t_3+(1-p)(t-t_4+ans))))$。
求出右边 $ans$ 的系数，解一下即可。

444B

由于数据随机，如果 $d$ 比较小，可以暴力枚举所有 $b$ 产生的贡献。
如果 $d$ 比较大，可以暴力枚举一些最大的 $a$，然后计算一下它们的贡献，由于 $d$ 很大且数据随机，所以大概率覆盖了所有位置。

863F

这个范围小的离谱，求出每个数能取的值的范围。
这个 $cnt(i)^2$ 的最小值，网络流的经典套路就是拆边，拆成 $1+3+5+7+\cdots$（差分建图）。
把每个值对应点拆成两个点，中间就连权值为 $1,3,5,7,\cdots$，每个数向能取的对应的值连边。

123D

SAM 模板。
求出 link 树上包含的子树大小和就可以知道出现次数了。

802I

还是 SAM 模板。
求出 link 树上包含的子树大小和就可以知道出现次数了。

362D

每次要么减少一个连通块，要么不变，不变花的代价是固定的。
类似哈夫曼树一样贪心，每次一定选两个最小的合并。

630P

将圆心向角连边（圆周上的角和向离凹的角）。
求出一个小三角形的面积后乘上 $2n$ 即可。
根据三个角度和长边的长度可以正弦定理求出其它边长进而求出面积。

457C

枚举一个 $x$，表示你的票数 $=x$，其它人的票数 $<x$ 需要的代价。
那么代价的计算方法就是先在每个里买里面最小的使得人数都 $<x$，如果自己票数还不够就接着买全局最小的。
考虑 $x$ 增加的时候，那么有些本身由于人数过多而买来的可能不需要买，如果有这样的那么你这次少买了，再买一个全局最小的一定不比原来的大，故答案不增；否则没有这样的人，每次要新买一个最小的，答案不减。
所以可以三分。

575G

到终点距离为 0 的先求出来，以它们为起点，跑 bfs（首先要求层数最小，层数）。
现在就变成求字典序最小的了，倒过来，给同层的点维护一个相对大小的值（看上一层的相对大小和新加的数），每次新加的越小越好，相同的还是赋成相同。

656D

每次 $\bmod 8$，看余数是不是 $1$，然后再 $/8$。

387D

枚举中心，那么所有点都得有和中心的双向边。
剩下的要求出入度为 $1$，拆点后二分图匹配即可。

311E

经典最小割建图，选 $0$ 和左边连通，选 $1$ 和右边连通。
对于限制，就是新建一个点，和某一边连，再和需要的点连。
初始认为所有利润都能取到，然后减去最小割即可。

730E

这题非常强大。由于你滚榜的时候如果排名变了，那么变化量就是那些它当前排名和你排名相对顺序变了。
如果最终相对顺序会变那么一定贡献 $1$，否则有可能过程中相对顺序变了，看两个分数的区间是否有交，有交就有贡献 $2$，否则没有贡献。

106E

显然三个维度都是单峰函数（另外两维没啥关系，你直接给距离三次方，然后另外两维和它没关系）。
都三分即可。

47D

搜索，每次看和每个密码不同的位数，如果 $>num[i]$ 就不行。
按照这个条件剪枝，最后判断是否相等即可。

690A2

先看 $n=4$，此时 $2$ 为了活命一定会赞成 $1$，那么就可以不多花金币。
而 $n=5$ 时那么 $2$ 就会反水，因为 $n=4$ 就都能活，所以一定得拉拢一半的。
$n=6$，由于 $n=5$ 一定会没金币，所以会支持 1 号，1 号再给别的。
可以发现如果等于 $2^k$ 的时候可以不花费活下来，等于 $2^k+2$ 的时候可以花费 $1$ 活下来，以此类推，等于 $2^k+2x$ 可以花费 $x$ 活下来。而如果是奇数，必须拉拢剩下的恰好一半。

883A

对于每个到来的顾客，看中间过程中开门的员工。
记录上一次知道的开门的时间，就可以求出这个顾客到来前最后一次开门的时间，判断一下顾客要不要自己开门。
方便起见可以加一个 $na$ 时间到来的顾客防止员工没算完。

316C2

二分图，还是经典操作，先二分染色，那么两双同色的鞋子最后放在相邻的位置上。
两只鞋一定是一只移动到另一只旁边，否则可以调整。把填同一种的变成两个点连同一条边匹配。
搞个带权匹配，边权是两个颜色是否相同。网络流即可。

60C

相连的点可以看做一个联通分量，要求每一个联通分量都合法。
当某一个点权值确定了，由于给定 gcd 和 lcm，根据 $ab=gcd\times lcm$，因此整个联通分量就确定了。
因此我们可以以某一点为该联通分量的起点，枚举该点可以取得的值，dfs 即可。

11C

大力搜索，先搜出四个方向的边长，再判断一下 1 的个数确认没有多余的边（也就是要和正方形框架上的数量相等）。

316C1（*，同 C2）

二分图，还是经典操作，先二分染色，那么两双同色的鞋子最后放在相邻的位置上。
两只鞋一定是一只移动到另一只旁边，否则可以调整。把填同一种的变成两个点连同一条边匹配。
搞个带权匹配，边权是两个颜色是否相同。网络流即可。

71D

枚举两张牌替换，处理出每个为左上顶点的矩形是否可以。
然后再枚举两个左上顶点看行不行。

183C

对于同一个起点到终点有多条不同路径，那么得要求 $\bmod $ 每条路径后的值都相同，也就是 $k$ 要是它们差的约数。
特别的一个环就是要求是它的约数。

243C

只有一千条线段，所以可以离散化（注意这里是左闭右开区间）。
然后就可以直接暴力覆盖了，时间复杂度 $O(n^2)$。

215C

这个条件看上去就是两个矩形取个并集。
枚举一个矩形（注意边长一定是奇数），如果总面积就是这个矩形，那么另一个举行被它包含就行了（注意中心点还得是同一个，边长是奇数）；否则要有多出来的，枚举多出来的长就可以计算出宽（注意上下是两部分，所以面积一定是偶数）。

215E

先求出有某个循环节的数字个数，这个数位 dp 好求，如果不压上界且位数到了那么方案就为 $1$。
然后再容斥，把循环节是约数的去掉。

690D3

直接 dp，这空间可能比较大，不过可以用 queue（或类似循环队列？）来存储（因为只会从 $-w$ 转移，而 $w$ 很小）。
转移需要预处理一下 $h$ 的幂。

409G

愚人节赛题，直接模拟。

316G2

把原串和询问串都拿来一起做广义后缀自动机。
然后对于每个串根据原串的出现次数和限制判断一下即可。

1505I

特殊语言题，直接输出。

54D

先把必须匹配的位置暴力填了。
剩下的位置爆搜看是否有解。

51D

经典删一个，那么前 3 个数一定有两个没被删。
看一下，序列就确定了（两项就能确定公比），如果前 3 个有被删的那么要求后面的完全一样，否则可以有一项少了。
每次找下一个相同的，看是否满足要求即可。

43E

先枚举两辆车，考虑它们的超车次数。
考虑两辆车一段速度不变的时间段，两辆车最多变前后顺序一次，计算一下即可。

213D

假设前 5 个顶点之间的距离为 $len$。
计算出前 4 个顶点的位置后，其他顶点的位置可以通过在前 4 颗星的 $x$ 坐标上加上 $k*len$ 计算。
然后通过横的边一条一条走到最后，再把这个五角星填满，回到上一个继续填。

491C

其实是个匹配问题，每一种匹配都有对应权值，求二分图最大权匹配即可。

212B

枚举子串，fix 左端点（要和前一个数不一样，不然会算重），然后再枚举右端点（要和后一个数不一样，不然会算重），给对应的二进制状态+1。
询问就看对应二进制状态的答案即可。

68C

范围这么小，都可以暴力。
枚举最小燃料量，然后 dfs，注意如果当前流的量不为 0 还要加上激活的代价。
dfs 就是从小到大，对每个点确认它往编号比它大的点的流量。

774A

谁家长是谁并不重要，只需要知道家长的人数。
枚举分了几组，那么每一组都要有个 $c_1$ 的代价和一个家长，那么剩下的要求人数尽量平均分即可。

77D

因为 $12$ 和左边块所处列不相邻，所以 $12$ 两列与其他列完全分离。
以 $dp[j]$ 表示前 $j$ 列划分的方案数，如果能用 $2*1$ 的填满整列就从 $dp[j-1]$ 转移。
再考虑这两列出现 $1*2$ 块的方案数，再计算一下两列的贡献即可。

241F

要根据 $s$ 的要求一个一个经过。
那么就从起始点开始，只要没到要求点，就花当前点的时间往那个点方向走。
如果时间用完了就结束，停留在当前点，输出。

1046I

一秒内，距离只会有三种情况：变小；变大；先变小后变大。
判断是哪种情况可以看开头和结尾的变化率是正是负。
分类讨论一下，二分即可。

1346G

题目写的比较哈人，简单来说就是分成两个序列使得它们分别 $\mod$ 某个 $p_i$ 同余（两两之差 $\bmod p_i=0$）。
根据经典结论，前三个数一定有两个是同一个序列的。
根据经典结论，约数个数很少，直接枚举然后暴力判剩下的有多少个可以在这个序列，剩下的把两两之差求个 $\gcd$ 看是否有 $p_j$ 满足即可。

926H

一定买橙红/橙白。
就是把两个最大的买了，剩下的从大到小买。

774E

这什么憨憨题。。。倍长后就变成了滑动窗口，求第一个不为 $0$ 的 $\bmod m$ 的最小值。
枚举左端点从左往右，每次更新当前 $\bmod m$ 的值即可。

661G

特殊语言题，先给第一行字符串的第一个位置改成大写。
如果第二行的是整数在第一行字符串前加 $i$ 否则加 $f$，然后输出。

661D

特殊语言题，直接模拟。

530H

特殊语言题，范围很小，直接枚举一维就行。

530G

特殊语言题，类似于求编辑距离的 dp，改一下转移权值即可。

530F

特殊语言题，范围很小，直接枚举青蛙能跳的距离，bfs 即可。

470H

特殊语言题，排序即可。

470G

特殊语言题，求一下汉明距离。

470F

特殊语言题，模拟即可。

345D

特殊语言题，求出哪些会收到信（bfs），看其中有多少个和 $n$ 号会发消息即可。

345B

特殊语言题，直接枚举不超过 $n$ 的底数暴力模拟即可。
注意底数 $>n$ 的表示方法就是原数，如果可以答案就是 -1。

316F2（*，同 F3）

这题好离谱啊。
先进行“收缩”，即如果一个点的周围有黑色就将它变成黑的，重复若干次。
然后再“展开”，即一个点周围有白色的就把它变成白的，重复若干次。
用原图减去这张图，得到那些光线。dfs 一下即可。

316F1（*，同 F3）

这题好离谱啊。
先进行“收缩”，即如果一个点的周围有黑色就将它变成黑的，重复若干次。
然后再“展开”，即一个点周围有白色的就把它变成白的，重复若干次。
用原图减去这张图，得到那些光线。dfs 一下即可。

207D10

长度 $\leq 50000$ 输出 3，$\geq 54000$ 输出 1，否则输出 2。

207D8

长度前两位（即 $/1000$）是偶数输出 1，否则输出 2。

207D6

长度前两位（即 $/1000$）是偶数输出 3，否则输出 1。

207D4

输出 1。

203E

把那些一定不能自己走的记录一下数量和它们能带多少个。
特判只有一个就能带着所有的。贪心，你尽量会选那些能自己走的能带人的，因为你可以套娃，套进来的自己占一个位置，而多了自己能套的位置。

本文永久更新地址:

https://blog.hydd.cf/p/codeforces_2100-2300/