久久久久久综合网天天,亚洲精品NV久久久久久久久久,AAA级久久久精品无码区

�Ҏ��的汉诺塔�Q�HDU 汉诺塔II 1207

zhoubaozhong — Mon, 18 May 2009 10:32:00 GMT

今天�l�队比赛旉��C��汉诺塔的题，开始时以�ؓ很难�Q�但是仔�l�看题时�Q�想��C��曾今在杭电上做个一题，却发现是水题一道，直接一个打表！
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]);
}

真正的题目还是杭电上�?nbsp; 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]);
    }
}

规律�Q?br>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~

zhoubaozhong 2009-05-18 18:32 发表评论

图论

zhoubaozhong — Mon, 18 May 2009 03:06:00 GMT

【图论�?a id=0 name=0>

　1�?/font>Dijkstra��法
　2�?/font>Floyd��法
　3�?/font>Kruskal��法
　4�?/font>Prim��法
　5�?/font>�Ƨ拉回�\

Dijkstra��法
Dijkstra��法是典型最短�\��法�Q�用于计��一个节点到其他所有节点的最短�\径。主要特�Ҏ��以�v始点��Z��心向外层层扩展，直到扩展到终点�ؓ止。Dijkstra��法能得出最短�\径的最优解�Q�但�׃��它遍历计��的节点很多�Q�所以效率低�?br>Dijkstra��法是很有代表性的最短�\��法�Q�在很多专业评��中都作�ؓ基本内容有详�l�的介绍�Q�如数据�l�构�Q�图论，�q�筹学等�{��?br>Dijkstra一般的表述通常有两�U�方式，一�U�用�怹�和��时标��h��式，一�U�是用OPEN, CLOSE表方式，Drew��Z��和下面要介绍�?A* ��法�?D* ��法表述一��_��q�里均采用OPEN,CLOSE表的方式�?/p>

大概�q�程�Q?br>创徏两个表，OPEN, CLOSE�?br>OPEN表保存所有已生成而未考察的节点，CLOSED表中记录已访问过的节炏V�?br>1�Q?讉K��路网中里起始�Ҏ��q�且没有被检查过的点�Q�把�q�个�Ҏ��入OPEN�l�中�{�待��查�?br>2�Q?从OPEN表中扑և�距�v始点最�q�的点，扑և��q�个点的所有子节点�Q�把�q�个�Ҏ��到CLOSE表中�?br>3�Q?遍历考察�q�个点的子节炏V��求��些子节点距�v始点的距��d��|��攑֭�节点到OPEN表中�?br>4�Q?重复2�Q?�Q�步。直到OPEN表�ؓ�I�，或找到目标点�?/p>

Floyd��法
Floyd-Warshall ��法用来扑և�每对点之间的最短距��R��它需要用��L��矩阵来储存边�Q�这个算法通过考虑最佛_��路径来得到最佌��\径�?

注意单独一条边的�\径也不一定是最佌��\径�?

从�Q意一条单边�\径开始。所有两点之间的距离是边的权�Q�或者无�I�大�Q�如果两点之间没有边相连�?
对于每一寚w��?u �?v�Q�看看是否存在一个顶�?w 使得�?u �?w 再到 v 比己知的路径更短。如果是更新它�?
不可思议的是�Q�只要按排适当�Q�就能得到结果�?
// dist(i,j) ��Z��节点i到节点j的最短距��?br>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�?#8220;媒介节点”
For i←1 to n do
For j←1 to n do
if (dist(i,k) + dist(k,j) < dist(i,j)) then // 是否是更短的路径�Q?br>dist(i,j) = dist(i,k) + dist(k,j)�q�个��法的效率是O(V3)。它需要邻接矩阉|��储存图�?br>�q�个��法很容易实玎ͼ�只要几行�?
即��问题是求单源最短�\径，�q�是推荐使用�q�个��法�Q�如果时间和�I�间允许(只要有放的下��L��矩阵的空��_��旉��上就没问�?�?
[�~�辑] 旉��复杂�?O(N^3)

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

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

Prim��法

基本思想
1. 在图G=(V, E) �Q�V表示��点 �Q�E表示边）中，从集合V中�Q取一个顶点（例如取顶点v0�Q�放入集�?U中，�q�时 U={v0}�Q�集合T(E)为空�?br>2. 从v0出发��L��与U中顶点相邻（另一��点在V中）权值最��的边的另一��点v1�Q��ƈ使v1加入U。即U={v0,v1 }�Q�同时将该边加入集合T(E)中�?br>3. 重复2�Q�直到U=V为止�?br>�q�时T(E)中有n-1条边�Q�T = (U, T(E))��是一��|��生成树�?/p>

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
{��L��ȝ��成树最�q�的未加入顶点k}
min:=maxlongint;
for j:=1 to n do
if (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]:=cost[k,j];
closest[j]:=k;
end;
end;
end;{prim}

〖返回顶部�?/u>

�Ƨ拉回�\
定义�Q?br>在一个图中，��L��一条只通过每条边一�ơ的路径�Q�这叫做�Ƨ拉路径�Q�如果�v点和�l�点是同一点，那么�q�条回�\叫做�Ƨ拉回�\�Q?br>判定一个图中是否存在欧拉回路：�q�不是每个图都存在欧拉回路．以下分三�U�情况：
无向图：每个点的度数是偶敎ͼ�则存在欧拉回路．
有向图：每个�l�点的入度等于出度，则这个有向图中存在欧拉回路．
�ȝ��Q�以上两�U�情况很��单，其原理归根结底是每个�l�点�q�入和出�ȝ��路径条数相等�Q�就存在�Ƨ拉回�\�Q�还有一�U�更加复杂的情况�Q�那��是混合图．
混合图：�Q�有时边是单向的�Q�有时边是无向的�Q�就像城市交通网�l�，有的街道是单向的�Q�有的街道是双向的）找一个给每个无向边定向的�{�略�Q�这样就可以把图转化成�ؓ有向图，使每个顶点的入度与出度是相等的，�q�样��׃��存在�Ƨ拉回�\�Q?br>具体�q�程如下�Q�新��Z��个图�Q�对于原图中的无向边�Q�在新图中新加一个顶点e(i);对于原图中的每一个顶点j�Q�在新图中徏一个顶点v(i)�Q�对于原图中每一个顶点j和k之间有一条无向边i�Q�那么在新图中从e(i)出发�Q�添加两条边�Q�分别连向v(j)和v(k)�Q�容量都�?�Q?br>在新图中�Q�从源点向所有的e(i)都连一条容量�ؓ1的边�Q? 对于原图中每一个顶点j�Q�它原本都有一个入度in、出度out和无向度un。显然我们的目的是要把所有无向度都变成入度或出度�Q�从而��它的入度�{�于��d��数的一半，也就�?in + out + un) / 2�Q�显然与此同时出度也是��d��数的一半，如果��d��数是偶数的话�Q�。当�Ӟ��如果in已经大于��d��数的一半，或者��d��数是奇数�Q�那么欧拉回路肯定不存大。如果in��于��d��数的一半，�q�且��d��数是偶数�Q�那么我们在新图中从v�Q�j�Q�到汇点�q�一条边�Q�容量就�?in + out + un) / 2 – in�Q�也��是原图中顶点j�q�需要多��入度�?br>按照�q�个�|�络模型��出一个最大流�Q�如果每条从v(j)到汇点的辚w��辑ֈ�满流量的话，那么�Ƨ拉回�\成立�?/p>

〖返回顶部�?/u>

zhoubaozhong 2009-05-18 11:06 发表评论

��单的DP�Q�TJU 2794.Bus �Q�O(∩_�?O~

zhoubaozhong — Sat, 16 May 2009 02:25:00 GMT

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);
    }
}

zhoubaozhong 2009-05-16 10:25 发表评论

�l�典的打�?zoj 3193 Accurately Say "CocaCola"! Again

zhoubaozhong — Mon, 04 May 2009 14:14:00 GMT

#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
比赛时没有想刎ͼ��是靠�h脑�D例，��D��考虑不完��_��出现很多错误�Q�后来经高�h指点�Q�编学了个辅助程序，�l�于ac了！
O(∩_∩)O~�Q�看来还是要好好利用电脑�Q�！

�ȝ��序：

#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");
    }
}

zhoubaozhong 2009-05-04 22:14 发表评论

HDU 2690 Boys and girls

zhoubaozhong — Wed, 29 Apr 2009 13:01:00 GMT

#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");
    }
}

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

zhoubaozhong 2009-04-29 21:01 发表评论

HDU 2687 Matrix Rotation

zhoubaozhong — Mon, 27 Apr 2009 12:41:00 GMT

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

#include
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++) //首先求解每��@环四�ơ的��d��*(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的结�?br>            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                printf(" ");}
            printf("\n");
        }
    }
}

�q�题只要分清对应的�{动位�|�就能求解！�q�要注意转动��序�Q�！�Q?br>

zhoubaozhong 2009-04-27 20:41 发表评论

��单博弈！�Q�HDU 1847

zhoubaozhong — Sun, 26 Apr 2009 02:53:00 GMT

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

该题属于��单博弈题,只要��结果化到最��可以推��律！�Q?/span>

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

O(∩_∩)O~

zhoubaozhong 2009-04-26 10:53 发表评论

�q�踪法求解洗牌问�?HDU 1210

zhoubaozhong — Tue, 21 Apr 2009 08:34:00 GMT

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

开始寻找规律，找了好久想不出，最�l�想��C��q�踪�W�一张牌来进行求解！O(∩_∩)O~

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

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

�z�牌问题�Q?br>很多人都是跟�t�第一张牌来完成的�Q�大家会不会证明呢？

定理1�Q�当�W�一张牌(�?)回到初始位置�Ӟ��所有的牌都回到了初始位�|��?br>
证明�Q�设有一�ơ操作，某牌在操作前处于位置r(1<=r<=2*N)�Q�那么，操作后，如果r原来是前一半的�Q�显然r'=r*2; 否则�Q�r'=(r-n)*2-1�Q�即r'='r*2-(N*2+1);
��两个式子综合，可以得到r'= (r*2)%(N*2+1);
�Ҏ��同余定理之一 ((i%m)*j)%m=(i*j)%M�Q�可以整理出公式�Q�i�ơ操作后�Q�该牌的位置为：
(r*(2^i))%(N*2+1);其中^表示乘方�?br>现在�Q�我们假讄��q�M�ơ操作后�Q�牌1回到了初始位�|�，�?1*(2^M))%(N*2+1)=1�Ӟ��再次应用同余定理�Q�可以证明对于�Q意的k(1<=k<=2*N)�Q�有(k*(2^M))%(N*2+1)=k�Q�翻译成自然语言��是�Q�当�W�一张牌回到初始位置�Ӟ��所有的牌都回到了初始位�|�。命题得证�?br>
定理2�Q�一定存在某�ơ操作M�Q�这�ơ操作后�Q�所有的牌都回到了初始位�|��?br>证明�Q�我们已�l�证明了�?回到初始位置�Ӟ��所有的牌都回到初始位置�Q�所以我们只需要证明牌1可以回到初始位置�Q�即(2^M)%(N*2+1)=1一定有正整数解。证明这个定理前我们首先证明�q�样一个定理：
定理2.1�Q?2*r)%(2*n+1)==t
当t��定�?�?*n中的某值时(1因�ؓ2*n+1是奇敎ͼ�我们只要看一下就会发现r到t是一个一一映射�Q�当t为偶数时�Q�显然r=t/2�Q�当t为奇数时�Q�r=(t+1)/2+n�Q?br>
现在我们来证明定�?。运用反正法�Q�若�?永远不能回到初始位置�Q�根据鸽�W�定理，�?必然陷入了某个不包含位置1的��@环，因�ؓ下一状态仅和当前状态有养I��当前状态最多只�?*N�U�，所以显然一定在不超�q?*N+1�ơ操作内出现重复状态。而重复状态则意味着循环�?br>因�ؓ我们假设�q�一循环不包括位�|?�Q�我们设f(i)为��@环中某状态，f(0)=1,f(n+1)=(f(n)*2)%(2*N+1)�Q�f(j)��q�次循环后出现的重复状态，即f(i)=f(j)。因为��@环一直持�l�，不妨假设j>i+i。又因�ؓ循环不包括状�?�Q�即对于��L��的k>=i�Q�f(k)!=1
�Ҏ��定理2.1�Q�我们可以根据当前状态推��Z��一状态，换句话说�Q�若f(i)=f(j)�Q�则f(i-1)=f(j-1)。��l�套用定�?.1�Q�可以得到f(i-i)=f(j-i)�Q�即�Q�f(j-i)=f(0)=1。又有假设j>i+i�Q�即j-i>i�Q�与另一假设对于��L��的k>=i�Q�f(k)!=1矛盾�?br>因此�Q�可以证明，�?所陷入的��@环，必然是包含位�|?的，即一定有某次操作�Q�操作后�?回到了初始状态。而且昄��的，初始状态就是这循环中的一个状态�?br>因此命题得证�?br>

zhoubaozhong 2009-04-21 16:34 发表评论

HDU 2608 AC了好久，最�l�列��Z��?0才找到规率！晕啊�Q�！

zhoubaozhong — Sun, 19 Apr 2009 10:40:00 GMT

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

#include <stdio.h>  //��Cؓ1的是某数的��^�Ҏ��某数�q�x��?倍，之前�l�果之和取余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;
}

zhoubaozhong 2009-04-19 18:40 发表评论

zhoubaozhong — Sat, 18 Apr 2009 13:26:00 GMT

     因�ؓ我是菜鸟�Q�所以我一无是�?
     因�ؓ我是菜鸟�Q�所以我只会畅想�Q�！�Q?/span>
     因�ؓ我是菜鸟�Q�所以我只是大家的篏赘！�Q�！�Q�！
     因�ؓ我是菜鸟�Q�所以我不会在寻求改变！�Q�！�Q�！�Q�！
     因�ؓ我是菜鸟�Q�所以我改变不了什么只有自己去承受�Q�！�Q�！�Q�！�Q?/span>
     不就是个人吗�Q�！不就是缺��讨论吗�Q�！大家不需�?�q�嘛�q�要自作多情呢！�Q�！�Q�！�Q�！�Q?/span>
     我还�q�轻�Q�我玩的��P��Q�！�Q�！�Q�！�Q�！�Q�！�Q�！�Q�！�Q�！�Q�！�Q�！

zhoubaozhong 2009-04-18 21:26 发表评论