AtCoder Regular Contest
将 $n$ 个标志放在数轴上。第 $i$ 个标志可以放置在坐标 $a_i$ 或 $b_i$ 上，求出两个标志之间最小距离的最大值。
$n\le10^4$
很显然的二分答案，成功将问题转化为在 $O(n \log n)$ 或 $O(n \sqrt{n})$ 的时间内 check。
观察限制条件，不难想到用 2-sat 判定，缩点后，若 $a_i$ 和 $b_i$ 在同一个连通块中无解。
暴力连边的话时空复杂度都会爆炸，考虑数据结构（线段树/分块）优化建图。
ARC074C RGB Sequence | Solution
有一个序列 $a$，要给序列中的每个元素一种颜色：红/绿/蓝。有 $M$ 条限制 $(l,r,x)$，表示格子 $l~r$ 中颜色的种数要恰好为 $x$，问可行的方案数。
DP 设状态好题，限制转移好题。
需要根据数据范围以及如何转移考虑如何设状态，设 $f_{i,j,k}$ 要注意代表三种颜色并不是固定的，只是相对较前，较后，这是很重要的一点。
其次是限制转移的问题，真的很妙，写一个 check 去限制，非常妙。
哦，还有就是题目里给出的限制条件，经典的右端点排序。
ARC079E Decrease (Judge ver.) | Solution
给你 $n$ 个数，取这 $n$ 个数中最大的减 $n$，其它的数加 $1$，直到所有数都小于 $n$，问需要操作的次数。
这道题唯一的坑点在于翻译，，想明白之后就是一个模拟，发现顺序其实并没有必要，所以直接累加贡献，一个个减没有必要，直接换成除法，加完 $1$ 之后可能又超了，多来几次就好了，
题解里面关于时间复杂度的证明挺神奇的（虽然我不能证明那个证明是证明。
ARC084B Small Multiple | Solution
求一个 $K$ 的正整数倍 $S$，使得 $S$ 的数位累加和最小。
神仙题。
考虑如何构造 $S$，
$S \leftarrow S \times 10$ 数位和不变；
$S \leftarrow S + 1$ 数位和加 $1$；
然后同余最短路，01 bfs。
AtCoder Grand Contest
AGC005C Tree Restoring | Solution
美妙树的每条边长度都为 $1$，且有一个最重要的性质：对于每一个点 $i$（$1\le i\le N$），在树中离它距离最远的点与它的距离应恰好等于 $a_i$。对于一个给定的序列，是否存在一棵美妙树？
做法的话就是 if，if，if，对于大于 mid 的点找直径，如果不能构成就寄了，剩下的随便放，如果有小于 mid 的也是寄了。
这题如果增加难度的话可以输出方案。
反悔贪心/wqs 二分。
AGC032C Three Circuits | Solution
$n$ 个点 $m$ 条边的简单无向连通图，判断能否将边分成三个集合，每个集合都是一个可以多次经过重复点的环。
推一个“结论”：经过同一个点的两个环可以合并，也可以拆分，一个度数为 $d$ 的点可以拆出 $\dfrac{d}{2}$ 个环。
然后分情况讨论：度数为 $4$ 的点又要细分情况，，然后就没了。感觉最大的问题是情况是否考虑全了，嗯。
找路径的 dfs 1s 口胡，10 min debug，代码实现能力还是太差。
AGC038D Unique Path | Solution
给定 $Q$ 条限制，若 $C_i = 0$，则 $A_i$ 到 $B_i$ 仅有一条简单路径；若 $C_i=1$，则 $A_i$ 到 $B_i$ 有多条简单路径，判定在这 $Q$ 条限制下能否构造出合法的图。
分情况讨论，用并查集维护连通块，对于两个不同的连通块，最多只能连一条边。
AGC041D Problem Scores | Solution
AtCoder Beginner Contest
ABC162E Sum of gcd of Tuples (Hard) | Solution
$$\begin{aligned}&\sum\limits_{i_1=1}^m\sum\limits_{i_2=1}^m…\sum\limits_{i_n=1}^m\gcd(i_1,i_2,…,i_n)\\ =&\sum\limits_{i_1=1}^m\sum\limits_{i_2=1}^m…\sum\limits_{i_n=1}^m\sum\limits_{d|\gcd(i_1,i_2,…,i_n)}\varphi(d)\\ =&\sum\limits_{d=1}^m\varphi(d)\sum\limits_{i_1=1}^{\lfloor\frac{m}{d}\rfloor}\sum\limits_{i_2=1}^{\lfloor\frac{m}{d}\rfloor}…\sum\limits_{i_n=1}^{\lfloor\frac{m}{d}\rfloor}1\\ =&\sum\limits_{d=1}^m\varphi(d)\left(\lfloor\frac{m}{d}\rfloor\right)^n\end{aligned}$$
ABC162F Select Half | Solution
给定长度为 $n$ 的序列 $A$，请在这个序列中选择 $\lfloor\dfrac{n}{2}\rfloor$ 个数，并且这些数两两不相邻。
一眼 DP，一眼分奇偶，一眼不会转移。
默默的打开题解，奇数前缀和？额，算是学到新东西了吧，想到这个以后再列转移就好想很多了，
ABC163E Active Infants | Solution
给定 $n$ 个数，现在要将其重排。如果 $a_i$ 于重排前在第 $i$ 个位置，现在移动到了第 $j$ 个位置，那么对答案的贡献就是 $|j-i|\times a_i$。现在，你需要让答案尽可能大。
一道非常神奇的区间 DP，从小区间往大区间更新答案，
Others
直接放 link 定长路径统计
Contests DP Y Grid 2 | Solution
DP Part II 的某一道例题的双倍经验。
JOISC 2014 H JOIOJI | Solution
请你求出字符串中最长的、包含同样数目的 J、O、I 三个字母的连续子串。
一道极好的思维题（开始想的 DP，后来发现不太可做。
关键在于题意的转化，我只要找到之前的一个点，J，O，I 的相对数量相等就行，也就是说我只在乎三个字母的增量是否相等，而不是具体的数量。
代码实现的话就是一个 Hash。
JOI 2012 HO C Night Market | Solution
从 $N$ 个夜市中选择其中几个夜市进行游玩，给定：在夜市 $i$ 玩的乐趣值和游玩的时长。
要求：必须按顺序游玩；在夜市游玩的时间是 $0\sim T$；游玩时间不得与时间点 $S$ 重叠；使游玩乐趣值之和 $M$ 尽可能大。
一个非常裸的背包问题，设 $f_{i,j}$ 表示游玩第 $i$ 个夜市，时间为 $j$ 的最大的兴趣值，不考虑限制条件的话就是：$f_{i,j}=\max(f_{i-1,j}, f_{i-1,j-b_{i}} + a_{i})$
考虑限制条件，因为游玩是按顺序的，所以我们考虑分成 $S$ 前与 $S$ 后两部分考虑，后半部分可以倒推一个 $g_{i,j}$，与 $f$ 类似，我们可以得到：$g_{i,j}=\max(g_{i+1,j}, g_{i+1,j-b_{i}} + a_{i})$
最后的答案就是：$ans=\max(f_{i-1,s} + g_{i,t-s})$。
还有一种常数更优的做法，没想明白。
不知道序列带修是否可做。
ICPC 2014 F Reverse a Road II | Solution
每条道路只能走一遍，可以反转一条道路，求最大流。
因为每条边最多只能走一遍，所以建一条容量为 $1$ 的边，跑一遍最大流。
考虑将 $s$ 能扩展到的节点扔进 $\text{set}_s$，将能扩展到 $t$ 的节点扔进 $\text{set}_t$，枚举残量网络上的边 $e$，如果 $u \in \text{set}_t \land v \in \text{set}_s$，那么反转这条边就能够构成一条 $s \to t$ 的合法路径，累加 $tot$。
APC001C Vacant Seat | Solution
震惊！zerc 竟然连二分都不会写了，
其实就是一个二分套上交互（好多交互题都是二分哎，
关键在于 check，额，也很好写，因为过分在乎 20 次的限额，然后就没判，就坑的很惨，，。
关于二分的话，记住一个没有问题的板子就好了，但一定要去分析内在逻辑，大凯的疑惑那个题 Pozhu（和他师傅）就是因为一个微妙的二分问题 de 了好长时间。