题意：给出$n$，求$1$到$n$的和
题解：略
题意：$n$个人做成一排，问有多少种握手方式，一个人只能和隔壁人握手。
题解：$fib_{n-1}$
题意：一条路上，从左往右有$2n$个村庄，有些类型是g，有些类型是t。现在你要将他们配对，要求任意两队不相交。
题解：维护个栈，每次和栈顶类型不一样就配对一下。
题意：给出$n$，构造$n$条垂直线段，使得互相可见的对数最多。互相可见当且仅当存在一个$y$坐标，使得这条水平线段不和其他人相交。
题解：每次新加一条线段最多使得答案$+3$。
题意：有$n$个球，第$i$个球上有数字。选出若干球，求出它们上面数字的积。问所有方案的和的digit root。
题解：$\prod_{i=1}^{n}(1+w_i)-1 \bmod 9$，需要特判下$w_i$全零。
题意：给出$n$个点的树，有$k$个位置有人，需要找到个位置，使得这$k$个人能够同时到达这个位置。
题解：如果这$k$个位置奇偶性不同则无解；否则就是找这$k$个点的直径，两遍bfs即可。
题意：$n$个点$m$条边的有向图，在图上有两种走的方式
-
backwards：$u$能够到$v$当且仅当边$v \to u$存在 -
normally：$u$能够到$v$当且仅当边$u \to v$存在
一开始你处于backwards状态，图上有些特殊边，经过之后会改变你行走方式（backwards变成normally，normally变成backwards）。
对于每个点$i$，求出从$i$出发能到且能回到$i$的路径上能经过的点的个数。
题解：考虑这样构图，对于一条普通边$u \to v$，新建$u \to v$和$v^\prime \to u^\prime$两条边；对于特殊边$u \to v$，新建$u \to v^\prime$和$v^\prime \to u$两条边。然后求一下强连通分量。
题意：在$b \times a$的格子里，要放入$c \times d$的矩形（横竖皆可）。对于每一行$i$ (
题解：横竖方法只要交换$c$和$d$即可求出，不妨考虑$c$和$a$这条边平行。那么先把$c$压缩掉，也就是说把$l_i$都减去$c$。接下来只要求放$1 \times d$的方案数，也就是枚举$i$，求$[i,i+d)$内$x_i$的最大值和$x_i+l_i-c$的最小值，用单调队列即可。
题意：给出一个长度为$n$的字符串$s$和一个数$k$，求出另一个长度为$n$的字符串$t$，使得$s$和$t$之间最多有$k$个位置不一样，并且$t$中连续相同的字符段数最少。
题解：$dp_{i,j,c}$表示前$i$个字符，$j$个位置不同，最后一个字符是$c$的最小段数。
题意：给出两条平行的直线$a_1x+b_1y+c_1=0$和$a_2x+b_2y+c_2=0$，会把平面分成$4$部分。给出一个整点$(a,b)$，你需要找一个整点$(c,d)$使得它俩在同一个区域，且$(c,d)$和直线交点的距离最小。
题意：有个正方体，$8$个顶点分别标号为ABCDEFGH。给出一个起点和终点，问恰好走$k$条棱的方案数，对$p$取模，要求不能有两条一样的边连续出现。
题解：矩阵乘法，以边为状态，正反两个方向，总共$24$个状态。
题意：有$n$个景点，第$i$个景点的收益是$w_i$（可能为负），第$i$个景点如果去了的话，有$k_i$个景点也必须要去，其中第$j$个为$a_{i,j}$，但是你可以花费$b_{i,j}$不去这个景点。问选择拿哪些景点才能使得收益最大。
题解：构建网络流模型，如果$w_i$是正数，从$S$到$i$连一条流量为$w_i$的边，否则从$i$到$T$连一条流量为$-w_i$的边。对于其他边，正常连即可，流量为边权。求最大流，然后$S$能够到达的点就是答案。
题意：给出平面上$n$个圆心在$(x_i,y_i)$，半径为$r_i$的圆形障碍物，一个起点$(x_a,y_a)$，和$m$个终点$(x_j,y_j)$。求到每个终点的最短路。
题解：圆和圆的内外公切线，点到圆的切线，点到点的线段，圆弧，总共只有这几种边，全部构造出来求最短路即可。
题意：令$fib_0=b,fib_1=a,fib_n=fib_{n-1}fib_{n-2}$。给出字符串$s$和一个数$m$，求
-
$s$ 在$fib_m$里面出现次数，记为$t$ - 有多少字符串在$fib_m$里出现次数不小于$t$
题解：第一问可以用矩阵乘法来做，但是也可以用其他方法来解决。
考虑建出$fib_n$的后缀自动机，显然$fib_n$的后缀自动机可以由$fib_{n-1}$的扩展而来。下图是$fib_6$的后缀自动机，[*]是接收态。
_________a________ _________________a_______________
/ \ / \
0-a->[1]-b->[2]-a->[3]-a->4-b->[5]-a->6-b->7-a->[8]-a->9-b->10-a->11-a->12-b->[13]
\_____b_____/ \__________b__________/
这个后缀自动机有如下一些性质可以用来做这个题（更多的性质和证明可以参考这篇paper）：
- 每个fibonacci串交替以
ab和ba结尾，且每个fibonacci串对应了后缀自动机的一个接收态。 - 每个节点除去往相邻点有个出边外，$fib_n$的后缀自动机恰好有$\min(n-2,0)$条额外的边。
- 每条额外的边要么是从
ab结尾的fibonacci串的ab前出发，通过标号为a的边，跳到下一个ba结尾的fibonacci串的ba中间处；要么是从ba结尾的fibonacci串的ba前出发，通过标号为a的边，跳到下一个ab结尾的fibonacci串的ab中间处。 - 在这个后缀自动机上走的时候，肯定不会连续两次经过额外边。
有了以上性质，对于一个给定的串$s$，很容易就知道这个串是不是$fib_n$的子串。只需要从$fib_n$的后缀自动机中抠出$O(|s|)$那么大的一个子图即可（从矩阵乘法的做法也可以得出这个结论，暴力构建fibonacci串，当$|fib_ {n-1}|$超过$|s|$的时候就停止。这个时候如果$s$没在$fib_{n+1}$中出现，那么肯定不会再之后的fibonacci串里出现）。
至于出现次数，可以发现$s$的每个出现位置必然都是一个后缀的前缀，只要找出这些对应的后缀即可。找到$s$在后缀自动机对应的节点，从这个节点出发能够到达接受态的方案数就是出现次数，因为每条这样的路径其实对应了一个合法后缀。
方案数计算非常容易，按照fibonacci串出现位置依次往后递推即可，最后还需要一个矩阵乘法。
接下来是第二问。令$ways(x)$是从节点$x$出发能到接收态的路径数目，显然我们可以发现$ways(0) \ge ways(1) \ge \dots \ge ways(fib_n)$。也就是说，令第一问的答案为$ans$，只需要找到一个临界节点$y$使得$ways(y) \ge ans$并且$ways(y+1) < ans$即可。
可以发现，如果一个节点$x$有一条额外出边，或者$x$是个接收态，必然有$ways(x) > ways(x+1)$。于是，假设$s$在$fib_n$对应的后缀自动机上的节点为$u$，我们只需要沿着$u$找到第一个$v$使得$v$是接收态，或者$v$有一条额外出边即可。
令$f(x)$是从$0$出发能够到达$x$路径条数，$\sum\limits_{x=1}^ {v}f(x)$显然就是我们所求的答案。这个的计算也是非常容易，仅需考虑所有满足$fib_m \le v$的$f(fib_m)$和$f(fib_m-1)$即可，其他位置要么和$f(fib_m)$相同，要么和$f(fib_m-1)$相同。
题意：给出$e$，质数$p$和$k$个$n_i$。对于每个$n_i$，求是否存在一个$x$满足$x^e=n_i \bmod p$
题解：离散对数
题意：给出两个凸多边形，点数分别为$n$和$m$，求Minkowski Sum
题解：把边按照极角序排序依次接起来。
题意：有一把锁，外部和内部都有$n$个旋钮，刻度从$0$到$p-1$。外部第$i$个转动后，内部第$j$个位置会转动$c_{i,j}$，内部全部变成$0$后锁会打开。给出初始状态，求外部每个旋钮转的次数。
题解：直接高斯消元
题意：给出$n$，求有多少个01串没有连续的$1$，且首尾不同时为$1$。
题解：$f_0=2, f_1=1, f_n=f_{n-1}+f_{n-2}$
题意：给出一个$n$个点$m$条边的有向图，每条边初始边权是$c_i$，每天会减少$p_i$。给出$s$，$t$和$d$，在第$1$天到第$d$天选一条路，是的从$s$到$t$再回到$t$的最短路。保证$1$到$d$天内，边权都是正的，且不超过$10000$
题解：假设当前天是$x$，那么这一天从$s$到$t$再回到$s$的所有路径可以当做是一堆直线$y=a_ix+b_i$取最小值。这个东西其实是个上凸的分段函数，然后我们还要在这个分段函数上取个最小值，那么最小值显然只能在端点处取到，也就是第$1$天和第$d$天。
题意：有$2n+1$个格子，前$n$个放了一个黑色的棋子，后$n$个放了白色的棋子，中间的位置是空的。你可以移动一个棋子到相邻空位置或者跳过一个颜色不同的棋子到空位置。求最小步数使得黑白交换。
题意：给出$n$个边和坐标轴平行的多边形，第$i$个有$m_i$个点。问是否存在一种排列方式，使得第二个完全在第一个内部，第三个完全在第二个内部，依次类推。
题解：如果合法，那么通过每次删去一个$y$坐标最小的多边形，一定可以找到排列方式。于是按照这样招一个排列方式，然后暴力检查相邻两个是否满足条件即可。
题意：给出$n \times n$的格子，有些位置是障碍物。你需要放$n$个车，要求任意两个不在同一行或者同一列。求方案数的奇偶性。
题解：看成二分图，就是求积和式的奇偶性，等价于行列式的奇偶性。用bitset优化的高斯消元即可。
题意：有$n$个俄罗斯方块，第$i$个是高度为$1$，宽度为$l_i$，最左边位置在$p_i$。你不能旋转或者平移，但是可以改变放的顺序。求怎样才能使得最后高度最低。
题解：其实就是划分成最少的不相交区间。按照$p_i$排序，每次放到右端点不超过$p_i$且最大的区间后面。