这几天在机房上课,下午都是考试,matrix67连续5天出二分答案,真是晕死了....

当10a+b能被7整除,因为7a+7b能被7整除,所以3a-6b能被7整除

则a-2b能被7整除,这也就是判断是否能被7整除的方法

则有结论: 11...17(有n个1,最后一个数为7),  当n能被6整除时, 那么这个数就能被7整除.

例:定义P(n)为n的所有数字的乘积。例如，P(1243)=1*2*4*3=24，P(198501243)=0。
我们称一个数n为“好数”，如果P(n)<>0且n mod P(n)=0。
我们称一个数n为“完美数”，如果n和n+1都是好数。
读入一个数K，输出恰好为K位的完美数有多少个。(k<=1000000)

如果n为完美数,那么n和n+1均为好数

则它们末位均不为零,前k-1位都相同,所以前k-1位相乘的值是n和n+1的公约数,又因为n与n+1互质,所以这个数前k-1位肯定全为1

那么完全数只可能是形如11...1x(k-1个1)的数,再分别判断k不同时,x有哪些取法.(7的判断就用到了上面说的那个结论)

顺序给出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).

并查集满足等价关系

等价关系:自反,对称,传递

Tarjan算法(需要用到并查集)

深度优先遍历,正在处理的点是指向集合是自己,处理完的点指向集合为父亲,处理完后再看它是否有询问,询问的对方点一定是处理完的点,若没处理完,则等到下次再问.若处理完,则合并,并且路径压缩.

LCA问题转换成RMP问题:

按层次标号,再深度优先遍历,得到遍历序列(每个点正在处理或处理完都需打印),则LCA问题就转换成了RMP问题.

正负1RMP问题转换成LCA问题:

该序列的任何相邻数一定相差1,那么+1表示往下走一步(加一个新的儿子),-1表示往上走一步(回到父亲).当然在首尾要补数保证第一个和最后一个数是最小值.最后就可构建一棵树,这种RMP问题的询问就可以转换到这棵树上的LCA问题的询问.

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的递减队列即可

D(1)=0,D(2)=1

递推式：D(n)=(n-1)(D(n-1)+D(n-2))

通项: D(n)=n!(1-1/2!+1/3!-.....+(-1)n/n!)

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

用s[i,j]=k 表示决策

则s[i,j-1]<=s[i,j]<=s[i+1,j] , s[i+1,j]<=s[i+1,j+1]<=s[i+2,j+1] ...... (该结论很显然,就不证明了)

所以对于相同长度的j-i,决策总共是O(n),所有长度为j-i状态为O(n),总是件复杂度为O(n^2)

当出现类型于f[i,j]=min{f[i,k]+f[k+1,j]}+w[i,j]的DP,可以先用三方把决策s[i,j]用二维表打出来,如果行和列都是递增的,那么就可以用四边形不等式优化.

问题:一个序列,多次询问某段区间的最大值

f[i,k] 表示从第i个开始2^k个数的最大值

则f[i,k]=max{f[i,k-1],f[i+1,k-1]} 

询问(i,j),则返回max{f[i,k],f[j-2^k,k]} (取最大的k使2^k<=j-i)

预处理 O(nlogn)  询问 O(1)

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]}

1+1/2+1/3+....1/n 等阶于 logn

log n! 等阶于 nlogn

给出2*n+1个数,其中有且仅有一个数出现了奇数次,求此数     x=a1 xor a2 xor a3.....xor an

一个图上A到B的最优路径一定在一棵最小生成树上(最优路径：最大边最小的路径)

最小生成树一定是瓶颈生成树,瓶颈生成树不一定是最小生成树

瓶颈生成树算法:

1.最小生成树

2.二分最大边,判断是否连通 O(ElogE)

要走的怎么也要走 留下来的总会留下来 也许这是真正的结束又或许是真正的开始

问题：求x

a1=x mod m1

a2=x mod m2

....

an=x mod mn

算法：

1.当m1,m2,...,mn两两互质的时候:

   M=m1*m2*m3*....*mn;  Mi=M/mi;

   解 p*Mi+q*mi＝1

   ei=p*Mi;

   则 ei mod mj=1 (i=j)

   或 ei mod mj=0 (i<>j)

   所以 x0=a1e1+a2e2+....+anen 为一个可行解

   所有解为 x=x0+kM (k为整数)

2.非两两互质的时候可通过此变化使其两两互质:

   设 k=gcd(m1,m2) n1=m1/k n2=m2/k

   x mod m1=a1 -> x mod (k*n1)=a1 -> x mod n1=a1 mod n1

   x mod m2=a2 -> x mod (k*n2)=a2 -> x mod n2=a2 mod n2

   根据此方法,当Mi和mi非互质时,改变mi和ai的值即可.

由于KM的过程是每次都做一次匈牙利中的"增广操作",没有增广路就修改顶标值标,直到找到完备匹配.

那么这个二分图首先必须是存在完备匹配的.不过这样还不一定能求出最优匹配,因为最优匹配不一定是最大匹配.

如果这个二分图两个集合的任意两个点之间都有边的话,那肯定可以保证正确性,但是这样KM就很有局限性了.

我们不妨自行地加上若干条边和若干个点(加点为了使两个集合的点数相等)使这个二分图变为"完全的".

每个新加的边的权值都赋为0,这样就能用KM算法解决所有二分图的最优匹配问题.

uses math;
const max=2000;
type
    link=^rec;
    rec=record
        i:longint;
        point:link;
    end;
    ss=record
        min,i:longint;
        p:link;
    end;
var
    f,c:array[1..max,1..max]of longint;
    g:array[1..max,1..max]of boolean;
    h:array[1..max]of boolean;
    a:array[0..max]of ss;
    d,b:array[1..max]of longint;
    v:array[1..max]of link;
    n,m,s,t,res:longint;   

procedure readp;
var
    i,j,k,l:longint;
    p:link;
begin
    readln(n,m,s,t);
    for i:=1 to m do
    begin
        readln(j,k,l);
        if (not g[j,k])and(j<>k) then
        begin
            new(p);
            p^.i:=k;p^.point:=v[j];v[j]:=p;
            new(p);
            p^.i:=j;p^.point:=v[k];v[k]:=p;
            g[j,k]:=true;g[k,j]:=true;
        end;
        inc(c[j,k],l);
    end;
end;

procedure bfs;//从汇点开始标号
var
    l,r,now:longint;
    p:link;
begin
    b[1]:=t;l:=0;r:=1;h[t]:=true;
    repeat
        inc(l);now:=b[l];
        p:=v[now];
        while p<>nil do
        begin
            if (not h[p^.i])and(c[p^.i,now]>0) then
            begin
                inc(r);b[r]:=p^.i;
                d[p^.i]:=d[now]+1;
                h[p^.i]:=true;
            end;
            p:=p^.point;
        end;
    until l=r;
end;

procedure dinic;
var
    r,now,i,k,l:longint;
    p:link;
begin
    fillchar(h,sizeof(h),0);
    r:=0;
    a[r].i:=s;a[r].min:=maxlongint;
    p:=v[s];h[s]:=true;
    while d[s]<n do
    begin
        now:=a[r].i;
        while (p<>nil)and((h[p^.i])or(d[p^.i]+1<>d[now])or(c[now,p^.i]-f[now,p^.i]+f[p^.i,now]=0)) do
            p:=p^.point;
        if p<>nil then
        begin
            h[p^.i]:=true;
            inc(r);
            a[r].i:=p^.i;a[r].p:=p;
            a[r].min:=min(a[r-1].min,c[now,p^.i]-f[now,p^.i]+f[p^.i,now]);
            if p^.i=t then
            begin
                k:=a[r].min;
                inc(res,k);
                for i:=1 to r do
                begin
                    inc(f[a[i-1].i,a[i].i],k);
                    if f[a[i-1].i,a[i].i]>c[a[i-1].i,a[i].i] then
                    begin
                        dec(f[a[i].i,a[i-1].i],f[a[i-1].i,a[i].i]-c[a[i-1].i,a[i].i]);
                        f[a[i-1].i,a[i].i]:=c[a[i-1].i,a[i].i];
                    end;
                    dec(a[i].min,k);
                end;
                while a[r].min=0 do
                begin
                    h[a[r].i]:=false;
                    dec(r);
                end;
                p:=a[r+1].p^.point;continue;
            end;
            p:=v[p^.i];
        end
        else
        begin
            p:=v[now];d[now]:=n;
            while p<>nil do
            begin
                if (not h[p^.i])and(c[now,p^.i]-f[now,p^.i]+f[p^.i,now]>0)and(d[p^.i]+1<d[now]) then
                    d[now]:=d[p^.i]+1;
                p:=p^.point;
            end;
            p:=v[now];
            if (d[now]=n)and(r<>0) then
            begin
                p:=a[r].p^.point;
                dec(r);
            end;
        end;
    end;
end;

begin
    readp;
    bfs;
    dinic;
    writeln(res);
end.