DP \text{DP} DP ：
题意：
有一个 n ∗ m n*m n∗m的矩阵，行的标号从 1 1 1到 n n n，列的标号从 1 1 1到 m m m，矩阵中共有 k k k个宝藏，第 i i i个宝藏的位置为 ( r i , c i ) (r_i,c_i) (ri,ci)。有 q q q个安全的列，第 i i i个安全的列的编号是 b i b_i bi。
最初你站在矩阵的左下角（也就是 ( 1 , 1 ) (1,1) (1,1)的位置），并且可以向左走（从 ( r , c ) (r,c) (r,c)到 ( r , c − 1 ) (r,c-1) (r,c−1)）和向右走（从 ( r , c ) (r,c) (r,c)到 ( r , c + 1 ) (r,c+1) (r,c+1)）。同时，你也可是向上走（从 ( r , c ) (r,c) (r,c)到 ( r + 1 , c ) (r+1,c) (r+1,c)），但是你必须在安全的列上。由于某些玄学原因，你不可以向下走。
你的任务是收集所有的宝藏，但是你的时间已经不多了，所以你必须走最快的路径。现在你要使用你的人脑大法来计算出最快的路径需要多少时间（经过有宝藏的格子时收集宝藏不消耗时间，只有移动消耗时间）。
n , m , k , q ( 2 ≤ n , m , k , q ≤ 2 ∗ 1 0 5 , q ≤ m ) n,m,k,q(2≤n,m,k,q≤2*10^5,q≤m) n,m,k,q(2≤n,m,k,q≤2∗105,q≤m)
思路：容易发现，对于一行，我们只需要关注两端的宝藏。当我们收集完一行的宝藏，我们就位于最左边或者最右边，然后走向最近的特殊列来进入下一行，那么一行就抽象出两个点。容易发现这一行的点连接下一行的点最多有 8 8 8 条边 。建图然后在拓扑图上跑一遍最短路即可。代码容易写的很繁琐。
AC代码：https://codeforces.com/contest/1201/submission/181314581
题意：略。
思路：枚举显示器的数量，对于满足数量要求的每个朋友，可以抽象为价值为 x x x 的物品，但是可以解决若干个对应问题。状态压缩 DP 最小花费即可。定义 d p ( i , j ) dp(i,j) dp(i,j) 表示前 i i i 个朋友解决状态为 j j j 的问题的最小花费。
注意要对朋友按照 k k k 进行排序，才能对每个前缀枚举答案。
AC代码：https://codeforces.com/contest/417/submission/181373058
题意：最开始你的背包有 k k k 的容积，有 n n n 轮 可以按照任意次序 参加的比赛，比赛分为两种(具体种类由输入给出)，一种的奖品是给你的背包增加 a i a_i ai 的容积，另一种是一个体积为 1 1 1 的物品，只有 任意时刻背包都能装得下当前赢得的所有物品 才算合法的方案，问赢得的比赛总场数 ≥ l \geq l ≥l 的合法方案的概率。
思路：概率 DP 即可。
AC代码：https://codeforces.com/contest/167/submission/182123019
题意：
给定 n n n 个点 m m m 条边的有向图，可能不连通，可能有重边，也可能会有自环。求最长的路径(可以经过重复节点)，使得这条路径的编号和权值都严格单调递增，其中编号指输入的顺序。路径的长度是指经过边的数量。
1 ≤ n , m ≤ 1 0 5 1\leq n,m\leq10^5 1≤n,m≤105， 0 ≤ w i ≤ 1 0 5 0\le w_i\le10^5 0≤wi≤105
思路：树上的 LIS ，可以使用 map 实现。注意修改时需要保证 map 内部的 value（值）仍然同为单调的。
AC代码：https://codeforces.com/contest/960/submission/182103597
构造题：
题意：
思路：考虑找答案的每一位。枚举位数 b i t bit bit ，构造 b i = a i % 2 b i t + 1 b_i=a_i\%2^{bit+1} bi=ai%2bit+1 （ b i t bit bit 位以上没有贡献）。问题转化为序列 { b } \{ b \} {b} 有多少对 ( i , j ) (i,j) (i,j) 满足 2 b i t ≤ b i ⊕ b j < 2 b i t + 1 2^{bit}\leq b_i\oplus b_j <2^{bit+1} 2bit≤bi⊕bj<2bit+1 或 b i ⊕ b j ≥ 2 b i t + 2 b i t + 1 b_i\oplus b_j \geq 2^{bit}+2^{bit+1} bi⊕bj≥2bit+2bit+1 ，判断其奇偶性。二分即可。
AC代码：https://codeforces.com/contest/1322/submission/181868398
题意：给定 n , m ( 1 ≤ n , m ≤ 1 0 5 ) n,m(1\leq n,m\leq 10^5) n,m(1≤n,m≤105) ，构造长度为 n n n 的非负整数序列 a a a ，使得对于给定的 m m m 个区间，满足 m m m 个区间的 mex i = l r a i \text{mex}_{i=l}^r a_i mexi=lrai 的最小值最大。
思路：结论为，mex 下界的最小值最大为：最小区间长度。可以构造序列为 0 ∼ m i n l e n − 1 0\sim minlen-1 0∼minlen−1 的周期序列，即可使得每个长度至少为 m i n l e n minlen minlen 的区间 mex 都大于等于 m i n l e n minlen minlen 。
AC代码：https://codeforces.com/contest/739/submission/182127473
题意：
求 n n n 个点的完全有向图的最小字典序欧拉回路的第 l l l 到 r r r 个节点。
2 ≤ n ≤ 1 0 5 2 \le n \le 10^5 2≤n≤105 , 1 ≤ l ≤ r ≤ n ( n − 1 ) + 1 1 \le l \le r \le n(n - 1) + 1 1≤l≤r≤n(n−1)+1 , r − l + 1 ≤ 1 0 5 r - l + 1 \le 10^5 r−l+1≤105
题解：题解 CF1334D 【Minimum Euler Cycle】
AC代码：https://codeforces.com/contest/1334/submission/182132223
题意：略。
思路：定义 t o i to_i toi 表示 i i i 会转移到哪个颜色，时间倒序维护即可。如果倒序到一个 x → y x\rightarrow y x→y 的操作，那么令 t o x = t o y to_x=to_y tox=toy 。
AC代码：https://codeforces.com/contest/1620/submission/182196661
题意：
给出一个序列 a a a，求出一个长度不超过 3 n 3n 3n 的操作序列，使序列 a a a 中每个元素相等。
定义一次操作为：选出 ( i , j , x ) (i,j,x) (i,j,x) 三元组，满足 i , j i,j i,j 为序列合法下标， x x x 为 1 0 9 10^9 109 以内非负整数，令 a i : = a i − x ⋅ i , a j : = a j + x ⋅ i a_i:= a_i-x\cdot i,a_j:=a_j+x\cdot i ai:=ai−x⋅i,aj:=aj+x⋅i。
必须保证操作过程中的任意时刻序列 a a a 中每个元素都非负。
输出时先输出操作次数 k k k，然后输出 k k k 行操作序列。
数据组数 t ≤ 1 0 4 t\le10^4 t≤104，序列长度 n ≤ 1 0 4 n\le10^4 n≤104，元素大小 1 ≤ a i ≤ 1 0 5 1\le a_i\le10^5 1≤ai≤105。
思路：容易发现，可以把所有的数量转移到 a 1 a_1 a1 头上，然后 a 1 a_1 a1 即可分出任意个数的数字给其他数字。对于前者， a 2 ∼ a n a_2\sim a_n a2∼an 从左到右移动到 a 1 a_1 a1 ，每个 i i i 最多两次操作。容易知道因为 a i ≥ 1 a_i\geq 1 ai≥1 ，因此在移动的过程中一定非负。
AC代码：https://codeforces.com/contest/1416/submission/182197741