置頂隨筆
摘要: 【問題描述】
一本書的頁數為N，頁碼從1開始編起，請你求出全部頁碼中，用了多少個0，1，2，…，9。其中—個頁碼不含多余的0，如N＝1234時第5頁不是0005，只是5。
【輸入】
一個正整數N(N≤109)，表示總的頁碼。
【輸出】
共十行：第k行為數字k-1的個數。
【樣例】
count.in count.out
11 1
4
1
1
閱讀全文
摘要: HDU 1217 Arbitrage
題意是說給你N種貨幣以及，貨幣與貨幣之間的M種匯率，
讓你判斷是否存在經過若干次貨幣的兌換使得某種貨幣的
價值大于原來本身的價值，比如所：美元：美元 = 1 ： 1；
題意就是讓你判斷，在當前的貨幣兌換率的基礎上，能不能
使 美元 ： 美元 > 1 : 1; 利用Floyd算法即可搞定，代碼如下：
閱讀全文
摘要: HDU 1280 前m大的數
給定的N個整數序列， 兩兩求和，從大到小輸出M個和數。
因為所有整數不超過5000，則相加不會超過10000，可以
用哈希解決。
閱讀全文
HDU 1116 Play on Words這個題目要運用到歐拉路得相關知識，并且也要并查集，題目說的是：給你n個單詞，要你判斷這些單詞能不能首尾相連。
理解題目意思后，進行轉化，輸入字符串，提取首位字母作為下標來表示兩節點的出現，以及相對應節點入度和出度的增加，
轉化為并查集的應用即可。那么從可以想象一幅由首位字母節點構成的圖，當且僅當圖是一條歐拉回路或者歐拉通路的時候，
才能滿足題目的要求，至于歐拉回路和歐拉通路的判定可以總結為如下：
1）所有的點聯通
2）歐拉回路中所有點的入度和出度一樣。
3）歐拉通路中起點的入度 - 出度 = 1，終點的 初度 - 入度 = 1， 其他的所有點入度 = 出度；
有了上面這些知識點做鋪墊，相信理解起來就比較容易了，下面我的代碼：
1 #include<stdio.h>
2 #include<string.h>
3 #include<math.h>
4 #define N 30
5 /*
6 歐拉回路，所有點連通，并且所有點的入度等于出度。
7 歐拉通路。從原點 S出發，經過所有點，從終點 t出去。
8 所有點除起點終點外的度都是偶數，且出度等于入度
9 起點的出度比入度大 1
10 終點的入度比出度大 1
11 */
12
13 int father[N],vis[N];
14 //father[i] 表示節點 i 的 BOSS ！ vis[i]表示節點 i 出現過！
15 int findx(int x)
16 { //找節點 x 的 BOSS ！
17 if(father[x]!=x)
18 father[x]=findx(father[x]);
19 return father[x];
20 }
21 void merge(int a,int b)
22 { // 合并 節點 a 和節點 b ！
23 int x,y;
24 x=findx(a);
25 y=findx(b);
26 if(x!=y) father[x]=y;
27 }
28 int main()
29 {
30 int text,cnt,i,j,n,out[N],in[N],p[30],a,b;
31 char str[1001];
32 scanf("%d",&text);
33 while(text--)
34 {
35 scanf("%d",&n);
36 memset(out,0,sizeof(out));
37 memset(in,0,sizeof(in));
38 memset(vis,0,sizeof(vis));
39 for(i=0;i<26;i++)
40 father[i]=i; //初始化數組
41 while(n--)
42 { // 處理所給信息 ！
43 scanf("%s",str);
44 a=str[0]-'a';
45 b=str[strlen(str)-1]-'a';
46 merge(a,b);
47 out[a]++;
48 in[b]++; // 記錄節點 a 和 b的入度和出度
49 vis[a]=1;
50 vis[b]=1; //標記節點 a 和 b的出現
51 }
52 for(i=0;i<26;i++)
53 father[i]=findx(i); //找出每個節點的 BOSS
54 for(cnt=0,i=0;i<26;i++)
55 if(vis[i] && father[i]==i)
56 cnt++; // 統計最終 BOSS 即根節點的個數 。
57 if(cnt>1) //圖不連通
58 {
59 printf("The door cannot be opened.\n");
60 continue;
61 }
62
63 for(j=0,i=0;i<26;i++)
64 if(vis[i] && out[i]!=in[i])
65 p[j++]=i; //統計入度和出度不相等的點的信息
66 if(j==0)
67 {//歐拉回路，即環
68 printf("Ordering is possible.\n");
69 continue;
70 }
71 if(j==2 && ( out[p[0]]-in[p[0]]==1 && in[p[1]]-out[p[1]]==1
72 || out[p[1]]-in[p[1]]==1 && in[p[0]]-out[p[0]]==1 ) )
73 {//歐拉通路
74 printf("Ordering is possible.\n");
75 continue;
76 }
77 printf("The door cannot be opened.\n");
78 }
79 return 0;
80 }
81
摘要: HDU 1301 Jungle Roads
這個題目的意思就是說給你n個相關點，用A - I 來表示，然后給出n-1行，第 i 行表示從點 i 到其他點的相關信息。
在給出的map的基礎上，要求選擇適當的路線，使得所有給出的點都能夠到達任意其他點，問題規模不大，直接矩陣
存儲，利用prim 算法搞定。
閱讀全文
摘要: HDU 1233 還是暢通工程
題目意思就是給你一個有n個點的圖，給出n *（n-1）/ 2 條邊的信息，包括邊的端點和邊的長度，要求
在滿足所有點在同一個連通分支上的前提下，選擇最短的道路來修建。典型的最小生成樹算法，同樣，問題
規模不大，直接矩陣就可以勝任。
閱讀全文
HDU 1232 暢通工程這個題目也是典型的最小生成樹算法的利用，不同于其他的題目就在于其它要求的是要添加的邊的最少數目，使得任意兩
點都有聯系，利用
并查集算法 ，在題目已經給出的map基礎上，統計兩棵樹相并的次數，即使要添加的路徑的最少數目。
1 #include<stdio.h>
2 #include<stdlib.h>
3
4 int father[1001], tot;//father[i] 記錄 i 的 BOSS ！
5 //tot 統計最初至少需要添加的路徑數目 ！
6
7 int find(int x)
8 {//找 到 x 的 BOSS ！
9 int r = x;
10 while (r != father[r]) r = father[r];
11 return r;//
12 }
13
14 void join(int a, int b)
15 {//將 a 和 b 的 BOSS 統一！
16 int fa = find(a), fb = find(b);
17 if (fa != fb)
18 {
19 father[fa] = fb;
20 tot --; // 統一了一次兩個陣營的 BOSS ，所以需要添加的路徑的數目減一！
21 }
22 }
23
24 int main()
25 {
26 int n, m, x, y;
27 while (scanf("%d", &n), n)
28 {
29 scanf("%d", &m);
30 tot = n-1; // 初始化 tot 等于 n 個點聯通所需要的最少邊的數目 ！
31 father[n+1];
32 for (int i=1; i<=n; i++)father[i] = i;//初始化自己是自己的 BOSS ！
33
34 for (int i=1; i<=m; i++)
35 {
36 scanf("%d %d",&x, &y);
37 join(x, y);
38 }
39 printf("%d\n",tot); //輸出在已有基礎上還需要的邊的數目！
40 }
41 return 0;
42 }
43
HDU 1162 Eddy's picture這個題目也是典型的最小生成樹算法，跟
之前的那個題目是差不多的，也就是說：給你n個二維平面點，
讓你添加適當的邊，使得所有的點都在同一個聯通分支上，也就是說任何點之間都有路徑可以到達。
問題規模不大，直接用矩陣存數據，利用
prim 算法就可以搞定。此時任意兩點之間的“權值”就是
兩點之間的距離。
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<math.h>
4 #include<string.h>
5 const double MAX = 1000000000.0;
6 struct Point
7 {
8 double x, y;
9 }point[101];
10
11 double map[101][101];
12 int v[101], n;
13
14 double Dis(Point a, Point b)
15 {
16 return sqrt((a.x - b.x) * (a.x - b.x) +(a.y - b.y) * (a.y - b.y));
17 }
18
19 void Build()
20 {
21 memset(map, 0, sizeof(map));
22 for (int i=0; i<n; i++)
23 {
24 for (int j=i; j<n; j++)
25 {
26 if (i == j) map[i][j] = MAX;
27 else
28 {
29 map[j][i] = map[i][j] = Dis(point[i], point[j]);
30 }
31 }
32 }
33 }
34
35 void MinTree()
36 {
37 double sum = 0.0, min;
38 memset(v, 0, sizeof(v));
39 v[0] = 1;
40 int flag;
41 for (int i=1; i<n; i++)
42 {
43 min = MAX;
44 for (int j=0; j<n; j++)
45 {
46 if (!v[j] && map[0][j] < min)
47 {
48 min = map[0][j];
49 flag = j;
50 }
51 }
52 sum += min;
53 v[flag] = 1;
54 for (int j=0; j<n; j++)
55 {
56 if (!v[j] && map[0][j] > map[flag][j])
57 {
58 map[0][j] = map[flag][j];
59 }
60 }
61 }
62 printf("%.2lf\n",sum);
63 }
64 int main()
65 {
66 while (scanf("%d", &n)!= EOF)
67 {
68 map[n][n];
69 point[n];
70 for (int i=0; i<n; i++)
71 {
72 scanf("%lf %lf", &point[i].x, &point[i].y);
73 }
74 Build();
75 MinTree();
76 }
77 return 0;
78 }
79
摘要: HDU 1102 Constructing Roads
這個題目的意思就是說，給你一個有n個村莊的地圖，map[i][j]表示從村莊 i 到村莊 j 的距離，然后給你
m 條已有道路，讓你在這個基礎上添加適當的道路，使得所有村莊之間都是聯通的，求添加道路的最短距
離的值。
閱讀全文
2011年8月18日
摘要: 【問題描述】
一本書的頁數為N，頁碼從1開始編起，請你求出全部頁碼中，用了多少個0，1，2，…，9。其中—個頁碼不含多余的0，如N＝1234時第5頁不是0005，只是5。
【輸入】
一個正整數N(N≤109)，表示總的頁碼。
【輸出】
共十行：第k行為數字k-1的個數。
【樣例】
count.in count.out
11 1
4
1
1
閱讀全文
2011年8月17日
摘要: HDU 1217 Arbitrage
題意是說給你N種貨幣以及，貨幣與貨幣之間的M種匯率，
讓你判斷是否存在經過若干次貨幣的兌換使得某種貨幣的
價值大于原來本身的價值，比如所：美元：美元 = 1 ： 1；
題意就是讓你判斷，在當前的貨幣兌換率的基礎上，能不能
使 美元 ： 美元 > 1 : 1; 利用Floyd算法即可搞定，代碼如下：
閱讀全文
2011年8月16日
摘要: HDU 1029 Ignatius and the Princess IV
給N個數字， N為奇數， 輸出出現次數大于 N / 2 的數
閱讀全文
摘要: HDU 1280 前m大的數
給定的N個整數序列， 兩兩求和，從大到小輸出M個和數。
因為所有整數不超過5000，則相加不會超過10000，可以
用哈希解決。
閱讀全文
2011年7月18日
HDU 1116 Play on Words這個題目要運用到歐拉路得相關知識，并且也要并查集，題目說的是：給你n個單詞，要你判斷這些單詞能不能首尾相連。
理解題目意思后，進行轉化，輸入字符串，提取首位字母作為下標來表示兩節點的出現，以及相對應節點入度和出度的增加，
轉化為并查集的應用即可。那么從可以想象一幅由首位字母節點構成的圖，當且僅當圖是一條歐拉回路或者歐拉通路的時候，
才能滿足題目的要求，至于歐拉回路和歐拉通路的判定可以總結為如下：
1）所有的點聯通
2）歐拉回路中所有點的入度和出度一樣。
3）歐拉通路中起點的入度 - 出度 = 1，終點的 初度 - 入度 = 1， 其他的所有點入度 = 出度；
有了上面這些知識點做鋪墊，相信理解起來就比較容易了，下面我的代碼：
1 #include<stdio.h>
2 #include<string.h>
3 #include<math.h>
4 #define N 30
5 /*
6 歐拉回路，所有點連通，并且所有點的入度等于出度。
7 歐拉通路。從原點 S出發，經過所有點，從終點 t出去。
8 所有點除起點終點外的度都是偶數，且出度等于入度
9 起點的出度比入度大 1
10 終點的入度比出度大 1
11 */
12
13 int father[N],vis[N];
14 //father[i] 表示節點 i 的 BOSS ！ vis[i]表示節點 i 出現過！
15 int findx(int x)
16 { //找節點 x 的 BOSS ！
17 if(father[x]!=x)
18 father[x]=findx(father[x]);
19 return father[x];
20 }
21 void merge(int a,int b)
22 { // 合并 節點 a 和節點 b ！
23 int x,y;
24 x=findx(a);
25 y=findx(b);
26 if(x!=y) father[x]=y;
27 }
28 int main()
29 {
30 int text,cnt,i,j,n,out[N],in[N],p[30],a,b;
31 char str[1001];
32 scanf("%d",&text);
33 while(text--)
34 {
35 scanf("%d",&n);
36 memset(out,0,sizeof(out));
37 memset(in,0,sizeof(in));
38 memset(vis,0,sizeof(vis));
39 for(i=0;i<26;i++)
40 father[i]=i; //初始化數組
41 while(n--)
42 { // 處理所給信息 ！
43 scanf("%s",str);
44 a=str[0]-'a';
45 b=str[strlen(str)-1]-'a';
46 merge(a,b);
47 out[a]++;
48 in[b]++; // 記錄節點 a 和 b的入度和出度
49 vis[a]=1;
50 vis[b]=1; //標記節點 a 和 b的出現
51 }
52 for(i=0;i<26;i++)
53 father[i]=findx(i); //找出每個節點的 BOSS
54 for(cnt=0,i=0;i<26;i++)
55 if(vis[i] && father[i]==i)
56 cnt++; // 統計最終 BOSS 即根節點的個數 。
57 if(cnt>1) //圖不連通
58 {
59 printf("The door cannot be opened.\n");
60 continue;
61 }
62
63 for(j=0,i=0;i<26;i++)
64 if(vis[i] && out[i]!=in[i])
65 p[j++]=i; //統計入度和出度不相等的點的信息
66 if(j==0)
67 {//歐拉回路，即環
68 printf("Ordering is possible.\n");
69 continue;
70 }
71 if(j==2 && ( out[p[0]]-in[p[0]]==1 && in[p[1]]-out[p[1]]==1
72 || out[p[1]]-in[p[1]]==1 && in[p[0]]-out[p[0]]==1 ) )
73 {//歐拉通路
74 printf("Ordering is possible.\n");
75 continue;
76 }
77 printf("The door cannot be opened.\n");
78 }
79 return 0;
80 }
81
摘要: HDU 1301 Jungle Roads
這個題目的意思就是說給你n個相關點，用A - I 來表示，然后給出n-1行，第 i 行表示從點 i 到其他點的相關信息。
在給出的map的基礎上，要求選擇適當的路線，使得所有給出的點都能夠到達任意其他點，問題規模不大，直接矩陣
存儲，利用prim 算法搞定。
閱讀全文
摘要: HDU 1233 還是暢通工程
題目意思就是給你一個有n個點的圖，給出n *（n-1）/ 2 條邊的信息，包括邊的端點和邊的長度，要求
在滿足所有點在同一個連通分支上的前提下，選擇最短的道路來修建。典型的最小生成樹算法，同樣，問題
規模不大，直接矩陣就可以勝任。
閱讀全文
HDU 1232 暢通工程這個題目也是典型的最小生成樹算法的利用，不同于其他的題目就在于其它要求的是要添加的邊的最少數目，使得任意兩
點都有聯系，利用
并查集算法 ，在題目已經給出的map基礎上，統計兩棵樹相并的次數，即使要添加的路徑的最少數目。
1 #include<stdio.h>
2 #include<stdlib.h>
3
4 int father[1001], tot;//father[i] 記錄 i 的 BOSS ！
5 //tot 統計最初至少需要添加的路徑數目 ！
6
7 int find(int x)
8 {//找 到 x 的 BOSS ！
9 int r = x;
10 while (r != father[r]) r = father[r];
11 return r;//
12 }
13
14 void join(int a, int b)
15 {//將 a 和 b 的 BOSS 統一！
16 int fa = find(a), fb = find(b);
17 if (fa != fb)
18 {
19 father[fa] = fb;
20 tot --; // 統一了一次兩個陣營的 BOSS ，所以需要添加的路徑的數目減一！
21 }
22 }
23
24 int main()
25 {
26 int n, m, x, y;
27 while (scanf("%d", &n), n)
28 {
29 scanf("%d", &m);
30 tot = n-1; // 初始化 tot 等于 n 個點聯通所需要的最少邊的數目 ！
31 father[n+1];
32 for (int i=1; i<=n; i++)father[i] = i;//初始化自己是自己的 BOSS ！
33
34 for (int i=1; i<=m; i++)
35 {
36 scanf("%d %d",&x, &y);
37 join(x, y);
38 }
39 printf("%d\n",tot); //輸出在已有基礎上還需要的邊的數目！
40 }
41 return 0;
42 }
43
HDU 1162 Eddy's picture這個題目也是典型的最小生成樹算法，跟
之前的那個題目是差不多的，也就是說：給你n個二維平面點，
讓你添加適當的邊，使得所有的點都在同一個聯通分支上，也就是說任何點之間都有路徑可以到達。
問題規模不大，直接用矩陣存數據，利用
prim 算法就可以搞定。此時任意兩點之間的“權值”就是
兩點之間的距離。
1 #include<stdio.h>
2 #include<stdlib.h>
3 #include<math.h>
4 #include<string.h>
5 const double MAX = 1000000000.0;
6 struct Point
7 {
8 double x, y;
9 }point[101];
10
11 double map[101][101];
12 int v[101], n;
13
14 double Dis(Point a, Point b)
15 {
16 return sqrt((a.x - b.x) * (a.x - b.x) +(a.y - b.y) * (a.y - b.y));
17 }
18
19 void Build()
20 {
21 memset(map, 0, sizeof(map));
22 for (int i=0; i<n; i++)
23 {
24 for (int j=i; j<n; j++)
25 {
26 if (i == j) map[i][j] = MAX;
27 else
28 {
29 map[j][i] = map[i][j] = Dis(point[i], point[j]);
30 }
31 }
32 }
33 }
34
35 void MinTree()
36 {
37 double sum = 0.0, min;
38 memset(v, 0, sizeof(v));
39 v[0] = 1;
40 int flag;
41 for (int i=1; i<n; i++)
42 {
43 min = MAX;
44 for (int j=0; j<n; j++)
45 {
46 if (!v[j] && map[0][j] < min)
47 {
48 min = map[0][j];
49 flag = j;
50 }
51 }
52 sum += min;
53 v[flag] = 1;
54 for (int j=0; j<n; j++)
55 {
56 if (!v[j] && map[0][j] > map[flag][j])
57 {
58 map[0][j] = map[flag][j];
59 }
60 }
61 }
62 printf("%.2lf\n",sum);
63 }
64 int main()
65 {
66 while (scanf("%d", &n)!= EOF)
67 {
68 map[n][n];
69 point[n];
70 for (int i=0; i<n; i++)
71 {
72 scanf("%lf %lf", &point[i].x, &point[i].y);
73 }
74 Build();
75 MinTree();
76 }
77 return 0;
78 }
79
摘要: HDU 1102 Constructing Roads
這個題目的意思就是說，給你一個有n個村莊的地圖，map[i][j]表示從村莊 i 到村莊 j 的距離，然后給你
m 條已有道路，讓你在這個基礎上添加適當的道路，使得所有村莊之間都是聯通的，求添加道路的最短距
離的值。
閱讀全文