置顶随笔
摘要: 【问题描述】
一本书的页数为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 条已有道路，让你在这个基础上添加适当的道路，使得所有村庄之间都是联通的，求添加道路的最短距
离的值。
阅读全文