备忘录

训哥增栈大法之乾坤大挪移：
        char * p = (char *) malloc(size) + size;
        __asm("movl %0,%%esp\n" :: "r"(p));

2010.4.9

pku3714  
	求出两个点集之间的最小距离，可以借用最近点对的方法分治，把所有点先按x轴排序，然后分治做，
	用另外的一个数组，通过利用递归分治的特点进行并归排序，按y排序，然后把这个数组的点按所属
	点集分成两边，于是这两边的y都是有顺序的，然后对一边进行枚举，另外一边选择y位置和它前后相差14个
	左右的点进行比较找最小的就可以了。
	
2010.4.15

pku2677 双调路径dp
	给一个点集，从最左走两条互不相交的路线到最右点，求最小路径长度和。
	f[i][j]（i<j）,表示从0到i和0到j这两条互不相交的路径的最短长度和，
	当i!=j-1时：f[i][j]=min{f[k][j-1]+dis(p[k],p[j])} 
	否则：f[i][j]=f[i][j-1]+dis(p[j-1],p[j])
	最后别忘了加上最后封口的那段距离。


2010.4.16

pku2431 贪心+堆
	n个加油站，油箱无限，最少加油次数使得到达目的地。
	对位置排序，从前往后一直走，直到没有油了就从之前的油站中选择最多的那个加上去。
	
pku2437 区间贪心
	n个区间，用长为l的木板覆盖所有区间，求最少木板。
	先按区间左边从小到大排，合并区间,然后从左向右能铺就铺。
	
pku1716 区间贪心
	n个区间，找到一个最小的集合s,使得对于每一个区间，集合中至少有两个元素在这个区间中。
	按照区间右边界从小到大排序，然后贪心的思想就是，在当前区间中，能往后放就往后放，这样后面的区间能和前面共享元素的几率会更大（在不改变当前集合元素个数情况下，选择最有利于子问题解的选择。）
	
PKU2287 DP
	田忌赛马。 
	详见2006集训队黄劲松的论文
	

2010.4.17

pku1984 并查集
	给出坐标点的相对位置，设计在线算法，回答任意点之间的曼哈顿距离。
	可以用并查集做，专门设计一个RELA的关系结构，自动实现加减，表示两点之间的相对位置(写起来方便)，然后路径压缩的时候通过加加减减来求出当前节点和代表点的关系即可。
	
pku1985 树的最长路，dp
	f[i][0],f[i][1]分别表示以i为根的最长，次长路（必须经过i），然后第一次dfs求出所有儿子的f[x]的值，第二次dfs就考虑连同i的祖先，经过i的路径的最长长度。这里需要注意最长次长是否来自同一个儿子的问题。
	
2010.4.18

sicily 1859 turan图
	给出n个点，加最多的边，使得不存在k阶完全子图。把n平摊分成k-1份，然后任意两分之间任意连边，这个边数可以证明是最多的。

sicily 1856 线段树
	给出一棵树，然后q个询问，每个询问给出一条边，问原树去掉这条边后分成的两个子树各自最大最小点值的积的和。
	把树进行先序遍历，然后在线段树中动态查找一棵子树的最大最小值，并且在先序序列中找出除这棵子树以外的地方的最大最小值便可。
	

2010.4.22

pku2110 二分+枚举下界+搜索判断
	给出一个带权矩阵，从（1，1）走到（n，n），求出所有路径中点的权值的最大权减最小权最小的值。
	二分这个差值，然后就可以枚举一个下界，就知道上界，从而可以用dfs直接去遍历一次来看是否可行。枚举下界的作用在于使得从起点到某一个点是否可能不依赖于具体的路径，而只要符合上下界就可以了，否则的话就要遍历所有的路径来判断是否可行，这样的话就会相当慢。
	还有需要注意的是，dfs的时候记得要考虑起点和终点是否在界内。
	
pku3340 数位统计
	水题，不说了。。。

2010.4.23

pku2303 dfs搜索
	给出2n个玩具，分成2份，每份中都可以不断的套在一起。
	搜索的一个优化思想在于，按照高度递减来做，然后搜一个的时候，顺便判断另外一个是否合法，这样速度就相当地快了。。。
	
2010.4.28

pku2157 2次dfs
	在迷宫中找钥匙，然后开门，看是否可能达到目标。
	2次dfs，第一次找钥匙，第二次开门，如果第二次都没有新的门可以开，那么就无解。

2010.4.30
 
pku3633 bfs
	一个填充字符串的搜索题目，可以先预处理IN_S[i][j]表示t字符串的i到j是否可以由s复制所得，IN_T[i][j][k][l]表示t的k到l是否能由t的i到j复制所得，这样作判断的时候就相当的方便了。
	然后就是位运算的bfs，0表示还没被填充，1表示已经填充，然后枚举空区间[i,j],接着分别看s和t[k][l]中是否存在区间可以填充[i,j]，这里可以进行优化的是，如果大的空区间可以填充，那么它的子区间就不必考虑了。做的过程中注意判重。这样速度就相当快了～～（哥排第五～哈）。

pku2688 暴力 或者 dfs(tsp)
	平面上有个机器人，有一些目标点，然后问机器人最少走多少部可以把所有目标点都遍历。
	先预处理对于任意的目标点之间的最短距离，然后就是典型的tsp问题。这道 题目目标点太小，所以可以暴力枚举所有排列顺序，500ms就过了，不过也可以dfs，加上dling优化就因该会快很多。

pku2449 两点间的k短路
	具体做法看网上，目前还未完全弄懂。
	
2010.5.14

pku 1704 博弈（转化为Staircase Nim）
	一行n列的方格，m个位置不同的硬币，每次把硬币往左移动，不能跨过任何硬币，而且一个
格子只能放一枚硬币，求是否必胜。
	其实可以转化为Staircase Nim问题，把相邻间的空格子数以及第一个硬币和左边界的
空格数作为一堆石子，然后每次的操作就相当于在当前这堆石子拿走一些，然后放到右边的那堆
石子，这就变成了Staircase Nim了，只要从右边起，把奇数的石子堆进行xor就可以了。

2010.5.15
pku3533 Nim积计算
	记(X)为nim积运算符，计算a(X)b,先把a和b化成二进制，例如a=(2^d1+2^d2+..)，然后
利用分配律，转化为求2^x(X)2^y的问题。接着对于2^x(X)2^y，考虑把x和y分别再化为二进制
形式，然后每一个数都是费马2-power数，利用桶排，从小到大做，把不同的数进行相乘，对于相同
的数，乘以3/2后再和其他数进行普通的nim积运算。
	这里要写两个函数，一个是用于普通nim积的运算，另外一个是对于2^x的nim积运算。为了加快
速度，可以预先处理所有2^x(X)2^y的值，然后对于普通的nim积运算只需要完成分配律的运算即可。
还要注意的一点是，中途运算过程中，调用函数的值可能会超过题目要求，所以最好把范围改大点。

hdu3404  nim积运算
	和上题一样。
	
2010.5.16
pku3710 树博弈
	按照game theory中的fusion principle做就可以了，要注意一些特殊情况。

pku2975 nim计数
	n堆石子，然后问如果必胜的话有多少种移动方法（一步）。
	因为答案最多只有n，令ans=a1^a2^...^an,如果需要构造出异或值为0的数，
而且由于只能操作一堆石子，所以对于某堆石子ai,现在对于ans^ai，就是除了ai以外其他的石子
的异或值，如果ans^ai<=ai，那么对于ai的话，是可以减小到ans^ai的值，然后使得所有数
的异或值为0，也即转移到了必败态。

pku2960 sg函数
	对于每一个堆，求出subtraction game的sg函数，然后进行异或就可以了。
	
pku1740 博弈分析
	ltc的题，关键是要理解当所有堆都能是成对出现的时候是必败状态，并且如果不是所有堆
都成对出现的话是能够转移到所有堆都成对。
	具体见网上解题报告.

2010.5.17
pku2425 sg函数
	拓扑图上移动若干个棋子的博弈。直接sg之。要做个拓扑排序。
	
2010.5.20
hdu1255 求矩形面积交
	扫描线，线段树记录覆盖一次的长度值，还有覆盖两次以上的长度值，这样更新的时候才能无误地更新.
	
2010.5.21
hdu1823 更新到点的二维线段树
	 更新到点的二维线段树，需要注意的两个地方是：
	 1.更新到点的时候，第一区间的祖先区间都要进行更新。
	 2.在更新第二区间时，因为对于该第二区间，所属的第一区间而言，
	   第二区间的一个格子是代表了实际的一行格子
       所以更新时是需要进行更优判断的。
     其实二维线段树上的所有点代表了二维平面上的所有可能的矩形，于是对某个点的改变，需要把所有包含
     这个点的矩形进行更改,所以就有注意2的存在。
pku2155 查找到点的二维线段树
	每次操作把一个矩形区域翻转，然后求某个点的情况。二维线段树，更新的时候只要把覆盖到的区间
直接覆盖，然后查找的时候要查找到底，把和这个点有关的所有矩形的覆盖次数都加起来，然后判奇偶就可以了。
注意查找返回时除了儿子的覆盖次数还要加上当前区间的覆盖次数。

2010.5.22
pku2185 二维的最小覆盖，kmp
	先考虑一维的，那最小的周期就是n-pre[n],然后对于很多行而言，现在要取一个区间大小值，作为最小覆盖矩阵
的宽度，那么这个宽度取什么合适呢？我们只考虑一行的周期串，如果区间的大小值是周期的倍数的话，那么这个区间的前
后就能够衔接在一起，所以对于多行的情况就是求他们的lcm。对列的情况也一样。注意如果最后答案大于行列的范围就定
为行列范围。
	

2010.5.27
pku3261 后缀数组+二分+height数组判断
	给出一个串，找出最长的重复至少k次的串。
	先求出后缀数组和height数组，然后二分答案len,接着在height数组中以len为长度分组，然后看是否存在一组的
个数>=k就可以了。

pku1743 和3261做法类似
	首先需要注意由于所谓“相等”的串很可能会有一个偏移值，所以需要对原来的字串进行转换，考虑如果两串之间是题目
所述的“相等”，那么他们相邻之间的差值一定是一样的，所以可以先把串相邻的相减得到新串，然后在新串上求出sa和height。
	第二步是二分答案len，然后像上题一样进行分组，接着看每组中sa的最大和最小的差值是否大于（注意这里是大于
而不是大于等于，因为这是相邻差值，等于的话前后串就会有一个是相交的）len就可以了。最后答案要+1。

pku2774 求两个串的最长公共子串
	把两串接在一起，中间加入一个从未出现的字符，最后添加一个特殊的最小字符。
	求出sa和height，然后求出height的最大值，不过这里要求sa[i]和sa[i-1]在两个不同的串中。

spoj705 求不同字串个数
	算法分析（摘自2009年集训队论文 罗穗骞）：
	“每个子串一定是某个后缀的前缀，那么原问题等价于求所有后缀之间的不 相
	同的前缀的个数。如果所有的后缀按照 suffix(sa[1]), suffix(sa[2]),
	suffix(sa[3]), …… ,suffix(sa[n]) 的顺序计算，不难发现，对于每一次新 加
	进来的后缀 suffix(sa[k]), 它将产生 n-sa[k]+1 个新的前缀。但是其中有
	height[k] 个是和前面的字符串的前缀是相同的。所以 suffix(sa[k]) 将 “ 贡献 ”
	出 n-sa[k]+1- height[k] 个不同的子串。累加后便是原问题的答案。这个做法
	的时间复杂度为 O(n) 。”

2010.5.28
spoj687 求重复次数最多的字串
	求出sa和height后，建立rmq，然后枚举长度l，如果字串出现至少两次的话，在s[0],s[l],s[2*l]。。中必有
相邻两个是这个字串的开头两个周期，然后向后看能匹配多少，接着再看往前能否补齐一个周期，如果可以则重复次数+1，
最后由于匹配的时候跨了一个周期，最后答案+1。

2010.5.29
pku1041 求边字典序最小的欧拉回路
	先判断是否是欧拉回路，然后把每个点的边的编号排序，然后就按照边从小到大遍历来找欧拉回路就可以了。。。

2010.5.30

pku1236 有向图加最少条边成为连通分量
	先求scc，缩点，然后在DAG图中计算入度为0的点数，ind0，和出度为0的点数，od0,那么答案就是ind0和od0的
最大值。注意只有一个强连通分量的特殊处理.

pku2762 判断有向图的单向连通性
	判断对于任意u,v是否存在u->v或者v->u的路径。先求scc缩点，然后进行拓扑排序，每次都要看当前可选节点是否
为1个，如果多于1个的话，那么这些节点就必定不能单向连通，所以就可以直接这样做。

pku3352,3177 无向图加最少边成为连通分量
	首先需要知道的是，不同的low值表示是在不同的以桥为分界的分量里，而非书上所说的连通分量，不过这道题目照样
可以做，因为连通分量是针对删点的，也就是说在连通分量中任意删除一个点而能够连通。而这里只是说要删边，所以就可以
以桥为分界，把图通过low值分成多个分量，然后让度为1的点有cnt个，那么答案就是(cnt+1)/2.(叶子之间相互连接)

2010.6.1
pku2942 判断有多少个点不在任意一个奇圈内
	先进行bcc，然后对于每一个bcc，如果存在一个奇圈，那么所有的点都能在一个奇圈内。而判断一个图是否存在奇圈，
可以进行黑白染色，如果能够黑白染色，那么就是二分图，就不可能存在奇圈，否则就存在奇圈。

2010.6.2
pku2723 二分+2-SAT
	二分长度，然后判断2-sat图是否有解。2-sat问题一般都有这样的特点，有n对点，每对中选了一个，另外一个就不能
选，然后还有m个合取式，每个式都是形如X(v)Y的形式，(v)表示或关系，那么只需要对这m个合取式建图，对X(v)Y,
必有~X->Y和~Y->X,一个合取式建立两条边，然后求scc，判断在同一个scc中，是否~X和X同时存在，同时存在则无解。

pku2749 二分答案+根据二分值构图+2-SAT判断
	详细见解题报告，关键是理解合取式的意义。
	建立一堆形如(x v y)^(~x v y) ...等的合取式，然后对于单独的一个析取式x v y，添加边~x->y 和 ~y->x。
之后的工作就是判断在建立的这个有向图中是否存在矛盾。这里一般需要求解scc。
	http://acm.pku.edu.cn/JudgeOnline/showcontest?contest_id=1177
	
pku3207 模型转化+2-SAT
	n个点围成一圈，给出m对连线，那些线可以在圈内相连，也可以在圈外相连，问给出的线是否会相交。
	对于每一个线，把它看成一个点，对于相交的线x,y，建立合取式(x v y)^(~x v ~y),也就是说，如果1表示在圈内，
0表示在圈外，那么这个合取式为真的情况只有两条先分别一个在圈内，一个在圈外。于是就对所有的线判断相交然后添加合取式，
最后判断是否矛盾就可以了。

2010.6.4
pku3678 2-SAT
	这里只讲如何构图，其他的就直接模板水之。
	x and y=0   ~x v ~ y  //注意这里是析取式
	x and y=1   ~x->x  ~y->y    //这里是直接建边,因为x,y都必须取1，所以~x->x这样按照反拓扑顺序就能够
							  //使得先染x和y。
	x or y=0   x->~x  y->~y
	x or y=1   x v y
	
	x xor y=0   (x v ~y)^(y v ~x)
	x xor y=1   (x v y)^(~x v ~y)

pku1679 次小生成树
	1.先求原图的最小生成树T，并记录树边和最小值small1
	2.然后求dis[i][j],表示在T中x到y的唯一路径上的最大边
	3.枚举所有非树边(u,v),设其值为w,那么small2=min{small1-dis[u][v]+w},最后看small1和
	small2是否一样就可以了。

2010.6.6
pku2125 二分图最小点权覆盖
	给一个有向图，可以进行两种操作，删除某个点的所有出度，代价为wo[i],或者删除某个点的所有入度，代价为
wi[i],问把所有边都删除最少的代价。
	因为对于每一条边<u,v>，我们可以选择删除u的出度，或者v的入度，这就类似在二分图中，对应的一条边，然后我们选取代价最少的点，使得每一条边至少被其中一个点覆盖，这就是最小权点覆盖模型。
	然后做法就是拆点，左边的点表示出度，源点对左边每一个点连一条容量为wo[i]的边，右边每个点向汇点连一条
wi[i]的边，然后对于边<u,v>，连一条oo容量的边。于是剩下的就是在这个图中求最大流，也就是最小割。那么这个最小割就对应了所选的删除入度和出度的情况。
	还有一点要注意的是，平行边和自环都不能忽略，都要加到图中，因为这些边也是要计算到结果中的。
	
pku3469 最小割
	n个模块，要么在第一个cpu上运行，代价Ai，要么在第二个cpu上运行，代价Bi，而且如果有一些模块对<u,v>如果在不同的cpu上运行会有额外代价wj，问把所有模块都运行的最小代价。
	然后对于每个模块变为一个点，源点往每个模块连一条容量Ai的边，往汇点连Bi的边，然后对于<u,v>,连双向边，容量为w，求最大流便可。但至于为什么这样建图，为什么是最小割？目前还没有弄懂。
	
pku1815 枚举+最小割，最大流
	对于每个点拆点成u,u'，然后<u,u'>容量为1，对边<u,v>，建边<u',v>,<v',u>容量为inf，然后求最大流就可以了。不过由于题目需要输出所谓“字典序”最小，所以要从小到大枚举，然后先删除这个点，然后看最大流是否不变，如果不变的话，那么这个点就不是必须要删除的，否则就是个割，如果有变化的话，顺便修改最大流量，然后继续剩下的枚举。

2010.6.7
pku3422 最小费用流
	给出n*n的矩阵，从1,1走到n,n，每走一个地方，就把那个地方清空，可以走k次（不是k步），问最多得到的权值和最大是多少。
	矩阵中每个点拆成两个点，u,u',然后建边<u,u',1/-Aij>,<u,u',inf/0>,令v表示u的右边的点,w为u的下面的点，则有<u',v,inf/0>,<u',w,inf/0>，还有<st,1,k/0>,<n*n',ed,k/0>。
	求最小费用流就可以了。	
	
pku3680 最小费用流//最大k可重区间集问题
	n个区间，每个区间都有权值。选出一些区间，使得任意位置上都不能有超过k个区间重叠，且权值最大。
	一个很巧妙的构图方法：令离散点分别为a1,a2,...am，a0为源，am+1为汇，对任意0<=i<=m,建边
<ai,ai+1,k,0>,然后对于区间[x,y]，找出x,y离散后的点ai,aj,然后添加边<ai,aj,1,-w>，w为该区间的权值。
求最小费用流就可以了。至于为什么这样。。。还在想。
	后记：可以这样想，从左边到右边有一股水流过，流量限制为k，然后对于区间，所连的边相当于分流，使得在区间内的流量少于k，这样求最小费用流就能够符合条件了。

2010.6.8
pku3686 KM
	n个工厂，生产m个产品，每个产品在不同工厂生产的时间不同，同一时间一个工厂只能生产一个产品，问生产所有产品的最小完成时间是多少。也即每个产品完成“时刻“的和最小。
	这题首先就要想到和网络流，费用流，匹配之类的联系起来，对于这些有先后关系的情况，一般都是用拆点的方法来解决。先考虑对于某一个工厂来看，假如它生产的k个产品的时间为t1,t2,t3....tk,那么完成时间总和是k*t1+(k-1)*t2+(k-3)*t3+...+2*tk-1+tk,那么就可以这样建图，对于产品i和工厂j,如果i作为j的倒数第p个完成的产品，那么i的贡献时间为p*t[i][j],那么就从i连边到[jp],权值为-p*t[i][j]。
	然后就在这样的图上用KM求最小权匹配就可以了。不过由于不明原因，这个图是n-n*m的，并不需要补点就可以过，现在还不明白为什么。
	
2010.6.10
sgu199 最长XX序列
	要将数据有序化，先按s不减排，再按b不增排，然后对b做O(nlogn)的最长递增序列。注意，若i<j,要si<sj且bi<bj的时候才能符合所谓递增概念。第二个按不增排主要是让后面b更小的可以覆盖掉那些和它的s相同但是b更大的。
	
sgu153 sg+循环判断
	初看是sg计算，不过由于p值相当小，所以从递推的式子可以看出，最多前2^Pmax个就会出现循环，用一个二进制记录当前点和前面Pmax个点的sg01情况，然后每次计算出当前点sg后就找是否有循环就可以了。

2010.6.11
codeforce round 17 D  b^n*(b-1) %c
	b^n*(b-1)%c=(b%c)^(n%phi(c)-1+phi(c)) * (b%c-1+c) %c;
	由于对于n和c很小的时候，phi(c)有限制，所以对于strlen(n)<9也即n很小的时候直接算，不用phi(n),其余情况用该式。

2010.6.12
hdu3416 最大流
	给出一个有向图和起点st,终点ed,然后假设st到ed的最短路为dis,那么问st到ed有多少条边不相交的长度为dis的路径数。
	先求最短路，然后构图，对于边<u,v>，如果d[u]+w[u,v]==d[v]，那么建边<u,v,1>，然后求个最大流就可以了。
	思想不难，想想为什么这样。


2010.6.19
codeforce round 18 E dp
	给出n*m的字符矩阵，然后对字符进行修改，使得1.每行最多两种不同颜色.2.相邻颜色不同。问最少修改次数，并输出方案。
	令状态dp[i,a,b]表示前i行，而且第i行改为ababab..的矩阵的最少修改次数，由于题目限制，每行必定是两种颜色相间的，所以dp方程为：dp[i][a][b]=min{dp[i-1][j][k]}+Diff[i][a][b],j!=k && a!=b && a!=j && b!=k.
Diff[i][a][b]表示第i行改为ab相间需要修改的次数。这个方程还可以优化，由于j,k要符合j!=a && k!=b这个条件，然后这个条件是很稀疏的，所以可以记录上一行的最小值的位置p1,p2当a!=p1 && b!=p2时可以直接转移，否则就按照方程转移。时间复杂度为O(n*26^3)

codeforce round 17 C dp
	详见此处：http://codeforces.com/blog/entry/451
	
2010.6.20
uva 10891 dp
	给出n个数，a，b两个人每次从左或右取连续的若干个数，取完结束，求a最多比b大多少。
	f[i][j]表示i到j先手最多可以取多少，那么转移方程为：
	f[i][j]=max{sum[i,j]-f[i+k][j],sum[i][j]-f[i][j-k]}  1<=k<=j-i+1
	
2010.6.21
uva 11378 最近点对的变形
	给出n个点，然后以每个点为中心构造一个正方形（和坐标平行），而且不能和其他点的正方形相交，问最大的边长是多少。
	其实就是个最近点对的题目，分治，然后求出任意两点的x,y曼哈顿坐标最大的最小值。先把所有点按照x坐标排序，然后按照x坐标来划分，而且在分治做的时候顺便进行y坐标的并归排序。不过我这里犯的一个错误是，进行分界的时候取的点的x坐标是左右分治后的(l+r)/2上的点，但是在分治的时候，由于左边的[l,(l+r)/2]分治很可能已经把原来位于(l+r)/2上的点换了，所以作为划分的x坐标就不正确了，因此需要在分治前就记录划分的x位置。

2010.6.22
uva 10056 概率
	n个人扔色子，每次扔到赢的概率为p,从1～n扔，如果还没有人扔到赢，那么从新从1开始扔。问第i个人赢的概率。
	暴力模拟，sigma(p*(1-p)^(j*n+i-1)),j=0,1,2...oo, 只要j足够大达到精度就可以了。
	
uva 10491  概率
	题目有点难解释，看原题吧。
	主要解决方法是分情况，如果选手第一次选的是cow，那么得到car的概率是[cow/(cow+car)]*[car/(cow-1+show+car)]，如果选的是car，那么得到car的概率是[car/(cow+car)]*[(car-1)/(cow-show+car-1)],加起来就是答案了。
	
2010.6.25
codeforce round 19 B 
	有n个商品，每个商品有价值ci和登记时间ti,销售员登记某样商品需要ti时间，在ti秒内可以偷ti件物品，问最少要付的钱来把n件商品清空。
	一个牛人对此题的分析如下：
	My thought process was something like this:
	OK, this looks like DP or greedy. It's problem B so it might be greedy.
	How should I sort items? Should I always pay for the cheapest item? No, doesn't work. Should I pay for the item with largest time? No. What about items with t=0. 
	Well, I guess it isn't greedy.
	How would I write a recursive solution?
	For each item I should either pay for it or steal it. If I pay for it then I can steal some other items. Yeah, state should definitely contain the position in sequence and the sum of ti. 
	Well I guess that's it, I just keep track of amount of items I have bought and the amount of items I can steal. In fact if I add 1 to each ti then it's even simpler.
	That's it, more or less. It's hard to recall and describe exactly. 
	A lot of experience with DP and memoization helps ofcourse, but I think the best advice is to write or think about writing a simple recursive brute force solution and then figure what the state is.
	When thinking about recursive solution you should try to make it as iterative as possible, that is scan elements in order and decide what to do with it.
	排除了贪心的方法后，具体做法就是dp了。
	状态就是dp[m][s]表示前m件物品，取出一些来付钱，使得sigma(ti+1)>=s 而且代价最少。
	dp[m][s]=min{dp[m-1][s-t[m]-1]+c[m],dp[m-1][s]}

2010.7.3
pku1966 无向图的点连通度
	对于有向图求边连通度，只需要固定一个源点，然后枚举汇点，求最小割的最小值就是边连通度了。固定源点的意思就在于对于把原图分割成不连通图的过程中，这个固定的源点必定在任意分割两点的一个之中，所以就可以固定一个而枚举汇点了。
	对于无向图的点连通度，先拆点，u变为u',u''，建边<u',u'',1>，对(u,v),建边<u'',v',inf>,<v'',u',inf>.
	源点取A'',汇点取B'。剩下做法和边连通度一样。
	
pku3189 二分或者枚举界+网络流
	n只牛，b个牛棚，每只牛都有b个牛棚的喜好程度，然后求出把所有牛都放进牛棚中的最小喜好程度差。
	枚举或者二分差值，然后再枚举下界，就知道上界了，接着就把超出这个界的边忽略掉求最大流，看是否满流。

2010.7.5
sgu269 dp
	给出n个数，b1...bn，然后给出一个矩阵，第i行从左边到右边，左对齐有bi格是可放车的，而其他地方是不可放车的。而且这里的车是会对同行同列的其他车造成威胁，然后问在这样的矩阵中放置k个车有多少种方案。（注意车是可以跨越那些不能放车的空格进行攻击的）
	首先考虑到，由于车可以跨“沟”攻击，所以其实bi的顺序对结果不造成影响，所以把bi按小到大排序，然后考虑使用递推来计算，一个容易想到的方法是f[n][k]表示前n行放k个车的方法数，以行为阶段划分，那么进而出现一个问题，对于列的重复如何进行判断？状态压缩？空间太大。增加决策状态？时间复杂度太高。其实陷入这个问题的关键是，我们一直对“选择了哪几个”而”耿耿于怀“，而没有想到我们只需要知道“选了多少个”和“当前能选多少个”就可以了，也就是说，之前选择了哪几个的顺序和位置信息对于决策无用处，我们只需要知道前n-1行选了多少个就可以了，这个可以在状态方程中知道，另外还要知道当前还能有多少种选择。由于bi从小到大排，所以就能很容易的知道当前还能选的个数，于是就有了以下的优美的状态转移方程。
	f[n][k]=f[n-1][k-1]*(b[n]-(k-1)) //选
			+f[n-1][k]  //不选
	这题要用到高精度。 

sgu256 dp
	N个人(N<=10)要吹M(M<=100)个气球，每个人只能够在一分钟之内操纵机器，吹出A[i]个气球，之后，就要休息至少B[i]分钟(1<=B[i]<=4)，才能够再次操纵机器吹气球。问吹出这M个气球至少要多少分钟。
	来自GHY神牛的思路：
	由于题目给出的规模都很小，我们可以考虑到搜索。注意到休息的时间最多只有四分钟，因此可以使用一个5元组DP[m,p1,p2,p3,p4]表示：吹出m个气球，这1分钟吹的人是p4，前1分钟吹的人是p3，前2分钟吹的人是p2，前3分钟完的人是p4，p1,p2,p3,p4的取之范围是[0,n]，为0则表示当前分钟没有人吹气球（大家都在休息）。那么可以得到转台转移方程：
DP[m,p1,p2,p3,p4]=min(DP[m-A[i],p2,p3,p4,i])，i从1遍历到n,若第i个人在此时不需要休息。
	如果得不出答案，则DP[m,p1,p2,p3,p4]=DP[m,p2,p3,p4,0]，相当于轮空1分钟。
	另外，如果直接按照普通dp的话很可能会超时，而且这道题目有很多的无效状态，所以为了避免这些无效状态可以用记忆话dp来做，这样就能省去很多无效状态的枚举。
	
sgu223 压缩状态dp
	给出n*n的棋盘，问放k个王有多少种方案。
	由于王只对相邻的造成威胁，所以可以通过状态压缩的方法来进行递推计算，令f[i][j][state]表示前i行放j个王，而且第i行的状态为state的方案数，那么可以枚举i-1行的状态来进行递推，其余的就不详细了。
	如果很裸的做的话会很慢，所以可以预先处理出一些合法的状态以及合法状态之间可以作为相邻的一些关系，然后可以发现这道题目的有效状态其实很少，所以可以用记忆化dp来做，可以省去很多无效状态。还有我在这里犯的一个错误是状态0和0是可以相通的，但是在添加状态关系的时候加了两次，导致错误，这里值得注意。

2010.7.22
pku 3764 xor 加 trie判断
	给出一棵树，边有权，xor路径值为树路径上所有边的值异或的结果，问最大的xor路径值。
	首先求出所有从根到点的xor值，然后就考虑在遍历树的过程中，对于每一个点，判断在之前遍历过的点中，和当前的值进行异或运算后值能达到最大的情况，这个可以通过对已经遍历了的点根据二进制构造一个trie树，然后从高位到低位，和当前的值进行逐位配对，看是否尽可能的做到每一位都尽量xor后为1，这样就能够找到和之前的点进行xor后得到的最大值。
	
2010.7.23
pku 3763 树dp
	给出一棵树，然后问最少添加多少条边使得该图存在哈密顿回路。
	一个重要的思想是，让最多的树边在这条回路上，那么也就相当于尽量利用原树边来构造尽量少的树路径。令f[x][0],f[x][1]分别表示x这个点和父亲在同一个路径和不在同一个路径上，而且构成一条链所需要的最少添加的边数。
	对于f[x][0],最多只能和一个儿子相连，其余的都作为f[v][1]来连接，所以就有：
	f[x][0]=min{f[x][0],f[v][0]+tot-f[v][1]+son[x]-1}   其中tot=sigma{f[v][1]},son[x]为x除父亲以外的邻接数。
	对于f[x][1]，考虑枚举两个儿子，使得他们经过x连成一条路径，其余的都以f[x][1]来连接，所以又有：
	f[x][1]=min{f[x][1],f[a][0]+f[b][0]+tot-f[a][1]-f[b][1]+son[x]-2}
	然而事实上是不许要对这两个儿子进行枚举的，因为对上面式子进行分析会发现只需要取f[a][0]-f[a][1]最小的两个就可以了，这个可以O(n)内完成。
	然后f[x][1]=min{f[x][0],f[x][1]}，因为不和父亲相连也可以像f[x][0]那样做。
	最后答案是f[1][1]+1。
	这里犯了一个错误，我取了一个全局数组aug，然后在递归的那个循环中对aug进行操作，后来才发现因为这个循环中有递归，所以在递归过程中会把该层中数组之前的一些值改变了。这里需要值得警醒，递归的时候如果需要用到全局变量，需要特别小心。
	
2010.7.25
pku3762 最大k可重区间集问题
	有n个任务，每个任务有权值和运行的时间段，任务不能并行，给出k天，问最多可以达到多少权。
	和pku3680一样，不过只是题目描述不同而已，可以把运行的时间段看成线段，而k就是最多k个区间可以相交，因为相交的线段可以分在k天中运行，而不相交的则没有关系。这就转化成了最大k可重区间集问题。
	
2010.7.28
codeforce24 D  暴力数学期望
	n*m的格子，开始位置为i,j，只能向下，向左，向右走，或者停留原地问到达第n行的期望步数是多少。
	从i,j到第n行的期望相当于从n行到i,j的期望，所以我们从下到上来做。
	令e[i][j]表示第i,j的期望步数，那么迭代式为：
	e[i][j]=1+sigma{e[i'][j']}/div;  其中div是sigma中的e[i'][j']的个数，而且由于sigma中也包括e[i][j]本身，所以把式子变换一下，得到：
			      sigma{e[i'][j']}
				  ----------------
	e[i][j]=   (1+     div       )
			   --------------------
			   		1-1/div
	然后暴力迭代直到达到某个精度为止。
				
zju2949 数学期望
	有n碗A面条和n碗B面条，每次丢硬币决定吃哪种，直到只剩下一种为止，求丢硬币的次数。
	考虑结束状态，吃了n个A面，i个B面，期望就是sigma{发生的步数*发生的概率},那么结果就是：
	sigma{c[n+i-1][i]/2^(n+i)*(n+i)}
	由于最后一碗肯定是A面，所以就是c[n+i-1][i]，而且总状态是2^(n+i),一除就是概率，再乘以次数就是期望，这里考虑的是吃完A的，由对称性，还要乘以2才是结果。这里由于n很大，所以要注意计算精度，可以考虑用
e[i][j]=c[i][j]/2^j,并且e[i][j]=e[i-1][j]+e[i-1][j-1]/2。
	另外一种解法，递推：
	令f[i][j]表示AB面分别剩余i,j的期望值，那么f[i][0]=f[0][j]=0;
	f[i][j]=f[i-1][j]/2+f[i][j-1]/2+1
	输出f[n][n]即可。这个方法更加简单。
	
NOI2005 聪聪和可可 数学期望
	给出一个图，有A和B在初始的位置，A要抓B，而且每次A先走，如果走一步后没有抓到B，则再走一步，而且每次都朝着更靠近B的路径的方向走，问A抓到B的期望步数。
	求期望的题目大多都可以用递推做，如果递推中涉及到循环，一般先进行暴力，如果不涉及循环，那么就可以从终点开始进行递推，或者状态不好表示时可以用记忆化搜索，本题可以用递推的记忆化方法。
	p[i][j]表示i到j的路径上，从i出发的第一个点的编号。w[j][k]表示j的第k个相邻的点。T[i]为i的度数。
	x=p[p[i][j]][j]
	那么f[i][j]=[sigma{f[x,w[j][k]]}+f[x][j]]/(T[j]+1)+1.

2010.7.29
SRM 420 DIV1 500 数学期望
	有R张红色牌，B张黑色牌，随机抽取，红色得到1分，黑色扣1分，问在最优情况下的分数期望值。
	令f[i][j]表示剩下i张红色，j张黑色的数学期望，而且是最优策略下的。
	那么f[i][j]=max{0,(f[i-1][j]+1)*i/(i+j)+(f[i][j-1]-1)*j/(i+j)}
	f[0][j]=0; f[i][0]=i;
	f[r][b]为答案。

2010.8.4
NWERC08 a //ad hoc
	给出一个称，而且挂称的地方只在中点，相当于一个二叉树，不会有单个叶子，而且所有叶子都有权值，现在就希望修改最少的叶子节点，使得对于所有非叶子节点，它的左右权值都平衡。
	考虑最坏情况下只有一个叶子不会修改，那么所有其他的节点的值都已经被固定下来了，也就是说只要我们枚举固定的那个点，然后看以这个点为标准的话有多少个叶子是不需要修改的，那么取其中的最优就可以了。
对于深度为dep，权值为w的叶子节点，以它为标准，该树的权值总和为w<<dep。对于每个叶子都这样求，看所有其他叶子中和它一样的有多少个就可以了。

NWERC08 c //最小点覆盖（用点覆盖边）
	有分别c,d,v个猫，狗和投票者，每个投票者都有自己喜欢和不喜欢的猫狗，现在需要选出一些猫狗，使得满足最多投票者的要求。
	把投票者作为二分图的点，然后有冲突的连线，题目就转化为求最小点覆盖问题，使得去掉最少的投票者，使得剩下的投票者之间没有冲突。最小点覆盖问题就是最大匹配问题，由于构图的时候存在对称性，所以令最大匹配为m，那么答案就是v-m/2。
	
NWERC08 f flood fill
	给出一些立方体，然后把些立方体组成的东西放到水里面去，求这个东西和水的接触面积和占水量。
	由于坐标很小，所以先进行离散化，然后用100*100*100的数组来表示，接着就对它进行flood　fill。逐个进行排查，模拟水和这个东西接触的过程，然后。。。就这样咯。

2010.8.6
SWERC96 f 压缩状态bfs
	有r个房间，从1号房间开始，每次只走有灯亮的房间，而且房间之间有灯的控制关系和连接关系，求从1号房间，而且1号房间亮的状态到r号房间，只有r号房间亮的状态至少需要多少步操作，包括开关灯都算一步。
	由于r<=10，可以把状态进行压缩，然后就用典型的bfs处理之。

SWERC96 h dynamic programming
	给出n个p[i]和d[i]，找出m个出来，使得|sigma{p[j]}-sigma{d[j]}|最小，如果相同则取sigma{p[j]+d[j]}最大的那个。并且输出方案。
	令f[i][j][k]表示前i个选择j个，而且sigma{p[j]}-sigma{d[j]}=k的最大的sigma{p[j]+d[j]}。
	那么f[i][j][k]=max{f[i-1][j-1][k-p[i]+d[i]］+p[i]+d[i],f[i-1][j][k]}
	求的时候顺便记录父状态即可。
	
2010.8.7
NWERC04 a 递推统计
	给出n个字符串，合法字符串表示不包含任意一个这些字符串为子串的字符串，把所有的合法串按照字典序排序，给出字符求字典序，给出字典序求字符。
	这道题目的一个关键的条件是这n个字符串长度最多为3，所以令f[left][x][y]表示剩余left个字符还没有决定，而且当前以xy为结尾的情况下不包含不合法字符串的有多少种。f[len][0][0]则为长度为len的所有合法字符串个数。
	那么left=0时，f[0][x][y]=1;
	left>0时，f[left][x][y]=sigma{f[left-1][y][z]},其中xy,yz,xyz都是合法的串（这里就明白为什么要利用的到题目给出的关键条件）。
	然后给出序号求字符串的时候，先用f[len][0][0]判断长度，然后再进行逐位判断。给出字符求序号的话利用序号求字符的方法来进行二分就可以了。
	具体实现的时候还有许多的细节要注意。

NWERC04 c 最小路径覆盖
	给出一些乘客的上车时间地点和终点，问满足所有乘客要求至少需要多少辆出租车。
	以每个乘客的乘车要求为点，先拆点i,i'，然后如果满足i的情况下能够满足j，那么连边<i,j'>。
	然后根据最小路径覆盖和最大二分匹配的关系，在这个图上求最大匹配m，那么答案就是n-m了。算是典型题目。
	
2010.8.8
NWERC04 h 带模的高斯消元
	对矩阵bij=i^(j-1),求a[i]，使得在模p情况下得到f[i]。bij,f[i]已知。
	就是普通的带模的高斯消元，不过在带模情况下用bii消去bji需要些技巧。由于p是素数，所以对于任何(n,p)=1的n，都有n^(p-1)==1(mod p),所以消去bji的时候，需要找到一个x，使得bji-x*bii==0(mod p),变换得到
bji*bii^-1==x(mod p),而且由费马小定理，左右乘以式子bii^(p-1)==1(mod p),得到：bji*bii^(p-2)==x (mod p)。这就把x找出来了。消成上三角后，最后回代一下就可以了。而且由于p是素数，必定只有一个解。

2010.8.9
SWERC09 a 二分+区间交
	给出点集，求出在x轴上离所有点最长的那个最短是多少。
	二分长度，然后对于每个点都求在y轴上那个x的范围，求出所有点是否存在交集就可以了。
	
SWERC09 d 暴力递推求概率
	扔飞镖，有20个均匀分布的靶，有2个人玩，开始时大家都有n分，扔到哪块就扣多少分，如果不够扣就保持分数，第一个扣到0分的为胜，A的策略是随便扔，B的策略是瞄准一个扔，但是他所瞄准的及旁边的三个都有相同概率中，他会取其中的最大概率的那个来扔。分别问A先扔和B先扔的赢的概率。
	求概率如果不是直接公式的话一般都会用DP做，考虑f[a][b],g[a][b]分别表示当前先手是A和B的情况下，A和B赢的概率，然后dp式子很容易求：
	f[a][b]=sigma{1-g[a-i][b]}/20;其中a<i的话g[a-i][b]的值是g[a][b]。
	g[a][b]=max{sigma{1-f[a][b-dart[i]]}/3,逐个枚举i,三个一组}。同样如果不够扣就保持分数。
	由于式子中包含了未知数，所以一般都会进行暴力处理，100次左右就足够了。
	
2010.8.10
SWERC 09 j 二分+后缀数组
	找出一个字符串中长度最长的出现至少m次的子串。
	先求出后缀数组和height数组，然后二分长度，对height分组，如果有一组的个数至少为m，那么该长度有解。
	注意m=1的特殊情况。

NWERC07 a 二分+判断
	组装一台电脑，需要各种不同组件，每种组件都有不同的生产厂家，其价格和质量不同。一个机器的性能取决于质量最差的那个组件，现在要在有限的预算中组装出质量最好的电脑。
	二分那个最差质量，然后对于每种组件找出大于等于这个质量的最便宜的，然后看是否在预算里就可以了。
	
NWERC07 b 网络流
	平面坐标上给出n个石块，有些石块上有青蛙，青蛙最大跳距离为D，而且每个石块最多允许mi只青蛙跳出，问有哪些石块可以成为所有青蛙的集中的地方。
	假设石块i原来有ni只青蛙，允许mi次跳出，那么把所有石块拆点，建边<i,i',mi>，和<st,i,ni>,对于距离在D范围内的两点i,j，建边<i',j,mi>,<j',i,mj>。
	然后就枚举集中的那个石块，建边<i,ed,inf>,做完后删除这个边。

2010.8.12
NWERC06 i 转化为图论
	给出26个字母的排列，问是否是ABC...Z通过两次置换得到的。
	我们把这个排列看成是一个置换，不过一次置换相当于原来的两次置换，那么我们先把所有的环都给找出来。然后我们发现对于奇环，一定能构造出原来的置换。而对于偶数环，我们发现它缺少了另外对称的一半，所以如果是合法的话，那么相同长度的偶数环必定有偶数个来配对，否则就无解。
	
2010.8.13
NWERC06 e 暴力dp
	给出n本书的高度h[i]和厚度t[i],放在三层不为空的书架上，问这个书架最小面积是多少。
	假定最高的那本书在第一层，那么我们只需要知道后两层的最小高度和以及厚度就可以确定面积了，所以令f[i][t1][t2]表示前i本书，后两层厚度分别为t1,t2下这两层的最小高度和。
	有：f[i][t1][t2]=min{f[i-1][t1][t2],
						f[i-1][t1-t[i]][t2],
						f[i-1][0][t2]+h[i],//t1==t[i]
						f[i-1][t1][t2-t[i]],
						f[i-1][t1][0]+h[i]}//t2==t[i]
	最后枚举f[t1][t2]来判断最小面积即可。

NWERC05 f 暴力枚举
	给出n个数，问最小的m，使得所有数mod m的值互不相同。
	枚举m，然后直接判断。
	
2010.8.15
NEERC 09 i 网络流
	给出一个有向无环图，求出最少的路径，覆盖所有的边。
	这个构图比最小覆盖问题要复杂些，这个是覆盖边的问题，构图如下：
	拆点，i,i',统计i的出度和入度之差，d[i]表示出度-入度，如果d[i]>0，那么<i',ed,d[i]>,如果d[i]<0，<st,i,-d[i]>,然后对于邻接矩阵做floyd，如果i可到达j，那么<i,j',inf>。
	统计sum为所有d[i]>0的和（d[i]<0的和也可以，因为都是相同的），求图的最大流maxflow，那么答案就是sum-maxflow。这个构图的一个主要思想就是对于那些可以通过合并的度都通过最大流消除，然后剩下的就是必须的。因为每个入度为0的点都必须带出一条路线，但是不一定就能覆盖所有边，所以还需要另外的一些点来带出路线来覆盖。那么对于这些点就不能通过流来消除度，于是就会增加路线数。

NEERC 09 j dp+搜索
	n道题目,m种类型，还有这n道题目中做对r题，还有每种类型的正确率（这个正确率的计算有点纠结,0.5会归到最近的偶数上,不是四舍五入也不是五舍六入），求出每种类型的题目数和错误的数，并且使得题目数最多和最少的差距最小。
	令f[i][j][k]表示前i种类型，共有j道题目，其中答错了k道是否有可能。记忆化搜索之，顺便建图。最后搜索所有的路径找出差距最小值就可以了。

2010.8.17
NEERC 08 f 递推计算统计
	给出一个斐波那契的数字表示法，然后问在二进制的这个表示法中，从1开始的连续N位中有多少位是1。
	解题的关键是进行分组统计，按照位数来分，那么第i组有f[i-1]个。
	令p[i]=f[i-1]*i,表示每组的位数之和。b[i]=b[i-1]+(b[i-2]+f[i-2])+1表示1。。i-1组的1的个数。
	然后通过这些计算这连续的N位得到的最大的整个数n，统计出在二进制的斐波那契表示法中1。。n的1的个数。假设n的表示法中a1,a2,..ak为1，那么答案就是sigma{(i-1)*f[ai]+b[ai]+1}。其中f[ai]的含义需要自己琢磨一下才明白它的原因。最后还需要对n+1处理完剩下的几位。这里要注意f[i]的i可能达到150++。
	
NEERC 08 h 构造？
	给出ai(1<=ai<=i),求出bi,使得sigma{ai*bi}=0。
	还没想明白的构造方法，从后往前，s初始为0，若s>0，则加a[i],否则减a[i]。

2010.8.18
NEERC07 a 调整
	给出平面上n只蚂蚁和n棵树，求蚂蚁和树的一个对应关系使得这些线段不会相交。
	想到了一个调整的方法，先随机分配，然后每次把相交的进行交换，做若干次后就出结果，可能是相交那里有问题，思路和其他的代码和petr一样，petr瞬间出解，但是我的却卡住某个数据，。。。不明白。
	
NEERC07 l trie+hash
	给出若干个单词，构造状态机出来，而且需要最少的状态。
	先构造trie，然后对trie进行hash，求不同的值即可。因为对于“最省”的状态机来说，一个状态对应唯一的一个trie子树，然后把每个trie子树变成hash值，看不同的个数就是状态机的状态数了。不过这里还需要注意，对于trie树中非叶子的终止状态，要与同“形状”的trie子树有一些区别就可以了。
	
2010.8.19
NEERC06 i  数学期望+map
	给出无向图G(V, E).  每次操作任意加一条非自环的边(u, v),  每条边的选择是等概率的. 问使得G连通的期望操作次数. (|V| <= 30, |E| <= 1000) 
	由于结果只和连通的状态有关，所以读入图后求出连通块和他们的个数。设状态s={c1,c2,...,ck},表示由k个模分别为c1,c2...,ck的集合组成的图的状态，为了防止重复，令c1<=c2<=...<=ck。然后考虑连一条边，有2种可能，一个是连回原来的连通块，一个是连去其他连通块。所以令f[s]表示s这个状态的期望，那么有：
	f[s]=[c(n,2)-sigma{ci*cj}]/c(n,2) *(f[s]+1) //连到自己原来的连通块，s状态未变
		+ sigma{ ci*cj*(f[s'ij]+1)}/c(n,2) //连到其他的连通块，s'ij表示这条边把i，j连通块连在一起后的状态。
	把这个式子变换一下，然后就利用记忆化递推，利用map<vector<int>,double> 作为f，很方便的进行状态的表示。写起来很舒服。
	
NEERC06 c 循环矩阵
	给出一圈数a[i]，每次对所有位置i，把距离i为d范围内的所有数加起来mod m得到下一轮位置i的值。问k轮之后这圈数的值。
	构造一个矩阵A，使得a[i]乘以这个矩阵后得到了一轮过后的值。那么剩下的就容易做了，利用对数复杂度的方法求A^k，最后a*A^k就是结果。不过这里n最大有500，比较慢，不过这里有一个知识点我是不知道的，那么我们分析一下A这个矩阵的特点，A其实是一种循环矩阵，而且A*A得到的结果也是循环矩阵，所以我们就可以只需要求出一行或一列的值，然后循环赋值给剩下的就可以了，于是复杂度变为O(n^2*logk)
	
2010.8.20
CEERC08 b 扩展欧几里德判断
	求a*b的方砖能否铺满c*d的地板。
	作以下猜想，该矩形可先分为3种分割方式
	1：若干的c*a子矩形
	2：若干的c*b子矩形
	3：c*x和c*y的子矩形
	对于大矩形c*d，我们需要用a边和b边去组合成c边，有3种方案
	1：只用a				组合成的子矩形是c*b
	2：只用b				组合成的子矩形是c*a
	3：既用了a也用了b			组合成的子矩形是c*lcm(a,b)
	如果c可以用方案1和方案2：那么d就
		(i)只能用b
		(ii)只能用a
		(iii)既用了a也用了b
	如果c只能用方案1：那么d就只能由b组成
	如果c只能用方案2：那么d就只能由a组成
	如果c只能用方案3：那么d就只能由lcm(a,b)组成
	其中求c能否由a,b组成用到扩展欧几里德，看是否有非负整数解。
	
2010.8.22
ZOJ monthly 3378
	给出一个非简单无向图，求出0到n-1的必经边。
	先求桥，然后找出0到n-1的随意一条路径，求交集。

ZOJ monthly 
	
2010.8.26
hdu3418 二分+判断
	有n种产品，分别有a[i]个，如果收集m种不相同的产品算装备一个人，问最多可以装备多少个人。
	二分人数len，然后从a[i]大到填充m*len的方形，如果多出来就放到下一层，只是不要和上一层的同一类型在一起就可以了，用贪心的方法来想就容易理解了。

ural1158 trie图
	给出组成单词的字符集，还有一些邪恶单词，问长度为m的所有单词中不包含这些邪恶单词的数量。
	先把邪恶单词构成一个trie图，然后就相当于在安全图中从根走m步有多少种走法。这个就可以用地推来做，dp[step,i]表示step步走到i的方法数，然后就直接从根一直递推过去就可以了。
	这题要用高精度。

2010.9.2
hdu3468 bfs+二分图最大匹配
	给出一个地图，一些地方有金矿，从标志的A走到B再走到C...每次都走最短路，然后可以选择在最短路上某个有金矿的地方挖一次，走一次只能挖一次，然后问最多可以挖多少个。
	先求每个标志点到所有其他地方的最短路，然后判断所有金矿，是否在相邻的标志点的最短路上。二分图左边表示相邻路径，右边表示金矿，然后如果金矿在相邻的最短路上则二分图建边，求个最大匹配就可以了。
	
2010.9.5
pku1637 混合图的欧拉回路
	摘自网上的：http://www.cppblog.com/guojingjia2006/archive/2008/08/02/57859.html
　　原来混合图欧拉回路用的是网络流。
　　把该图的无向边随便定向，计算每个点的入度和出度。如果有某个点出入度之差为奇数，那么肯定不存在欧拉回路。因为欧拉回路要求每点入度 = 出度，也就是总度数为偶数，存在奇数度点必不能有欧拉回路。
　　好了，现在每个点入度和出度之差均为偶数。那么将这个偶数除以2，得x。也就是说，对于每一个点，只要将x条边改变方向（入>出就是变入，出>入就是变出），就能保证出 = 入。如果每个点都是出 = 入，那么很明显，该图就存在欧拉回路。
　　现在的问题就变成了：我该改变哪些边，可以让每个点出 = 入？构造网络流模型。首先，有向边是不能改变方向的，要之无用，删。一开始不是把无向边定向了吗？定的是什么向，就把网络构建成什么样，边长容量上限1。另新建s和t。对于入 > 出的点u，连接边(u, t)、容量为x，对于出 > 入的点v，连接边(s, v)，容量为x（注意对不同的点x不同）。之后，察看是否有满流的分配。有就是能有欧拉回路，没有就是没有。欧拉回路是哪个？察看流值分配，将所有流量非0（上限是1，流值不是0就是1）的边反向，就能得到每点入度 = 出度的欧拉图。
　　由于是满流，所以每个入 > 出的点，都有x条边进来，将这些进来的边反向，OK，入 = 出了。对于出 > 入的点亦然。那么，没和s、t连接的点怎么办？和s连接的条件是出 > 入，和t连接的条件是入 > 出，那么这个既没和s也没和t连接的点，自然早在开始就已经满足入 = 出了。那么在网络流过程中，这些点属于“中间点”。我们知道中间点流量不允许有累积的，这样，进去多少就出来多少，反向之后，自然仍保持平衡。
　　所以，就这样，混合图欧拉回路问题，解了。
　　	/*其实网络流的作用是决定把哪些边反向从而使得度平衡*/
　　	
hdu3472 混合图的欧拉路径
	这个跟上面的几乎一样，只有一点不同，那就是随意无向边方向后统计度数差为奇数的点数，如果不是2个或者0个，那么无解，然后对于这两个点随意连一条有向边，剩下的和上面一样。
	这里的不同在于为什么这两个点也可以随意连边，因为网络流的作用在于决定应该反哪些边使得度平衡，所以如果形成欧拉回路的话，这两点必须要连边，只是方向要由网络流的结果决定。
	

2010.9.8
hdu3590  树博弈Anti-SG
	给出一棵树，两人轮流砍一些树边，谁不能砍则赢，问先手是否有必胜策略。
	首先求树的SG值，对于叶子为0，非叶子则是各个儿子的SG值+1的异或和，然后利用sj定理，也就是Anti-SG定理：
SJ 定理：
	对于任意的一个 Anti-SG 游戏，如果我们规定当局面中所有单一游戏的 SG 值为 0 时游戏结束，则先手必胜当且仅当以下两个条件满足任意一个：
	(1)游戏的 SG 函数不为 0，且游戏中某个单一游戏的 SG 函数大于1。
	(2)游戏的 SG 函数为 0，且游戏中没有单一游戏的 SG 函数大于 1。

hdu3584 三维树状数组
	给出一个01立方体，有两种操作，把一个子立方变为非，或者问某个小立方块的01情况。
	三维树状数组，用加来表示非，通过一个十分对称的加1的方法来模拟异或，这样求1,1,1到x,y,z的和就是x,y,z的01情况。
		
2010.9.9
hdu3595 Every-SG博弈
	每个单一游戏由两堆石子构成，每次选取其中一堆石子，假设有x个，那么可以在另外一堆石子中取k*x个，当然要保证另外一对的石子个数y>=k*x。整个游戏由n个单一游戏构成，然后每次决策都要在所有剩下的还没有结束的单一游戏中进行选择，不能选的为输，问先手是否有必胜策略。
	这个原来就是Every-SG博弈，先把所有单一游戏的SG都求出来，然后利用Every-SG定理：
	算出每个游戏的SG函数的时候，对于SG不为0的点，最慢几步可以到达终止状态，对于SG为0的点，最快几步可以到达终止状态。
				0	v为终止状态
	step[v]={	max(setp[u])+1	SG[v]>0 && u为v的后继状态 && SG[u]=0
				min(step[u])+1	SG[v]=0 && u为v的后继状态
	先手必胜当且仅当单一游戏中最大的step为奇数。
	
2010.9.10
hdu3562 特殊图的最大环
	开始的时候是一个三角形，然后每次新建的点都和某两个原图中就直接相连的点连接起来，问这样的图中的最大环。
	开始的时候忽略了那个重要的条件，原图中直接相连的两个点。。。结果就纠结好久。主要的做法就是倒着做，对于i点和它相连的x和y点，如果s[i][x]+s[i][y]>s[x][y]则更新，而且顺便看i,x,y三点是否能形成最大环，最后把开始的三个点也判一下最大环就可以了。
	
spoj375 树路径剖分
	给出一棵树，两种操作，修改某条边的权值，询问两点间的最大边权。
	通过轻重边剖分成一条条链，对于每一条链建立一棵线段树，把边权下降到两个端点深度较小的那一个点上，这样就把边权转化为点权。然后修改的时候维护线段树，询问的时候先找出lca，然后从某个点x向上寻找，当x和lca不在同一条链上的时候，x先跳到当前链的顶端，求出这段的最大值，然后再小跳一步到另外一条链上，直到在同一条链上为止。此时，要注意由于我们把边权转化为了点权，对于lca这个点的权值是它和父节点那条边的权值，所以这里询问的时候，是查询lca往下一个节点到x之间的点权。注意好这点就可以了。
	
2010.9.13
hdu3563 矩形切割
	给出若干个n维矩形，求并的空间和（如二维是面积，三维是体积）
	矩形切割，用链表实现，先判断是否每一维都相交，然后每次都增加该维上没有相交部分的n维矩形，然后把当前维变成相交的部分，接着去做下一维，最后把切剩的加到链表中去。速度还是很快的。。
	对于维数少而矩形多，最好用线段树，维数多而矩形少用矩形切割比较好。
	
2010.9.15
hdu3589 二次剩余
	给出Legendre和Jacobi定义，求所给的Jacobi符号值。
	枚举题意，判断是否是二次剩余的时候用欧拉判别法：
	p是奇素数，d%p!=0,那么d是模p的二次剩余的充要条件：d^((p-1)/2)==1 (mod p)
	
zju2314 有上下界的网络流判存在性
	构图详见周源的《一种简易的方法求解流量有上下界的网络中网络流问题》，添加源和汇，然后一个最大流就可以了。至于有上下界的网络最大最小流则需要多加一个二分再进行可行性判断。	
　设f(u, v ) = B(u, v) + g(u, v ) (*)，显然0 <= g(u, v ) <= C(u, v) - B(u, v)。将(*)代入流量平衡条件中，则得到∑[B(u, i) + g(u, i)] = ∑[ B(i, v) + g(i, v)] => ∑g(i, v) - ∑g(u, i) = ∑B(u, i) - ∑B(i, v)。如果设M(i) = ∑B(u, i) - ∑B(i, v)，即M(i)为流入结点i的下界总和减去流出i的下界总和。
　　至此，可如此构造一个只有流量上界的附加网络：增加附加源S'和附加汇T'，原网络中M(i)非负，则C'(S', i) = M(i)，否则C'(i, T') = -M(i)；原网络中任意有弧相连的结点u和结点v在附加网络中的弧C'(u, v) = C(u, v) - B(u, v)。
　　这样，如果附加网络满流，则在原网络中就存在一个与之对应的可行流。而想判断附加网络能否满流可通过求解附加网络的最大流进行判断。如果满流，则有解；否则无解。
　　这个问题弄明白后，就可以进行下一步的求解有上下界网络中的最大流和最小流问题了。
　　增加一条弧(T, S)，使原网络变成一个无源汇的网络。如果求最大流，则B(T, S) = a，C(T, S) = inf；如果求解最小流，则B(T, S) = 0，C(T, S) = a。可以通过二分法枚举a，按上文提到的方法构造附加网络，判断附加网络中是否有可行流即可。最终，a即为所求。
　　这种方法实现起来较为简单，所需的代价是多次求解最大流。复杂度为O(logF Maxflow(V, E))。
2010.9.21
hdu3656 二分+最大团
	找出至少k个点，使得他们的最近的距离最大。
	二分距离，如果u，v的距离大于改距离，则建边，然后看这个图中是否存在>=k的团。

2010.9.28
hdu3627 动态找出某坐标右边最近的点
	对输入坐标离散化，然后对x坐标维护一个线段树，每个节点记录当前x区间内最大的y坐标，然后对于l==r的节点，维护一个set<int>，保存当前x坐标下的各个y坐标，插入和删除操作维护这两个东西就可以了。查找的时候，先判断左区间是否有解，无解才去右区间判断。
	通过此题，原来set的效率还是灰常高的，在某些处理二维问题上可以给不少力。

2010.9.29
hdu3664 递推
	给出n和k，问1~n的排列a1,a2...an,刚好有k个ai>i的排列的个数。
	令f[n][k]表示前n个数，有k个ai>i的排列数，那么我们考虑最后一位n,那么n有3种交换的方法，一个是和前面那些ai<=i的位交换，这样k的个数就加1，第二个是和前面ai>i的交换，那么k不变，第三个是摆在原地。于是就有以下递推式：
	f[n][k]=f[n-1][k-1]*(n-k)  //第一情况
			+f[n-1][k]*k	//第二情况
			+f[n-1][k]	//第三情况
	
2010.9.30
hdu3661 排序
	有n份A产品和n份B产品，所需时间分别为xi和yi，共有n个工人去加工，每个工人选择一个A和一个B来加工，如果xi+yj超过常规工作时间T，那么就要付加班费xi+yj-T,问最少要多少加班费。
	由于x和y的顺序无关，所以可以先考虑进行排序，按xi-T从小到大排序，然后对yi从大到小排，然后对应的xi和yi一起是最优的，正确性就在于如果进行交换的话不会有更优解，这个需要仔细想想。
	
hdu3666 差分约束
	有一个矩阵cnm,然后问是否存在a1...an,b1...bm，使得第i行所有元素乘以ai,第j行所有元素除以bj后处于[L,U]区间中。
	对于cij,那么就是L<=cij*ai/bj<=U,取对数后得到 log L-log cij<=xi-yj<=log U-log cij
然后化成差分不等式：xi<=yj+log U-log cij,yj<=xi+log cij-log L,接着建图，看是否有环。
	然后果断的TLE了，后来仔细发现，这个图的特点就是一个二分完全图，所以我猜想每个点进队列的次数肯定是很少的，所以就直接判断看是否>2，然后很无语的过了= -。不解释。
	
2010.10.1
hdu3667 费用流
	给出一个图，每条边有费用系数ai和流量上限ci,然后如果该边流量为x，那么费用为ai*x^2，问从1到n运送k单位流量最少花费。
	由于这里的费用计算是x^2，那么一个很神奇的想法就是1+3+5+。。=n^2,也就是拆边，拆成ci个流量为1，费用分别为(2*j-1)*ai的边，那么按照连续最短路增广的方法，肯定是先走1，再走3.。。这样子就能够保证正确性。然后一个最小费用流就可以了。
	
2010.10.3
pku 3734 生成函数
	用四种颜色w,x,y,z染1*n的格子，其中y,z两种颜色需要染偶数个格子，问有多少种方法。
	用指数生成函数，得到g(x)=[(e^x+e^-x)/2]^2*e^2x
	最后化得：gn=2^(2n-2)+2^(n-1)
	
2010.10.4
pku3716 条件概率，贝叶斯公式
	有4个色子，每局，对于每个色子的每个面，都有平均的几率被刷成红色或黑色，然后再扔色子，现在已知前两局各有p,q个色子抛出红色，问下一次抛出红色的色子个数期望值。
	先求出对于单个色子p(x=1 | x=00),p(x=1 | x=01),p(x=1 | x=10),p(x=1 | x=11)的概率，然后找出形成p,q的这4个色子的各种组合情况，那么对于一种组合情况，sigma{p(x=1 | x=??)}为抛出的色子的个数，然后还要乘以1/M,(M为组合总数)，那么就变为了求期望值的经典公式形式了。
	然后剩下的问题是如何求p(x=1 | x=??) 。考虑到每个色子的不同面数对于求这个概率有联系，那么p(x=1 | x=??)= sigma{ p( T=t | x=??)*p(x=1 | T=t)| 0<=t<=6 }
然后对于p( T=t | x=??)可以利用贝叶斯公式处理：
	p( T=t | x=??)= p(x=?? | T=t)*p(T=t) / sigma{p(x=?? | T=t)*p(T=t) | 0<=t<=6}
	然后就把p0...p3都求出来了，接着就解决了问题。。。
	详细见：http://hi.baidu.com/5l2_/blog/item/dbb67843252e631a73f05df6.html
	
2010.10.5
hdu3564 线段树+树状数组
	给出一个序列的构造方法（从1..n进行添加），然后问每次添加i的时候，序列中的LIS是多少。
	先利用线段树反向构造出原来的序列，并且记录每个数在原序列中的位置，然后正向重新构造这个序列，可以利用树状数组动态维护前j个的最大值，由于从1.。n来构造，所以对于第i个而言，它是当前最大的，只要知道它前面的最长就可以了，更新LIS的值。
	
2010.10.9
zju 3412 容斥原理或mobius函数
	给出n个数a1..an，然后对在取值在[x,y]区间内的所有b1...bn,使得s<=sigma{gcd(ai,bi)}<=t的有多少种bi的选择方案。
	递推式子很容易求：f[i,j]表示前i个ai与bi，gcd的和为j的情况下的方案数。那么有：
	f[i][j]=sigma{f[i-1][j-di]*S[A;ai/di]},其中di是ai的约数，A表示区间[x/di,y/di],S[A;k]则表示在A数集里面，和k互质的数的个数。那么现在问题就在于如何求S[A;k]
	通过mobius函数，能够求出一个数和一个数集的互质的个数，有下面的定理：
	S[A;k]=sigma{u[d]*|Ad|},d是K的约数，Ad表示A数集中能被d整除的数的个数。
	mobius函数可以利用线性筛素数的方式预先处理出来，S[A;ai/di]则可以在进入j的循环前处理出来，于是总的复杂度为O(n*(Range(ai)+t*sqrt(Range(ai)))
	
zju3329 数学期望(把环化成一次方程)
	有三个色子，分别有k1,k2,k3个面，每次同时抛出这三个色子，如果第1，2，3个分别为a,b,c，那么积分归零，如果超过n积分则结束，问游戏结束的期望步数。
	以下是官方解答：dp[i]用来表示当前总和为i时，到游戏结
	束的期望步数。则当i>n时，dp[i]=0，否则dp[i]=sigma(p[k]*dp[i+k])+pp*dp[0]+1
	其中p[k]为扔到总和为k的概率，pp为扔到abc的概率。这个时候按照左电梯的思路，
	是要写成矩阵然后高斯消元，不过这题的n有500这么大，又有300个case，N^3的高斯
	消元显然是吃不消的。观察后发现，每个dp[i]除了跟dp[0]有关，就只和比i大的dp
	值有关了。于是，我们可以让i从n到0，一路都把dp[i]表示成dp[0]的一次函数，最后
	就是一个dp[0]=a*dp[0]+b的式子了，直接解出dp[0]即可，复杂度非常小。
	
2010.10.16
zju3404
	摘引自watashi的报告：“那个，首先背景和配图什么的就略过了。题目说的就是你有m种交换方式，用a交换别人的b，这可以看成一个a到b的有向边，题目保证了每个顶点的入度和出度都不超过1。题目问的是有多少种不同的序列，能够通过变换，最后成为一个n的排列。

	注意每个顶点的入度和出度都不超过1，所以每个联通分量只有可能是链或环。对于环的情况，显然就可以任意分配了，所以环内部任意交换的顺序有mm(A000312)种。对于链的情况，这是一个非常经典的问题，答案是m+1m-1(A000272)种（一个非常漂亮证明），也可以通过动态规划dp[i][j] = sum{c[j][k] * dp[i - 1][k]}求得，其中答案就是dp[m][m]，c[j][k]表示j选k。有了这些基础，就只要先构图，再求出所有联通块的大小，并判断它是链还是环，最后直接算出答案。”
	这里需要注意的是：dp[i][j]表示j个位置放1..i的方案数，首先要知道对于链表状态的，我们可以先把它们规约为1..i放在j个位置上的情况，然后如果要变为合法的排列的话，要符合j<=i，这也是理解这个递推式子的关键，如果不符合这个条件则无法通过单向链表形成合法的排列，而对于当前的i的每一种选法都有c[j][k]个状态，所以就有这个式子。
	
hdu3663 D-link精确覆盖
	给出一些城镇，每个镇都有发电站，这些发电站都有一个发电的时间区间，而且每个发电站只能在这个时间区间的一个子集时间上发电，而且停了之后就不能再工作，某个镇发电的时候，相邻的镇就有电，但不能同时发电。现在要求每个镇在1.。D天都有电供应，问每个镇的供电时间表。
	把这个问题转化为精确覆盖问题，也就是在n*m的01矩阵中选出一些行使得对于每一列都有且只有一个1。转化的方法就是化成(n*16)X(n*d+n)的矩阵，这里的16是指[1..5]的所有子区间和[0,0]，表示了每个镇的每一个发电时间区间，也就是所选出的行，对于列，则表示每个镇的1.。d天都要有唯一来源的供电，最后的n列是表示，一个镇的发电区间只能选一个，这样就对应了题目的要求。
	这样转化之后就是经典的Dlink，直接模板之。
	
pku3074 数独dling做法
	把数独转化为精确覆盖，变为(9*81)X(9*9+9*9+9*9+81)的矩阵，关于列的说明，首先是1～9行，每行有1..9的选择，每行都要有唯一的1..9，然后对于每一列和每个宫格都是如此，所以就有前面3个9*9，最后一个81表示对于每个格子，也是选且只选一个值。对于行来说就是提供选择给各个列，那么对于每个空格，有9种填法，对应有9行，空格最多有81个，而对于已经填好的，那么就只有1行。
	
pku3076 和上题一样，不过是16*16的。

2010.10.17
hdu3617 递推
	给出N个学生，以及他们对自己成绩的猜测ri和bi，表示他的成绩顺数ri和倒数bi，问最多有多少学生能猜中。
	其实对应于n区间[ri,n-bi+1]中的成绩是一样的，然后问能组成完整的1..n的区间组合中区间数量最多的是哪个。注意同一个区间的猜测人数可能会大于该区间大小的情况，此时要排掉多余的，然后就是简单的dp了。
	

2010.10.18
hdu3533 字符串，后缀数组
	给出一个字符串和k，问这个字符串的所有子串中字典序排第k的是哪个。
	大致做法，先求出后缀数组，现在考虑答案的第一个字符，先找出最前的，而且所有子串个数总和>=k的这个位置，然后这个位置的第一个字符就是答案的第一个字符了，然后找出后缀数组中第一个字符是这个字符的范围，k要减去这个范围之前的那些子串个数，然后让当前的区间变为我们所找到的范围，下一次就在这个范围里继续做。对于第二个字符也是同样的做法。
	实现的时候有很多细节，文字很难表达。。。
	
2010.11.6 
hdu3686 双连通分量，缩点
	问某边到某边必须经过的点数，先求各个割点，然后求出双联通分量，每条边都属于一个双联通分量，然后对于每个联通分量和割点组成新的图，显然这个图是一棵树，然后对于每个询问就在这棵树上做Lca，然后就可以求出某边到另外一条边所必须经过的点数。实际写起来需要注意好多东西。。。
	
2010.11.11
pku 1015 dp
	在遥远的国家佛罗布尼亚，嫌犯是否有罪，须由陪审团决定。陪审团是由法官从公众中挑选的。先随机挑选n个人作为陪审团的候选人，然后再从这n个人中选m人组成陪审团。选m人的办法是：控方和辩方会根据对候选人的喜欢程度，给所有候选人打分，分值从0到20。为了公平起见，法官选出陪审团的原则是：选出的m个人，必须满足辩方总分和控方总分的差的绝对值最小。如果有多种选择方案的辩方总分和控方总分的之差的绝对值相同，那么选辩控双方总分之和最大的方案即可。
	动态规划状态表示： VALU_MAX 表示最大喜好分值。 p [k] , d[k]分别表示第k个人对原被告的喜好分值。 
	Last[i][j] 表示已经选了i个人得到差值j（j = D（J） - P（J）+ VALUE_MAX * m）的时候，和i个被选中的人的编号k(k = 1到n) Sum[i][j] 表示已经选了i个人得到差值j（j = D（J） - P（J）+ VALUE_MAX * m）的状态时最大的（D（J） + P（J））值。
	状态转移方程： Sum[i + 1][j + p [k] – d[k]] = max(sum[i + 1][j + p[k] – d[k], sum[i][j] + p[k] + d[k]) (其中第k个人和须在前i次选择中没被选中) 最终选出方案 K = min{ i | 0 <= i <= value_max * m && (sum[m][value_max * m + i] || sum[m][value_max * m – i]) >= 0 }再利用last数组查出记录。
	这里循环的时候，顺序为m,j(差值),n,这样循环n的时候，要进行重复判断，如果先进行n再进行m的循环，那么会造成重复，而且不容易进行重复判断。
	
2010.11.12
pku3683 2-sat+方案输出
	给出N个婚礼，每个婚礼有开始和结束时间Si,Ti,还有婚礼中的宣言的时间长度Di，而宣言的时间要么是在婚礼一开始或者在婚礼最后的那段时间进行，然后要参加所有的婚礼，问一个方案。
	对于2-sat问题，主要走两个步骤，第一个是分组，每组2个，而且是两者不能都选，只能选一个。不同的题目对于分组的概念不同，例如这道题目是明显的给出分组的，每组都必须要选且只选一个，而有的题目只说明要取一些，每个东西都可选可不选，而通过拆点，拆成x和~x，那么就变成了每组都必须要选一个的情况。第二个就是建立组和组之间的矛盾，这个就通过析取式完成，于是就完成构图了。
	对于输出方案的方法，先对scc缩点，对于x和～x，要找出缩点后对方所在的缩点的编号，然后拓扑排序。接着以相反的拓扑顺序，对于没选的点，选择之，对于不选的那些，就要把所有指向它的点都不选（这里就需要知道x和~x对方所在的缩点编号）。最后输出即可。
	
2010.11.13
pku2699 网络流
	给出一个有向图的出度序列，然后如果某个点有边指向所有出度比它大的点，那么这个点就称为king。现在问所给出的出度序列所构成的图中，最多能有多少个king。
	这里有个很巧妙的构图方法：
	“设一个源点Ｓ引一条边到每个人，边容量为这个人打赢别人的数量　，
Ｎ个人两两比赛共N*(N-1)/2场比赛，每场比赛只有一个胜出,所以每场比赛引一条边到汇点，容量为一，表示最后赢的总场数为N*(N-1)/2而这些由这Ｎ个人去瓜分,
	每场比赛有两个人参加，所以，这两个人各自引一条边到这场比赛，如果Ａ在某场比赛打羸了Ｂ，那说明这场比赛只能让Ａ到达Ｔ，从而使Ａ赢的场数增加１，这时只要把Ｂ引向这场比赛的边去掉便可！
	由于要使得King更多，而最有可能成为Ｋing的人中分数高的比分数小的人的概率要大，所以从高分往低分枚举，由于枚举到第i个人时要打败前面i-1个人才能成为King ,所以，把凡是有i和前面i-1个人参加的比赛都定为i赢,即去掉i-1个与相关比赛的边，做一次最大流，如果等于SUM(所有人赢的场数）则枚举下一个人,否则结束!”
	
2010.11.18
zju3421 三分
	给出n个函数fi(x)=ax^2+bx+c,定义F(x)=max{fi(x)} ,0<=x<=1000。求min{F(x)}
	通过观察，发现F(x)函数是一个单峰函数，于是就可以直接用三分法求峰值，注意精度要至少2倍于输出精度，我选了1e-10。
	

	


///////////////////////new age///////////////////////////////////////////
2011.1.19
swerc10 d 网络流+扩展路判断
        给出一个矩阵，矩阵元素要么是0或者1，并且给出每行和每列1的个数，然后问是否有解，如果有解，给出字典序最小的那个。
        求是否有解可以直接利用网络流得到。如果满流则有解，现在是考虑如何使得字典序最小。那么我们可以按照先行后列的形式，如果某个位置为1，那么考虑把这个1退流，然后判断在只改变优先顺序比这个后的点的情况下（优先顺序高的不能变），是否存在扩展路，如果存在，那么就是说当前元素就可以变成0而继续有解，这样字典序变小而不改变解性质。

2011.1.20
uva 11874 转化成判正环
    给出一个带权有向图，每条边有收入和支出，问能否找到一条点不重复的环，使得总收入/总支出>=p,其中p给出。
    sigma{income} /sigma{outcome} >=p  转化为  sigma{income}- p* sigma{outcome} >=0 也就是对于每条边权值化为 in-p*out 然后看是否存在正环即可。这个用bellmanford就可以解决。


2011.1.23
seerc10 d 格雷码，网络流
        有n个竞赛和m个题目，每个竞赛都有固定的题数，每道题目有一些适合的竞赛，如何分配问题使得可以同时举办最多竞赛，每个问题只能分配到一个竞赛。
        由于竞赛数<=15，可以枚举哪些竞赛必须得到满足，然后构图，如果满流则有解。这里有个优化就是通过格雷码来枚举，每次都只需要修改一个竞赛的状态，这样子再进行增广的时候就可以少很多重复工作。然后还有一些简单的优化就可以很快了。


2011.2.15
zju Jan monthly A:
    给出n,(0<=n<=99),求出最小的m,使得1/m产生的小数,除去前导0,剩下的连续的2个组成的数能够包含0~99中除n以外的数.
    对于1/m,做m次之后就有循环节,所以最好的方法是做m次,暴力打表即可.
    当然也可以判断循环节,不过前导0不加入set中,否则会使得把00的情况乎略掉.

小技巧:
    求出一个状态s的所有子状态,可以这样写:
        for(int i=s;i!=0;i=(i-1)&s)
                i ... //这里的i就遍历了所有s的子状态,而且不会有无效状态,关键是 (i-1)&s ,是比i小的最大的那个子状态

2011.2.16
hdu 3762(2010 Northeastern European Regional Contest k)
    给出一个无向图,有奇数个点,求出一个k染色方案(k为奇数,且不小于最大的点的度数).
    由于有奇数个点,而且图的度数之和为偶数,那么必然存在一个度数为偶数的点,然后由于k为奇数,所以以某个度数为偶数的点开始dfs,考虑这棵dfs树,根最多有 k-1个儿子,那么必然能将所有儿子染色,然后再递归到每个子树,每个子树的根都已经被染色,如果这个根是偶度点,那么必然能继续染色,如果是奇点,那么由于有父亲节点,剩下最多k-1个儿子,所以也必然能继续染色.
    于是,这个图必然有解,任意点开始染色即可.

2011.2.22
hdu 3735 矩阵乘法 
    Given two integers N and M, we define a recursive sequence g[i] (indexed from 0) as follows:
(1) If 0 <= i < M, then g[i] = a[i]
(2) If i >= M, then g[i] = b[0]*g[i-M] + b[1]*g[i-M+1] + ... + b[M-1]*g[i-1]
Now your task is very simple: Try to find g[N] mod 1,000,000,003.
    传统的做法显然是不能过的,不过矩阵中有一个定理:A^m=sigma{b[i]*A^i | 0<=i<m }.有了这个定理之后使得对于求A^n变为求A^n的一个线性表达(其实就是转换了一种表达方式,而且要计算这种表达方式会少些计算).于先求出C[i][j]:表示A^i 中A^j项的系数. 0<=i<2*m-1. c[i+1]可以由c[i-1]乘以A,然后将A^m的线性表达式又代入原来的线性表达式,就可以求出当前c[i+1]的线性表达式了.
  把C[i][j]求出来之后,只需要求A^n-m+1的线性表达式就可以了,这个可以log时间完成.只是两个线性表达式相乘得到的线性表达式需要对一些指数>=m的进行处理,降为<m的.最后把A^m-1...A^0化掉(和a相乘),再和B(A^n-m+1的线性表达式)相乘得到答案.
  详细解题报告:http://wenku.baidu.com/view/e7513a2f453610661ed9f470.html



2011.2.23
hdu 3736
    把m个人放入n个矩阵中,其中矩阵i长宽为ni*mi,每行每列不能放超过2个人,问有多少种方法.
    f[i,j]为前i个矩阵放j个人的方案数,那么f[i,j]=sigma{f[i-1,j-k]*g[i,k]} ,g[i,k]为第i个矩阵放k个人的方案数,那么如何求g[i,k]呢?
    令c[i][t0][t1][t2]表示前i行,其中有t0列为0人,t1列为1人,t2列2人.那么考虑当前行不放人,放1个人,放2个人的5种情况递推就可以了.注意优化.

2011.3.2
zju 3475 枚举+最小割
    在一个20*20的方格中，建造一些围墙，使得X和某些A与E和外界都不联通，建造围墙有对应的花费，而对于满足条件的A，有对应的收入。
首先2^5枚举哪些A要被围住，然后就要求所需的最小费用，这就是典型的最大流最小割问题。其中X和所枚举的A同源连一条流量为inf的边，E和边界同汇连一条流量为inf的边。

 zju 3474 贪心
    某人要挑战n个人,有三种攻击分别消耗p1,p2,p3能量,分别获得3,2,1分,每次都至少拿7分才过关,血要多于0,开始有s血,问结束时最多剩多少血.
    首先，对于打倒某个对手至少需要多少体力，我们可以通过DP求得，实际上考虑背包大小只有7，只有三种物品，所以直接暴力三个for循环更简单。然后这个问题就和ZOJ3077 Move to Baggage Office类似了。所以可以直接参考这题的解题报告和证明。详见《ZOJ月赛的三个tooold解题报告》。根据证明可以知道，对于恢复的体力小于消耗的体力的战斗，应该按照恢复体力降序排列的顺序打。而对于恢复体力大于消耗体力，我们要用另一种贪心方式：按消耗体力升序排列的顺序打，这个证明非常显然，就不详细说明了。当然，总的顺序是先打恢复体力大于消耗体力的。所以是O(nlgn)的贪心。

ural 1817  数学期望
     有一个环型木马,每秒转一格,每次每个小孩都随机站在某个位置上,若有空位则上去,没有则等待直到有位.问第i个小孩等待时间的数学期望值是多少.
     令f(s)表示木马的状态为s的概率,f(s)=sigma{f[s']*1/n} s'是去掉某个1的s的子集.然后g[k]表示二进制有k个1(也就是有k个小孩)的等待数学期望值,那么g[k]=sigma(f[s]*1/n*step[s,i])  step[s,i]是在s状态下,在i位置的等待时间.k为站在i位置的人坐上去之后的状态的二进制的1的个数.
     打表才能过.


2011.03.5
codeforce round 58 D
     给出一个图的欧拉回路的点序列,然后求出这个图的欧拉回路中字典序刚好比给出的大的那个序列.
     其实求字典序小的欧拉回路的求法直接在扩展的时候按照点从小到大扩展就可以了.只是这题需要记录第一次走的时候所选的点,然后在回溯回来的时候所选的点比原来的大就可以了.其实本质就是搜索,但是由于欧拉回路都很容易找出来,所以速度还是很快的.


Network Flows  p259 Application 8.2
     给出一个无向图,对于每条边i,j都有刷新次数aij,每一天都能对所有点j的相邻边进行共bj次的刷新(每条相邻边可能分到的刷新次数不一样).问最少需要多少天使得每条边都满足了刷新次数.
     建立二分图,左边是n个点,右边是n(n-1)/2个点,代表边i-j,建立边<s,i,r*bi>,<i,i-j,inf>,<j,i-j,inf>,
<i-j,t,aij>.然后二分r,看是否满足所有aij.


Network flows p720 最大闭合权图
        给出一个有向图,点有权值,闭合图是G=(N,A),使得 for each node i in G'; for i,j in A 都有 j in G'.
        也就是说有i在里面,i所指向的所有点也在G里面.
        求出最大权值的闭合图.
        对于wi>0的,建立边<s,i,wi>,对于wi<0,建立边<i,t,-wi>,对原图边i,j建边<i,j,inf>.这样求最小割,用权值和减去最小割就是最大权闭合图.(因为每个割都对应一个闭合图,详细见书的证明)

Network flows p721 application 19.1 open pit mining
        有一堆砖头,每个砖头都有价值wi(可正可负),要挖下面的砖头必须先把架在这个砖头上的砖头都挖走才可以,问获得的最大价值是多少?
        建图时,下面的砖头向上面的砖头连inf的边,表示一种拓扑关系.
        典型的闭合权图....

Network flows p721 19.2 Selecting Freight handling terminals
        给出无向图,边有权,点有负权,要获得边的权,必须要安装边所连的点的终端,问获得的最大权是多少.
        把边化成点,左边是n*(n-1)/2个点,右边是点,每条边连两个点,然后就是最大闭合图.(由于选边必须选点,所以边连inf的边到点,也表示一种拓扑关系).


Network flows p727 19.5 Asymmetric Data Scaling 
        有n行m列的矩阵aij,是否存在Ai(1<=i<=n),和Bj(1<=j<=m),使得对aij,有L<=aij*Ai/Bj<=U.
        不等式取对数,化为和式,然后移位,就化为了差分约束系统.

2011.3.9
uva 11090 最小平均值环

  一張圖上每條邊都有權重，最小平均值環是「權重除以邊數」最小的環，可能有許多只。
最小平均值環也可以視作是最小比率環的特例，當每條邊的第二組權重都等於 1 的時候。

  令V為圖上的所有點構成的集合，n為圖上的點數。
圖上任意取一個點作為起點，d(k, i)為起點走k條邊到達i的最短路徑。
                                     d(n, i) - d(k, i)
平均權重 = min  max   ─────────────────
           i∊V 0≤k≤n-1      n - k
如果圖上有不連通的部分，可以使用最短路徑 Johnson's Algorithm 所提到的技巧，在圖上另外新增一個起點，並且增加起點連到圖上其他點的邊，其權重皆設為零。如此一來，圖上的每一個點都可以由起點走到，而且最小平均值環也不會改變。


2011.3.10

Network flows p734   Just-in-Time Scheduling
        有n个工作,不同工作之间有先后关系,每个工作有耗时ci,并且对于工作对<i,j> j必须要在i开始之后aij时间内完成(aij<=ci) ,问完成所有工作的最短时间是多少.
        设u[i]表示i开始的最快时间,那么对于<i,j>有:  u[i]+ci<=u[j]<=u[i]+aij 移位一下,然后就是差分约束鸟!

Network flows p302  最大区间权值和
        给出n个区间,每个区间有范围[xi,yi],然后最多能够同时存在k个区间,每个区间有价值ci,和数量bi,问在满足要求的情况下最大的权值和.
        这是个最小费用流问题.建立源汇s,t,然后对于s,1,2...n,t相邻间连边<i,i+1,k,0> 费用是0.对于区间<xi,yi>建立边<xi,yi,bi,-ci>.然后求最小费用流就可以了,每个费用流的答案都对应了一种方案.

Network flows p303  Scheduling with Deferrral Costs
        给出p个工作,和q个机器,工作i如果在机器上第k个运行,那么耗时为c[i][k].问把所有工作完成最少耗时是多少.
        化成最小费用流来做.左边是p个点,s连到每个点<s,i,1,0>. 右边有p/q上取整个点,假设为r个点.那么对于右边的点j ,建边<j,t,q,0> 表示这个点最多容纳q个作业同时运作(其实就是q个机器同时开工).然后对于左边的每个点i都向右边每个点j建立一条边<i,j,1,c[i][j]>.然后求最小费用流就可以了.(至于右边为p/q个点的原因是,这是个完全二分图,p/q上取整个点肯定能容纳p个工作流,必然有解.)


Network flows p743 有向图和无向图的中国邮路问题
        中国邮路问题,其实就是在一个有权图中,从某个点开始,每条边至少走一次,最后又走到起点,求最小花费.
        其实中国邮路问题和欧拉回路有很大的联系.
        对于有向图而言,可以用最小费用流解决.设每个点的入度为ri,出度为ui,对于ri>ui,连边<s,i,ri-ui,0> ,对于ri<ui,连边
<i,t,ui-ri,0>,对于原图边则容量无限,费用不变.然后就可以通过最小费用流解决.
        对于无向图而言,把所有的奇度点找出来(而且必定有偶数个,想想为什么?),然后变为完全二部图,相互连接,权值为两点间的最短路.求一个最小权匹配就可以了.


Network flows p749 动态运输(最短路或最小费用流)
        有一个商店要进行n天的销售,每天都有一定的销售需求di,每天可以选择从批发市场进货,但是每个货物需要ci的价格,当然也可以用以前卖剩下的来继续卖,但是每件货物存一天就要wi的花费,问完成这n天的销售最少花多少钱.
        先考虑建图,弄源s和s',<s,s',sigma{di},0> ,然后对于<s',i,inf,ci>,对于这n天相邻的两天<i,i+1,inf,wi>.最后对于每一天<i,t,di,0>.
        如果每天的供货都是无限的而且仓库也是无限大的话,那么可以直接用最短路来求.
        否则供货有限,仓库也有限,那么就可以用最小费用流来求.


NCPC 2010 G    DP
     给出n，求n的所有排列形成的置换中，环的长度不超过k的概率。
     令p[n]表示n个数还没形成环，而且符合k的要求的概率，那么p[n]=1/n* sigma{p[n-i] |  1<=i<=k}。考虑当前剩下的n个数，从某个数开始，一直找到环为止，而且剩下的每个的选择都是等概率为1/n的，所以就有这个结果。加个优化就可以O(n)了。

NCPC 2010 E  分析
     给出n×m的方格，然后从1,1开始向右下角走，遇到边界反射，问最终有多少格被走过。
     首先考虑把x和y的运动独立，然后最后结束必定是在四个角落上，所以x走到边缘的步数总是(n-1)*k,而对于y也是(m-1)*k'，那么当x和y都走到边上时，也就走到了角落上，于是总的步数就是LCM(n-1,m-1)，然后加上开始的那个空格,加1.
     这时候，就要考虑重复点的问题，对x而言，跨越上下一共走了L/(n-1)次，而跨越左右则有L/(m-1)次，那么相互之间就共有L/(n-1) *  L/(m-1) 次相交。但是还有一些是相连而不是交叉，那么这些点都是“碰壁”的点，而且要么是x碰壁，要么是y碰壁，所以总数为L/(n-1)+L/(m-1)-1 ，-1是因为最后一步是同时碰壁。然后就是由于x和y的相交是双向的，多算了一倍，要乘以1/2.
     于是总数为L+1-1/2*(L/(n-1)*L/(m-1)-(L/(n-1)+L/(m-1)-1))=L+1 - 1/2*(L/(n-1)-1)*(L/(m-1)-1)。


NCPC 2010 J   离散化
     给出平面上若干的梯形，其中有三面都垂直xy轴，且都平放在x轴上。现在按照从近到远的顺序给出这些梯形。然后问对于每个梯形，能看到的面积是多少。
     离散化+判断。先对x坐标都进行离散化，然后再加入那些斜线相交的点来一起离散化，接着根据这些来切梯形的斜边，把梯形都切为一个个斜线段，然后按顺序计算每个小的三角形或四边形是否在某个梯形内，然后把面积加进去就可以了。


NCPC 2010 B   2次BFS
     给出n*m方格中的A，B ，C ，D点，然后A曼哈顿连线到B点，C连到D点，线不可相交，问最短路线是多少。
     一个很重要的思路就是，两条线路必定有一条走的是最短路，否则肯定不会是最优。因此就分别让AB先走最短路，或者先让CD走最短路，然后最小值即可。


NCPC 2009 C DP
     给出n个药品进行过敏检测，每天早上为注射时间（最多注射一种药物），晚上为检测时间，检测的时候假如有2个过敏反应，则无法辨别是哪种过敏。问要检测出n种药品的过敏性最少需要多少天。
     数据很小，用状态DP解决。m[i][stub]表示状态为i的时候，并且最后那一段空闲长度为stub的最短时间，那么：
     m[i][stub]=min{m[i-2^j][old]+stub+1}
     其中stub=max{d[j]-old-1,0}   //注意，由于j也需要有一天来进行独立检测，所以需要减1。
     0<=j<n ,  0<=old<7  
     感觉这样做也太暴力了，umum~~~期待有木有更好方法？



NCPC 2009 G 枚举+树最长路
     给出一棵树，然后删除一条边，加上一条新边，问形成的新树中最长路最短是多少。
     枚举删除哪条边，然后现在就分成了2棵树，那么对于这两颗树都找出对应最长路的中点，那么在两个中点之间连边是使得新树最长路最短的方法，注意会存在新树的最长路在分离的其中一棵树的情况。找树最长路可以O(n)完成。

NCPC 2008 A 排序+DP
     给出n（n为偶数）棵树在x轴位置，并且要把这n棵树分别栽种到两条平行相隔为W的种植区中，而且栽种的时候相邻相隔距离一致，而且平行的也要相互对应，问最小的总移动距离是多少。
     一个十分重要的特征是，对树的位置排序后，那么按照从前往后的顺序来填坑是最优的，如果交叉则不会更优（这个需要些证明）。
     然后就是c[i][j]表示第一二行分别栽了i,j棵树的最小代价，那么就是c[i][j]=min{c[i-1][j]+dist1,c[i][j-1]+dist2} 。


2011.3.30

NCPC 2008 C 后缀数组
     给出n个字串和一个主串，问主串和各个字串间最大的连续子串是多少，如果最大有相同则全部输出。
     把n个字串连起来，中间加一个神马都不同的符号以区分，然后也把主串加进去，求一个后缀数组，和height数组。然后对于每一个非主串的位置，找出这个位置前面和后面最近的主串位置，然后就知道这个位置和主串的最长字串长度了，然后进行比较就可以了。
     
NCPC 2008 I  贪心+堆
     有na个数据需要读取，有大小为c的cache，每次读取都需要载入cache中，如果cache中有相应数据，则不用读内存，如果cache满了而且没有相应数据，则需要调出一个数据腾出位置来放新数据，那么现在问读取这na个数据至少需要读多少次内存。
     贪心算法，维护cache    中每个数据的下一次读取的时间，从晚到早排序，满的时候，把最晚需要读取的那个换出，那么总读取次数最小。注意，每次读一个数据都要维护cache中的下一次读取时间，无论这个数据是否在cache上。

2011.3.31
Topcoder SRM 501 DIV 1 500  DP
     给出一个序列，每个数字-1<=a[i]<=40,然后-1代表该位可以为0~40的任意数。现在问有多少个序列满足：（1）不存在连续的三个是递减的a[i]>a[i+1]>a[i+2];（2）每个值都小于等于前面值的平均值。
     令f[l][tot][j][2]表示前l个序列，总和为tot，最后一个数字是j，并且[2]中0表示a[l-1]<=a[l],1表示a[l-1]>a[l]，然后就是直接DP即可。这个状态比状态f[l][tot][j][k]要好，因为其实没有必要记录最后的两个是多少，只需要知道最后的两个的大小关系和最后一个的值就可以唯一确定状态了。这种状态表示方法也值得学习。


2011.4.1
NCPC 2007 D 搜索
   给出S串和T串，现在玩一种类似填字游戏的东西，要把T串填出来。一开始T串各个位置都还是没有填的，每次都可以从S串中截取连续的一段，或者从反向截取一段出来，如果和T未填的某些连续的段一致则填下去，或者可以使用T已经填了的段来填没有填的位置。问填完T至少需要多少步。
   预处理出来S对于T的那些连续段可以填，还有T的各个段对其他段的填写情况。然后搜索的时候2^m的状态表示，并且一个优化的地方是，先填长度大的，然后如果长度大的填好了，那么所有在这个长度子集的都不会更优，可以直接去掉，这样搜索速度就会快很多了。


2011.4.2
NCPC 2007 G Dilworth定理
     给出n个玩具，每个玩具长宽为wi,hi，那么如果wi<wj 且hi<hj，那么i能被j包住。现在问把所有玩具都包在一起，那么最少会看到多少个玩具？
     dilworth定理：
     最长链=最小反链集合数
     最大反链集合大小=最少链数
     如果把包含看作是偏序关系，那么题目求的就是最少链数，也就是求最大反链集合的大小。如果从链的角度来解决问题，那么对于最小链数，也就是偏序的最小路径覆盖数，但是题目n很大，二分图匹配超时。如果从反链的角度来解决问题，那么对于最大反链，也就是对于不符合偏序关系的边和点组成的无向图中找出最大团（因为反链是相互之间都没有偏序关系）。但是由于这道题目的特殊性，当我们按照w从大到小，然后相同则h从小到大，那么由于传递性，找出h的最长不递减子序列就是最大反链集合的大小（因为这个序列两两都不具有偏序关系而且是最大的，于是也是反链关系的最大团）。


2011.4.8

pku3715 二分图最小点覆盖（用最少点覆盖所有边）
        给出一个二分图，求最小点覆盖，而且是字典序最小。
        求最小点覆盖就是最大匹配，但是要找出字典序最小的，那么就从小到大枚举匹配了的点，去掉这个点，假如最小覆盖改变，则这个点是必须在最小覆盖中的，输出，否则恢复。由于是从小到大枚举的，可以保证字典序最小。并且确定某个点是在最小覆盖中的话，那么对应匹配那一点也要清掉匹配标志，防止重复。
        最难的一点是如何判断去掉某个点之后最小覆盖是否改变，那么这个可以从匹配的对应点看是否能够找到增广路，找到则最小覆盖不变，于是总复杂度为O(n*m)。


2011.4.9
SRM 465 greenwarfare div 1 600   最小割-最大流
    给出n个加农炮的位置，和m个基地位置，还有电厂位置，加农炮可以无限打，每次打一个基地，要摧毁基地可以直接用炮或者摧毁在基地方圆r的所有电厂，炮攻击某个位置的代价为距离平方。问摧毁所有基地最少代价。
    建图，左边是基地，右边是电厂，s到基地i为离基地i最近的炮打的代价为流量上限，右边也类似，中间的流量为inf，那么每个割对应了一种方案，最小的割就是最小的代价。


2011.4.13
Tokyo 2010 	Test Case Tweaking  最短路
      给出一个有向图，边有权，现在修改一些边权（不能改为负），问最少改动多少条边使得1到n的最短路长等于于一个给定的值C（C小于原来最短路）。
      拆点，f[i][l]表示到i这个点，并且修改了l条边的最短路，并且我们考虑到，如果要修改一条边，那么要比C小，既然修改了，那么肯定要改到最短，也就是0,于是在这个条件下spfa就可以了。

Tokyo 2010  Awkward Lights   二进制高斯消元
      给出一个矩阵，每个矩阵都是一盏灯，如果某个灯开环切换，那么曼哈顿距离为D的其他灯状态都会改变，自己也会改变，然后问是否存在方案使得所有灯都关掉。
      对于矩阵每一格，都建立方程，系数都是对其有影响的方格。然后利用高斯消元方法做就可以了。充分利用bitset，能够快很多。注意有解可能有唯一解或者无穷解。


2011.4.14
hdu1569  二分图最大权独立集
         给出一个棋盘，每个格子都有非负权值，现在要取一些格子，相互不相邻，并且总权值最大。
         将格子黑白染色后，就变成了二分图，现在就是要在这个图里选出一些点，它们之间没有边相连，并且权值最大，这个就是二分图最大权独立集，等价于求二分图最小权点覆盖的补集，     又因为二分图最小权点覆盖和最小割一一对应，于是现在建图：st到所有黑点连边，容量为改格权值，所有白点到ed连容量为权值的边，相邻的黑点和白点则连边，容量无穷，那么这个图的最小割和最小点权覆盖对应了。

codejam 20008 The year of code jam 最大流-最小割
        给出一个棋盘，有些标志为蓝色，有些白色，还有些是没决定的颜色，对于每个蓝色，权值为上下左右白色的个数，那么现在需要对没决定颜色的格子来染色，使得总的权最大。
        其实假如现在已经染好了色，那么权值除了可以对每一个蓝色进行计算以外，还可以发现权值等于不同颜色的边的个数，也就是边的两旁是不同颜色的个数。
        那么也就是说要最大化不同颜色边的个数，那么换过来就变成最小化相同颜色的边的个数，于是这个就对应了一个最小割模型。
        先对棋盘黑白染色，左边是所有蓝色和?的黑格，右边是蓝色和？的白格，于是这就是一个二分图，图上的边对应了相邻相同颜色的权值，现在求这个二分图的最小割，也就是求相同颜色相邻的边的最小个数，对于左边st到所有蓝色边权oo，到？边权为4,右边类似，然后中间的所有相邻都为2。求最大流，然后4×总非白格数-最小割就是答案了。（至于原理现在还是没能完全弄懂，待以后再想）


2011.4.18
SRM 503 DIV1 500 概率题
    给出n个城市，m个村庄，每个村都要连到一个城市。每次按照下面规则来做：随机找一个还没连的村i，然后i找出离它最近的城市或者已经连上的农村，如果距离相同则选中概率相等，花费为欧几里得距离，现在问所有农村连上的期望花费。
    最暴力的是m!的算法，但是是否有更好的呢？
    总期望=每个村的期望的总和，所以现在考虑单独一个村i，把所有城市和村和i的距离求出来，然后小到大排个序，现在发现，从左到右第一个城市以后的所有点都不可能连到i，因为按照规则，无论顺序如何i都不可能连到后面的点。于是现在考虑前面是村落，最后一个是城市的情况。
    对于序中的第j个村(j从0开始)，假如j要被i连上，那么所有j之前的都要排在i之后，那么概率为j!/(j+2)! 。如果j是城市，那么由于城市是不参与排列的（因为只有村落的选择顺序才对结果有影响），因此概率为j!/(j+1)!=1/(j+1)。然后概率乘以距离求和就是结果了。


2011.4.19
SRM 499 DIV1 1000 图论+计算
    hhanger的报告：
    用户输入一个长度为k<=30的只由A B C D四种字母组成的字符串，并且可以对字符串进行两种变换操作：
交换字符串两个相邻字符。
有最多50对字符串，每对两个字符串a和b长度相等，同样也是只由A B C D四种字符组成。如果当前字符串中有一个子串为a，则可以把该串变成b。
总共有4^k个不同的字符串，每个字符串对应某个颜色。用户需要通过一系列变换，把初始的串变成另外一个不同的但是有同样颜色的串。现在要求设计这4^k的串的颜色，问最少使用多少种不同的颜色，才能保证用户不管怎么选择初始串、怎么变换都无法完成这一任务。
如果我们把每个字符串看成一个点，则每个变换操作就对应了点到点的一条有向边，这样我们就得到一个有向图。则题目就是要求给有向图所有点染色，保证在图中任意走都不会遇到两个相同颜色的不同点。如果图中没有环，则这就等价于求图中最长路的长度，现在有环的话，也不难处理，只要首先对图求一次强联通缩点，这样的话就得到了一个顶点带权的DAG，在这个DAG上求带权最长路即可。   
于是，现在最主要的问题就是图的定点数太多了，不可能直接求DAG。减少点数的关键就在于第一个变换，相邻字符可以交换，意味着如果两个字符串包含的A B C D四个字符数量相等，只有顺序不同的话，他们一定是可以互相变换的，即一定在同一个强联通分量中。因此，我们可以不用考虑字符串中字符之间的顺序，只用管4种字母的个数，4^k个字符串可以根据这一点直接缩成C(k+3,3)，即最多5456个点，这样在根据第二种变换来构边，就可以根据上面的算法缩成DAG后求带权最长路的长度了。
     注：原图每个点的权是C[k][x1]*C[k-x1][x2]*C[k-x1-x2][x3]，因为由于相邻交换，使得每种颜色个数为x1,x2,x3,x4的方案数就是每个点的初始权值，因为这些点都是可以相互变换的，而且对于scc中的点也是一样，所以scc的权值为所有点权值和。


2011.4.26
sicily 2384 ac自动机上dp
       给出n个串，如果一个串是另一个的子串，那么连边（单向），问最长路。
       把n个串建成ac自动机，然后在构造fail指针的时候进行dp，要么从fail处转移，要么从父亲处转移。


2011.4.27
sicil 2372  数论？
       给出N(<=10^18),问0~N-1是否存在a，使得a^2=a(mod N),且不存在b, 使得b^2=a(mod N)。
       对于a!=0 && a!=n/2，那么(n-a)^2=a (mod n) ，所以只有0和n/2是有可能没有b^2=a。那么令k=n/2，那么假如存在b^2=0,则k^2+b^2=k(mod n),  而且2*k*b=0(mod n),把两式加起来，得到(k+b)^2=k(mod n)，那么k就不唯一了。所以整个条件就变为，如果不存在b^2=0(mod n)，那么0就是解。
       至于判断0~n-1是否存在b^2%n=0,那么可以考虑，假如n不存在完全平方因子，那么0~n-1中找不到一个数使得能够“集齐”被n整除所需的质因数，否则如果存在的话，令n=p^2*q,那么b=p*q，使得b^2能够被n整除，则b为解。于是就有下方法：
       解法是判断N是否有完全平方因子，如果有则无解。也即是否存在素数Pi,  使得pi^2 | N。可以先把10^6以内的素数都找出来，然后找这个范围内是否有完全平方因子，顺便做素数分解，然后除掉10^6以内的素数后，剩下的数n假如是有完全平方因子，那么必然大于10^6，最多只有2个，而且只需要判断筛剩下的n是否是完全平方数即可。       


2011.5.2
zju 3505 DP+计数
    现在有一个长度在1~n的字串，由0，1,2,3构成，相邻数字不同，没有前导0,并且按照字符串进行大小比较，那么把这些字符串组成一个集合，并且排好序。现在给出一个字串，问排在该字串前k个的字串是神马。譬如n=2时，1 < 10 < 12 < 13 < 2 < 20 < 21 < 23 < 3 < 30 < 31 < 32。排3前面5个的是13。
    这个集合其实相当于给一个深度为n的三叉树，的每个点进行编号的集合。那么理解了这个就容易写str2id和id2str()这两个函数。细节可以看代码，主要思想是从高位到地位，逐个位来进行计算求和。id2str也是如此，高位到地位逐位相减。


    
 zju 3506 DP
     给出一棵树，每次切一条边，然后选择其中的一部分继续切，另外一个丢掉，问k次之后的那个部分最大和最小是多少？
     树形DP，f[x][j]表示x为根（不考虑x和父亲的那条边），并且其子树切0~k次的最小值（最大值类似）。然后对于每个儿子v，有两种请情况，保留儿子，那么
chkmin(f[x][j],f[x][l]+f[v][j-l]) ,0<=l<=j-1,舍去儿子，那么chkmin(f[x][j],f[x][j-l]) ,1<=l<=son[v]+1。最后答案包括f[root][k]，或者某个i，f[i][k-j] ,    1<=j<=n-son[i]，求最小值。

2011.5.3
sicily 2407  压缩状态DP
       给出s个点(s<=10),n<=4个人，p条边，然后一开始所有人都在0号点，每一秒都可以走向相邻的点，人都是独立走的，问这n个人要把所有点覆盖完最少需要多少步。
       由于人走都是独立的，所以可以先进行f[i][s]表示当前在i点，覆盖了s的最小步数（单独一个人，而且这里要用spfa求，因为并不是每一步都走新的点，可能需要回去之前走过的），然后令g[num][s]表示num个人走出s这个状态所需要的步数，g[1][s]=min{f[i][s]}  ，然后对于g[num][s1 | s2]=max{g[num-1][s1], g[1][s2]}，就可以了。
       这题关键在于想到人走的是相互独立的，而且走出那个状态s最终停在哪里对于最终结果没影响，于是对于多个人的时候就没必要记录每个人都在哪里。


2011.5.3
sicily 2469  树DP
       给出一棵树，对于每一条边，问切掉这条边之后，再增加某条边连起来，使得新的树的最长路最短。
       首先假如已经知道这两部分的最长路，那么要最短就连中点就可以了。现在就需要知道分开的两部分的最长路。
       类似求树最长路一样，分两部分来做，第一次dfs求出x为根的一些信息值，maxpath[x]表示不一定连接到根的子树最长路，mostpath[x][3]表示连接到根的最长路前3个。mpath[x][2]表示那些不一定连接到根的最长路的前2个（这个会在跌入次dfs中用到）。
       然后第二次dfs的时候，需要记录fmaxpath表示不一定和x节点连接的父亲那一堆点的最长路，flpath表示连接到x的从父亲部分过来的最长的那条路，那么假设现在要删除x到v的边，那么v子树的最长路显然是maxpath[v]，那么对x-v分割的x这一边的最长路就比较复杂了，主要有原来的fmaxpath,还有flpath和除v以外的其他儿子相连的路（这些路经过x），或者x的某两个儿子相连的路径，或者x的某个儿子的mpath（不一定经过该儿子的路径）。那么对于这几个取最大值就是下个递归的fmaxpath了。
       这个算法的一个大优点在于可以在线性时间内求出一条边分割后的两部分的分别最长路。

       
2011.5.7
codejam 2011 qualification C implement
        给出n个物品，每个物品价值ai，然后分成两堆，使得每一堆的异或和相等，并且使得其中一堆的总价值最大。
        列出式子,设第一堆选择i1,i2,...in,第二堆选择j1,j2,...jm，而且有ai1^ai2^..^ain=aj1^aj2^..^ajm，那么移项一下就得到所有价值的异或和为0,则一定有解，然后只要把最小的一个移到一边去，那么剩下的就是总价值最大的了。

2011.5.9
codeforces Yandex Qualification 2 D  DP
           n个人排队，每个人都有处理时间，每次都从队伍头的三个中选择2个来并行处理，所需时间为两个的最大值，最后落单的一个单独处理，问最少需要的时间。
           设状态f[i][j]表示队列头为i,j时的最小值，那么i~j之间的肯定已经清空，j之后的全部都还在，那么这个Dp式就很容易推了。。。用队列推过去就是了。

2011.5.11
codeforces round 71 D  转化为图+bitmask dp
           n个格子，黑色或者白色，然后给出l个长度ai，每次都可以把连续的长度为ai的区间都翻转，开始全部是白色，然后最终结果使得x1,x2...xk位置上的点都是黑色，其余为白色。问最少翻转次数。
           默认0位置和n+1位置为白色，然后对于两格之间假如不同颜色，那么中间那里就标注为1，否则为0.那么我们可以发现，对于一个区间的翻转（边缘至少有一个是1）的时候，相当于把1转移到另外一个边缘上，而且区间的边缘都是1的话，就相当于两个一起消失。那么可以抽象出来，每两个格子之间的边缘抽象成点，然后为1的那些边缘上有炸弹，每次根据ai可以把炸弹转移到其他位置上，假如两个炸弹在一起则消失。现在问题转化为最少多少步可以把所有炸弹消灭（把最终状态和初始状态对换）。
           考虑一个bitmask dp  f[s]表示有炸弹的那些点的状态，最多2*k个，然后转移为f[s]+g[j][k]->f[s+(1<<j)+(1<<k)],这里g[j][k]表示j到k最少要走多少步，可以bfs出来，关键是j和k的取值，j和k都是s上为0的那些位置，不过j是从左边起固定为第一个为0的位置，因为假如j不是第一个的话，由于最终结果是两两配对消失的，因而总有一个k‘要和j配对消失，所以转移状态是不会漏掉的，只是把相同的转移路线调换了一下位置而已，对最终结果不影响。dp的复杂度为O(k*2^2k)。


2011.5.12
coeforce Yandex Qualification 1 E (81E) tree dp
         给出n个点，每个点都只有一个朋友，也就是出度，现在要把人两两配对，而且使得至少其中一个是另外一个的朋友（朋友是单向的），问最多配对多少。顺便因为人有性别，问最多配对的情况下最多男女配对是多少？还要输出方案。
         由于每个点最多只有一个出度，于是一定有环，而且绕着环的都是一些树，那么,dp分两步来做，首先用scc找出环，然后对于连接到环上的树进行dp：
         f[x][0/1]表示x这个点是否参与匹配的最大匹配数。
         f[x][0]=sigma{ max{f[j][0],f[j][1]} }
         f[x][1]=max{ f[x][0]- max{f[j][0],f[j][1]} + f[j][0] +1}
         上面的应该不难理解，接下来要对那个环（每个连接块有且只有一个环）进行dp，考虑起点为start，然后断开和last的边，对链进行类似的dp：
         g[x][0]=f[x][0]+max{g[x-1][0],g[x-1][1]}
         g[x][1]=max{f[x][1]+max{g[x-1][0],g[x-1][1]},f[x][0]+g[x-1][0]+1}
         
         如果start和last连在一起，那么初始条件：
         g[0][0]=-oo  g[0][1]=1+f[0][0]
         答案为g[last][0]
         如果start和last不连在一起，那么：
         g[0][0]=f[0][0]   g[0][[1]=f[0][1]
         答案为max{g[last][0],g[last][1]}
         至于求方案则倒推回去就是了，只是写起来麻烦。。


2011.5.14
UVA 12000 World Final Warm Up II  状态dp+矩阵
    给出n个数1~n，然后进行排列，如果对于i，排列之后的位置和原来的位置相差不超过k，那么就是k排列。现在给出n和k，问k排列的个数。
    首先由于k<=3,所以考虑一个状态dp  f[i,s]表示前i个数，而且以i为中心的填的状态为s的方案数(其实只需要考虑i左边k个和i右边k-1个就可以了)，然后f[i,s]= sigma{f[i-1][s']}。其中s'能够推到s的状态的情况：如果s'最低位为0，那么必定需要i-1去填，否则就在1~2*k位中选择一个空的填上，从而转移到s。由此而建立一个矩阵A。
    然后对于给出的n，求出B=A^n，然后B[1<<k-1][1<<k-1]的值就是答案了，因为位置0左边默认都是1,然后n位左边也全部是1.

2011.5.15
UVA 12005 World Final Warm Up II 利用整除性计数+开三根分解质因数
    给出c，然后问有多少个a,b使得满足c=ab-(a+b)/2+1。把式子变化一下得到(4*c-3)/(2*a-1)=(2*b-1)。那么由于利用整除性，(2*a-1) | (4*c-3)，于是问题就在于求4*c-3的因数有多少个。那么由于c~10^14,根号算法是很容易超时的，不过可以用开三根来做。考虑d=4*c-3的所有素因子，除掉所有<d^(1/3)的，那么剩下的只有三种情况：单个素数，2个不同素数积，一个素数的平方。然后利用miller_rabin判一下素数和平方就能得到因子个数了。

    
UVa 12003 World Final Warm Up II  分段+二分
    给出n个数a1..an，有m个操作，每个都是（L，R，V，P）表示求出L~R当中比v小的个数，设为k，然后k=u*k/(R-L+1),(u常数)，那么把a[p]改为k,继续做。
    其实就是需要一个数据结构，支持区间有序查找，用分段来做，每个段设为500，然后左右暴力，中间的二分就可以了（要特别注意边界的问题）。

2011.5.16
codeforce 83D  容斥原理
          给出a，b，和k，求出[a,b]中那些最小因子为k的数的个数。
          k如果不是素数，则肯定为0。否则可以考虑1~n内最小因子为k的个数。然后再利用容斥原理，n/k 再加减那些k和比k小的素数的乘积为因子的那些数，最后就能得到答案了。而且由于2×3×5×7。。×23已经超过2*10^9了，也就是说，最多只有9个素数的乘积，容斥还是很快的。


2011.5.17
codeforce 76A 排序+消环最小生成树
          给出一个无向图，每条边有两个值gi,si，然后要找出一个A,B，使得对于图中任意两点，总存在一条路，使得路上每条边gi<=A,si<=B,而且求出G*A+S*B最小值（G，S已给出）。
          首先对于生成树，存在一条定理，最小生成树的最大边是所有生成树中最大边最小的。然后对gi排序，从小到大枚举gi，然后求出只能利用1~i这些边生成的si的最小生成树，那么找出这些生成树的最小的就是答案了。这里需要利用到消圈算法，对于kruskal算法，由于边已排序，因而不需要消圈，但是这里由于si无序，因而需要消圈。


2011.5.19
topcoder TCO11 Qual 2 1000
    一个函数f(s),然后f的值是s的各个数字的和，一直做下去，直到f的值为个位数为止。给出一个很大的s，问f(s)的最终值（这是第一步）。然后给出一个范围，问这个范围内有多少个这样的x，使得存在一个y，y*f(y)=x。
    求f(s)，需要先看规律，然后利用归纳法证明。观察f(s)发现f(s)=s%9，若f(s)==0,那么f(s)=9。这个可以通过归纳法证明。
    
    
srm     504.5  观察+暴力
        有n个人，每个人有ai元，现在有m元可以捐给他们，每次求出平均数avg，然后捐x元给最穷的那个，假设为a1，并且使得a1+x>avg, x要最小。一直这么做下去，直到分完钱为止。问最终每个人都分了多少钱。
        有某人证明过，（或者需要观察一下），如果模拟一直做下去，那么假如m够大，那么很块就能达到所有人的钱数都相同的状态（可以证明每次都使得最小和最大的差距变小1/n^2，也就是最多n^2次就能达到平衡），然后就平均分下去，最后剩余的继续模拟。(Orz一下证明的人。)


2011.5.25
codeforce 85 D  线段数
          给出三个操作，add x,del x，sum。add,del为对数集加入/删除某个数，然后对sum操作，将数集从小到大排序，输出sigma{ ai |  i mod 5==3} 。
          先进行离散化，然后维护一个线段树，每个节点维护一个移位值和一个mod的向量，表示这个区间mod 5=xx的和为多少，然后利用类似懒惰删除的方法，每个节点维护一个“覆盖值”，其实就是移位值，表示这个数向右边移动多少位。每次加入一个数x，那么[x+1,len]这个区间都加1的移位值，然后再修改x，向上更新的时候先把儿子的相应位加起来，然后根据当前节点的移位值移动后作为本区间的和向量。最后每次sum操作的时候将1号节点的mod 5=3的那个值输出就可以了。

codeforce 85C    binary search /trees  
          给出一个二叉查找树，每个节点key值不同，然后还有q个询问qi，qi和key两两不同，每次对于qi，在这个二叉查找树中进行查找，然后这个过程中有且只有一次出现错误，也就是说本来要走向左儿子，却走向了右儿子。然后最终会到达某个叶子节点，然后得到叶子节点的值，现在问对于每个qi求出期望的叶子节点值。
          我们考虑到一个问题，也就是说假如出错以后，走的路径是固定的，这个十分重要。然后我们只考虑对于单独的一个qi，模拟查找过程（假设最终叶子深度为d），然后每经过一个点，求出走错那个方向的最终叶子值（其实就是错误方向的子树的最大或者最小值，这个可以用装下所有key的set来求），那么这个方向贡献的期望值为key_of_wrong_leaf/d ，因为在查找过程的d步中，每步的错误是等概率的（这个也是解题的重要思路之一），于是模拟走完之后就能得到qi的期望值。
          但是如果对于每个qi都这么做会超时，于是我们可以考虑先把qi排序，然后一次过“扔”进树中，然后每次记录当前节点对应于某个范围内的qi，然后根据当前节点key，将范围进行左右切割，并且两个部分都记录在当前点走错的期望值（对于单独的一个部分，这个期望值都是相同的，因为这个部分的qi都比当前key要小/大），于是就需要最多nlogn的复杂度就完成所有qi的计算（感谢set的使用，简化了很多东西）。



2011.5.28

codeforce 85E 二分+黑白染色
          给出n个点，然后分成点集，每个点集的代价为这个点集中曼哈顿距离最大的两个点的距离，总代价为两个点集的最大值，现在问最小的代价为多少，然后最小代价有多少种分配方法？
          首先求这里最大中求最小的一般会想到二分然后判合法。这里就很显然先二分答案，然后合法图是否分成小于等于2个连同块，那么对于2个连同块，只有2种方法，对于1个连同块，要计算分成两个连同块的切割方案数不容易计算。
          然后一个很重要的条件就需要用上，因为是分成两个连同块，那么就相当于对于不合法图，我们进行黑白染色，因为不合法图相邻的不可能在同一个点集中，每个染色方案对应于一种切割方案。于是问题转化为求不合法图中有多少种黑白染色方案。这个问题就简单很多了，先看是否可以黑白染色，每个合法块只有2种方案，然后各个块之间相乘就可以了。
          不过貌似还有一种O（n）的方法计算，目前表示还不太懂。


2011.5.29  
codeforce 86D 数据结构
          给出n个数ai,然后t个询问[l,r]，问在[l,r]这个范围里面，计算Ks*Ks*S,其中Ks为s在这个范围内出现的次数，然后求这个范围内所有的Ks*Ks*S的和。
          解决的关键有两点，第一个是，假如现在已经知道一个区间的和，而且也知道各个数出现的次数，那么现在加入一个数，然后总和可以在O（1）中计算出来，譬如已知：(Ks-1)*(Ks-1)*s 的值，如果加入的数为s，总和只需要+(2*Ks-1)*s就可以了，删除一个数也是类似。因此如果区间没有包含关系，那么所有的询问都能在O（n）内完成，但是所给出的区间是有包含关系的，这个怎么解决呢？
          分段！p=sqrt(n),每个询问判断左右分别在哪个段，然后给所有询问排序，先按照左边段，然后再按右边。由于原始不分段的方法算的话，会造成相邻的两个区间，左边差别不大，但是右边是一长一短，那么就会退化，按照段分，就会先把临近的先走完，才会走远的，而同一个段最坏情况下走的次数为n/p*n,于是让p=sqrt(n)使得这个复杂度最低，因而可以在O(n^3/2)解决。



2011.6.5
codeforce 73D 图论+贪心构造
          给出一个n个点的无向图，这个图不一定连通， 每个连通块最多能和其他连通块k个隧道，然后每个点只能接一个隧道，也就是说每个连通块最多接min(k,ci)个隧道(ci为连通块大小)。现在需要让整个图都连通，那么可以建造隧道或者普通的路，普通路会把不同的连通块连接成一个连通块，隧道则可以区分连通块。现在问最少用多少个普通路可以让整个图连通。
          先缩点，然后每个点求si=min(k,ci)。缩点之后的图共有comp个点。考虑k=1，那么显然就是comp-2个。现在k>=2，首先对所有si>=2的连成一条链，然后剩下的肯定只有si=1的，那么显然si=1的肯定是只有一个点的，然后一个点的两两用隧道互连，这样子就连接了s/2条边了。然后将si=1的块用普通路和si>=2连起来的那条链对接，由于k>=2，所以这样就构造出一种方案使得能够充分利用了s/2条隧道把整个图连接起来。
          总的结果就是:comp-s/2-1。


codeforce 76F 最长上升子序列
          在一个x,t坐标上，给出一些事件点(xi,ti)表示在ti时在xi上有馅饼，只能在x坐标上跑，速度为v，然后问如果初始在（0,0）,那么最多可以捡到多少个馅饼，如果可以随意开始位置，那么同样最多可以捡到多少个馅饼？
          对于每个事件(xi,ti)，考虑(xi,ti)如果能到达(xj,tj)，那么必须符合：abs(xi-xj)<=(tj-ti)*v，这里假设tj>ti，然后拆出绝对值，得到充分必要条件<==> xi+ti*v<=xj+tj*v && -xi+ti*v <=-xj+tj*v ，如果ti<tj，由对称性可以得到相同结论。现在让pi=xi+ti*v,qi=-xi+ti*v，那么当且仅当pi<=pj &&qi<=qj 时i能到达j，然后先按pi排序，再qi，然后第二个答案就是求qi的最长不下降子序列，对于第一个，可以加入一个点（0,0）并且显然加入这个点不会使第二个答案更优，因而可以直接加入，然后从后往前，求-qi的最长不下降子序列，注意判断最后一个要用>=，用>来判断加入到最后一个的话会出问题。


2011.6.8
codeforce  87C 博弈论sg函数
           游戏一开始给出一堆石子共n个，每次可以把一堆石子分成k堆，并且满足：a1>a2>a3>...>ak>0,而且对于相邻的ai-1=ai+1。两人轮流做，问最后谁获胜？
           对这个约束条件整理一下，k<=sqrt(n)的，然后对于每一堆石子，就是一个子游戏，对于这堆石子可以进行的操作，也就是分成k堆的操作的结果进行mex运算，而分成的这k个堆，由于已经变成了独立的游戏，因而要通过xor运算，所以总的就是对于所有分的情况的结果进行mex运算，而对于每一种分法所分出来的k堆，则进行sg的xor运算后作为这次分堆的结果上传给mex运算。然后。。。就这样咯。

codeforce 87D 树+并查集+dfs
          给出一棵树，边有权，任意两点之间都有一条路径，找出路径上最大的那条边，然后那条边就标记一次。然后问标记最多的是哪条边。
          考虑两种特殊情况，第一种是所有边都相等，那么一次dfs就可以了，而第二种特殊情况是所有边不同，那么就可以把边从小到大排序，然后用并查集就能求出以这条边为最大边的路径数目。现在就需要解决有相同边权的情况。考虑现在同时把所有相同的都加到图中，然后会把多个连通分量合并，那么假如把之前的连通分量缩点，这就形成了一个所有边权都相同的新图，然后利用第一种方法就可以求出这些相同边权的路径数。


2011.6.17
codeforce 89A  贪心
          给出一行n个盒子，每个盒子有石头ai个，现在要偷石头，然后每次移动可以把一个石头从一个盒子移动到另外一个盒子，或者直接拿到口袋中，或者从口袋放到盒子里。保安每隔m分钟就会对相邻的两个算一个和，如果和上一次检测的不同，那么就会报警。并且保安总共会检查k次。问最多可以偷多少个石头。
          考虑一种偷石头的方案并且不被发现，如果对于偶数个盒子来说，那么是没办法偷到石头的。对于奇数个盒子，那么将偶数号盒子（0开始）放一个到奇数的盒子，然后从剩下的那个唯一的偶数号的盒子中拿到袋子里，这样就不会被发现。并且能够拿的最多个数是所有偶数号石头个数最小值。接着发现要偷一个石头，需要走(n+1)/2步，每轮能拿m/((n+1)/2)个，总共m/((n+1)/2)*k个。然后之前的最小值取最小即可。


2011.6.23
codeforce 91B 模型转化，并查集
          给出一个无向图，逐次加边，然后每加一次都要进行计算当前这个图能形成多少个base，一个base由多条回路（边不同，点可重复）组成。
          做法是逐次加边，ans=1,然后如果相连的点是在同个连通块，则答案乘以2,否则无视，最后为ans-1.
          将当前的图转化为方程矩阵，行是边，列是点，然后对于一些行的集合（也即边的集合）如果构成base，那么其xor的和为0。那么对于新加进来的边，如果连接的两个点不在同个连通块，那么就不存在一个包含这条边的集合能够构成base，所以答案不变，否则如果在同个连通块，那么必然可以消去这一行，然后消去之后和原来的性质一样还是行的集合xor和为0则形成base，既然这行为0,那么这条边可以存在也可以不存在，于是答案×2。



2011.6.27
codeforce 73E 数论
          给出n个数ai,还有一个猜数的范围x,问最少选出多少个ai使得对于[2,x]的每个数n，n/ai 上取整之后的数的表示方式各不相同。（譬如列出一个表格，行是n,列是ai，使得相邻行之间不会完全一致。） 
          有一个很重要的性质，对于y=[2,x],  令 b(y,i)= round_up(y/ai)，那么b(y,i)<b(y+1,i)的充分必要条件就是 ai | y ，那么就是说，选出来的ai集合必须满足对于每个y，至少有一列的ai能整除该y，于是怎样的ai集合能够满足这个要求呢？
          [2,x)内的所有质数。假设少了其中的一个质数pi，那么pi和pi+1这两行是相同的，所以这是最少的个数，而且对于所有的[2,x]，都至少有一个pi能够整除之，所以是最多的，因此就是就是所有质数的个数。注意如果x=2,那么是0,如果有ai=1，那么就是1，否则只需要找出min(x,20*n)的质数看是否都有。


2011.7.1
codeforce 91E  线段排序+数据结构
          给出n个建筑物，每个建筑物i在时刻t的高度为ai+bi*t。然后有q个询问，每个询问li,ri,ti，问在[li,ri]中在时刻ti最大的个建筑物是哪个。
          分段d=sqrt(n),然后对于每一段，给所有的建筑物ai,bi排序，按照ax>ay || (ax==ay && bx>by)来排，然后利用类似于graham的方法找出一条递增的线段序列，用于后面进行查找。然后还需要对询问[li,ri,ti]按照ti从小到大排序，每一段记录一个线段的index，表示当前线段在当前时刻最大的那条线段是序列中第几个，然后对询问按照时间先后进行查找，把询问区间拆成段，覆盖不完整的段直接做，覆盖完整的段就通过那个index然后看在当前时刻ti是否后面的线段>=当前的线段，然后移动index（因而配合index和询问的排序可以做到询问阶段总共只需要O(n+q)的复杂度），然后就可以解决这个问题了。
          做这题时一个困扰了好久的问题是移动index的时候，如果当前的等于后面的一个时，也要移动，否则这个index会卡在那里而得不到更优解。


2011.7.4
hdu3518 trie统计
        给出一个字符串，问有多少个子串出现至少两次并且不重叠。
        对于trie树有一个性质，将一个字符串所有后缀构造成一个trie，那么trie树的节点数代表了不同的子串的数量。然后将这个字符串从后往前构造trie，并且沿路标记，每个子串都记录从后往前最现出现的位置以防重复。然后边构造边记录和哪些点出现了至少两次并且位置不重叠。如果直接做会MLE，改成链表会超时，然后由于出现两次并不重叠，那么加入的长度只要小于等于一半就可以了。

2011.7.5
hdu 3480 斜率优化DP
    给出n个数，然后分成m个集合，每个集合的代价为(max-min)^2，max,min为集合中的最大最小元素，问划分的最小代价是多少？
    先把n个数排序，f[j][i]表示用前i个分成j个集合的最小代价.f[j][i]=min{ f[j-1][k]+(a[k]-a[j])^2} ,  j<=k<i 。然后考虑两个选择k1<k2,并且k2比k1优的情况，f[k2]+(a[i]-a[k2])^2<f[k1]+(a[i]-a[k1])^2 ，然后把k1,k2放到一边，得到  
    (f[k2]+a[k2]^2- (f[k1]+a[k1]^2)) / 2(a[k2]-a[k1])  <=a[i] ,用g(k1,k2)来代替左边的式子，那么g(k1,k2)<=a[i]就说明k2比k1优（k1<k2），那么k1就可以忽略了，维护一个队列 k1,k2 ...km ,使得ai<g(k1,k2)<g(k2,k3)<...< g(km-1,km)，然后由于ai递增的，若g(ki,ki+1)<=ai，那么ki就没必要在队列中了，然后队列的第一个就是最优选择，接着把i加进队列后面，维护g()的有序性就可以了， 注意<=的也要删除。

 
2011.7.6
hdu3484 矩阵，枚举，trie
        给出两个01矩阵A,B，有两个操作，把某一行的01兑换（0变1,1变0）,或者交换任意两列，问A是否可能变换到B。
        枚举A的哪一列和B的哪一列对应，然后每一行是否要翻转就确定了，然后就需要把B的每一列加入到trie树中，然后看A的每一列是否都唯一对应上。复杂度看上去是O(n^4)，但由于这个问题存在两难性，也即如果每行01个数不相同，那么翻转情况就马上确定了，否则01相同的比较多则很容易就找到答案，所以复杂度是很难达到O(n^4)。

hdu3481   DP
          网上找的解题报告：
问长度为n的bad serial串的个数。bad serial 指每一个长度为m的子串都不是good serial    (good serial指要么全相同，要么全不同)，所以bad serial就是两个以上不同，但不能m个都不同
    dp[i,j](1<=j<m)表示长度为i的串最后j个数字互不相同的串个数（即str[i-j]与末尾这j个数中一个相同）
    考虑dp[i+1,j+1]
    (1)dp[i+1,j+1]+=dp[i,j]*(m-j)   选一个与i及之前j个数字都不同的
    (2)dp[i+1,k]+=dp[i,j]  2<=k<=j  选一个与i之前j个数字某个相同的 str[i+1]=str[i+1-k]
    还有一种特殊的就是dp[i,1]，即末尾几个数字都相同的合法串个数
    (3)dp[i+k,1]+=dp[i,j]  (1+k<=m-1, j>1||i==1)
    如果j=1的话有可能一连串都相同导致不合法，要j>1
    特殊的是i=1，j=1就可取，因为1之前没有数字，认为与1不同（跟j>1一样）
    心得：只考虑最后一个字符（第i+1），考虑怎么合法过来的
           dp转移时，由之前的转移过来难写的话，写成从当前扩展到之后的！
           按照题意定义状态，这里要2个以上不同，定义末尾有j个不同（j=1时是特殊情况，即末尾可以几个连续相同）

2011.7.14
sicily 1951 矩阵乘法
      有n<=10个格子 ，每个i格子在t时刻的权值为p[i][t%len[i]] ,len[i]为周期。然后每次可以停在原地或左右走一格，问T<=10^16步以内最多可以得到多少权值和。
      原始方法：f[t][i][j]表示t时间，从i到j的权值最大为多少，h[t][i][j]表示在t时间内，从i到j的最大权值（注意和f[t][i][j]的区别）, f[t][i][j]=max{f[t-1][i][j+-=1]+p[j][t%len[j]]}, h[t][i][j]=max{f[t'<=t][i][j]}。 先把所有循环的lcm都求出来设为m，然后把m以内的f,h都求出来。然后以m为单位，做一个T/m的矩阵乘法, 分别记录g[i][j]表示t步从i到j的最大权值，还有h[i][j]表示t步#以内#i到j的最大权值，然后类似快速幂的方法对g,h求值就可以了。最后结果要对剩下的T%m个遍历一次就可以了。注意为什么要以m为单位的原因在于，二分之后，每个幂次的dp情况是一样的，如果以1为单位，那么dp时取权值时是难以确定的，因为即使幂次相同，由于所在时间不同，权值是不同的，如果以m为单位，无论在哪个时间，所取的权值情况是一样的。

矩阵乘法扩展：
      给定一个有向图，求s到e边数不超过K的路径的最大边最小。对每个点，增加i到i的-oo的边，然后矩阵乘法K次就可以了。
      给定一个有向图，求s到e边数在[K1, K2]内的路径的最大边最小。先用原矩阵G0乘K1次，然后再用增加了i到i的-oo边的矩阵G乘K2-K1次，也即G0^K1*G^(K2-K1)。


2011.7.15
topcoder SRM 377 1000 矩阵乘法
         一个单词有P个元音字母和Q和辅音字母组成，然后元音必须出现在辅音前面，元音和辅音都最多可以出现N次，也可以0次，但不能是空串。然后还有每个单词重音可以不出现，可以出现在一个字母上，或者出现在一个元音和一个辅音字母上，问这样的单词有多少个。
         由于元音和辅音独立，可以只考虑元音。那么现在问题变为字符集为K，长度为N的单词有多少个（可以为0长度）。那么Sn=Sn-1 + (n+1)*K^n 。这个式子不能直接用来做矩阵乘法，变换一下还发现Sn=K*Sn-1 + sigma{k^i | 0<= i <=n+1},  然后利用矩阵乘法来做 初始矩阵为[Sn , sigma{K^i | 0<=i<=K+1}, 1]，单位矩阵:[ [K, 0, 0], [1, K, 0], [0, 1, 1]]，做N次结果就出来了。


2011.7.16
codeforce 95E 背包
          给出一个图，然后分成若干个联通块，现在问加最少的边使得连通块大小为幸运数(由4和7组成的数字）。
          找出不同大小的连通块的个数，然后问题就转化为多重背包问题。。。

codeforce 93D 矩阵乘法
          4种字母bwry，有一些2个字母组合不能出现和一些3个字母组合不能出现，而且相邻的不相同，问长度在L到R之间的字符串有多少个。并且翻转也算相同。
          现在先只考虑长度刚好为N的字符串个数，并且不考虑回文的问题，那么令f(N)为这样字符串的个数。如果直接f(N)/2的话，那么那些回文因为只出现一次而被错误除掉，所以要加上长度为N的回文的个数然后再除2才是真正的数量也即(f[N]+f[(N+1)/2])/2。然后就解决了长度刚好为N的问题。
          那么对于长度在L到R之间的怎么解决呢？考虑长度为1~N的总数，然后相减就可以了。然后构造一个合法转移矩阵xy -> yz （最多有8种情况），然后增加一维用于记录总数，总共9维，然后初始向量为[1,1,1,,.(8个)..1,4]，最后一个表示长度为1的个数，这个向量乘以矩阵之后得到了长度为2的以各个状态结束的情况数，而最后一个为长度为1~2的情况的总数，所以把这个矩阵快速幂N-1次后就可以得到结果了。


2011.7.18
codeforce 95D 计数类DP
          给出K,然后问在区间[L,R]之间的所有数x中，把x当做数字串来看，定义4,7为lucky digit, 并且存在至少一对lucky digit的距离<=K，那么这个x就算作lucky number，然后就问[L,R]有多少个lucky number。
          这种属于计数类DP，可以求出1~N的有多少个，然后相减就可以了。由于求存在至少一对的，那么我们就求不存在这样一对的有多少个，求补就是结果了。然后定义f[len,0/1] 表示长度为len，0为最后一个数字是4或者7的有多少个，1为最后不是4和7的有多少个，那么f[len][0]= 2* sigma {f[len-i][0]* 8^(i-1) | i>k} ，f[len][1] = 8*(f[len-1][0]+f[len-1][1]) 。然后对于N从高位到低位，记录高位起最后一个lucky digit在哪里，这样就能确定后面哪里开始才可以放4和7,令这个位置为pos，当前枚举的位置为i,那么i到pos中间的就有8^(pos-i)种情况，乘以(f[len-pos][0]+f[len-pos][1])就是当前前缀的结果，类似这样的思想去逐位做就可以了。
 
codeforce 93E 容斥原理
          给出a1...ak，相互互斥，然后问[1,n]里面不能被任意一个整除的个数。
          经典的容斥原理，但是n<=10^13, k<=100，直接做是不行的，这里有个公式F[n][a1..ak]=F[n][a2..ak] - F[n/a1][a2..ak]，也就是不被a1..ak任意整除的个数为不能被a2..ak任意整除的减去能被a1整除的那些数中不能被a2..ak整除的。
          做的时候将那些n比较小的（n<=10^5）的结果都记录下来，空间换时间，这样才能过掉。

2011.7.19
codeforce 71E 状态压缩DP
          给出n个元素，每个元素都有唯一的原子质量，然后再给出k个合成元素，问如何分配这n个元素来进行原子反应得到这k个元素，而且n个元素每个用且只用一次。
          由于n<=17,考虑压缩状态的递推，那么令状态dp[s]表示用了s这些元素的情况下，下一个要合成的元素是哪个。对于s，将s的补集的每个子集都找出来，看剩下的是否能组成
下一个要合成的元素，假设i状态能组成，那么转移到 dp[s | i] = dp[s] +1，因此对于状态s | i，下一个要组的元素为dp[s]+1，因为合成元素的顺序是无关系的，所以可以这样规定按顺序合成。

codeforce 69D sg博弈
          在平面坐标上两人博弈，棋子开始位置为x,y，有n个向量xi,yi可以作用在棋子上，离开0,0点距离超过d的为输，并且每个人最多只能把棋子相对y=x翻转一次，问先手胜负。
          其实发现那个翻转是无用的，无论必败方是否翻转，必胜方总可以再翻一次，结局不变。然后就充分利用了map，求出每个点的sg函数，。。即可。

2011.7.24
codeforce 60E 矩阵乘法
          给出n个数，从小到大a0...an-1，每次在相邻的数中间生成一个新的数，大小为相邻数的和。经过x轮之后，把所有数都从小到大排，再做y轮，问最后所有数的和是多少？
          首先通过找规律，每轮做完之后，所有数总和sum(x) = sum(x-1)*3 - a[0] - a[n-1]。那么通过矩阵乘法可以找到x轮之后的总和，然后对于排序，最小的依然不变，但是最大的数，通过找规律，发现是F(x)*an-1 + F(x-1)*an-2 ， Fx是Fabonacci数，F-1=0。然后也是通过矩阵乘法就可以求出最大数，再做y轮就可以得到所有数的总和了。

codeforce 60D 数学+并查集
          给出n个数a1..an，如果ai,aj能和一个数b形成完美三角形(x^2+y^2=z^2)，且x,y,z互质。那么i,j相邻，问最终有多少个连通分量。
          对于这样的三角形，有一种形式(x^2-y^2, 2*x*y, x^2+y^2) ，然后可以通过这个形式来找出x,y的范围，然后枚举x,y，看三个中是否至少2个在里面（map或者数组），然后合并，最终查找连通分量个数就可以了。


codeforce 60C 质因数分解，暴力
          给出一个无向图，n个点，m条边，每个点有权值，并给出每条边的两个点的权值的gcd和lcm，求出原图中每个点的权值，或者无解输出-1。
          由于ai<=10^6，所以只能有最多7个不同的素数是未能确定的，因而可以对于一个点，暴力2^7枚举素数的分配情况，然后一个点的值确定了，那么这个连通分量每个点的值也确定了。而且还要判断生成出来的值是否符合给出的gcd和lcm的要求。
          充分利用不同素数之积呈指数增长的条件也可以简化解决方法。


codeforce 55D 计数类dp
          给出范围[L,R]，求出这个范围内的beautiful number，定义一个数能被它所有数字整除则为beautiful number。
          先进行dp，由于1~9的LCM为2520,所以只需要知道mod这个数的余数就知道其他数字组合的余数，f[len][rem][st]表示长度为len的，mod 2520余数为rem，用st来表示使用了哪些数字（不包括0）的数字个数，这个可以通过递推来求。然后就从高位到低位，逐位计算，记录前面的数的大小和使用了哪些数字，然后就可以在后面找出f[i][rem][news]使得rem和前面的加起来能够被所使用的数字的LCM整除，把这些f[i][rem][news]加起来就是结果了，注意要优化一下才能过。。
          由这个题目可以发现，涉及到整除的dp，状态里一般都带有对于某个mod的剩余值，这种思想可以借鉴一下。


2011.7.27
zju3511  栈的运用
         给出一个凸多边形，然后切若干刀，并且保证切线不会相交，问最后切出来的边数最多的多边形是多少条边。
         从任意一个点开始，把点加进栈中，遇到有切线连接当前点和栈中的点，则退栈，而且枚举和当前节点相连的切线要按照距离由近到远，这样做能保证每次退栈的多边形都是最外边的，中间不会有切线，从而按顺序找出所有的切多边形。


2011.8.1
codeforce 12D 数据结构
          给出n个人，每个人有三个参数b,l,r，如果存在某个人三个参数都比这个人大，那么这个人就会挂，问最后有多少个人挂了。
          先排序，按照bi>bj || (bi == bj && li < lj)来排序，然后利用树状数组统计比li大的那些人中最大的rj是否比ri大，是则这个人要挂了，然后根据li的hash位置，把ri加入到树状数组，继续统计。

2011.8.3
codeforce 55E 两个指针
          给出一个凸多边形，给出一个点，问有多少个三角形包围这个点。
          思路上反过来，可以先计算出不包含这个点的三角形个数，可以枚举一个点A，然后找出一条最远的对角线连到B，使得AB之间没有这个点，那么AB之间有多少个三角形就可以直接算出来，然后移动A，B也只需要跟着移动就可以了，这样就能在O（n）内完成计算。

codeforce 70C 统计
          两个数a,b,如果a*b = rev(a)*rev(b) ,rev(x)为把数字x按数字翻转的数，那么a,b称为幸运对，然后问在 X =[1,maxX], Y =[1, maxY] 里面找出一个范围X，Y使得1<=x<=X, 1<=y<=Y，有至少w对幸运对，并且X*Y最小。
          首先找出求幸运对的快速方法：把式子转化一下得到a/rev(a) == rev(b) /b ，然后可以map的方法找出总范围里的幸运对，然后维护两个map数据结构m1,m2，分别记录x的rev(x)/x的数量和y的rev(y)/y的数量，考虑一个长x宽y的矩阵，如果删去x，那么幸运对数减去m2[x/rev(x)],并且m1[rev(x)/x]--，对y也有类似的操作。 然后从x=maxX, y=1开始，每次x递减，y递增，相应修改m1和m2的值，维护使得包含的范围的总数>=w,并记录x*y最小值。


2011.8.4
codeforce 54C 统计+概率dp
          给出n个区间[Li, Ri]，这个区间的每个数出现概率相同，如果一个数最高位为1则为幸运数，现在问这n个区间出现至少k%的幸运数的概率。
          先对每个区间求概率p[i]为最高位为1的概率，然后dp：f[i][s] 前i个有s个幸运数出现的概率：f[i][s] = f[i-1][s-1] * p[i] + f[i-1][s] *(1-p[i]); 最后统计有至少k%的概率总和就是结果。裸题= =

codeforce 53E 状态压缩统计
          给出一个图，n<=10,删去一些边，使得形成一棵树，并且叶子刚好有k个，问能形成多少种树。
          状态f[sm][sd]表示使用sm这个状态的点，并且sd这个状态的点是叶子的方案数。那么枚举一个不在sm上的点i,然后找出和i相邻的并且在sm中的点j，然后根据j是否在sd中，递推出新状态。这里需要注意重复计算的问题，由于达到同一个sd状态有多种方法，但其形成的树的形状是一样的，对新状态sd，有__builtin_popcount(sd)种方法可以递推过来，但是其形状是一样的，因而对每个f[sm][sd]计算之后要除以__builtin_popcount(sd)，初始状态对每条边x-y, f[1<<x | 1<<y][1<<x || 1<<y] =2。 最后把所有f[(1<<n)-1][sd {__builtin_popcount(sd) ==k }] 的加起来就可以了。


2011.8.5
codeforce 57C 组合数学
          给出1~n，然后组成排列（数可以重复），使得要么非递增或者非递减，问有多少种方案。
          考虑从n个里选出多少个出来，然后再考虑每个该重复多少次，那么就是 sigma{ C(n,r)*C(n-1, r-1) | 1<=r<=n } 。

codeforce 50D 二分+概率DP
          给出n个点的位置，还有一个核弹的位置x0,y0,现在要求最小的核弹爆炸半径R，在R内的所有位置都被摧毁，在R外的存在一个几率会被摧毁P(D,R) = exp(1- D^2/R^2)，D为该位置和核弹的距离，R为核弹半径，并且给出摧毁至少k个位置的概率至少达到epson,求出最小半径R符合这些条件。
          二分半径R，然后进行概率DP，f[i][j]表示前i个摧毁j个的概率，然后判断一下是否符合条件即可。

codeforce 51E 矩阵+统计
          给出一个无向图，求出所有点不同的长度为5的环的个数。
          记原图为A，先求出长度为2的路径B[i][j]，然后枚举一条边i-j, A[i][j]，并且枚举k，i-k和j-k长度为2+2，再加上i-j刚好为5，统计sigma { (B[i][k]-A[j][k]) * (B[j][k] - A[i][k])}。并且注意特殊情况i-j-k相连时，答案要减去deg[k]-2。


2011.8.6
codeforce 101D 树+贪心+统计
          给出一棵树，边权为走需要的时间，从1号点开始，开始时间为0，遍历所有点，每次经过边都要算时间，把第一次到每个点的时刻加起来，记为TOT,求最小的TOT/(n-1)。
          题目其实也是求对于每个点按照什么顺序来遍历儿子，考虑按照s1,s2,...sn的顺序，并且其子树节点数分别为k1,k2...kn,子树边权和的2倍为T1,T2,....Tn，那么每个子树自身所花费时间为t1,t2...tn，那么总和为(t1+t2+..+tn) + k1*0 + k2*(T1) + k3*(T1+T2) +...+kn*(T1+T2+...+Tn-1)，考虑对调ki和ki+1，那么假设原来的就是最优，那么得到Ti/ki < Ti+1/ki+1。于是只需要根据Ti/ki排序就得到了遍历的顺序，然后模拟做一次就得到答案了。

codeforce 70E 树DP
          给出一棵树，在树中建立中心，每建立一个中心花费k，其他没有建立中心的花费为d[len]，len为这个点离它的中心的距离（树的距离，边长都相同），d事先给出，问总的最少花费为多少。
          树dp，假设根就是1，然后dp[i][j]表示i这个节点为根，以j为中心的最少花费(还不算当前选择中心的k花费)，c[x]表示x选择的中心， dp[x][i] += min{ dp[v][i], dp[v][c[v]] + k }，对于子节点，要么选择和x一样的中心，要么选择自己的中心（所以要+k），然后x在dp[x][i]中选择最小的作为当前的中心c[x]。结果就是dp[0][c[0]] + k。但是题目需要求出方案，那么可以从根开始，根据最终结果反推出子节点的选择。如dp[i][c[x]] < dp[i][c[i]] + k，那么c[i]就是c[x]，这样两次dfs的DP就能把结果和方案都求出来。
          这道题目的一个思想就是，要求中心（或者区域的划分）变成对于每个点求它所选择的中心，从每个点出发，然后利用树dp经典的方法，两次dfs，求出最优解和根据最优解找方案。


2011.8.9
codeforce 49E DP
          给出2个字符串,s1,s2,和给出一些转换规则（固定的）如c->ba，c->cc，如果存在一个字符串s3,使得s3经过转换，可以得到s1,s2，那么s3就是最近祖先，现在求s3最短长度。
          dp[i][j]表示s1前i个，s2的前j个的最近祖先的长度，然后枚举mi,mj，使得mi~i，mj~j能够通过这些规则由相同字符转换而来，设str1[i][j]表示s1的i~j可以由哪些字符转化而来(这个可以用1<<26的压缩状态表示，并且进行预处理)。如果str1[mi][i] & str2[mj][j] > 0，那么就说明mi~i,mj~j可以通过相同的字符转化而来，此时dp[i][j] = min{ dp[mi-1][mj-1] + 1}。

2011.8.10
codeforce 103D 分段统计
          给出n个数wi，和m个数列ai,bi，对于每个数列，将所有在n范围以内的w[ai+k*bi](k>=0)求和，输出,(n,m<3*10^5)。
          直接暴力是不行的，不过n*sqrt(n)的算法是可以接受的。先对数类进行排序，先按照bi，相同则再按照ai%bi的大小排。这样子，如果bi == bj, ai%bi == bj%bj 的话，则记为i和j相同，由于要算和，那么对于相邻不相同的序列，需要重新计算和，把n个数分成段，每段为sqrt(n)个，算和的时候把同段的和都算在一起，然后求ai+k*bi的和时，在临界区直接扫，其他地方则通过段和来加起来，这样保证每个询问最多由sqrt(n)的复杂度来处理。至于求段和的复杂度，平摊之后不超过O(n*sqrt(n))。

codeforce 62E dp求网络流
          给出格点图，n*m的，n<=5, m<=10^5，还有对于每一列，第一行和最后一行相邻（环形）。并且格点之间有容量限制，以第一列为源点，最后一列为汇点的网络流最大为多少。
          直接求最大流是不行的，最大流就是最小割，可以通过dp求出最小割出来。可以以列来划分阶段，用当前列的每个点01表示这个点属于哪个割集，而且最小割只和相邻的两列的状态相关，可以令f[i][j]表示当前列为i，状态为j的情况下最小割，那么假设压缩状态的1表示属于源的那个割集，那么对f[i][j]，枚举k，使得k为j的子集，然后用f[i][j] + hb[i+1][j^k] + vb[i+1][k]来更新f[i+1][k]，hb[i][k]表示水平线上k状为割时的流量和（1表示这条水平线是割），vb[i][k]表示i列上垂直状态的割为k时的流量和（如果相邻位不同则那条边就是割），然后对f[i+1][k]求最小值，也即求最小割，就得到的最大流。结果是f[m][0]。


2011.8.11
codeforce 48E 最短路+tarjan判环
          给出h，t表示怪物的头和尾的个数，然后有n个攻击用于消灭头，第i(1<=i<=n)个攻击会消灭i个头，但是会增加hi个头和ti个尾巴（副作用），然后还有有m个用于消灭尾巴，同样第i个攻击会消灭i个尾巴，增加hhi个头和tti个尾巴，并且任何时候怪物的头+尾巴的数目不超过R，否则挂掉。问如果能胜利，最少攻击多少次，否则能否一直玩下去，再否则就是挂了。
          通过最短路找最少次数，否则需要找环，找环可以用tarjan求scc来找，这样比spfa的方法要快，对于有向图，建议用tarjan找scc来判环。如果没有环则找最长路。否则会超时。


2011.8.12
codeforce 48C 不等式
          油站间隔一致，从第一个油站开始出发，每走10km则耗油10升，开始时油箱有a升油，如40.32，从出发点一直走不停下来，直到不能达到下一个油站则在该油站加a升油，然后继续走，油箱无限大，那么按照这样的策略，所停的位置为a1,a2...am，现在给出ai，问下一个停下来的站是多少？并且问是否是唯一的。
          通过题目的限定，根据ai和ai+1以及一直走直到不能走到下一个油站的策略，可以得出一些不等式，譬如g=a1-a0，那么    g*10 <=a<(g+1)*10,对于g1=a2 - a1也有类似的不等式，从而找出a的范围，然后枚举an+1的大小，看和a范围相交的那些不等式否唯一就知道下一个站是否唯一了。


2011.8.16
codeforce 46F bellmanford+集合
          给出一个无向图，有些点有人，每个人带有不同的若干个钥匙，每个钥匙只在一个人手上，每条边只能通过唯一一个钥匙打开，如果两个人在同一点，则可以交换钥匙。然后给出初始每个人的位置和每个人拥有的钥匙，以及结束状态时每个人的位置和拥有的钥匙，问是否可以由起始状态到结束状态。
          对于一个人以及他拥有的钥匙，可以通过一些边变成一个连通块，如果两个人的连通块是相交的，那么他们拥有的钥匙也是可以共享的。于是可以考虑通过并查集来记录连通性，同时用于记录这个连通块拥有的钥匙集合(bitset),通过类似bellmanford那样的n*m来不断更新钥匙的传递。接着记录两个bool矩阵p2p[i][j]表示i这个人到每个点j的连通情况，还有k2k[i][j]每个钥匙i到每个点j的连通情况，初始状态和结束状态都求这两个矩阵，看是否一致就知道是否可以到达了。


codeforce 45C 数据结构
          给出n个人，每个人标志是B或者G，然后每个人有一个数值ai，每次从相邻的不同标志而且数值差ai最接近的进行输出，然后将这两个人移除，继续做，求移除的顺序。
          链表+set，set记录相邻的不同的，并且通过.begin()找到最小的，然后更新链表即可。
通过这个，可以看出，用set比优先队列更有优势，可以直接取最大最小值，而且还提供删除功能，性能和优先队列一样，因而用set代替优先队列是一个很好的想法。


codeforce 45G 歌德巴赫猜想
          给1..n，染色，使得同样颜色的和都为质数，并且使得颜色数最少。
          歌德巴赫猜想，任意大于4的偶数都由2个质数组成，那么，答案最多就是3，令s=n*(n+1)/2, 如果s为偶数，那么找出一个i<s，使得i和s-i都为质数，那么使得i染不同色就可以了，那么i如果>n呢？貌似没有这种情况，不明中。如果s为奇数，那么先考虑2和s-2是否能为质数，否则把1，2染成不同颜色，然后剩下的继续找2个奇质数，结果就是3种颜色。


codeforce 44H 计数DP
          给出初始数字s1...s2，譬如12345，然后找出长度相同的另外一些数字，譬如95444，将这两排数字上下对齐，然后发现(9+2)/2 = 5.5，所以第二排数字第二个就是5，但是也可上取整为6，然后还有(3+5)/2 = 4,所以第二排接下来就是4，而且整除所以唯一为4。问题是，给出初始数字，有多少种长度相同的数字和初始数字串符合这个性质。
          DP。f[len][j]表示长度为len，最后一个数字为j的合法的个数，然后根据第一个串的对应位，得到结果。f[len][j] = f[len-1][(s[len-1]+j)/2 ] + f[len-1][(s[len-1]+j)/2+1]。


2011.8.18
zju2672 DP+hash
        给定一个长度为n<=3000的序列，要求满足Fibonacci性质(c[i]=c[i-1]+c[i-2])的最长的子序列。
        dp[i][j]表示i，j为开始的序列的长度，那么dp[i][j] = max{dp[j][k] +1 }，而且a[i]+a[j]= a[k]，k是满足k>j且最小的，改变一下dp顺序，用hash_map<int,int>来找出k，复杂度O(n^2)。

2011.8.19
codeforce 42D 边权化点权，构造
          给出n<=20个点的完全图，给每条边赋予唯一的权值，并且使得从任意一点开始的哈密顿回路的边权值和都一样，求构造方案。
          最为核心的想法就是把边权化为点权，使得每条边的权为两端的点权和，关键在于构造点权，使得任意两条边不相同。那么可以枚举构造，使得对任意之前的p,q,r点，构造as使得满足 ap+aq-ar != as 就可以了。


2011.8.27
zju2709 DP
        给出一个长度为m的字符串，然后给出一个n长度的盖子，每个盖子盖住的字符都必须是字符串中出现的，问使得在n个盖子中任意揭开m个的最大概率和最小概率是多少。
        假设不同的字母个数分别为x1, x2, ... , xk，那么对于合法状态，盖住字母个数分别为y1, y2, ..yk,而且使得yi >= xi，sigma{yi} = n，并且找出yi的分配，使得c[y1][x1]*c[y2][x2]*...*c[yk][xk] / c[n][m] 最大或者最小。 令f[i][j]为前i个，分配了j个盖子的最大值，那么很容易f[i][j] = max{ f[i-1][j-k] * c[k][xi] }，最小值类似。


zju3525 区间统计
        给出n个人，每个人有3个属性bi, wi, hi和一个附加属性si，然后选出一个集合，使得三个属性中最大的和最小的分别不超过Lb, Lw, Lh，而且使得si的和最小。
        先按照bi排序，然后两个指针维护属性bi在允许范围内，然后这个范围用set<node1> s1来维护hi的有序性，然后再利用2个指针，维护s1中属性wi在允许范围内，然后再利用set<node2> s2来维护这里面关于hi的有序性，再然后现在就是找出一些区间，使得hi的差值在允许范围内，并且把所有<0的si都加起来，这里再利用2个指针扫过去来统计就可以了。复杂度是两难性，几乎比O(n^3)低一个数量级。

2011.8.30
zju 2699  tarjan + DP
          给出一个有向图，并且在其中放k个警察局，使得对于每个点，都能到达某个警察局，或者存在某个警察局能到达这个点，问摆放警察局的方案数。
          先缩点，然后对于那些没有出度或者入度的点，就必须要选，剩下的随意，那么利用dp[i][j]表示前i个必选的点中共放了j个警察局，那么转移就是枚举当前这个点（缩点）要放多少个，假设当前点由ai个点组成，那么f[i][j] = sigma{ f[i-1][j-s]*C(ai, s)} ，s<=ai，最后还要统计sigma{f[n][i]*C(nleft, k-i)}，i是那些必选点所放的个数，对于剩下的点直接任意选即可。
          re~卡了好久一直以为那些没有入度或者出度的点的“度数”为1,然后就sb了 T_T。。

2011.8.31
hdu 3944 Lucas定理
    求出(c[n,k]+c[n-1][k-1]+...+c[n-k][0] ) % p。n很大（n<=10^9, p <=10000）。
    根据二项式的定理，c[n,k]+c[n-1][k-1]+...+c[n-k][0] = c[n+1][k]。然后就是如何求mod p。c[n][m]=n! / ((n-m)! * m!)。那么首先考虑上下的p的约数个数，如果分子大，那么结果必然为0,否则约数个数必然相等，然后上下把所有p因子都除去，那么对于那些i*p的数就剩下i了，然后发现对于n! %p呈现周期性，所以令L(n, p)为n! %p 且考虑i*p除去p因子后的结果，然后有L(n,p) = (p-1)^(n/p) * L(n/p) *(n%p)!。对于(n%p) !预处理即可。


2011.9.1
钩子公式
    对于一个行为n,每列长度为ai，而且长度非递增的一个形状，在上面填1..m个数(m为所有格子总数)，使得行列都是递增的。钩子公式 :方案数为 m! / (每个格子右边和下面的格子数+1  的乘积) 。

2011.9.2                                                                                                                  
hdu 3915 高斯消元
    给出n个数a1...an，然后找出若干个，使得它们的xor和为0,问方案数。
    设a1*x1 ^ a2*x2 ^ ...^an*xn = 0，那么xi为0/1表示是否取这个数，于是就变成了方程组，用高斯消元看有多少个解。

hdu 3917 最大权闭合图
         给出一个图，还有m个公司，每个公司税收taxi.每条边由某个公司负责运营，有相应的费用。如果某个点的入度是A公司，出度是B公司，则A和B关联（单向关系）。那么选择A公司的路费必须要选择B公司的路费，税收是白给的，问政府最大的收入是多少。
         建图，st到每个点taxi的容量，每个点到汇点，容量为该公司所有路费和，如果A和B公司有关联，A到B容量无限，求最小割cut。则sigma{taxi} - cut就是收入。

2011.9.8
hdu 4013 无根树判同构
         给出一棵树，然后问有多少个不同构的子树。
         枚举连接哪些边，然后枚举这个连通块的点作为根，对这个树进行hash。先求出子节点的hash，然后对所有儿子的hash值进行sort，然后再进行hash得到当前子树的hash值。（不同层的幂最好不同，这样准确度会高很多）。然后对于这个连通块，就会得到每个点的hash值，再进行排序，形成一个向量，然后看有多少个不同向量就得到不同构的子树个数。



2011.10.18
hdu 3893  合法字符串统计
    给出6种颜色拼成n长度的字符串，要回文，相邻不同颜色，而且不能出现012345或者543210的情况，问有多少种方法。
    先对所有的不合法串（如012345,11..）构造一个trie树,并在所在点标记，然后问题就变成在这个trie树种走n步且不走入标记点的情况数。根据转移情况构造矩阵，然后一个矩阵乘法即可。

hdu 3891 规律+lucas+中国剩余定理
    给出A1..AN,而Ax = sigma{ 0<=i<=N-1 | ai * x^i},且a0..an-1未知，求AN+1。
    把Ai在a0..an-1上的线性表达式列出，然后猜想AN+1可以由A1..AN线性表示出来，后来通过规律发现An+1 = sigma{ 0<=i<n | (-1)^(n+i) * C(n, i) * Ai+1 },然后由于MOD = 112233 = 3 × 11 × 19 × 179 不是素数，于是要拆开成各个素因数来通过lucas算法求结果，然后把得到的各个结果通过中国剩余定理来求最后的答案。折腾。。。


2011.10.19
hdu 3892 多项式gcd
    给出m个高次同余多项式f(x) = an*x^n + an-1* x^n-1 + ... + a0 (mod P), P 是素数，然后问这些多项式是否有共同的根。
    由于目前对于高次同余多项式目前没有找到通用解法，所以不能直接求解来做。考虑到对于式子f和g，假如f = g * x + y, 那么如果存在解r，使得f(r) = g(r) = 0, 那么就有y(r) = 0, 于是问题就转化为求g 和 y的共同解问题，这个不是很类似于gcd的求法么？求出m个式子的gcd，然后判断这个式子是否有解即可（由于题目说每个式子都必定有阶数解，所以只需要看gcd是否阶大于1,或者阶为0且常数项为0即可。）

2011.10.20
hdu 3894 图论
    给出一棵树，其中有east个为东部，west个为西部，而有p个东部存放有火车，然后每次一条边只能过一辆火车，把p个火车从东部运到不同的西部最少时间。（特殊条件是必定存在一条边把东西划分）
    突破点在于那条划分的边，所有的火车都要经过这条边，但是必然会按照顺序经过，于是到了西部后就不会有冲突了，所以做法就是先在临界点把东部的火车到达临界点的时间都计算出来，然后把到西部各个点的时间也找出来，排序按贪心选择就可以了。此外求东部火车到达临界点的时间可以一层层来考虑，然后只需要计算每个点到临界点的深度就可以了。

2011.10.21
zju2612 图论
    给出两个多项式p(x)和q(x) (在mod R的剩余系中)。问有多少个这样的值域集合A 子集于 {0,1,2,...,r-1}，使得{p(x) | x in A} = A,且q(x)也满足这个条件。
    考虑对于单个多项式，那么 {p(x) | x in A} = A相当于对于每个x在A中，它关于多项式的映射在A中，同时也存在一个A的值能映射到它。那么变成图论就是这样的A和他们的映射形成一个环，不在环内的必然不属于A。所以可以先对一个多项式建立有向图，把环缩点，其他的丢弃，如果有n个独立的环，那么结果就是2^n。现在对于2个多项式，只需要把两个图中有重合点的连无向边，最后求有多少个连通分量即可。

2011.10.22
hdu3266 数学/概率
    两个人赌博，扔硬币{H,T}的概率相同。A给出抛出可能的顺序HTHTT..（pattern A）,B给出pattern B，然后问随机扔的情况下，哪个会先赢。
    具体数学P410有结论，需要先构造扩栈kmp，然后按照公式算即可。


2011.11.04
hdu 4107 线段树
    有n个数，一开始都是0,有m个操作，每次把[xi,yi]这里面的数都加上ci，如果大于等于p，那么加上2×ci。问最后的每个数的结果。
    对每个点记录minP，maxP表示最大的值和最小的值，如果minP[x]  >=p 那么全部加2*ci，如果maxP[x] <p 那么加ci，否则就要继续往下做。

hdu 4106 最小费用流
      有n个水果，每个水果有价钱，切水果，然后保证连续的m个水果中切的个数不超过k，问最大切的价钱总和。
      n+2个点，st到第一个连容量k，0费用边，每个点连下一个k容量，0费用边，另外连去i+m这个点，1容量，-wi费用的边，i+m>n则直接连去ed。求最小费用流。