给定一个有向图，问从A点恰好走k步（允许重复经过边）到达B点的方案数mod p的值
     把给定的图转为邻接矩阵，即A(i,j)=1当且仅当存在一条边i->j。令C=A*A，那么C(i,j)=ΣA(i,k)*A(k,j)，实际上就等于从点i到点j恰好经过2条边的路径数（枚举k为中转点）。类似地，C*A的第i行第j列就表示从i到j经过3条边的路径数。同理，如果要求经过k步的路径数，我们只需要二分求出A^k即可

我把N个白色(2<=N<=10000)的小球摆成一排。现在，我想把其中一些小球涂黑，使得每M个连续的小球中至少有两个球是黑色的(2<=M<=100)。我已知给第i个球染色需要花费Ci个单位的染料。我想知道，至少需要花多少染料才能满足我的要求。

f[i,j]=min{f[j,k]}+w[i]  

f[i+1,j]=min{f[j,k]}}+w[i+1] (决策一样 所以可以优化)

=> 当i=j+1时 f[i,j]=min{f[j,k]}+w[i]

    当i>j+1时 f[i,j]=f[i-1,j]-w[i-1]+w[i]

给一个无向图，每条边有个权值，你可以让任何一条边权值减半，这样的操作可以做10次，每条边可以减多次，求减了之后的单元最短路。要求与一般的求最短路方法同时间复杂度的方法。

把这个图分成10层，边成一个三维图，每层的边权值都不变，第i层到第i＋1层的边减半一次，第i层到第i+2层的边减半两次.......

最后求的即是从第一层的起始点到第10层的终点的一条单元最短路。

1.一段数，每次给一个区间涂色，询问某个数的染色。

分析：记录涂的颜色和涂色的序号，询问一个数时，从下到上取序号最大的染色。

2.一颗二叉树，每次改某个节点的值，询问某棵子树的节点和。

分析：不能直接在二叉树上做，因为二叉树易退化。

先前序遍历一次，每个节点对应一个数(前序遍历的序号)，每棵子树表示一个区间(前序遍历中该子树的最小标号到最大标号)，即可用线段树解决

3.一段数，每次改一个数，询问某个区间的最大子序列和。

分析：线段树每个位置记录三个东西：最大子序列和、左边开始最大和、右边开始最大和

顺序给出N(1<=N<=50000)个数A1,A2,A3,...,An，其中第i个数的“最小波动值”定义为它与在它前面的数中所能产生的最小差值，即Ai的最小波动值为Min{ |Aj-Ai|, j<i }。我们规定，A1的最小波动值就是A1。

编写程序求出所有数的最小波动值的总和。

1.动态树

2.线段树

3.排序+二分查找

*4.排序+双向链表

先排序,用双向链表记录新序列并且原序列每个数用指针指向新序列对应的位置. 在原序列中从右往左枚举,当前数的最小差值就等于在新序列中与左右两个相邻数的差值的最小值,然后在双向链表中把这个数删掉(因为从右往左做,每次都会删掉,所以剩下的数全是它左边的,则相邻的一定是可行的且是最优的),所以用双向链表就可以在O(n)完成.当然,排序需要O(nlogn).

P 必胜  N 必败

P->只要有一个N    N->所有都是P

一般地:先写个DP(可行性转移),再来找规律

1.欧几里德游戏:给一个数,每次可以减去小于它的一个约数,不能再减了(即拿到一了)就算输.

  偶数为必胜,奇数为必败.

2.分巧克力:一个n*m的巧克力块,可以任意分成边长均为整数的两个小巧可力,如果不能再分了(即拿到1*1的了)就算输.

  当m=n时必败

3.猫老大取数(2^n):给一个数n,每次可以减去2^k(k属于非负整数),如果把这个数减成0了就算赢.

  3的倍数必败

4.Lim取火柴:有n堆火柴,第i堆有ai根火柴,每次可以在任何一堆里取走任何数量的火柴,先取完者算赢.

  把每一堆的火柴数全部xor,若为0则必败

1.收入计划

问题描述
    高考结束后，同学们大都找到了一份临时工作，渴望挣得一些零用钱。从今天起，Matrix67将连续工作N天(1<=N<=100 000)。每一天末他可以领取当天及前面若干天里没有领取的工资，但他总共只有M(1<=M<=N)次领取工资的机会。Matrix67已经知道了在接下来的这N天里每一天他可以赚多少钱。为了避免自己滥用零花钱，他希望知道如何安排领取工资的时间才能使得领到工资最多的那一次工资数额最小。注意Matrix67必须恰好领工资M次，且需要将所有的工资全部领走（即最后一天末需要领一次工资）。

输入数据
    第一行输入两个用空格隔开的正整数N和M
    以下N行每行一个不超过10000正整数，依次表示每一天的薪水。

输出数据
    输出领取到的工资的最大值最小是多少。

输入样例
7 5
100
400
300
100
500
101
400

输出样例
500

样例说明
    采取下面的方案可以使每次领到的工资不会多于500。这个答案不能再少了。

100 400   300 100   500   101   400   每一天的薪水
<------1 <-------2 <---3 <---4 <---5  领取工资的时间
  500       400     500   101   400   领取到的工资

2.架设电话线

问题描述
    Farmer John打算将电话线引到自己的农场，但电信公司并不打算为他提供免费服务。于是，FJ必须为此向电信公司支付一定的费用。
    FJ的农场周围分布着N(1<=N<=1,000)根按1..N顺次编号的废弃的电话线杆，任意两根电话线杆间都没有电话线相连。一共P(1<=P<=10,000)对电话线杆间可以拉电话线，其余的那些由于隔得太远而无法被连接。
    第i对电话线杆的两个端点分别为A_i、B_i，它们间的距离为L_i (1<=L_i<=1,000,000)。数据中保证每对{A_i，B_i}最多只出现1次。编号为1的电话线杆已经接入了全国的电话网络，整个农场的电话线全都连到了编号为N的电话线杆上。也就是说，FJ的任务仅仅是找一条将1号和N号电话线杆连起来的路径，其余的电话线杆并不一定要连入电话网络。
    经过谈判，电信公司最终同意免费为FJ连结K(0<=K<N)对由FJ指定的电话线杆。对于此外的那些电话线，FJ需要为它们付的费用，等于其中最长的电话线的长度（每根电话线仅连结一对电话线杆）。如果需要连结的电话线杆不超过K对，那么FJ的总支出为0。
    请你计算一下，FJ最少需要在电话线上花多少钱。

输入数据
    第一行输入3个用空格隔开的整数：N、P、以及K
    以下P行中，第i行为3个用空格隔开的整数：A_i、B_i、L_i。

输出数据
    输出一个整数，为FJ在这项工程上的最小支出。如果任务不可能完成，输出-1。

输入样例
5 7 1
1 2 5
3 1 4
2 4 8
3 2 3
5 2 9
3 4 7
4 5 6

输出样例
4

样例说明
    FJ选择如下的连结方案：1->3、3->2、2->5，这3对电话线杆间需要的电话线的长度分别为4、3、9。FJ让电信公司提供那条长度为9的电话线，于是，他所需要购买的电话线的最大长度为4。

3.旅行路线

问题描述
    Matrix67打算带他的朋友们一同出去旅游。旅游地共有N(2<=N<=1000)个景点，第i个景点的乐趣值为F_i(1<=F_i<=1000)。有M(2<=M<=5000)条道路连接这N个景点，第i条道路的行走时间为T_i(1<=T_i<=1000)。由于大城市中总是寸土寸金，所有的道路都很窄，政府不得不把它们都设定为通行方向固定的单行道。与花费在旅行道路中的行走时间相比，游玩景点的时间可以忽略不计。Matrix67打算选择一条回路，使得这条回路所产生的平均乐趣值最大，即回路上的景点乐趣值之和与所有道路的时间总和之比最大。Matrix67的朋友们不会愿意游览同一个景点两次，也就是说，虽然他们可以两次经过同一个景点，但他们的乐趣值只会增加一次。为了得到更多的锻炼，他们需要参观至少2个景点。

输入数据
    第一行输入两个用空格隔开的整数N和M。
    以下N行每行一个正整数F_i。
    以下M行每行三个数X_i、Y_i、T_i，表示第i条道路单向从景点X_i连接到景点Y_i，行走时间为T_i。

输出数据
    输出一个实数，保留到小数点后2位（直接输出，不要做任何特殊的取整操作），表示如果Matrix67和他的朋友们按题目中描述的一系列规则来安排他们的旅行的话，他们能获得的最大平均乐趣值。

样例输入
5 7
30
10
10
5
10
1 2 3
2 3 2
3 4 5
3 5 2
4 5 5
5 1 3
5 2 2

样例输出
6.00

样例说明
    如果选择1 -> 2 -> 3 -> 5 -> 1的旅行路线，能得到的总乐趣值为60，为此需要花费10单位的时间。于是他们在这次旅行中的平均乐趣值为6。如果他们走2 -> 3 -> 5 -> 2的路线，就只能得到30/6 = 5的平均乐趣值。并且，任何去参观景点4的旅行路线的平均乐趣值都没有超过4。

4.猜数游戏

问题描述
    为了提高自己低得可怜的智商，奶牛们设计了一个新的猜数游戏，来锻炼她们的逻辑推理能力。
    游戏开始前，一头指定的奶牛会在牛棚后面摆N(1 <= N<= 1,000,000)堆干草，每堆有若干捆，并且没有哪两堆中的草一样多。所有草堆排成一条直线，从左到右依次按1..N编号，每堆中草的捆数在1..1,000,000,000之间。
    然后，游戏开始。另一头参与游戏的奶牛会问那头摆干草的奶牛Q(1 <= Q <= 25,000)个问题，问题的格式如下：
    编号为Ql..Qh(1 <= Ql <= Qh <= N)的草堆中，最小的那堆里有多少捆草？
    对于每个问题，摆干草的奶牛回答一个数字A，但或许是不想让提问的奶牛那么容易地得到答案，又或许是她自己可能记错每堆中干草的捆数，总之，她的回答不保证是正确的。
    请你帮助提问的奶牛判断一下，摆干草的奶牛的回答是否有自相矛盾之处。如果有矛盾，则最早发生在什么位置。

输入数据
    第一行输入两个用空格隔开的整数N和Q。
    以下Q行每行为三个用空格隔开的整数Ql、Qh、A，描述了一个问题以及它对应的回答。

输出数据
    如果摆干草的奶牛有可能完全正确地回答了这些问题（也就是说，能找到一种使得所有回答都合理的摆放干草的方法），输出0，否则输出一个1..Q中的数，表示第一个与它之前的回答有冲突的询问。

样例输入
20 4
1 10 7
5 19 7
3 12 8
11 15 12

样例输出
3

样例说明
    对于第3个问题“3 12”的回答“8”与前面两个回答冲突。因为每堆中草的捆数唯一，从前两个回答中我们能推断出，编号为5..10的干草堆中最小的那堆里有7捆干草。很显然，第3个问题的回答与这个推断冲突。

分析:

1.二分工资最大值,再用贪心方法(从左往右能去就去)判断是否可行.

2.二分自己要赋的最大值x,把所有大于x的边标记,则需判断经过最少标记是否小于k.

  求最少经过标记数:把标记的边赋为1,没标记的边赋为0,求出起点到终点的最短路即可.

3.由于  min(a/b,c/d)<=(a+c)/(b+d)<=max(a/b,c/d)    (证明略)

  那么最优的回路肯定不会经过同一个点两次,即所求回路为简单回路.

  对于某个环: t 乐趣  t 时间 

  二分x , s/t>=x  ->  t*x-s<=0 , 即判断是否有负环即可

4.对于每个数,赋为所有覆盖它区间的最大值,再看是否满足每个区间即可.

  离散化n个数即可变成q个数,再二分问题数O(logp),然后赋值和判断O(p),总时间复杂度O(plogp)

1.树的划分

给定一棵树,为了分离出一棵有K个结点的子树，最少需要删掉多少条边

将其转为二叉树
设F[i,j]表示第i个节点从以它为根的子树（二叉树上的）上选j个点需要去掉的边数（包括不在二叉树上的边，以及i在多叉树上的父亲上的边）
F[i,j]:=Min{F[i.Left,n]+F[i.Right,j-n-1](1<=n<=j-1),F[i.Right,j]+1,F[i.Right,j-1]+1}
最后扫描整棵树，结果即所有F[i.left,k-1]+1(根节点不加1)的最小值

2.07年m67生日邀请赛 wolf

给出一个图,每条边上都有权值,除一号节点外,其它节点上都有A、C两种不同的权值,选取C权值和不超过K的若干顶点,使这些顶点及它们到1号结点的最短路上经过的所有其它顶点的A权值和最大,有多条最短路可选时总是选择前往编号小的结点

由所有的最短路构成了一棵树,然后多叉转二叉,f[i,j]表示在这棵二叉树上的子树花费j个材料的最大值

    (1). 自己把材料用了；
    (2). 自己把材料用了后剩下的给右边；
    (3). j个材料全部用到左边去，加上自己的权值；
    (4). j个材料全部用到右边去，不加自己的权值；
    (5). j个材料左边用一点，右边用一点，加上自己的权值。

状态O(nk)个，决策为O(k)，时间复杂度O(nk^2)

3.IOI2005 Day2 Rivers

一棵树n个节点,根结点已有个工厂,需要再设k个工厂,每个节点有个货物数,每条边有权值,每个节点的货物都送到上面的最近的设了货物的节点.                      

算法O(n^2k^2)    (多叉转二叉)      j表示i上面最近的工厂  k表示一共设的工厂数

f[i,j,k]= 不设工程 min{f[i.left,j,k']+f[i.right,j,k-k']+w[i]*d[i,j]}

           设工程    min{f[i.left,i,k']+f[i.right,j,k-k'-1]}

1.定义鹰蛋的坚硬程度E为：从第E层楼及以下楼层落下时不会碎，但从第E+1层楼及以上楼层向下落时会摔碎。                           任务：不断在一幢N层大楼内向下扔鹰蛋来确定坚硬程度E,可供使用的鹰蛋共有M个,假设所有的鹰蛋都具有相同的坚硬度,求最坏情况下确定E所需要的最少次数。

f[i,j]=min{max{f[i-1,k-1],f[i,j-k]}}+1   O(mn^2)

f[i-1,k-1]为非减的,f[i,j-k]为非增的,则min取的是两个"函数"的交点

可以用二分的方法找这个"交点" , 则优化到 O(mnlogn)

2.NOI2005 adv1900 (队列优化)

给定一个带障碍物的MxN阵列,给出K次船体倾斜的方向及其时间范围,钢琴随船体倾斜方向滑行,钢琴不能撞到障碍物或滑出边界,天使可在任意时刻使钢琴暂时静止,求钢琴最长的滑行距离

不妨设k方向为右

f[(i,j),k]=max{f[(i,j'),k-1]+j-j'} => f[(i,j),k]=max{f[(i,j'),k-1]-j'}+j 

当j增加,j'范围是增加或不变的,所以直接维护一个长度小于等于m的递减队列即可

1.序列A1,A2,....,AN,一次操作是将某个数增一或减一,用最少的操作次数将原序列改为递增序列

f[i,j]=min{f[i-1,k]}+|a[i]-j| (k=1~j-1) => f[i,j]=min{f[i,j-1]-|a[i]-j|,f[i-1,j-1]}+|a[i]-j|

2.给定一个带权值的M*N矩形方阵,去掉k个格子,要求剩下的任何一个格子都可以看到右边界和下边界,求去掉格子权值之和最少值

f[i,j,k]=min{f[i-1,j',k-j}+s[i,j] (j'=j+1~n) => f[i,j]=min{f[i,j+1,k+1]-a[i,j+1],f[i-1,j,k-j]+s[i,j]}