[Problem Link](https://www.luogu.com.cn/problem/P12403) 首先树上 $s,t$ 距离 $>2$ 那么可以相向移动，所以只要暴力枚举距离 $\le 2$ 的点对。 对于基环树上的问题，类似地如果 $s,t$ 都不在环上，则只要考虑距离 $\le 2$ 的情况。 否则我…

[Problem Link](https://www.luogu.com.cn/problem/P11613) 首先转成最大独立集，对图 $\bmod p$ 计数有经典做法，取出前两个点，如果这两个点邻域不同则交换之，得到一个相等的图。 因此这两个点邻域相同，讨论两点间是否有边，如果有边那么两个点至多选一个，看成删除一…

Problem Link](https://www.luogu.com.cn/problem/P13346) 首先我们的信息肯定只能传递第一次删掉哪个点。 首先菊花只要保留第一次没删掉的点就能得到菊花的根。 链则是每次删掉之前被选但没删掉的点。 考虑如何同时处理这两种矛盾的决策：我们取出链的终点，然后删掉交替删掉左侧和…

[Problem Link](https://www.luogu.com.cn/problem/P13533) 可以把我们的操作看成询问区间中假币标号和。 首先我们有一个朴素的做法，对值域倍增分块，那么如果一个区间中假币个数 $\le 1$ 可以直接判断出来，否则按 $[l,mid],[mid+1,r]$ 分治即可。…

[Problem Link](https://www.luogu.com.cn/problem/P11834) 首先 $w=1$ 考虑的部分，要求缩点后的 DAG 只有一个入度为 $0$ 的 SCC。 回顾一下经典的主旋律容斥，我们加入一层入度为 $0$ 的点 $T$ 系数为 $(-1)^{|T|-1}w_T$。 考虑…

[Problem Link](https://www.luogu.com.cn/problem/P14471) 首先 $t=0$ 时是经典后序背包，在 dfn 序上 dp 即可做到 $\mathcal O(nk)$。 考虑如何在 dfn 序上背包时处理子树信息，注意到我们的限制是二操作上 $u$ 不能选超过 $c_u-…

[Problem Link](https://www.luogu.com.cn/problem/P12204) 把边反向，变成白点的前驱至少有一个黑点。 首先每个 SCC 内部可以直接黑白间隔染色，但我们要使得 SCC 之间没有黑点向黑点的连边。 考虑按拓扑序处理，每次把所有没有入度的 SCC 按上述方法染色，注意到此…

[Problem Link](https://www.luogu.com.cn/problem/P13786) 首先假设 $p=[1,\dots,n]$，则 $a=\mathrm{LIS}(q),b=\mathrm{LIS}(r)$。 通过 $a=1,c=n$ 的部分分可以猜测合法条件为 $abc\ge n,a+b\l…

[Problem Link](https://www.luogu.com.cn/problem/P11989) 首先难度确定是就是朴素贪心，每个时刻弹出最大值可以做到 $\mathcal O(n\log n)$。 但另一种等价的做法就是按 $p$ 从大到小考虑每个怪兽，尽可能向后一直打该怪兽，用并查集维护非空段，时间复…

[Problem Link](https://www.luogu.com.cn/problem/P11992) 首先一条链可以尝试二分找第一个 OR，即选一个前缀，每个点挂的叶子填 $1$，链下方的点填 $0$，那么可以判断前缀中是否有 OR，找到 OR 后，可以同时翻转该点以及其两个儿子使其变成 AND，然后就能继续…

[Problem Link](https://www.luogu.com.cn/problem/P11994) 首先选择 $x$ 则后面所有 $\le x$ 的数都要选，那么每种值选的是一个后缀且长度递减。 我们需要进一步刻画性质，不妨考虑值域为 $2$ 的情况，那么我们猜测做法一定是优先选尽可能多的 $1$。 反证法…

[Problem Link](https://www.luogu.com.cn/problem/P11983) 首先可以想到按值从大到小贪心地确定每个区间。 那么我们的思路就是从前往后，每个没被确定的区间填成当前的最大值 $v$，要求加入后可以通过不超过 $c$ 个点覆盖所有区间，$c$ 是 $v$ 的出现次数。 考虑…

[Problem Link](https://www.luogu.com.cn/problem/P11990) 首先对于每个 $?$ 连续段，观察其两侧的字符： - 如果相同，不妨设是 $A$，那么这个连续段中有 $B$ 或 $C$ 时代价 $+2$，同时有则代价 $+3$。 - 如果不同，不妨设是 $A,B$，那么这…

[Problem Link](https://www.luogu.com.cn/problem/P11984) 首先朴素的想法就是用 $a$ 个 $0$ 和 $b$ 个 $1$ 表示 $\binom{a}{a+b}$ 级别的信息。 有几个问题需要解决：首先如何确定要发送的信息，可以想到用最后 $k$ 个元素发送前 $n…

[Problem Link](https://www.luogu.com.cn/problem/AT_ddcc2020_qual_f) 首先把行列重标号使 $(i,j),(i,j+k),(i+k,j)$ 相邻，那么 $(i\bmod \gcd(n,k),j\bmod \gcd(m,k))$ 不同的点无关，那么可以转成若…

[Problem Link](https://www.luogu.com.cn/problem/AT_agc073_b) 首先 $n=2$ 的时候，可以分讨：如果有一种步长向左向右都移动过，那么答案 $\ge a_1+a_2$，这是因为相邻的 $\pm a_1$ 中间至少隔了一个 $a_2$。 否则最优解就是每次增加…

[Problem Link](https://www.luogu.com.cn/problem/AT_agc065_f) 考虑如何判定图合法，在圆方树上判定原图的每个点双，计算每个点是否要在该点双内匹配，如果同时有要匹配和不要匹配的点，那么必定能找到这样的两个相邻的点，把这个要匹配的点其他出边都删掉后求生成树，则必然无…

[Problem Link](https://www.luogu.com.cn/problem/AT_arc178_f) 首先逆序对数是二元信息，不好维护，考虑通过容斥的方式转成一元信息，对于 01 序列 $a_0\sim a_{n-1}$，逆序对数可以表示成 $\sum_i i(1-a_i)+\binom{\sum…

[Problem Link](https://www.luogu.com.cn/problem/AT_keyence2020_f) 检验一个网格能否生成，只要每次删掉所有同色的行列，直到不能删除时判定是否和原网格一致。 通过钦定检验顺序使得每种删除方案恰被计数一次，可以想到依次按行、列、行、列的顺序删除。 那么当我们删…

[Problem Link](https://www.luogu.com.cn/problem/AT_agc063_f) 考虑哪些元素 $(u,v)$ 能得到点 $(x,y)$，那么 $y=\dfrac vux$ 的直线应该经过 $[x,x+1]\times [y,y+1]$ 这个正方形，且不是 $(x,y+1)/(x…

[Problem Link](https://www.luogu.com.cn/problem/AT_agc064_e) 首先我们不妨假设 $S=X$，我们观察对于一组确定的 $s_{i,j}$，能否得到矩阵 $M$ 的值。 简单提取贡献得到 $W=\sum M_{i,j}=\dfrac{\sum s_{i,j}}{2…

[Problem Link](https://www.luogu.com.cn/problem/AT_agc071_d) 我们声称序列合法当且仅当如下两个条件均满足： - 定义 $z_i=\begin{cases}i&i #define ll long long using namespace std; const i…

[Problem Link](https://www.luogu.com.cn/problem/P9353) 手玩一下发现每次操作都是给一个前缀染红或者一个后缀染蓝，设起点为 $x$，具体的方向和范围只和 $[1,x)$ 中红色点数以及 $(x,n]$ 中蓝色点数有关。 考虑操作若干次后，序列会变成前缀 $k$ 个红点…

[Problem Link](https://www.luogu.com.cn/problem/P11921) 先二分答案，注意到答案的分子 $\le L$，分母 $\le n$，直接排序后二分即可。 如果每个人入睡顺序确定时，只要贪心找最早可能的入睡时间即可。 如果暴力枚举下一个入睡的人，对每个 $i\in[1,L]…

[Problem Link](https://www.luogu.com.cn/problem/P12485) 序列信息不好维护，在值域上考虑。 记 $a_i=0$ 的下标为 $b_1\sim b_m$，对于每个 $v\in[1,n]$，$c_v=\min\{i\mid a_i=v\}$。 那么对于 $b_1$，找到最…

[Problem Link](https://www.luogu.com.cn/problem/P13539) 先考虑直径过 $0$ 的情况，朴素想法就是用最后 $\log_4 n$ 位传递前 $n-\log_4 n$ 位的最大深度，如果某个后 $\log_4 n$ 位的数变成了新的直径端点，那么直接返回 $4$ 即可…

[Problem Link](https://www.luogu.com.cn/problem/P13540) 首先图中点数太多，只考虑所有的 $(0,y)$ 类点，把每条路径按经过 $(0,y)$ 分段。 具体来说，设 $w_y$ 表示第 $y$ 列上极长的可通行前缀，那么路径经过某个 $x\le w_y$ 的 $(…

[Problem Link](https://www.luogu.com.cn/problem/CF2084H) 观察题目的操作，注意到删除元素一定是 $s_i$ 或 $s_{i+1}$，因此 $s_{i+2}$ 总是不变，并且除非 $s_i=s_{i+1}=s_{i+2}$ 时生成两个 $s_{i+2}$，否则必定生…

[Problem Link](https://www.luogu.com.cn/problem/CF2127G2) 单个询问几乎没有信息，考虑两个近似排列答案的变化量。 如果没有 $i\ne k$ 的限制，那么询问 $q$ 的每个循环移位答案都不变，因为原本的 $q_n$ 入边贡献必定减少，出边贡献必定增多。 那么加上…

[Problem Link](https://www.luogu.com.cn/problem/CF2115D) 可以看成从 $\oplus a_i$ 开始每次选择是否异或上 $v_i=a_i\oplus b_i$。 从高到低确定每一位的取值，首先最高位 $k$ 的取值只和最后一个包含 $2^k$ 的 $v_i$ 对应…