Tags:「A.生成树」「B.Tricks」
分类处理询问的 trick：连接两个连通块的边显然合法，先用这些边构建生成森林。发现每条边至多在一个环上，所以可以用 BIT 在 DFS 序上维护其余边是否可行。
Tag:「C.性质/结论」
把操作转化成“对于边 ((u,v))，令 (a_u) 或 (a_v) 加上 (1)”，有以下结论：
-
合法的序列数量为 (2^{n-1})，归纳可证不重不漏；
-
当 (k>1)，至多只有一种方案使得所有 (kmid a_u)，递归构造可证唯一性；
-
当 (k>1)，存在方案使得所有 (kmid a_u)，则 (kmid(n-1))，显然。
然后就随便做了。
Attention: 先分析性质，再想算法。例如这道题走起来想 DP 就裂开了。
Tag:「A.DP-状压/插头 DP」「A.分治-二分答案」「B.Tricks」
二分答案 (l)，枚举每种字符第一个长度超过 (l) 的位置的顺序关系，每次放置一定是尽量考前放，所以可以利用预处理判断，将这一过程状压即可。
Attention: 很讨厌这种字符串填充的题……不要一味地追求“扫一遍出解”！
Tags:「A.并查集」「A.生成树」「B.Tricks」
所以学了下 Boruvka 求 MST 的算法，类似于朱刘算法，维护连通块，每次求每个连通块连出的最小边，尝试加入这些边合并连通块。一共只有 (mathcal O(log n)) 次加边，故复杂度为 (mathcal O(mlog n))。这个算法的优势在于：如果 (m) 很大，但我们存在一种直接求出连通块连出最小边的方法，就可能回避复杂度中的 (m)。
回到本题，在 (i,j) 间连从 (a_i) 跳到 (a_j) 所需的最小 (k)，求出 MST 就能预处理所有答案。使用 Boruvka 及上述优化 trick，利用 std::set 在 (mathcal O(log n)) 的时间内找最小边，可以做到 (mathcal O(nlog^2n))。
Tags:「A.并查集」「C.性质/结论」
考虑奇偶性，答案显然在 ({0,1,2})，故只需判断答案能否为 (0,1)。对于 (0)，并查集直接维护连通块。对于 (1)，考虑每个 (a_i+1) 带来的连通块之间的连边，暴力 (mathcal O(log^2 A)) 记录信息，若两个连通块间有边答案就是 (1)。
Attention: “素因子个数平方”是很小的，不要定式思维觉得“暴力”过不了。
Tags:「C.构造」「C.性质/结论」「C.思维」
震撼兔子一整年.jpg 首先分析一个 Simple 图的性质：((u,v)in ELeftrightarrow |uoplus v|=1)，所以钦定某个点为 (0)，其邻接点为 (2^{0..n-1})，然后 BFS 构造，每个结点的编号为与它邻接的上层结点的或和。易证。
此后，第二问，仅需对 Simple 图求解。由于颜色总数为 (2^n)，每种颜色出现次数相等，所以有解的必要条件为 (nmid 2^n)（(n) 是 (2) 的整幂）。接下来给出人类智慧构造：
正确性易证，但能构造出来这玩意儿就离谱 qwq。
Tag:「A.DP-计数 DP」
这题评分和上题一样就离谱……令 (f(i,j)) 表示长度为 (i) 的排列对 ((p,q)) 中 (p) 的逆序对数减 (q) 的逆序对数之差为 (j) 的方案数，利用二次前缀和优化转移。求答案枚举 (p,q) 的 LCP 和第一个不同位置的差值即可。
Attention: 注意检查模意义下的四则运算函数，这个写错就没救了。
Tags:「A.DP-计数 DP」「C.性质/结论」
一次操作起作用的条件是 (a_{i+1}-a_i<b_i)，记最终序列为 (f)，那么有 (sum f=sum a)。考虑最前一段被操作影响的区间，有 (f_1+(f_1+b_1)+(f_1+b_1+b_2)+cdots=a_1+a_2+cdots+a_i)，进而 (f_1=frac{S_a(i)-S^2_b(i)}{i})（(S^2) 即二次前缀和）。那么由于 (i) 任取，我们要保证 (S_a(i)ge ix+S^2_b(i-1))，DP 一发。注意到有用的 (x) 取值不多，仅 (mathcal O(n)) 中，所以可以预处理出所有答案。
Tags:「A.DP-杂项」「C.细节」
定义状态 (f(i,0/1)) 表示 左手/右手 拿着第 (i) 张卡，右手/左手 拿着第 (i+1) 张卡时，能否通过 (i) 及其以后的限制。转移枚举下一个换手的位置，显然这样的位置如果合法，必然越靠前越好。以 (f(i,0)) 为例，为了转移它，仅需记录从 (f(j,1)) 为 (1) 的 (j) 开始，左手牌的限制区间交集和是否每张右手牌都能通过紧接着的限制，虽然比较麻烦但不难想。（
Attention: DP 时注意不要让新的信息覆盖掉需要使用的旧信息，写完回头捋一捋各个变量在当前的意义！
Tag:「C.性质/结论」
打序列上游戏的 SG 表知环上后手必胜，而且后手操作只要合法都必胜。所以只需对双方共进行偶数次放置的结束状态计数。枚举放置数量，显然有
Attention: 你总不能把 SG 表打错了吧 qwq！
Tags:「A.缩点/圆方树」「B.模型转化」「C.性质/结论」
从 easy 版消除所有沙子为目标，可以把沙子的影响关系建图，每坨沙子向向上左右连至多一条边，缩点之后 (0) 入度点的个数即为答案。对于 hard，合法条件等价于每列第 (a_i) 坨沙子被消去，所以问题变成在 DAG 上选择若干点，使对于每个关键点，都至少有一个选择的点可以到达它。不难证明每坨沙子能覆盖的关键点是一个连续区间，所以可以拓扑出每个点的覆盖区间，此后转化为区间覆盖问题，随便贪心即可。
Tags:「A.DP-概率/期望 DP」「A.DP-状压/插头 DP」「A.数学-容斥计数」
容斥列和对角线的是否满足，行的概率可以直接算出来，结束了。（
Tags:「A.DP-最短路相关」「B.Tricks」「B.优化建图」
解决“原地等待边旋转指向某个结点”很好办：新建 (lang i,(i+1)mod n,1 ang) 即可。然后你发现不管这个图上的边怎么扭，Dijkstra 这类最短路算法的贪心结构是一直保证的，所以写一发 (mathcal O(n^2)) 的 Dijkstra 就行。
注意这个细节：也许图在变，但并不妨碍某些算法的正确性。
Attention: 略过或者叉掉某个思路的时候麻烦严谨说服自己，好多次都是秒出正解（比这题难的那种）然后莫名其妙就不想了 qwq。
Tag:「A.DP-数据结构优化 DP」
维护 (k) 棵线段树，第 (i) 棵的 (j) 位置表示 (f(i,j)+) 从该状态转移到当前位置的花费，细节不难。
Attention: 虽然因为考虑到是 CF 所以才这样干，决策单调性什么的至少得打个表在下结论吧……如果在一个未证、甚至已证的结论下无法优化，不要一根筋，重启解决 (90\%) 的问题。（
Tag:「A.数学-组合计数」
求“超过 (i) 盏灯亮”的概率之和，问题在于求“(n) 个球里选 (m) 个，两两之间至少隔 (k) 个”，经典问题，先拿出用于分隔的 (k(m-1)) 个，选完放回去，方案数为 (inom{n-(m-1)k}{m})。
Tags:「B.Tricks」「C.构造」「C.思维」
一种重要的构造思想：给对象分类。例如奇偶分类、构造二分图……本题中，就可以按 此图（为了不占版面就不放图了 awa）所示把格子分为四类，发现蓝色格子是万能的，不可能与任何格子冲突，那么就把这类格子当做缓冲。具体地，依次填黄色和红色格子，发现填不了就丢蓝色格子。另一方面，可以根据必要条件算出答案下界，由构造方案知下界一定可行，这里不细讲。（其实直接二分答案放置也是可以的。）
Tag:「B.贪心」
贪心地递归，把树拆成若干链，具体地，递归出 (u) 子树时，需要知道 (u) 能否继续向上连边，若能，链的底部是谁。
Tag:「A.数学-数学推导」
好啊，模数敲错了！好啊，组合恒等式写错了！好啊，二项式定理合并错了！我想把自己炖了艹。
（不得不写成 (S(n,m)) 了，那个大括号怎么打出来 qwq……）
Tags:「C.构造」「C.思维」「C.性质/结论」窒息标签三连击 qwq
分类思想，如果能和 (1) 连就先连上。那么此时左森林的结点 (u) 与与之对应的右森林的结点 (u') 有三种情况：(1) 都在 (1) 连通块；(2) (u) 在 (1) 连通块；(3) (u') 在 (1) 连通块。我们发现 (2) 情况的 (u) 可以和 (3) 情况的任意一个 (v) 连边，此时 (u,v,u',v') 都进入 (1) 连通块。到无法操作时，必然有一片森林退化为树，所以答案达到了理论上界 (n-1-max{m_1,m_2})。
Tag:「C.构造」
(a+b=(a operatorname{or} b)+(a operatorname{and} b))，构造 (n) 个方程解出 ({a_n})。
Tag:「C.性质/结论」
是不是外国友人的技能树点得和我相差很远啊，这种玩意儿怎么都比上面那道简单吧。
令 (p_i) 表示 (p={1,2,dots,n}) 循环位移 (i) 次的结果，设 (p_i) 和询问排列 (q) 的不相同位置有 (c) 个。由于 (k) 次交换最多涉及 (2k) 个元素，所以 (p_i) 合法的必要条件为 (n-cle 2k)，发现 (cge n-2kge frac{n}{3})，且对于每个 (q_i)，有且仅有一个 (p_j) 满足 (q_i=p_{j,i})，所以暴力检查满足这一必要条件的 (p_i) 即可。