格点 $(x_1,y_1)$ 是否能走到 $(x_2,y_2)$ ，模 $2$ 是否相等。
给一个序列 $a_i$，求多少对 $(i,j,k)$ 使得 $a_i \cdot a_j \cdot a_k$ 最小。
排序之后特判 $a_0=a_1=a_2$和 $a_1=a_2$，组合数数一下。
求有多小于等于 $n$ 的数，其值和各位数和之差大于等于已知常数 $s$ 。
首先注意到，如果 $n$ 满足以上性质，若其个位数改为其本身一直到 9，差值不变，若发生进位，差值不增，所以 $\forall x \ge n$ 也满足上性质，因此可以二分。
定义一个序列的最大值最小值之差，求一个序列的所有连续子序列的差值之和。
可以分开计算最大值和最小值，通过类似单调队列的数据结构维护出一个位置左右能够掌管的长度即可。
时间复杂度：$O(n)$。
传送门：http://codeforces.com/gym/101933/problem/E
奥术飞弹！
自己和对方场地分别有 $n,m$ 只随从（$1 \le n,m \le 5$），已知每个随从的血量（$1 \le hp \le 6$）。
求 $d$ 个奥术飞弹将对面场地清空的概率。
概率状压 $dp$ 。
显然要状压 $dp$ 一下，但是状态数有 $7^{10}$ 好像不大可做？
但是注意到有类似于 $2,1,4$ 和 $2,4,1$ 之类的重复状态，因此对于所有状态压成一个字典序最小的 5 位数。
跑一下 dp 转移即可。
传送门：http://codeforces.com/gym/101933/problem/A
井底之蛙想要跳出井底，已知井的深度 $d$。
给出 $n$ 个三元组 $(l_i,w_i,h_i)$ ，表示一只青蛙的跳跃高度，重量和高度。
每次青蛙可以一层一层叠成一个塔，那么最顶层的青蛙跳跃高度为 $ {l}_{i} + \sum h$，其中塔必须满足每层的青蛙重量必须大于上面所有青蛙的重量之和。每次叠成塔送顶层跳出去之后，可以立马重新堆一个新的塔送顶层青蛙跳出去。
问最多能送多少只青蛙出去。
可以感觉到限制青蛙能否堆在一起跳出去的条件是重量限制。
先对三元组按照重量排序，倒着做，重量越大肯定越往后跳出去，最重的那个肯定最后一个跳出去。
然后处理倒数第二重的那个，他肯定至多倒数第二个跳出去，此时只剩最重的那个作为跳板跳出去，因此可以得出 $dp$ 状态。
令 $dp[i]$ 表示可以在放一个 $重量 < i$ 的青蛙在上面时，塔的最大高度。
转移方程：$dp[j]=max(dp[j+1],dp[j],dp[j+w_i]+h_i)$ ，其中 $1 \le j \le w_i$。
转移时更新答案，当且仅当 $dp[w_i+1] + l_i > d$ 。
边界条件：$dp[j]=h_0$，其中 $1 \le j \le w_0$。
这样时间复杂度显然是 $O(n \log n + n \max(w))$ ，好像不大可做啊？但是注意到题面 $\sum w \le 10^8$ ，那么实际上时间复杂度是 $O(n \log n + \sum w)$。
1 | const int maxn = 5000 + 5; |
1 | struct MCMF { |
显然如果要把序列弄成 $1,2,3, \dots, n$ 的操作数就是逆序对的数量。
然后我们可以 $O(1)$ 将原答案转移为 $n,1,2,3,\dots,n-1$ ，即其余数操作不变，将最后一个数放到最后的操作数改成放到第一个。
时间复杂度：$O(n \log n+n)$ 。
1 | const double delta = 0.998; |
1 | namespace SA { |
1 | char s[maxn], p[maxn]; |
1 | void getfail(int len, char* s, int fail[]) { |
1 | char s[maxn], t[maxn]; |