题意：给出一个弓形，弦长是$l$，弧长是$l+d$，求弦中点和弧中点的距离。
题解：二分半径
题意：$10^4 \times 10^4$里有一个$n$个点的多边形区域，保证边都和坐标轴平行。给出两个多边形内的起点和终点，求最短路。
题解：坐标离散化，假设离散化后权值都是$1$，找到从起点到终点的一条最短路，显然，这条路径和，权值非$1$的路径是一样的。
问题变成如何判断一条线段是否在多边形内，这个就直接用射线法搞搞即可，优化优化可以$O(1)$判，总复杂度$O(n^2)$。
题意：给出一个$n$个点$d$条边的边双联通图，要求找到一个排列$x_1,x_2,\dots,x_n$满足：
$x_1=1$ - 从$1$出发，$x_i$可以
- 只用$x_2,\dots,x_{i-1}$的点到达
-
$x_1,x_n,x_{n-1},\dots,x_2$ 也要满足上面两个条件
题解：观察下可以得知这个排列$x_1,x_2,\dots,x_n$只要满足：
-
$x_1$ 和$x_n$有边相连 - 对于任意$i$ (
$2 \le i \le n - 1$ )，存在$j,k$ ($j < i < k$ )使得$x_j$和$x_i$有边相连，$x_i$和$x_k$有边相连
考虑如下构造：
- 选出${1,u}$作为初始选中的点，其中$u$是和$1$相邻的一个点
- 从$s=1$开始，如果$s$存在一个邻居没有选中，那么找一条路径$s \to v_1 \to v_2 \to \dots \to v_k \to v_{k+1}$使得$v_1,v_2,\dots,v_k$是未被选中的点，$v_{k+1} \ne s$且$v_{k+1}$是一个被选中的点。然后$v_1 \to v_2 \to \dots \to v_{k}$插到$s$后面去
- 如果不存在这样的邻居，则把$s$后移，指向下一个选中的点
显然这样构造出来的排列是满足条件的。
题意：有$n$个杯子，容量为$o_i$，一开始都装满了水，你可以：1. 从一个杯子把水全部倒到另一个杯子，前提是第二个杯子有足够的容量；2. 用另一个杯子的水把一个杯子装满；3. 把杯子里的水倒掉
给出一个最终状态，求最少操作步数
题解：bfs
题意：给出$5$个数，用最小次数排序
题解：假设$5$个数分别编号$a,b,c,d,e$.
-
$a$ vs$b$ ,$c$ vs$d$ ，$2$次，假设$a>b$，$c>d$ -
$a$ vs$c$ ，$1$次，假设$a>c$，则$a>c>d$
把$e$插入$a,c,d$中，需要$2$次，结果有4种：
-
$e>a>c>d$ ，则把$b$插入$c,d$中，需$2$次 -
$a>e>c>d$ ，则把$b$插入$e,c,d$中，需$2$次 -
$a>c>e>d$ ，则把$b$插入$c,e,d$中，需$2$次 -
$a>c>d>e$ ，则把$b$插入$c,d,e$中，需$2$次
只要$7$次就够了
题意：给出$n \times n$的棋盘，你要在上面放$n$个车，已知第$i$个车一定要放在矩形$(a_i,b_i)-(c_i, d_i)$里面，并且同一行或者同一列不能有多余一个车。求一个方案。
题解：显然$x$坐标和$y$坐标可以分开考虑，那么显然就变成了一个convex bipartite graph的最大匹配问题。考虑$i$从$1$枚举到$n$，考虑那些可以放在$i$的车，取一个右端点最小的即可。
题意：令$fib_1=b, fib_2=a, fib_{k+2}=fib_{k+1}+fib_{k}$，给出一个字符串$s$，求$fib_n$中出现的次数。
题解：$n \le 11$的时候，直接暴力计算即可。之后考虑$s$出现次数一定来自于$f_{n-1}$，$f_{n-2}$以及中间新加部分。稍加讨论下即可。
题意：有$n$个生成器$G_1,G_2,\dots,G_n$，$G_i$可以生成$S_i \subseteq {1,2,\dots,n}$或者$0$（代表游戏结束）。$G_i$每次生成的数必须和上一次的不一样，否则就生成$0$。
从$G_1$开始生成数，如果生成的数是$r$，那么下次由$G_r$开始生成数。如果$G_n$生成了$0$，并且其他生成器用尽了$S_i$，那么就输了。
求一个生成序列，使得最后生成了$0$，但是不输。
题解：显然可以构造一个有向图出来，目的是构造一个从$1$出发的路径，标记经过的每一条边，假设终点是$s$，要求$s$的每条出边都被标记过了；如果$s=n$，还要求全图至少存在一条边没有被标记过。
如果存在从$1$到$n$的欧拉路径，那么显然我们只要在图中删掉一个圈就可以得到所求路径。如果不存在，直接乱走即可。
题意：给出$n$，构造$n$的一个排列，使得没有长度为$3$的等差子序列。
题解：分奇偶，递归构造
题意：有$n$个间谍，有$r$个监视关系$(a,b)$，如果$a$监视$b$，那么逮捕$a$后，$b$也能被逮捕。现在有$p$个间谍可以被收买，问最少的代价，逮捕所有间谍。
题解：先求强连通分量，然后只要挑入度为$0$的点里某个间谍收买即可。
题意：有$n$个盒子围成一个环，第$i$个盒子里有$a_i$块石头，每次可以移动一块石头到相邻位置。求最小步数，使得每个盒子里最多只有一块石头。
题解：费用流模型很明显，优化下建边，然后上原始对偶就过了。
题意：给出$3 \times n$的格子，要在上面放“骑士”，其中每一列最多有一个位置不可放。求最多能放多少互不攻击的“骑士”，以及方案数。
题解：$dp(i,j,k)$表示前$i$列，上一列放置状态是$j$，当前列放置状态是$k$的最值以及方案数。
题意：有两个字符串$x$和$y$，然后另有一个字符串集合${s_1,s_2,\dots,s_k}$，现在可以任意往$x$和$y$后面append字符串，使得最后它们相等，求最小append次数。
题解：观察一下可以知道，显然之后长串和短串的长度差，以及长串最后append的是谁比较重要。令$dp(i,j)$表示长串最后append的是$i$，还有长度$j$的后缀没有匹配的最小操作次数。枚举一个串，往短串后面接即可。注意短串可能会转变成长串。