posts - 12,  comments - 10,  trackbacks - 0
  2009年5月18日

今天组队比赛时遇到了汉诺塔的题,开始时以为很难,但是仔细看题时,想到了曾今在杭电上做个一题,却发现是水题一道,直接一个打表!
TJU 1731.   Strange Towers of Hanoi
#include<stdio.h>
int main()
{
    
int a[13]={0,1,3,5,9,13,17,25,33,41,49,65,81};
    
for(int i=1;i<=12;i++)
      printf(
"%d\",a[i]);
}
 
真正的题目还是杭电上的  http://acm.hdu.edu.cn/showproblem.php?pid=1207
#include<stdio.h>
#include
<math.h>
int main()
{
    
long a[65];
    a[
1]=1;
    
long i,j,n,m,r;
    
for(i=2,j=1,r=1,m=2;i<66;i++,j++)
        
if(j<=m)
            a[i]
=a[i-1]+pow(2,r);
        
else {
            m
++;
            j
=1;
            r
++;
            a[i]
=a[i-1]+pow(2,r);
        }

    
while(scanf("%d",&n)==1){
        printf(
"%d\n",a[n]);
    }

}

    
规律:
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~
posted @ 2009-05-18 18:32 zhoubaozhong 阅读(719) | 评论 (0)编辑 收藏

【图论】

 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)到汇点的边都达到满流量的话,那么欧拉回路成立。

〖返回顶部〗

posted @ 2009-05-18 11:06 zhoubaozhong 阅读(161) | 评论 (0)编辑 收藏
  2009年5月16日
http://acm.tju.edu.cn/toj/showp2794.html

#include<stdio.h>
long max(long a,long b)
{
    
if(a>b)return a;
    
return b;
}

int main()
{
    
long i,n,m,ma;
    
static long a[1000001],b[1000001];
    scanf(
"%d",&m);
    
while(m--){
        scanf(
"%d",&n);
        
for(i=0;i<n;i++)
            scanf(
"%d",&a[i]);
        
for(i=0;i<n;i++)
            scanf(
"%d",&b[i]);
        a[
1]+=a[0];
        b[
1]+=b[0];
        
for(i=2;i<n;i++){
            a[i]
+=max(a[i-1],b[i-2]);
            b[i]
+=max(b[i-1],a[i-2]);
        }

        ma
=max(b[n-1],a[n-1]);
        printf(
"%d\n",ma);
    }

}

    
posted @ 2009-05-16 10:25 zhoubaozhong 阅读(67) | 评论 (0)编辑 收藏
  2009年5月4日
#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~,看来还是要好好利用电脑!!

主程序:
#include<stdio.h>
int main()
{
    
long n,t;
    scanf(
"%d",&t);
    
while(t--){
        scanf(
"%d",&n);
        
if(n==1)printf("7\n");
        
else if(n==2)printf("27\n");
        
else if(n<=10)printf("70\n");
        
else if(n<=11)printf("270\n");
        
else if(n<=100)printf("700\n");
        
else if(n<=101)printf("2700\n");
        
else if(n<=1000)printf("7000\n");
        
else if(n<=1002)printf("26999\n");
        
else if(n<=10000)printf("70000\n");
        
else if(n<=10001)printf("270000\n");
        
else if(n<=100000)printf("700000\n");
        
else if(n<=100001)printf("1699999\n");
        
else if(n<=1000000)printf("7000000\n");
        
else if(n<=1000001)printf("27000000\n");
        
else if(n<=10000000)printf("70000000\n");
        
else if(n<=10000001)printf("270000000\n");
        
else printf("700000000\n");
    }

}

        
    

posted @ 2009-05-04 22:14 zhoubaozhong 阅读(332) | 评论 (0)编辑 收藏
  2009年4月29日
#include<stdio.h>
int main()
{
    
int max,min,n,i,x,t,a[10001],sum1,sum2,s;
    scanf(
"%d",&t);
    
while(t--)
    
{
        scanf(
"%d",&n);
        max
=0;
        min
=10001;
        s
=0;
               
for(i=0;i<n;i++)
               
{
                scanf(
"%d",&a[i]);
                
if(a[i]>max)
                max
=a[i];
                
if(a[i]<min)
                min
=a[i];
                
if(a[i]>=n&&a[i]<0)s=1;
               }

               
if(s==1||n==1&&max==0){ printf("Impossible!\n"); continue;}
               sum1
=sum2=0;
               
if(max==min+1){
                  
for(i=0;i<n;i++){
                    
if(max==a[i])sum1++;
                    
else sum2++;
                  }

                  
if(sum2==max)printf("%d\n",max);
                  
else  printf("Impossible!\n");
               }

                    
               
else if(max==min)
               
{    if(max==0)printf("0\n");
                    
else {
                    
if(max==n-1)printf("%d\n",n);
                    
else printf("Impossible!\n");   }

               }

               
else
               printf(
"Impossible!\n");
    }

}

这题是在组队时候做的!需要考虑很多情况!特别 0 和 1 !!
http://acm.hdu.edu.cn/showproblem.php?pid=2690
posted @ 2009-04-29 21:01 zhoubaozhong 阅读(141) | 评论 (0)编辑 收藏
  2009年4月27日
http://acm.hdu.edu.cn/showproblem.php?pid=2687

#include<stdio.h>
int main()
{
    int n,i,k,j,a[11][11],b[11][11];
    while(scanf("%d",&n)!=EOF){
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
                scanf("%d",&a[i][j]);
        scanf("%d",&k);
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++) //首先求解每循环四次的总和*(k/4)
                b[i][j]=(a[i][j]+a[j][n+1-i]+a[n+1-i][n+1-j]+a[n+1-j][i])*(k/4);
        if(k%4==0)//再求解k%4的结果
            for(i=1;i<=n;i++)
                for(j=1;j<=n;j++)
                    b[i][j]+=a[i][j];
        else if(k%4==1)
            for(i=1;i<=n;i++)
                for(j=1;j<=n;j++)
                    b[i][j]+=a[i][j]+a[n+1-j][i];
        else if(k%4==2)
            for(i=1;i<=n;i++)
                for(j=1;j<=n;j++)
                    b[i][j]+=a[i][j]+a[n+1-j][i]+a[n+1-i][n+1-j];
        else
            for(i=1;i<=n;i++)
                for(j=1;j<=n;j++)
                    b[i][j]+=a[i][j]+a[n+1-j][i]+a[n+1-i][n+1-j]+a[j][n+1-i];
        for(i=1;i<=n;i++){
            for(j=1;j<=n;j++){
                printf("%d",b[i][j]);
                if(j<n)
                printf(" ");}
            printf("\n");
        }
    }
}
这题只要分清对应的转动位置就能求解!还要注意转动顺序!!!

posted @ 2009-04-27 20:41 zhoubaozhong 阅读(159) | 评论 (0)编辑 收藏
  2009年4月26日
http://acm.hdu.edu.cn/showproblem.php?pid=1847

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

#include<stdio.h>
int main()
{
    long n;
    while(scanf("%d",&n)==1){
        if(n%3==0)printf("Cici\n");
        else printf("Kiki\n");
    }
}

O(∩_∩)O~
posted @ 2009-04-26 10:53 zhoubaozhong 阅读(149) | 评论 (0)编辑 收藏
  2009年4月21日
http://acm.hdu.edu.cn/showproblem.php?pid=1210

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

#include<stdio.h>
int main()
{
    
long i,n,sum;
    
while(scanf("%d",&n)==1){
        sum
=1;
        i
=2;//追踪 1 的位置; 
        while(i!=1){
            
if(i>n)
                  i
=(i-n)*2-1;
            
else i*=2;
            sum
++;//表示排序的次数 
        }

        printf(
"%d\n",sum);
    }

}


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

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

定理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回到了初始状态。而且显然的,初始状态就是这循环中的一个状态。
因此命题得证。
posted @ 2009-04-21 16:34 zhoubaozhong 阅读(518) | 评论 (0)编辑 收藏
  2009年4月19日

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



#include <stdio.h>  //数为1的是某数的平方或某数平方的2倍,之前结果之和取余2
#include<math.h>
int main()
{
    
int t,sum;long long n,i,k;
    scanf(
"%d",&t);
    
while(t--)
    
{
        scanf(
"%I64d",&n);
        sum
=k=sqrt(n);
        
for(i=1;i<=k;i++)
        
{
            
if(i*i*2<=n)sum++;
        }

        sum
=sum%2;
        printf(
"%d\n",sum);
    }

    
return 0;
}


 

posted @ 2009-04-19 18:40 zhoubaozhong 阅读(282) | 评论 (0)编辑 收藏
  2009年4月18日

     因为我是菜鸟!所以我一无是处!
     因为我是菜鸟!所以我只会畅想!!!

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

posted @ 2009-04-18 21:26 zhoubaozhong 阅读(100) | 评论 (10)编辑 收藏
仅列出标题  下一页
<2019年12月>
24252627282930
1234567
891011121314
15161718192021
22232425262728
2930311234

常用链接

留言簿(3)

随笔档案

杭电!!

搜索

  •  

最新评论

阅读排行榜

评论排行榜