1.Codeforces Round #418 E (dp+组合数学)：
https://loj.ac/problem/6094
http://codeforces.com/contest/814/problem/E
虽然题目是一样的，但是时限不一样，cf的时限大1s，所以在cf上这题
O
(
n
5
)
可以过，但是loj就不行了，
codeforces：
把图按照最短路分层，那么这个图需要满足每个点都向上一层有且只有一条边，并且没有更向上的边。
我们用
d
p
[
u
]
[
i
]
[
j
]
[
k
]
[
l
]
表示前
u
个节点，上一层有
i
个读数为
1
的插头和
j
个度数为
2
的插头，
这一层有
k
个度数为
1
的插头和
l
个度数为
2
的插头。注意我们甚至并不需要关心最短路到底是多少。
大力讨论一下转移就可以了。当前点先和上一层的一个点连接，剩下的度数可以留下，也可以和这一层的随便连。
http://blog.csdn.net/sdfzyhx/article/details/73003862
loj:
O(n^3),参考一下cf上的KAN的做法。很神奇。
http://codeforces.com/blog/entry/52449
.
2.二分图染色。(组合数学，递推公式)
https://loj.ac/problem/6160
这题是美团初赛的题，在一个完全二分图上将边进行染色的问题，红色不共享端点，蓝色不共享端点，绿色随意染。
可以转化为棋盘模型，即 N×N 棋盘上放黑白棋子，每个格子至多放一个，同行同列没有相同颜色的棋子。
令
b
n
为只有一种颜色，那么，
b
n
=
∑
n
i
=
0
C
i
n
∗
A
i
n
。
然后我们考虑容斥掉两个颜色在同一格，如果一个格子既放黑又放白，那么这一列和这一行不会有其他棋子，直接删掉。
a
n
=
∑
n
i
=
0
(
−
1
)
i
∗
C
i
n
∗
A
i
n
∗
(
b
n
−
i
)
2
。
b
n
=
2
∗
n
∗
b
n
−
1
−
(
n
−
1
)
2
∗
b
n
−
2
，可以花点时间想想左边这个公式。
第一项是在第 n 行或者第 n 列上放一枚棋子或者不放的方案数，由于放两枚棋子的情况会
被统计两次，最后还需减去摆两枚棋子的方案数，即第三项。
http://blog.csdn.net/u014609452/article/details/73744264
3.「美团 CodeM 初赛 Round A」倒水 （二分）
二分温度，返回总共使用的体积。
这道题要注意一下精度。有的人用了long double,其实double也是可以的，分类二分温度一下。
当全部t_i相同时，什么操作都不需要，直接输出。
当T>max{t_i},就for 200-300次二分，有可能升温，也有可能降温。
当T< min{t_i},就只能降温了，直接算能不能把其他杯水是否能降到当前min{t_i}，否则就Impossible。
4.「美团 CodeM 初赛 Round A」合并回文子串 （区间dp）
注意：a,b子串中的字母是相对不变的。
考虑c中的回文子串，既然是子串，就一定可以拆成 a, b 两串的两个子串的组合。
不妨 设是 a[i, j]与 b[k, l]的组合，则可以考虑动态规划的状态
d
p
[
i
]
[
j
]
[
k
]
[
l
]
表示
a[i, j]与 b[k, l]的组合能否组成回文子串。 新组合的串的串头一定是S1和S2串头中的一个，
串尾一定是S1和S2串尾中的一个，则可以匹配第一个字符和最后一个字符来转移，
根据第一个字符和最后一个字符分别来自 a 还是 b 共有四种转移:
(注意分别l和1)（L和一）
d
p
[
i
]
[
j
]
[
k
]
[
l
]
<
−
−
d
p
[
i
+
1
]
[
j
−
1
]
[
k
]
[
l
]
(
i
<
j
,
a
[
i
]
=
a
[
j
]
)
d
p
[
i
]
[
j
]
[
k
]
[
l
]
<
−
−
d
p
[
i
+
1
]
[
j
]
[
k
]
[
l
−
1
]
(
i
<
=
j
,
k
<
=
l
,
a
[
i
]
=
b
[
l
]
)
d
p
[
i
]
[
j
]
[
k
]
[
l
]
<
−
−
d
p
[
i
]
[
j
−
1
]
[
k
+
1
]
[
l
]
(
i
<
=
j
,
k
<
=
l
,
b
[
k
]
=
a
[
j
]
)
d
p
[
i
]
[
j
]
[
k
]
[
l
]
<
−
−
d
p
[
i
]
[
j
]
[
k
+
1
]
l
−
1
]
(
k
<
l
,
b
[
k
]
=
b
[
l
]
)
5.「美团 CodeM 初赛 Round B」模（数学题。证明题。）
如果没有进位，则数字和为S(a)*n，一次进位对数字和的贡献和是1-k，而数位和需要在模b下与c相等，
根据模方程的扩展欧几里得解法，可以发现方程有解的必要条件是
g
c
d
(
a
,
k
−
1
,
b
)
|
c
。然后我们要证明
这个条件是充分条件。
证明可以通过构造完成，对于任何a,一定【存在】其某个倍数p最低非零位的前一位不为 9，
设此时最低非零位为 t,则一定存在其倍数 q 使得最高位为 k - t，设 q 在 k 进制下有 r 位，
考虑构造如下两个数：
u
=
p
∗
k
r
+
q
v
=
p
∗
k
(
r
−
1
)
+
q
可以发现u,v贡献的a数量相同,而进位数恰好 v 比 u 多 1。
在模 b 意义下，构造
x
∗
a
+
y
∗
(
1
−
k
)
。
由于an可以任意大，我们在无限位中分散地摆放 x 个 a(可能有一些进位)，再摆放一共
b 个 u 或 v ，其对 a 的数目没有贡献，但可以把进位数变成 [0,b-1]的任意值 即 y。
既然任意
x
∗
a
+
y
∗
(
1
−
k
)
可以被构造出来，
所以在b剩余系下有且仅有
g
c
d
(
a
,
k
−
1
,
b
)
|
c
的倍数可以被构造出来。
6.LOJ #6165. 一道水题（线性筛）
先用线性筛筛出[1,n]的所有素数，记为p[i]。
答案是对每个
p
[
i
]
，求出最大的
p
[
i
]
k
，满足
p
[
i
]
k
<
=
n
。把所有这些
p
[
i
]
k
乘起来就是答案。
注意：模是1e8+7。
7.「美团 CodeM 初赛 Round B」送外卖2 （状压dp）
三进制状压DP。
d
p
[
i
]
[
j
]
表示三进制状态为 i，最终走到 j 点的最小时间花费。
那么状态对应一个位置是0表示没有取餐，是1表示取了餐没有送，2表示送到了，
然后分析每一位上是0还是1进行状态转移，转移之前要预处理一下最短路，
这个点比较少直接Floyd预处理一下即可。
8.ACdream 1113 （概率dp）
http://acdream.info/problem?pid=1113
设dp[i]表示从i丢到n才达到目标和的期望的次数。
dp[n]肯定等于0，那么就从最后往前推。
不难想到掷到123456的期望都是6.00。
dp[i] += dp[i+j]。
dp[i]+ = 6 ==> dp[i]/=(6 - tot) (tot表示当前掷到的数和之前掷到的书的和大于n的次数)
最终答案就是dp[0]。
9.ACdream 1124 喵喵的遗憾（Fib数模n的循环节）
http://acdream.info/problem?pid=1124
输入 N 和 P ，输出
F
i
b
[
F
i
b
[
F
i
b
[
n
]
]
]
%
P
。
找循环节。
对于一个正整数n，我们求Fib数模n的循环节的长度的方法如下：
（1）把n素因子分解，即
n
=
p
a
1
1
∗
p
a
2
2
∗
p
a
3
3
∗
∗
∗
∗
p
a
k
k
（2）分别计算Fib数模每个的循环节长度，假设长度分别是
x
1
,
x
2
.
.
.
.
.
x
k
.
（3）那么Fib模n的循环节长度
L
=
l
c
m
(
x
1
,
x
2
,
.
.
.
.
.
,
x
k
)
从上面三个步骤看来，貌似最困难的是第二步，那么我们如何求Fib模
p
m
的循环节长度呢？
这里有一个优美的定理：Fib数模
p
m
的最小循环节长度等于
G
(
p
)
∗
p
(
m
−
1
)
，其中G(p)表示Fib数模素数p的最小循环节长度。
可以看出我们现在最重要的就是求G(p).
对于求G(p)我们利用如下定理：
如果5是模p的二次剩余，那么循环节的的长度是p-1的因子，否则，循环节的长度是
2
(
p
+
1
)
的因子。
顺便说一句，对于小于等于5的素数，我们直接特殊判断，
l
o
o
p
(
2
)
=
3
,
l
o
o
p
(
3
)
=
8
,
l
o
o
p
(
5
)
=
20
。
那么我们可以先求出所有的因子，然后用矩阵快速幂来一个一个判断，这样时间复杂度不会很大。
注意：需要注意的是P可能为1，因此n==0或者1的时候，特判要输出1%P而不是1.
10.HDU 2993 （斜率优化）
链接：
http://acm.hdu.edu.cn/showproblem.php?pid=2993
题意i：给你一个长度为 n 的序列，找出长度 >= k 的平均值最大的连续子序列。输出其平均值。
题解：斜率优化+fread。数据后期加强了。不加fread不能过。
复杂度：O(n)。
斜率优化的例题。
先求出前缀和数组sum[]，然后问题转化成给出n+1个点求出两点横坐标差>= k的点对所能构成的最大斜率。
然后朴素的想法是对于每一个可能的序列末端点 i，去寻找集合 [1,j]（i-j+1 >= k）中与它能构成的最大斜率，不断更新最大值。复杂度 O(n^2)。
然后斜率优化的思想，是对于不断增长的集合[1,j] 维护一个下凸曲线，每次找出曲线中的切线即为当前最优值。
找切线的时候，根据下凸曲线中切点斜率递增的性质，可以删除已经找到的切点之前的点。复杂度为 O(n)。
数据被加强过，必须加fread才能AC。
11.HDU 1500（dp）
链接：
http://acm.hdu.edu.cn/showproblem.php?pid=1500
题解：
从大到小排序，保证k对筷子都有一支最大的条件 。
d
p
[
i
]
[
j
]
表示前 j 支筷子取 i 对筷子的最小 badness，不考虑第三根筷子 。
d
p
[
i
]
[
j
]
=
m
i
n
(
d
p
[
i
]
[
j
−
1
]
,
d
p
[
i
−
1
]
[
j
−
2
]
+
(
L
[
j
−
1
]
−
L
[
j
]
)
∗
(
L
[
j
−
1
]
−
L
[
j
]
)
)
;（L为筷子的长度）
12.HDU 1511（dp+思维）
链接：
http://acm.hdu.edu.cn/showproblem.php?pid=1511
题解：
先从前往后dp，
d
p
[
i
]
表示包括第i位往前，满足题目要求能得到的最小长度。
这样就可以求出，最后一个最小的满足的数了。
求出最后一个最小的数后，从后往前dp,dp[i]表示从第i位开始往后，在满足题目要求的情况下，能得到的最大长度。
这样就可以求出，按顺序依次最大的。
简而言之：
①从前往后DP，找出最后一个数的最小值，即最后一个数尽可能的小；
②从后往前DP，找出最前面一个数的最大值，即第一个数尽可能的大。
14.Codeforces Alpha Round #21 D（状压dp）
链接：
http://codeforces.com/contest/21/problem/D
题意：给一个无向图，要求从1出发回到1，但是必须经过图中每一条边，并且至少经过一次。注意：这不是欧拉回路。
/
*********************************************************************
/
判断欧拉路是否存在的方法：
有向图：图连通，有一个顶点出度大入度1，有一个顶点入度大出度1，其余都是出度=入度。
无向图：图连通，只有两个顶点是奇数度，其余都是偶数度的。
判断欧拉回路是否存在的方法：
有向图：图连通，所有的顶点出度=入度。
无向图：图连通，所有顶点都是偶数度。
/
*********************************************************************
/
题解：状压DP。
度数为偶数的点不需要被考虑，只需要考虑度数为奇数的情况。首先每条边必须要访问一次，所以，所有边权加起来就是答案的初值。
然后度数为奇数的点就需要访问之前已经走过的边。我们考虑两个度数为奇数的点可以组合一下，就变成了度数为偶数的点，
相当于是在这两个点之间新连了一条边，我们可以floyd预处理一下两点之间的最短路。
然后状压dp，状态表示当前哪些结点的度数为奇数，然后枚举每次连哪两条边就可以了。
now = i^(1<<(j-1))^(1<<(k-1));
dp[now] = min(dp[now],dp[i]+ w[j][k]);//取或不取 j 和 k 两条边
15.Codeforces Beta Round #14 (Div.2) D （树形dp）
链接：
http://codeforces.com/contest/14/problem/D
题意：
给定一个无向图，含有一定的路。从中找出两个最长的路径（每条路径有一些相通路组成）。
这两个路径不能经过公共的点，求什么时候两条路径的乘积最大。
题解：
把一个图沿一条边割开，分成两个树，求这两个数中最长的路的乘积。
这里需要分别求两个树的直径。
因为题目数据不大，直接枚举边即可。(n^2)
DFS从当前点开始搜索，把枚举的那条边先当作删掉，DFS当前点存在的最大深度和次大深度。
两个相加不断更新最值，便可得到其中一边树的直径。
同样再DFS一次就可以得到另外一边树的直径。
最后相乘即可。
复杂度就是：
O
(
n
2
)
.
16.Codeforces Beta Round #14 (Div.2) E （dp）
链接：
http://codeforces.com/contest/14/problem/E
题意：
画骆驼峰，给你n步，要你求可以画t个骆驼峰的方案数。
要求骆驼峰的高度不能超过4。
(3≤n≤20, 1≤t≤10).
题解：
四维dp。
d
p
[
n
]
[
t
]
[
j
]
[
s
]
。
n代表点数（步长），t代表尖峰数，j代表高度，s代表上升（1）还是下降（0）的方案数。
初始化第一步，第一个尖峰，高度为j的是一个上升峰。
因为初始值看成了一个上升峰，那么步数为2时会出现下降峰。比如21，32这些。但是这些不合法。
所以要把步数为2时的置0就可以了。
转移方程：
一.更新上升峰（1：上升峰再加一个上升，2：下降峰加一个上升）
d
p
[
n
]
[
t
]
[
i
]
[
1
]
+
=
(
d
p
[
n
−
1
]
[
t
]
[
j
]
[
1
]
+
d
p
[
n
−
1
]
[
t
−
1
]
[
j
]
[
0
]
)
;
二.更新下降峰（1:下降峰再加一个下降，2：上升峰加一个上升）
d
p
[
n
]
[
t
]
[
i
]
[
0
]
+
=
(
d
p
[
n
−
1
]
[
t
]
[
j
]
[
0
]
+
d
p
[
n
−
1
]
[
t
]
[
j
]
[
1
]
)
;
复杂度：
O
(
n
3
)
.