置頂隨筆
摘要: 【問題描述】
一本書的頁數(shù)為N，頁碼從1開始編起，請你求出全部頁碼中，用了多少個(gè)0，1，2，…，9。其中—個(gè)頁碼不含多余的0，如N＝1234時(shí)第5頁不是0005，只是5。
【輸入】
一個(gè)正整數(shù)N(N≤109)，表示總的頁碼。
【輸出】
共十行：第k行為數(shù)字k-1的個(gè)數(shù)。
【樣例】
count.in count.out
11 1
4
1
1
閱讀全文
摘要: HDU 1217 Arbitrage
題意是說給你N種貨幣以及，貨幣與貨幣之間的M種匯率，
讓你判斷是否存在經(jīng)過若干次貨幣的兌換使得某種貨幣的
價(jià)值大于原來本身的價(jià)值，比如所：美元：美元 = 1 ： 1；
題意就是讓你判斷，在當(dāng)前的貨幣兌換率的基礎(chǔ)上，能不能
使 美元 ： 美元 > 1 : 1; 利用Floyd算法即可搞定，代碼如下：
閱讀全文
摘要: HDU 1280 前m大的數(shù)
給定的N個(gè)整數(shù)序列， 兩兩求和，從大到小輸出M個(gè)和數(shù)。
因?yàn)樗姓麛?shù)不超過5000，則相加不會(huì)超過10000，可以
用哈希解決。
閱讀全文
HDU 1116 Play on Words這個(gè)題目要運(yùn)用到歐拉路得相關(guān)知識(shí)，并且也要并查集，題目說的是：給你n個(gè)單詞，要你判斷這些單詞能不能首尾相連。
理解題目意思后，進(jìn)行轉(zhuǎn)化，輸入字符串，提取首位字母作為下標(biāo)來表示兩節(jié)點(diǎn)的出現(xiàn)，以及相對(duì)應(yīng)節(jié)點(diǎn)入度和出度的增加，
轉(zhuǎn)化為并查集的應(yīng)用即可。那么從可以想象一幅由首位字母節(jié)點(diǎn)構(gòu)成的圖，當(dāng)且僅當(dāng)圖是一條歐拉回路或者歐拉通路的時(shí)候，
才能滿足題目的要求，至于歐拉回路和歐拉通路的判定可以總結(jié)為如下：
1）所有的點(diǎn)聯(lián)通
2）歐拉回路中所有點(diǎn)的入度和出度一樣。
3）歐拉通路中起點(diǎn)的入度 - 出度 = 1，終點(diǎn)的 初度 - 入度 = 1， 其他的所有點(diǎn)入度 = 出度；
有了上面這些知識(shí)點(diǎn)做鋪墊，相信理解起來就比較容易了，下面我的代碼：
1 #include<stdio.h>
2 #include<string.h>
3 #include<math.h>
4 #define N 30
5 /*
6 歐拉回路，所有點(diǎn)連通，并且所有點(diǎn)的入度等于出度。
7 歐拉通路。從原點(diǎn) S出發(fā)，經(jīng)過所有點(diǎn)，從終點(diǎn) t出去。
8 所有點(diǎn)除起點(diǎn)終點(diǎn)外的度都是偶數(shù)，且出度等于入度
9 起點(diǎn)的出度比入度大 1
10 終點(diǎn)的入度比出度大 1
11 */
12
13 int father[N],vis[N];
14 //father[i] 表示節(jié)點(diǎn) i 的 BOSS ！ vis[i]表示節(jié)點(diǎn) i 出現(xiàn)過！
15 int findx(int x)
16 { //找節(jié)點(diǎn) 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 { // 合并 節(jié)點(diǎn) a 和節(jié)點(diǎn) 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; //初始化數(shù)組
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]++; // 記錄節(jié)點(diǎn) a 和 b的入度和出度
49 vis[a]=1;
50 vis[b]=1; //標(biāo)記節(jié)點(diǎn) a 和 b的出現(xiàn)
51 }
52 for(i=0;i<26;i++)
53 father[i]=findx(i); //找出每個(gè)節(jié)點(diǎn)的 BOSS
54 for(cnt=0,i=0;i<26;i++)
55 if(vis[i] && father[i]==i)
56 cnt++; // 統(tǒng)計(jì)最終 BOSS 即根節(jié)點(diǎn)的個(gè)數(shù) 。
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; //統(tǒng)計(jì)入度和出度不相等的點(diǎn)的信息
66 if(j==0)
67 {//歐拉回路，即環(huán)
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
這個(gè)題目的意思就是說給你n個(gè)相關(guān)點(diǎn)，用A - I 來表示，然后給出n-1行，第 i 行表示從點(diǎn) i 到其他點(diǎn)的相關(guān)信息。
在給出的map的基礎(chǔ)上，要求選擇適當(dāng)?shù)穆肪€，使得所有給出的點(diǎn)都能夠到達(dá)任意其他點(diǎn)，問題規(guī)模不大，直接矩陣
存儲(chǔ)，利用prim 算法搞定。
閱讀全文
摘要: HDU 1233 還是暢通工程
題目意思就是給你一個(gè)有n個(gè)點(diǎn)的圖，給出n *（n-1）/ 2 條邊的信息，包括邊的端點(diǎn)和邊的長度，要求
在滿足所有點(diǎn)在同一個(gè)連通分支上的前提下，選擇最短的道路來修建。典型的最小生成樹算法，同樣，問題
規(guī)模不大，直接矩陣就可以勝任。
閱讀全文
HDU 1232 暢通工程這個(gè)題目也是典型的最小生成樹算法的利用，不同于其他的題目就在于其它要求的是要添加的邊的最少數(shù)目，使得任意兩
點(diǎn)都有聯(lián)系，利用
并查集算法 ，在題目已經(jīng)給出的map基礎(chǔ)上，統(tǒng)計(jì)兩棵樹相并的次數(shù)，即使要添加的路徑的最少數(shù)目。
1 #include<stdio.h>
2 #include<stdlib.h>
3
4 int father[1001], tot;//father[i] 記錄 i 的 BOSS ！
5 //tot 統(tǒng)計(jì)最初至少需要添加的路徑數(shù)目 ！
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 統(tǒng)一！
16 int fa = find(a), fb = find(b);
17 if (fa != fb)
18 {
19 father[fa] = fb;
20 tot --; // 統(tǒng)一了一次兩個(gè)陣營的 BOSS ，所以需要添加的路徑的數(shù)目減一！
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 個(gè)點(diǎn)聯(lián)通所需要的最少邊的數(shù)目 ！
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); //輸出在已有基礎(chǔ)上還需要的邊的數(shù)目！
40 }
41 return 0;
42 }
43
HDU 1162 Eddy's picture這個(gè)題目也是典型的最小生成樹算法，跟
之前的那個(gè)題目是差不多的，也就是說：給你n個(gè)二維平面點(diǎn)，
讓你添加適當(dāng)?shù)倪叄沟盟械狞c(diǎn)都在同一個(gè)聯(lián)通分支上，也就是說任何點(diǎn)之間都有路徑可以到達(dá)。
問題規(guī)模不大，直接用矩陣存數(shù)據(jù)，利用
prim 算法就可以搞定。此時(shí)任意兩點(diǎn)之間的“權(quán)值”就是
兩點(diǎn)之間的距離。
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
這個(gè)題目的意思就是說，給你一個(gè)有n個(gè)村莊的地圖，map[i][j]表示從村莊 i 到村莊 j 的距離，然后給你
m 條已有道路，讓你在這個(gè)基礎(chǔ)上添加適當(dāng)?shù)牡缆罚沟盟写迩f之間都是聯(lián)通的，求添加道路的最短距
離的值。
閱讀全文
2011年8月18日
摘要: 【問題描述】
一本書的頁數(shù)為N，頁碼從1開始編起，請你求出全部頁碼中，用了多少個(gè)0，1，2，…，9。其中—個(gè)頁碼不含多余的0，如N＝1234時(shí)第5頁不是0005，只是5。
【輸入】
一個(gè)正整數(shù)N(N≤109)，表示總的頁碼。
【輸出】
共十行：第k行為數(shù)字k-1的個(gè)數(shù)。
【樣例】
count.in count.out
11 1
4
1
1
閱讀全文
2011年8月17日
摘要: HDU 1217 Arbitrage
題意是說給你N種貨幣以及，貨幣與貨幣之間的M種匯率，
讓你判斷是否存在經(jīng)過若干次貨幣的兌換使得某種貨幣的
價(jià)值大于原來本身的價(jià)值，比如所：美元：美元 = 1 ： 1；
題意就是讓你判斷，在當(dāng)前的貨幣兌換率的基礎(chǔ)上，能不能
使 美元 ： 美元 > 1 : 1; 利用Floyd算法即可搞定，代碼如下：
閱讀全文
2011年8月16日
摘要: HDU 1029 Ignatius and the Princess IV
給N個(gè)數(shù)字， N為奇數(shù)， 輸出出現(xiàn)次數(shù)大于 N / 2 的數(shù)
閱讀全文
摘要: HDU 1280 前m大的數(shù)
給定的N個(gè)整數(shù)序列， 兩兩求和，從大到小輸出M個(gè)和數(shù)。
因?yàn)樗姓麛?shù)不超過5000，則相加不會(huì)超過10000，可以
用哈希解決。
閱讀全文
2011年7月18日
HDU 1116 Play on Words這個(gè)題目要運(yùn)用到歐拉路得相關(guān)知識(shí)，并且也要并查集，題目說的是：給你n個(gè)單詞，要你判斷這些單詞能不能首尾相連。
理解題目意思后，進(jìn)行轉(zhuǎn)化，輸入字符串，提取首位字母作為下標(biāo)來表示兩節(jié)點(diǎn)的出現(xiàn)，以及相對(duì)應(yīng)節(jié)點(diǎn)入度和出度的增加，
轉(zhuǎn)化為并查集的應(yīng)用即可。那么從可以想象一幅由首位字母節(jié)點(diǎn)構(gòu)成的圖，當(dāng)且僅當(dāng)圖是一條歐拉回路或者歐拉通路的時(shí)候，
才能滿足題目的要求，至于歐拉回路和歐拉通路的判定可以總結(jié)為如下：
1）所有的點(diǎn)聯(lián)通
2）歐拉回路中所有點(diǎn)的入度和出度一樣。
3）歐拉通路中起點(diǎn)的入度 - 出度 = 1，終點(diǎn)的 初度 - 入度 = 1， 其他的所有點(diǎn)入度 = 出度；
有了上面這些知識(shí)點(diǎn)做鋪墊，相信理解起來就比較容易了，下面我的代碼：
1 #include<stdio.h>
2 #include<string.h>
3 #include<math.h>
4 #define N 30
5 /*
6 歐拉回路，所有點(diǎn)連通，并且所有點(diǎn)的入度等于出度。
7 歐拉通路。從原點(diǎn) S出發(fā)，經(jīng)過所有點(diǎn)，從終點(diǎn) t出去。
8 所有點(diǎn)除起點(diǎn)終點(diǎn)外的度都是偶數(shù)，且出度等于入度
9 起點(diǎn)的出度比入度大 1
10 終點(diǎn)的入度比出度大 1
11 */
12
13 int father[N],vis[N];
14 //father[i] 表示節(jié)點(diǎn) i 的 BOSS ！ vis[i]表示節(jié)點(diǎn) i 出現(xiàn)過！
15 int findx(int x)
16 { //找節(jié)點(diǎn) 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 { // 合并 節(jié)點(diǎn) a 和節(jié)點(diǎn) 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; //初始化數(shù)組
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]++; // 記錄節(jié)點(diǎn) a 和 b的入度和出度
49 vis[a]=1;
50 vis[b]=1; //標(biāo)記節(jié)點(diǎn) a 和 b的出現(xiàn)
51 }
52 for(i=0;i<26;i++)
53 father[i]=findx(i); //找出每個(gè)節(jié)點(diǎn)的 BOSS
54 for(cnt=0,i=0;i<26;i++)
55 if(vis[i] && father[i]==i)
56 cnt++; // 統(tǒng)計(jì)最終 BOSS 即根節(jié)點(diǎn)的個(gè)數(shù) 。
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; //統(tǒng)計(jì)入度和出度不相等的點(diǎn)的信息
66 if(j==0)
67 {//歐拉回路，即環(huán)
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
這個(gè)題目的意思就是說給你n個(gè)相關(guān)點(diǎn)，用A - I 來表示，然后給出n-1行，第 i 行表示從點(diǎn) i 到其他點(diǎn)的相關(guān)信息。
在給出的map的基礎(chǔ)上，要求選擇適當(dāng)?shù)穆肪€，使得所有給出的點(diǎn)都能夠到達(dá)任意其他點(diǎn)，問題規(guī)模不大，直接矩陣
存儲(chǔ)，利用prim 算法搞定。
閱讀全文
摘要: HDU 1233 還是暢通工程
題目意思就是給你一個(gè)有n個(gè)點(diǎn)的圖，給出n *（n-1）/ 2 條邊的信息，包括邊的端點(diǎn)和邊的長度，要求
在滿足所有點(diǎn)在同一個(gè)連通分支上的前提下，選擇最短的道路來修建。典型的最小生成樹算法，同樣，問題
規(guī)模不大，直接矩陣就可以勝任。
閱讀全文
HDU 1232 暢通工程這個(gè)題目也是典型的最小生成樹算法的利用，不同于其他的題目就在于其它要求的是要添加的邊的最少數(shù)目，使得任意兩
點(diǎn)都有聯(lián)系，利用
并查集算法 ，在題目已經(jīng)給出的map基礎(chǔ)上，統(tǒng)計(jì)兩棵樹相并的次數(shù)，即使要添加的路徑的最少數(shù)目。
1 #include<stdio.h>
2 #include<stdlib.h>
3
4 int father[1001], tot;//father[i] 記錄 i 的 BOSS ！
5 //tot 統(tǒng)計(jì)最初至少需要添加的路徑數(shù)目 ！
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 統(tǒng)一！
16 int fa = find(a), fb = find(b);
17 if (fa != fb)
18 {
19 father[fa] = fb;
20 tot --; // 統(tǒng)一了一次兩個(gè)陣營的 BOSS ，所以需要添加的路徑的數(shù)目減一！
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 個(gè)點(diǎn)聯(lián)通所需要的最少邊的數(shù)目 ！
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); //輸出在已有基礎(chǔ)上還需要的邊的數(shù)目！
40 }
41 return 0;
42 }
43
HDU 1162 Eddy's picture這個(gè)題目也是典型的最小生成樹算法，跟
之前的那個(gè)題目是差不多的，也就是說：給你n個(gè)二維平面點(diǎn)，
讓你添加適當(dāng)?shù)倪叄沟盟械狞c(diǎn)都在同一個(gè)聯(lián)通分支上，也就是說任何點(diǎn)之間都有路徑可以到達(dá)。
問題規(guī)模不大，直接用矩陣存數(shù)據(jù)，利用
prim 算法就可以搞定。此時(shí)任意兩點(diǎn)之間的“權(quán)值”就是
兩點(diǎn)之間的距離。
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
這個(gè)題目的意思就是說，給你一個(gè)有n個(gè)村莊的地圖，map[i][j]表示從村莊 i 到村莊 j 的距離，然后給你
m 條已有道路，讓你在這個(gè)基礎(chǔ)上添加適當(dāng)?shù)牡缆罚沟盟写迩f之間都是聯(lián)通的，求添加道路的最短距
離的值。
閱讀全文