2009年5月18日
今天組隊(duì)比賽時遇到了漢諾塔的題，開始時以為很難，但是仔細(xì)看題時，想到了曾今在杭電上做個一題，卻發(fā)現(xiàn)是水題一道，直接一個打表！
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]);
}
}
規(guī)律：
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 閱讀(944) |
評論 (0) |
編輯 收藏【圖論】
1、Dijkstra算法
2、Floyd算法
3、Kruskal算法
4、Prim算法
5、歐拉回路
Dijkstra算法
Dijkstra算法是典型最短路算法，用于計算一個節(jié)點(diǎn)到其他所有節(jié)點(diǎn)的最短路徑。主要特點(diǎn)是以起始點(diǎn)為中心向外層層擴(kuò)展，直到擴(kuò)展到終點(diǎn)為止。Dijkstra算法能得出最短路徑的最優(yōu)解，但由于它遍歷計算的節(jié)點(diǎn)很多，所以效率低。
Dijkstra算法是很有代表性的最短路算法，在很多專業(yè)課程中都作為基本內(nèi)容有詳細(xì)的介紹，如數(shù)據(jù)結(jié)構(gòu)，圖論，運(yùn)籌學(xué)等等。
Dijkstra一般的表述通常有兩種方式，一種用永久和臨時標(biāo)號方式，一種是用OPEN, CLOSE表方式，Drew為了和下面要介紹的 A* 算法和 D* 算法表述一致，這里均采用OPEN,CLOSE表的方式。
大概過程：
創(chuàng)建兩個表，OPEN, CLOSE。
OPEN表保存所有已生成而未考察的節(jié)點(diǎn)，CLOSED表中記錄已訪問過的節(jié)點(diǎn)。
1． 訪問路網(wǎng)中里起始點(diǎn)最近且沒有被檢查過的點(diǎn)，把這個點(diǎn)放入OPEN組中等待檢查。
2． 從OPEN表中找出距起始點(diǎn)最近的點(diǎn)，找出這個點(diǎn)的所有子節(jié)點(diǎn)，把這個點(diǎn)放到CLOSE表中。
3． 遍歷考察這個點(diǎn)的子節(jié)點(diǎn)。求出這些子節(jié)點(diǎn)距起始點(diǎn)的距離值，放子節(jié)點(diǎn)到OPEN表中。
4． 重復(fù)2，3，步。直到OPEN表為空，或找到目標(biāo)點(diǎn)。
Floyd算法
Floyd-Warshall 算法用來找出每對點(diǎn)之間的最短距離。它需要用鄰接矩陣來儲存邊，這個算法通過考慮最佳子路徑來得到最佳路徑。
注意單獨(dú)一條邊的路徑也不一定是最佳路徑。
從任意一條單邊路徑開始。所有兩點(diǎn)之間的距離是邊的權(quán)，或者無窮大，如果兩點(diǎn)之間沒有邊相連。
對于每一對頂點(diǎn) u 和 v，看看是否存在一個頂點(diǎn) w 使得從 u 到 w 再到 v 比己知的路徑更短。如果是更新它。
不可思議的是，只要按排適當(dāng)，就能得到結(jié)果。
// dist(i,j) 為從節(jié)點(diǎn)i到節(jié)點(diǎn)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為“媒介節(jié)點(diǎn)”
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)。它需要鄰接矩陣來儲存圖。
這個算法很容易實(shí)現(xiàn)，只要幾行。
即使問題是求單源最短路徑，還是推薦使用這個算法，如果時間和空間允許(只要有放的下鄰接矩陣的空間，時間上就沒問題)。
[編輯] 時間復(fù)雜度 O(N^3)
Kruskal算法
基本思想
假設(shè)WN=(V,{E})是一個含有n個頂點(diǎn)的連通網(wǎng)，則按照克魯斯卡爾算法構(gòu)造最小生成樹的過程為：先構(gòu)造一個只含n個頂點(diǎn)，而邊集為空的子圖，若將該子圖中各個頂點(diǎn)看成是各棵樹上的根結(jié)點(diǎn)，則它是一個含有n棵樹的一個森林。之后，從網(wǎng)的邊集E中選取一條權(quán)值最小的邊，若該條邊的兩個頂點(diǎn)分屬不同的樹，則將其加入子圖，也就是說，將這兩個頂點(diǎn)分別所在的兩棵樹合成一棵樹；反之，若該條邊的兩個頂點(diǎn)已落在同一棵樹上，則不可取，而應(yīng)該取下一條權(quán)值最小的邊再試之。依次類推，直至森林中只有一棵樹，也即子圖中含有n-1條邊為止。</p>
Procedure kruskal(V,E);
begin
sort(E,1,m);//將邊按照權(quán)值排序
for t:=1 to n do begin
if getfather(edge[t].u)<>getfather(edge[t].v) then begin //利用并查集判斷兩個頂點(diǎn)是否在同一集合內(nèi)
tot:=tot+edge[t].data;//計算權(quán)值和
union(edge[t].u,edge[t].v);//合并頂點(diǎn)
inc(k);//合并次數(shù)
end;
end;
if k=n-1 then 形成了一棵最小生成樹
else 不存在這樣的最小生成樹；
end;
優(yōu)化：在判斷兩個頂點(diǎn)是否在同一集合內(nèi)時可用并查集
Prim算法
基本思想
1. 在圖G=(V, E) （V表示頂點(diǎn) ，E表示邊）中，從集合V中任取一個頂點(diǎn)（例如取頂點(diǎn)v0）放入集合 U中，這時 U={v0}，集合T(E)為空。
2. 從v0出發(fā)尋找與U中頂點(diǎn)相鄰（另一頂點(diǎn)在V中）權(quán)值最小的邊的另一頂點(diǎn)v1，并使v1加入U。即U={v0,v1 }，同時將該邊加入集合T(E)中。
3. 重復(fù)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
{尋找離生成樹最近的未加入頂點(diǎn)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; {將頂點(diǎn)k加入生成樹}
{生成樹中增加一條新的邊k到closest[k]}
{修正各點(diǎn)的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}
〖返回頂部〗
歐拉回路
定義：
在一個圖中，尋找一條只通過每條邊一次的路徑，這叫做歐拉路徑，如果起點(diǎn)和終點(diǎn)是同一點(diǎn)，那么這條回路叫做歐拉回路．
判定一個圖中是否存在歐拉回路：并不是每個圖都存在歐拉回路．以下分三種情況：
無向圖：每個點(diǎn)的度數(shù)是偶數(shù)，則存在歐拉回路．
有向圖：每個結(jié)點(diǎn)的入度等于出度，則這個有向圖中存在歐拉回路．
總結(jié)：以上兩種情況很簡單，其原理歸根結(jié)底是每個結(jié)點(diǎn)進(jìn)入和出去的路徑條數(shù)相等，就存在歐拉回路．還有一種更加復(fù)雜的情況．那就是混合圖．
混合圖：（有時邊是單向的，有時邊是無向的，就像城市交通網(wǎng)絡(luò)，有的街道是單向的，有的街道是雙向的）找一個給每個無向邊定向的策略，這樣就可以把圖轉(zhuǎn)化成為有向圖，使每個頂點(diǎn)的入度與出度是相等的，這樣就會存在歐拉回路．
具體過程如下：新建一個圖，對于原圖中的無向邊，在新圖中新加一個頂點(diǎn)e(i);對于原圖中的每一個頂點(diǎn)j，在新圖中建一個頂點(diǎn)v(i)，對于原圖中每一個頂點(diǎn)j和k之間有一條無向邊i，那么在新圖中從e(i)出發(fā)，添加兩條邊，分別連向v(j)和v(k)，容量都是1．
在新圖中，從源點(diǎn)向所有的e(i)都連一條容量為1的邊．. 對于原圖中每一個頂點(diǎn)j，它原本都有一個入度in、出度out和無向度un。顯然我們的目的是要把所有無向度都變成入度或出度，從而使它的入度等于總度數(shù)的一半，也就是(in + out + un) / 2（顯然與此同時出度也是總度數(shù)的一半，如果總度數(shù)是偶數(shù)的話）。當(dāng)然，如果in已經(jīng)大于總度數(shù)的一半，或者總度數(shù)是奇數(shù)，那么歐拉回路肯定不存大。如果in小于總度數(shù)的一半，并且總度數(shù)是偶數(shù)，那么我們在新圖中從v（j）到匯點(diǎn)連一條邊，容量就是(in + out + un) / 2 – in，也就是原圖中頂點(diǎn)j還需要多少入度。
按照這個網(wǎng)絡(luò)模型算出一個最大流，如果每條從v(j)到匯點(diǎn)的邊都達(dá)到滿流量的話，那么歐拉回路成立。
〖返回頂部〗
posted @
2009-05-18 11:06 zhoubaozhong 閱讀(263) |
評論 (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 閱讀(142) |
評論 (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比賽時沒有想到，就是靠人腦舉例，導(dǎo)致考慮不完整，出現(xiàn)很多錯誤！后來經(jīng)高人指點(diǎn)，編學(xué)了個輔助程序，終于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 閱讀(456) |
評論 (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");
}
}
這題是在組隊(duì)時候做的！需要考慮很多情況！特別 0 和 1 ！！
http://acm.hdu.edu.cn/showproblem.php?pid=2690
posted @
2009-04-29 21:01 zhoubaozhong 閱讀(250) |
評論 (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++) //首先求解每循環(huán)四次的總和*(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的結(jié)果
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");
}
}
}
這題只要分清對應(yīng)的轉(zhuǎn)動位置就能求解！還要注意轉(zhuǎn)動順序！！！
posted @
2009-04-27 20:41 zhoubaozhong 閱讀(314) |
評論 (0) |
編輯 收藏
2009年4月21日
http://acm.hdu.edu.cn/showproblem.php?pid=1210開始尋找規(guī)律，找了好久想不出，最終想到了追蹤第一張牌來進(jìn)行求解！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++;//表示排序的次數(shù)
}
printf("%d\n",sum);
}
}
雖然做時不知道為什么！但是事后我在網(wǎng)上搜到了證明方法！
洗牌問題：
很多人都是跟蹤第一張牌來完成的，大家會不會證明呢？
定理1：當(dāng)?shù)谝粡埮?牌1)回到初始位置時，所有的牌都回到了初始位置。
證明：設(shè)有一次操作，某牌在操作前處于位置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);
根據(jù)同余定理之一 ((i%m)*j)%m=(i*j)%M，可以整理出公式：i次操作后，該牌的位置為：
(r*(2^i))%(N*2+1);其中^表示乘方。
現(xiàn)在，我們假設(shè)經(jīng)過M次操作后，牌1回到了初始位置，即(1*(2^M))%(N*2+1)=1時，再次應(yīng)用同余定理，可以證明對于任意的k(1<=k<=2*N)，有(k*(2^M))%(N*2+1)=k，翻譯成自然語言就是：當(dāng)?shù)谝粡埮苹氐匠跏嘉恢脮r，所有的牌都回到了初始位置。命題得證。
定理2：一定存在某次操作M，這次操作后，所有的牌都回到了初始位置。
證明：我們已經(jīng)證明了牌1回到初始位置時，所有的牌都回到初始位置，所以我們只需要證明牌1可以回到初始位置，即(2^M)%(N*2+1)=1一定有正整數(shù)解。證明這個定理前我們首先證明這樣一個定理：
定理2.1：(2*r)%(2*n+1)==t
當(dāng)t確定為1到2*n中的某值時(1<t<=2*n)，r在1到2*n間有唯一解
因?yàn)?*n+1是奇數(shù)，我們只要看一下就會發(fā)現(xiàn)r到t是一個一一映射，當(dāng)t為偶數(shù)時，顯然r=t/2，當(dāng)t為奇數(shù)時，r=(t+1)/2+n，
現(xiàn)在我們來證明定理2。運(yùn)用反正法，若牌1永遠(yuǎn)不能回到初始位置，根據(jù)鴿籠定理，牌1必然陷入了某個不包含位置1的循環(huán)，因?yàn)橄乱粻顟B(tài)僅和當(dāng)前狀態(tài)有關(guān)，當(dāng)前狀態(tài)最多只有2*N種，所以顯然一定在不超過2*N+1次操作內(nèi)出現(xiàn)重復(fù)狀態(tài)。而重復(fù)狀態(tài)則意味著循環(huán)。
因?yàn)槲覀兗僭O(shè)這一循環(huán)不包括位置1，我們設(shè)f(i)為循環(huán)中某狀態(tài)，f(0)=1,f(n+1)=(f(n)*2)%(2*N+1)，f(j)為若干次循環(huán)后出現(xiàn)的重復(fù)狀態(tài)，即f(i)=f(j)。因?yàn)檠h(huán)一直持續(xù)，不妨假設(shè)j>i+i。又因?yàn)檠h(huán)不包括狀態(tài)1，即對于任意的k>=i，f(k)!=1
根據(jù)定理2.1，我們可以根據(jù)當(dāng)前狀態(tài)推出上一狀態(tài)，換句話說，若f(i)=f(j)，則f(i-1)=f(j-1)。繼續(xù)套用定理2.1，可以得到f(i-i)=f(j-i)，即：f(j-i)=f(0)=1。又有假設(shè)j>i+i，即j-i>i，與另一假設(shè)對于任意的k>=i，f(k)!=1矛盾。
因此，可以證明，牌1所陷入的循環(huán)，必然是包含位置1的，即一定有某次操作，操作后牌1回到了初始狀態(tài)。而且顯然的，初始狀態(tài)就是這循環(huán)中的一個狀態(tài)。
因此命題得證。
posted @
2009-04-21 16:34 zhoubaozhong 閱讀(662) |
評論 (0) |
編輯 收藏
2009年4月18日
因?yàn)槲沂遣锁B！所以我一無是處!
因?yàn)槲沂遣锁B！所以我只會暢想！！！
因?yàn)槲沂遣锁B！所以我只是大家的累贅！！！！！
因?yàn)槲沂遣锁B！所以我不會在尋求改變！！！！！！！
因?yàn)槲沂遣锁B！所以我改變不了什么只有自己去承受！！！！！！！
不就是個人嗎！！不就是缺少討論嗎！！大家不需要,干嘛還要自作多情呢！！！！！！！！
我還年輕！我玩的起！！！！！！！！！！！！！！！！！！！！！
posted @
2009-04-18 21:26 zhoubaozhong 閱讀(224) |
評論 (10) |
編輯 收藏