今天组队比赛时遇到了汉诺塔的题，开始时以为很难，但是仔细看题时，想到了曾今在杭电上做个一题，却发现是水题一道，直接一个打表！
TJU 1731.   Strange Towers of Hanoi
 
真正的题目还是杭电上的  http://acm.hdu.edu.cn/showproblem.php?pid=1207
规律：
a[1]=1;
a[2]=a[1]+2;a[3]=a[2]+2;(2个加2^1)
a[4]=a[3]+4;a[5]=a[4]+4;a[6]=a[5]+4;(3个加2^2);
…………………………………………(4个加2^3);
O(∩_∩)O~

【图论】

　1、Dijkstra算法
　2、Floyd算法
　3、Kruskal算法
　4、Prim算法
　5、欧拉回路

Dijkstra算法
Dijkstra算法是典型最短路算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。
Dijkstra算法是很有代表性的最短路算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。
Dijkstra一般的表述通常有两种方式，一种用永久和临时标号方式，一种是用OPEN, CLOSE表方式，Drew为了和下面要介绍的 A* 算法和 D* 算法表述一致，这里均采用OPEN,CLOSE表的方式。

大概过程：
创建两个表，OPEN, CLOSE。
OPEN表保存所有已生成而未考察的节点，CLOSED表中记录已访问过的节点。
1． 访问路网中里起始点最近且没有被检查过的点，把这个点放入OPEN组中等待检查。
2． 从OPEN表中找出距起始点最近的点，找出这个点的所有子节点，把这个点放到CLOSE表中。
3． 遍历考察这个点的子节点。求出这些子节点距起始点的距离值，放子节点到OPEN表中。
4． 重复2，3，步。直到OPEN表为空，或找到目标点。

 

 

Floyd算法
Floyd-Warshall 算法用来找出每对点之间的最短距离。它需要用邻接矩阵来储存边，这个算法通过考虑最佳子路径来得到最佳路径。

注意单独一条边的路径也不一定是最佳路径。

从任意一条单边路径开始。所有两点之间的距离是边的权，或者无穷大，如果两点之间没有边相连。
对于每一对顶点 u 和 v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比己知的路径更短。如果是更新它。
不可思议的是，只要按排适当，就能得到结果。
// dist(i,j) 为从节点i到节点j的最短距离
For i←1 to n do
For j←1 to n do
dist(i,j) = weight(i,j)

For k←1 to n do // k为“媒介节点”
For i←1 to n do
For j←1 to n do
if (dist(i,k) + dist(k,j) < dist(i,j)) then // 是否是更短的路径？
dist(i,j) = dist(i,k) + dist(k,j)这个算法的效率是O(V3)。它需要邻接矩阵来储存图。
这个算法很容易实现，只要几行。
即使问题是求单源最短路径，还是推荐使用这个算法，如果时间和空间允许(只要有放的下邻接矩阵的空间，时间上就没问题)。
[编辑] 时间复杂度 O(N^3)

 

 

Kruskal算法
基本思想
假设WN=(V,{E})是一个含有n个顶点的连通网，则按照克鲁斯卡尔算法构造最小生成树的过程为：先构造一个只含n个顶点，而边集为空的子图，若将该子图中各个顶点看成是各棵树上的根结点，则它是一个含有n棵树的一个森林。之后，从网的边集E中选取一条权值最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，也就是说，将这两个顶点分别所在的两棵树合成一棵树；反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依次类推，直至森林中只有一棵树，也即子图中含有n-1条边为止。</p>

Procedure kruskal(V,E);
begin
sort(E,1,m);//将边按照权值排序
for t:=1 to n do begin
if getfather(edge[t].u)<>getfather(edge[t].v) then begin //利用并查集判断两个顶点是否在同一集合内
tot:=tot+edge[t].data;//计算权值和
union(edge[t].u,edge[t].v);//合并顶点
inc(k);//合并次数
end;
end;
if k=n-1 then 形成了一棵最小生成树
else 不存在这样的最小生成树；
end;
优化：在判断两个顶点是否在同一集合内时可用并查集 　

 

Prim算法

基本思想
1. 在图G=(V, E) （V表示顶点 ，E表示边）中，从集合V中任取一个顶点（例如取顶点v0）放入集合 U中，这时 U={v0}，集合T(E)为空。
2. 从v0出发寻找与U中顶点相邻（另一顶点在V中）权值最小的边的另一顶点v1，并使v1加入U。即U={v0,v1 }，同时将该边加入集合T(E)中。
3. 重复2，直到U=V为止。
这时T(E)中有n-1条边，T = (U, T(E))就是一棵最小生成树。

PASCAL代码
procedure prim(v0:integer);
var
lowcost,closest:array[1..maxn] of integer;
i,j,k,min:integer;
begin
for i:=1 to n do begin
lowcost[i]:=cost[v0,i];
closest[i]:=v0;
end;
for i:=1 to n-1 do begin
{寻找离生成树最近的未加入顶点k}
min:=maxlongint;
for j:=1 to n do
if (lowcost[j]<min) and (lowcost[j]<>0) then begin
min:=lowcost[j];
k:=j;
end;
lowcost[k]:=0; {将顶点k加入生成树}
{生成树中增加一条新的边k到closest[k]}
{修正各点的lowcost和closest值}
for j:=1 to n do
if cost[k,j]<lowcost[j] then begin
lowcost[j]:=cost[k,j];
closest[j]:=k;
end;
end;
end;{prim}

〖返回顶部〗

 

欧拉回路
定义：
在一个图中，寻找一条只通过每条边一次的路径，这叫做欧拉路径，如果起点和终点是同一点，那么这条回路叫做欧拉回路．
判定一个图中是否存在欧拉回路：并不是每个图都存在欧拉回路．以下分三种情况：
无向图：每个点的度数是偶数，则存在欧拉回路．
有向图：每个结点的入度等于出度，则这个有向图中存在欧拉回路．
总结：以上两种情况很简单，其原理归根结底是每个结点进入和出去的路径条数相等，就存在欧拉回路．还有一种更加复杂的情况．那就是混合图．
混合图：（有时边是单向的，有时边是无向的，就像城市交通网络，有的街道是单向的，有的街道是双向的）找一个给每个无向边定向的策略，这样就可以把图转化成为有向图，使每个顶点的入度与出度是相等的，这样就会存在欧拉回路．
具体过程如下：新建一个图，对于原图中的无向边，在新图中新加一个顶点e(i);对于原图中的每一个顶点j，在新图中建一个顶点v(i)，对于原图中每一个顶点j和k之间有一条无向边i，那么在新图中从e(i)出发，添加两条边，分别连向v(j)和v(k)，容量都是1．
在新图中，从源点向所有的e(i)都连一条容量为1的边．. 对于原图中每一个顶点j，它原本都有一个入度in、出度out和无向度un。显然我们的目的是要把所有无向度都变成入度或出度，从而使它的入度等于总度数的一半，也就是(in + out + un) / 2（显然与此同时出度也是总度数的一半，如果总度数是偶数的话）。当然，如果in已经大于总度数的一半，或者总度数是奇数，那么欧拉回路肯定不存大。如果in小于总度数的一半，并且总度数是偶数，那么我们在新图中从v（j）到汇点连一条边，容量就是(in + out + un) / 2 – in，也就是原图中顶点j还需要多少入度。
按照这个网络模型算出一个最大流，如果每条从v(j)到汇点的边都达到满流量的话，那么欧拉回路成立。

〖返回顶部〗

http://acm.tju.edu.cn/toj/showp2794.html

#include<stdio.h>
long f(__int64 n)
{
    while(n!=0){
        if(n%10==7)return 1;
        n/=10;
    }
    return 0;
}
int main()
{
    static __int64 a[1000000],n,m,i,j=0,f1;
    for(i=7;i<1000000000;i++){
        if(f(i)||i%7==0)
            a[j]++;
        else {
            f1=1;
            for(int k=0;k<j;k++)
                if(a[j]<=a[k])f1=0;
            if(f1){printf("p=%I64d,x=%I64d\n",a[j],i-a[j]);
                  j++;}
            else a[j]=0;
            
        }
    }
}

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=3318
比赛时没有想到，就是靠人脑举例，导致考虑不完整，出现很多错误！后来经高人指点，编学了个辅助程序，终于ac了！
O(∩_∩)O~，看来还是要好好利用电脑！！

主程序：

这题是在组队时候做的！需要考虑很多情况！特别 0 和 1 ！！
http://acm.hdu.edu.cn/showproblem.php?pid=2690

http://acm.hdu.edu.cn/showproblem.php?pid=2687

这题只要分清对应的转动位置就能求解！还要注意转动顺序！！！

http://acm.hdu.edu.cn/showproblem.php?pid=1847

该题属于简单博弈题,只要将结果化到最简就可以推出规律！！


O(∩_∩)O~

http://acm.hdu.edu.cn/showproblem.php?pid=1210

开始寻找规律，找了好久想不出，最终想到了追踪第一张牌来进行求解！O(∩_∩)O~


虽然做时不知道为什么！但是事后我在网上搜到了证明方法！

洗牌问题：
很多人都是跟踪第一张牌来完成的，大家会不会证明呢？

定理1：当第一张牌(牌1)回到初始位置时，所有的牌都回到了初始位置。

证明：设有一次操作，某牌在操作前处于位置r(1<=r<=2*N)，那么，操作后，如果r原来是前一半的，显然r'=r*2; 否则，r'=(r-n)*2-1，即r'='r*2-(N*2+1);
将两个式子综合，可以得到r'= (r*2)%(N*2+1);
根据同余定理之一 ((i%m)*j)%m=(i*j)%M，可以整理出公式：i次操作后，该牌的位置为：
(r*(2^i))%(N*2+1);其中^表示乘方。
现在，我们假设经过M次操作后，牌1回到了初始位置，即(1*(2^M))%(N*2+1)=1时，再次应用同余定理，可以证明对于任意的k(1<=k<=2*N)，有(k*(2^M))%(N*2+1)=k，翻译成自然语言就是：当第一张牌回到初始位置时，所有的牌都回到了初始位置。命题得证。

定理2：一定存在某次操作M，这次操作后，所有的牌都回到了初始位置。
证明：我们已经证明了牌1回到初始位置时，所有的牌都回到初始位置，所以我们只需要证明牌1可以回到初始位置，即(2^M)%(N*2+1)=1一定有正整数解。证明这个定理前我们首先证明这样一个定理：
定理2.1：(2*r)%(2*n+1)==t
当t确定为1到2*n中的某值时(1<t<=2*n)，r在1到2*n间有唯一解
因为2*n+1是奇数，我们只要看一下就会发现r到t是一个一一映射，当t为偶数时，显然r=t/2，当t为奇数时，r=(t+1)/2+n，

现在我们来证明定理2。运用反正法，若牌1永远不能回到初始位置，根据鸽笼定理，牌1必然陷入了某个不包含位置1的循环，因为下一状态仅和当前状态有关，当前状态最多只有2*N种，所以显然一定在不超过2*N+1次操作内出现重复状态。而重复状态则意味着循环。
因为我们假设这一循环不包括位置1，我们设f(i)为循环中某状态，f(0)=1,f(n+1)=(f(n)*2)%(2*N+1)，f(j)为若干次循环后出现的重复状态，即f(i)=f(j)。因为循环一直持续，不妨假设j>i+i。又因为循环不包括状态1，即对于任意的k>=i，f(k)!=1
根据定理2.1，我们可以根据当前状态推出上一状态，换句话说，若f(i)=f(j)，则f(i-1)=f(j-1)。继续套用定理2.1，可以得到f(i-i)=f(j-i)，即：f(j-i)=f(0)=1。又有假设j>i+i，即j-i>i，与另一假设对于任意的k>=i，f(k)!=1矛盾。
因此，可以证明，牌1所陷入的循环，必然是包含位置1的，即一定有某次操作，操作后牌1回到了初始状态。而且显然的，初始状态就是这循环中的一个状态。
因此命题得证。

http://acm.hdu.edu.cn/showproblem.php?pid=2608

 

     因为我是菜鸟！所以我一无是处!
     因为我是菜鸟！所以我只会畅想！！！
     因为我是菜鸟！所以我只是大家的累赘！！！！！
     因为我是菜鸟！所以我不会在寻求改变！！！！！！！
     因为我是菜鸟！所以我改变不了什么只有自己去承受！！！！！！！
     不就是个人吗！！不就是缺少讨论吗！！大家不需要,干嘛还要自作多情呢！！！！！！！！
     我还年轻！我玩的起！！！！！！！！！！！！！！！！！！！！！