置顶随笔

[置顶]页码计数

     摘要: 【问题描述】

一本书的页数为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

  阅读全文

posted @ 2011-08-18 19:26 AK 阅读(2220) | 评论 (2)编辑 收藏

[置顶]HDU 1217 Arbitrage

     摘要: HDU 1217 Arbitrage
题意是说给你N种货币以及,货币与货币之间的M种汇率,
让你判断是否存在经过若干次货币的兑换使得某种货币的
价值大于原来本身的价值,比如所:美元:美元 = 1 : 1;
题意就是让你判断,在当前的货币兑换率的基础上,能不能
使 美元 : 美元 > 1 : 1; 利用Floyd算法即可搞定,代码如下:  阅读全文

posted @ 2011-08-17 09:55 AK 阅读(1335) | 评论 (0)编辑 收藏

[置顶]HDU 1280 前m大的数

     摘要: HDU 1280 前m大的数
给定的N个整数序列, 两两求和,从大到小输出M个和数。
因为所有整数不超过5000,则相加不会超过10000,可以
用哈希解决。  阅读全文

posted @ 2011-08-16 16:40 AK 阅读(1526) | 评论 (0)编辑 收藏

[置顶]HDU 1116 Play on Words

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 




posted @ 2011-07-18 10:57 AK 阅读(1767) | 评论 (3)编辑 收藏

[置顶]HDU 1301 Jungle Roads

     摘要: HDU 1301 Jungle Roads
这个题目的意思就是说给你n个相关点,用A - I 来表示,然后给出n-1行,第 i 行表示从点 i 到其他点的相关信息。
在给出的map的基础上,要求选择适当的路线,使得所有给出的点都能够到达任意其他点,问题规模不大,直接矩阵
存储,利用prim 算法搞定。  阅读全文

posted @ 2011-07-18 09:31 AK 阅读(1467) | 评论 (0)编辑 收藏

[置顶]HDU 1233 还是畅通工程

     摘要: HDU 1233 还是畅通工程
题目意思就是给你一个有n个点的图,给出n *(n-1)/ 2 条边的信息,包括边的端点和边的长度,要求
在满足所有点在同一个连通分支上的前提下,选择最短的道路来修建。典型的最小生成树算法,同样,问题
规模不大,直接矩阵就可以胜任。  阅读全文

posted @ 2011-07-18 09:20 AK 阅读(2196) | 评论 (0)编辑 收藏

[置顶]HDU 1232 畅通工程

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 

posted @ 2011-07-18 08:59 AK 阅读(1576) | 评论 (0)编辑 收藏

[置顶]HDU 1162 Eddy's picture

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, 0sizeof(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, 0sizeof(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 


posted @ 2011-07-18 08:42 AK 阅读(1210) | 评论 (0)编辑 收藏

[置顶]HDU 1102 Constructing Roads

     摘要: HDU 1102 Constructing Roads

这个题目的意思就是说,给你一个有n个村庄的地图,map[i][j]表示从村庄 i 到村庄 j 的距离,然后给你
m 条已有道路,让你在这个基础上添加适当的道路,使得所有村庄之间都是联通的,求添加道路的最短距
离的值。   阅读全文

posted @ 2011-07-18 08:34 AK 阅读(1461) | 评论 (0)编辑 收藏

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

  阅读全文

posted @ 2011-08-18 19:26 AK 阅读(2220) | 评论 (2)编辑 收藏

2011年8月17日

HDU 1217 Arbitrage

     摘要: HDU 1217 Arbitrage
题意是说给你N种货币以及,货币与货币之间的M种汇率,
让你判断是否存在经过若干次货币的兑换使得某种货币的
价值大于原来本身的价值,比如所:美元:美元 = 1 : 1;
题意就是让你判断,在当前的货币兑换率的基础上,能不能
使 美元 : 美元 > 1 : 1; 利用Floyd算法即可搞定,代码如下:  阅读全文

posted @ 2011-08-17 09:55 AK 阅读(1335) | 评论 (0)编辑 收藏

2011年8月16日

HDU 1029 Ignatius and the Princess IV

     摘要: HDU 1029 Ignatius and the Princess IV
给N个数字, N为奇数, 输出出现次数大于 N / 2 的数  阅读全文

posted @ 2011-08-16 17:10 AK 阅读(1293) | 评论 (0)编辑 收藏

HDU 1280 前m大的数

     摘要: HDU 1280 前m大的数
给定的N个整数序列, 两两求和,从大到小输出M个和数。
因为所有整数不超过5000,则相加不会超过10000,可以
用哈希解决。  阅读全文

posted @ 2011-08-16 16:40 AK 阅读(1526) | 评论 (0)编辑 收藏

2011年7月18日

HDU 1116 Play on Words

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 




posted @ 2011-07-18 10:57 AK 阅读(1767) | 评论 (3)编辑 收藏

HDU 1301 Jungle Roads

     摘要: HDU 1301 Jungle Roads
这个题目的意思就是说给你n个相关点,用A - I 来表示,然后给出n-1行,第 i 行表示从点 i 到其他点的相关信息。
在给出的map的基础上,要求选择适当的路线,使得所有给出的点都能够到达任意其他点,问题规模不大,直接矩阵
存储,利用prim 算法搞定。  阅读全文

posted @ 2011-07-18 09:31 AK 阅读(1467) | 评论 (0)编辑 收藏

HDU 1233 还是畅通工程

     摘要: HDU 1233 还是畅通工程
题目意思就是给你一个有n个点的图,给出n *(n-1)/ 2 条边的信息,包括边的端点和边的长度,要求
在满足所有点在同一个连通分支上的前提下,选择最短的道路来修建。典型的最小生成树算法,同样,问题
规模不大,直接矩阵就可以胜任。  阅读全文

posted @ 2011-07-18 09:20 AK 阅读(2196) | 评论 (0)编辑 收藏

HDU 1232 畅通工程

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 

posted @ 2011-07-18 08:59 AK 阅读(1576) | 评论 (0)编辑 收藏

HDU 1162 Eddy's picture

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, 0sizeof(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, 0sizeof(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 


posted @ 2011-07-18 08:42 AK 阅读(1210) | 评论 (0)编辑 收藏

HDU 1102 Constructing Roads

     摘要: HDU 1102 Constructing Roads

这个题目的意思就是说,给你一个有n个村庄的地图,map[i][j]表示从村庄 i 到村庄 j 的距离,然后给你
m 条已有道路,让你在这个基础上添加适当的道路,使得所有村庄之间都是联通的,求添加道路的最短距
离的值。   阅读全文

posted @ 2011-07-18 08:34 AK 阅读(1461) | 评论 (0)编辑 收藏

仅列出标题  
<2019年12月>
24252627282930
1234567
891011121314
15161718192021
22232425262728
2930311234

导航

统计

常用链接

留言簿(1)

随笔分类

随笔档案

资源连接

搜索

最新评论

阅读排行榜

评论排行榜