title:题目
网络流
luogu4249 [WC2007]剪刀石头布
S - (1,0) - 边 - (1,0) - 点 - (1,0)/(1,1)/…/(1,n-1) - T
跑10000的费用流，数据较水能过
luogu3973 [TJOI2015]线性代数
每个数取0/1，建图如图
bzoj3894 文理分科
图
bzoj3232 圈地游戏
1.二分+spfa判负环
2.二分+[线性代数]建图，要解方程
bzoj2229 [Zjoi2011]最小割
gomory hu tree O(n*flow) 最小割树
建树有两种
1.任选s,t跑最小割，然后分治（递归）
2.1下面连2到n，从2到n，s=fa[x],t=x跑网络流，每次将和x相连的点的fa指向x
【BZOJ2085】[Poi2010]Hamsters hash+倍增floyd
bzoj2795 [Poi2012]A Horrible Poem
判断一个字符串的循环节：
枚举len（len整除|s|)
然后判断前|s|-len和后|s|-len个的hash值是否相同
对每个询问，不断除以长度的质因数并判断
总复杂度是O(n+qlogn)
先线性筛求出每个数的最小质因数，然后可以在O(总因数个数)内求出1到n的因数个数
[BZOJ 4416][Shoi2013]阶乘字符串
序列自动机就是dp（next）。。记录next[i][26]，O(26n)的预处理，从n到1，每次a[26]记录最后出现的位置，然后复制给next就可以了（next是dag）
状压加手算优化（大于21就无解我也不会证）
hihocoder1412 : Rikka with Subsequence
不考虑删除，建出next，问题等价于dag中以起点开始的不同路径的个数，dp即可
考虑删除
方程变成：
$c[ch]=\sum{j<i}$$(f[j]*\prod{(j<k<i\bigcup a[k]=ch)}a_k)$ c[ch]表示到i位置前面的f对第i位字符为ch的贡献
$f[i]=c[s[i]]*(1-ai)$ f[i]表示第i位对答案的贡献
（大概是这样请手推）
[NOI2015]品酒大会
codeforces 452E 和品酒大会差不多
bzoj4516 [Sdoi2016]生成魔咒
不同子串的个数为n(n+1)/2-sum(height)
[AHOI2014/JSOI2014]骑士游戏
最短路就是某种意义上的dp（无负边），每次用最小值更新
这题也是每次用每个点的最小值更新其他点，一开始将所有点的魔法值入堆
[AHOI2014/JSOI2014]支线剧情
上下界网络流
[AHOI2014/JSOI2014]奇怪的计算器
先二分出全变成l和r的地方
中间的在线段树上做，加、乘、at三个标记
[AHOI2014/JSOI2014]拼图
先枚举底在第i行，再枚举高度为j，最后每一列扫一遍
复杂度$O(nmmin(m,n))$
[Jsoi2014]病毒分类
trie树上搞出每个串属于的两个集合
每个串变成边
求最小点覆盖
题目：区间有每个数的出现次数限制，求数的最小次数
差分约束
[Jsoi2014]支线剧情2
[Jsoi2014]打兔子
观察发现发枪顺序没有影响，且不会发相邻的枪
dp[i][j][0/1]表示到i打j枪且i处是否发枪
多dp几遍，考虑第1个位置和第2个位置放不放
2118: 墨墨的等式
套路dp
考虑B%ai的值,0~ai-1
对每个余数i进行dp，求出最小的余数为i的B
f[i]=min(f[j]+ak|(j+ak%ai)%ai==i)
dp的顺序不知道
变成最短路即可
建图的复杂度是O(na)
跑spfa或者dijk的复杂度是O(能过)
显然用ai最小的值作除数
4082: [Wf2014]Surveillance
去掉包含的区间：
先排序，R[i]=max(R[i-1],end[i])表示左端点在i及左边，右端点的最远值，则对于区间[l,r]，只要判断R[l]和r的关系即可
先变成链（翻两倍），去掉包含的区间 O(nlogn)
在环上预处理后继的区间 O(nlogn)
再变成链倍增求出f[i][j]表示从第i个区间/第i个位置走j步到达的最远距离
然后每个区间的首位置再判一遍
2303: [Apio2011]方格染色
注意到第一行和第一列确定后可以确定整个图
图中每个点(i,j)可以列出异或方程：
a11^a1j^ai1^aij=[i,j都是偶数]
aij和a11都可以去掉
然后并查集
3150: [Ctsc2013]猴子
先考虑n=10
一个状态可以变成好多状态啊
列方程吧
f(s)表示s状态的胜率
结论：
f(s)∩f(t)=∅，f(s)+f(t)=f(s+t)
证明:s=s1+s2,f(s1)+f(s2)+f(t)=1,f(s)+f(t)=1 => f(s)=f(s1)+f(s2)
所以处理所有只有一个1的状态就可以了
4237: 稻草人
分治加平衡树
O(nlognlogn)
hdu5800 To My Girlfriend
f[i][j][f1][f2]
表示到第i个和为j已经’钦定’的选的个数为f1，’钦定’不选的为f2
多区间问题，每个区间有要求，如：
2018 计蒜之道 初赛 第四场 贝壳找房搜房
[USACO13OPEN]照片Photo
18-7-1
b. sigma(g[i](n-i)-g[i+1](n-i-1)*(i+1))
f.区间排序的套路：二分，使序列变成0/1
18-7-4
d.套路分块 f[i][x]表示从i到第x块结束的答案 f[x][i]表示从第x块开始到i的答案
O(nsqrtnlogn)
a.f[i][j][x]表示i到j最终变成字符x，转移是枚举i,j,分界点k,和变化规则，O(n^4)
g[i][j]表示第一个到i，第二个到j，的最短长度，转移再枚举p,q,O(n^4)
b.预处理撞到每个红灯的时间区间，从后往前做，在线段树上覆盖（动态开点），然后求出每个红灯到终点的答案（相当于求一辆车到的下一个红灯）
c.和最大的情况下x1最小，等价于x2最大，所以重新定义优先级后，再求线性基，线性基中的所有数都给x2，其他给x1
e.建图小技巧：要连nm条边的时候，考虑每个ai加辅助点ci，排序，每个点向自己的辅助点连wi，辅助点向自己连0，ci向ci+1连差，ci+1向ci连0，这样只有O(n)条边，在起点前加一个0点，重点后加两个0点（因为在新图上走一步就是走两条边）最终答案为最后两个0点中的较小值
约瑟夫问题
1)n个人，顺着杀和倒着杀k个人
顺着杀：
m=1(mod n)
m=1(mod n-1)
.
.
.
m=1(mod n-k+1)
倒着杀：
m=0(mod n)
m=0(mod n-1)
.
.
.
m=0(mod n-k+1)
2)n个人，要求让第k个人活下来，求m
若n为质数：
m=k-1(mod n)
m=0(mod 1)
m=0(mod 2)
.
.
.
m=0(mod n-1)
或者
m=k+1(mod n)
m=1(mod 1)
m=1(mod 2)
.
.
.
m=1(mod n-1)
若n为不是质数：
伯特兰—切比雪夫定理说明：若整数n > 3，则至少存在一个质数p，符合n < p < 2n − 2。另一个稍弱说法是：对于所有大于1的整数n，存在一个质数p，符合n < p < 2n。
不妨设k>n/2
m=1(mod lcm(1,2,…,n)/p)
m=k+1-n(mod p)
18-7-6
a.欧拉函数可以不管指数！用LL记录60个质数是否出现过，复杂度少一个60
b.f(S)表示集合S中连通块的个数（S包含1），$f(S)=\prod (C{ij}+1)-f(S’)*(C{i’j’}+1)$(S’属于S,i’,j’属于S/S’)
d.1e12以内因数最多的数大概有6000个因数，f[i][x]={a,b}表示前i个数选了a个，总和为b，且与k的最大公因数为x，f[i][x] - a[i+1] -> f[i+1][gcd(x*a[i+1],k)] 答案为f[n][k]，记录每个f从哪个状态转移过来的，倒推可以求出序列
f.n(n>=3)可以，则n+2可以。n=3，6可以，n=4不可以
e.线段树，维护加标记和相同标记和颜色标记(如果相同标记=1)，对于区间修改，若该区间相同标记=1,直接改，否则递归下去处理。复杂度等于添加标记的次数为O(nlogn)
18-7-8
a.用hash可以去一个log
b.基尔霍夫矩阵去一行一列的行列式的值等于选n-1条边构成树，每条边权的乘积的和。最傻的做法会发现没有考虑其他边被删掉的情况，所以先把所有边都删掉，再在矩阵中补上
$ans=\prod(1-p{ij})*|p{ij}/(1-p_{ij})|$
c.二维线段树可以改成一维线段树，按r建线段树，叶子节点开vector记录所有l，非叶子记录子树中l的最大值，删除的话就暴力删，反正只有m个区间
d.按dfs序排序，值等于相邻点的距离加起来/2
e.记录每个点向前最远到那+倍增
f.卡空间。两种做法：1.分块，每sqrt(n)行记录一次dp值，求路径的话就再用O(sqrt(n))的空间暴力求
2.分治，对于行(l,r)，找出中间行的最优位置，每次面积/2
18-7-10
a.多项式
c.谁想写谁写。。f[i][sta][s]表示到第i个数的，前i个数的集合为s，单调栈中的集合为sta，O(n)转移
d.n^2构造，对一个连通块，yes <=> sigma(ai)=sigma(bi)，dfs到叶子，以叶子为根再dfs，能流就流
e.dp优化网络流，0代表与s相连，1代表与t相连，1的前面有0的话就要有一个c的贡献，dp[i][j]表示前i个点中有j个1，O(1)转移
18-7-11
e.和[文理分科]很想，一只狗可以选择公的或者母的，一个人希望某些狗是公的或者母的。最小割，狗向s,t连边，人向他希望的那些狗连边。联系最小割的含义建图。
f.n=3,4无解，n>4，第一条边长1000，以后每条边减0.1，最后两条边直接算，有相等的概率很小。。
d.f[i][j][k]表示前i个人中，有j组未闭合，代价和为k。
1到n每个位置上有一盏灯，点亮i要w[i]的代价，每个位置会被自己及左右照亮，要求每个位置都亮的最小代价。
dp[i][0/1/2]表示到i，0：i点亮了，1：i没点亮i-1点亮了，2：i没点亮i-1没点亮
复杂度O(n)
加强：可以交换k（k<=9)对位置的代价，求最小代价
f[i][j][k][0/1/2]表示到i，前面有j个已经钦点了（可以是负数），已经换了k对，0/1/2同上
其实就是已经选了某些位置的集合不好表示，用背包来做
复杂度O(nk^2)