2014H-Star初赛题解

 

2014H-Star初赛题解

分类： ACM HHUC2014-04-19 11:17 110人阅读 评论(0) 收藏 举报

A.不要被阶乘吓倒

题型：数学

题意：

给你数字N(0<=N<=10000),让你求出N！末尾的零的个数

 

思路：

此题为编程之美书上的题目

 

一些初学者可能不知道什么是多组输入，即输入直到测试数据文件的末尾

while(cin >> n) || while(scanf("%d", &n) != EOF)均可实现以上功能

 

然后我们来数阶乘末尾的0，有参赛选手选用直接模拟用来统计最后零的个数，但大家可以大致测试一下，10000！是多少位数的(我用Python测试为35660位)。一般来说，1S的时限允许进行百万级别(即小于一千万)的循环

 

末尾1个0则必然出现了1个10。10只有两个因子构成(2*5)。所以我们只需要统计N！中出现a个2，出现b个5，取min(a,b)即可。然而我们可以很清楚地发现到2出现的频率是远大于5出现的频率的。从数学期望上来说，任意一个数有1/2的概率含有因子2，而只有1/5的概率含有因子5。因此我们只需要统计N！中5出现的个数。所有5的倍数出现1次，25的倍数在5的基础上再出现一次(25 = 5 * 5)

 

代码：/*代码来自Assassin*/

[cpp] view plaincopy

  1. #include <iostream>  
  2.   
  3. using namespace std;  
  4.   
  5. int main()  
  6. {  
  7.     int n;  
  8.     while(cin >> n){  
  9.         cout << (n/5 + n/25 + n/125 + n/625 + n/3125) << endl;  
  10. 10.     }  
  11. 11.     return 0;  

12. }  

 

B.Cow Pedigrees

题型：动态规划

题意：

农民约翰准备购买一群新奶牛。 在这个新的奶牛群中, 每一个母亲奶牛都生两个小奶牛。这些奶牛间的关系可以用二叉树来表示。这些二叉树总共有N个节点(3 <= N < 200)。这些二叉树有如下性质:

每一个节点的度是0或2。度是这个节点的孩子的数目。

树的高度等于K(1 < K < 100)。高度是从根到最远的那个叶子所需要经过的结点数; 叶子是指没有孩子的节点。

有多少不同的家谱结构? 如果一个家谱的树结构不同于另一个的, 那么这两个家谱就是不同的。输出可能的家谱树的个数除以9901的余数。

思路：

这是一个DP问题。我们所关心的树的性质是深度和节点数，所以我们可以做这样一张表：table[i][j]表示深度为i、节点数为j的树的个数。根据给定的约束条件，j必须为奇数。你如何构造一棵树呢？当然是由更小的树来构造了。一棵深度为i、节点数为j的树可以由两个子树以及一个根结点构造而成。当i、j已经选定时，我们选择左子树的节点数k。这样我们也就知道了右子树的节点数，即j-k-1。至于深度，至少要有一棵子树的深度为i-1才能使构造出的新树深度为i。有三种可能的情况：左子树深度为i-1 ，右子树深度小于i-1；右子树深度为i-1，左子树深度小于i-1；左右子树深度都为i-1。事实上，当我们在构造一棵深度为i的树时，我们只关心使用的子树深度是否为i-1或更小。因此，我们使用另一个数组smalltrees[i-2][j]记录所有深度小于i-1的树，而不仅仅是深度为i-2的树。知道了上面的这些，我们就可以用以下三种可能的方法来建树了：

table[i][j] := smalltrees[i-2][k]*table[i-1][j-1-k];

                  // 左子树深度小于i-1，右子树深度为i-1

table[i][j] := table[i-1][k]*smalltrees[i-2][j-1-k];

                  // 左子树深度为i-1，右子树深度小于i-1

table[i][j] := table[i-1][k]*table[i-1][j-1-k];

                  // 左右子树深度都为i-1

代码：/*代码来自NOCOW*/

[cpp] view plaincopy

  1. #include <cstdio>  
  2. #include <cstdlib>  
  3. #define MOD 9901  
  4. using namespace std;  
  5.   
  6. int table[101][202],N,K,c;  
  7. int smalltrees[101][202];  
  8.   
  9. int main() {  
  10. 10.     scanf("%d %d",&N,&K);  
  11. 11.     table[1][1]=1;  
  12. 12.     for (int i=2;i<=K;i++) {  
  13. 13.         for (int j=1;j<=N;j+=2)  
  14. 14.             for (int k=1;k<=j-1-k;k+=2) {  
  15. 15.                 if (k!=j-1-k) c=2; else c=1;  //判断树的结构是否对称  
  16. 16.                 table[i][j]+=c*(  
  17. 17.                         smalltrees[i-2][k]*table[i-1][j-1-k]  // 左子树深度小于i-1  
  18. 18.                         +table[i-1][k]*smalltrees[i-2][j-1-k]  // 右子树深度小于i-1  
  19. 19.                         +table[i-1][k]*table[i-1][j-1-k]);// 都为i-1  
  20. 20.                 table[i][j]%=MOD;  
  21. 21.             }  
  22. 22.         for (int k=0;k<=N;k++) {  
  23. 23.         // 确保接下来第i次迭代中的smalltrees[i-2][j]包含了深度小于i-1且节点数为j的树的个数  
  24. 24.             smalltrees[i-1][k]+=table[i-1][k]+smalltrees[i-2][k];  
  25. 25.             smalltrees[i-1][k]%=MOD;  
  26. 26.         }  
  27. 27.     }  
  28. 28.   
  29. 29.     printf ("%d ",table[K][N]);  
  30. 30.     return 0;  

31. }  

 

 

C.回文素数

题型：构造

题意：

找出范围[a,b](5 <= a < b <= 100,000,000)( 一亿)间的所有回文质数(回文又是素数);

思路：

这道题有两种思路：

  1. 用筛法求出1..1e8范围内的素数，然后判断每个素数是否是回文数。
  2. 生成1..1e8范围内的回文数，然后判断它是否是素数。

思路1的复杂度是O(n)，思路2的复杂度是O(√n*√n)=O(n)，从复杂度来看两种思路没有差别。但思路1用筛法用素数要开O(n)的数组，在n=1e8是就是90M，超出了空间限制，（而且有可能超时）,而思路2的空间复杂度是O(1)的，所以我们用思路2。

[cpp] view plaincopy

  1. //产生长度为5的回文数  
  2.  for (d1 = 1; d1 <= 9; d1+=2) {  // 只有奇数才会是素数  
  3.      for (d2 = 0; d2 <= 9; d2++) {  
  4.          for (d3 = 0; d3 <= 9; d3++) {  
  5.            palindrome = 10000*d1 + 1000*d2 +100*d3 + 10*d2 + d1;//(处理回文数...)  
  6.          }  
  7.      }  
  8.  }  

代码：/*代码来自NOCOW*/

[cpp] view plaincopy

  1. #include<cstdio>  
  2. #include<cstdlib>  
  3. #include<cstring>  
  4. #include<cmath>  
  5.   
  6. int A,B;  
  7. int answer[100000];  
  8. int numAnswer=0;  
  9.   

10. bool prime(int a)  

11. {  

  1. 12.      for(int i=2;i<=sqrt(a);i++)  
  2. 13.        if (a%i==0) return false;  
  3. 14.      return true;  

15. }  

  1. 16.   

17. int generate(int i,int j)  

18. {  

  1. 19.     if (j==1)  
  2. 20.     {  
  3. 21.         char a[30];  
  4. 22.         sprintf(a,"%d",i);  
  5. 23.         int len=strlen(a);  
  6. 24.         for(int k=0;k<len;k++)  
  7. 25.            a[k+len]=a[len-k-1];  
  8. 26.         a[len*2]='';  
  9. 27.         char* b;  
  10. 28.         return strtol(a,&b,10);  
  11. 29.     }  
  12. 30.     if (j==0)  
  13. 31.     {  
  14. 32.         char a[30];  
  15. 33.         sprintf(a,"%d",i);  
  16. 34.         int len=strlen(a);  
  17. 35.         for(int k=0;k<len;k++)  
  18. 36.            a[k+len-1]=a[len-k-1];  
  19. 37.         a[len*2-1]='';  
  20. 38.         char* b;  
  21. 39.         return strtol(a,&b,10);  
  22. 40.     }  

41. }  

  1. 42.   

43. int compareint(const void* a,const void* b)  

44. {  

  1. 45.     return *((int *)a)-*((int *)b);  

46. }  

  1. 47.   

48. int main()  

49. {  

  1. 50.   
  2. 51.     scanf("%d%d",&A,&B);  
  3. 52.   
  4. 53.     int x;  
  5. 54.     for(int i=1;i<=9999;i++)  
  6. 55.     for(int j=0;j<2;j++)//0:odd 1:even  
  7. 56.       if (prime(x=generate(i,j))&&x>=A&&x<=B)  
  8. 57.          answer[numAnswer++]=x;  
  9. 58.   
  10. 59.     qsort(answer,numAnswer,sizeof(int),compareint);  
  11. 60.   
  12. 61.     for(int i=0;i<numAnswer;i++)  
  13. 62.       printf("%d ",answer[i]);  
  14. 63.   
  15. 64.     return 0;  

65. }  

 

 

D.就这个计算

题型：大数计算

题意：

大数(+/-)运算

思路：

以手算的方式模拟即可

因为进位的关系，需要将数字倒置过来，进行运算。

代码：/*代码来自42号参赛队伍*/

[cpp] view plaincopy

  1. #include <stdio.h>  
  2. #include <stdlib.h>  
  3. #include <string.h>  
  4. #define M 1005  
  5. int main()  
  6. {  
  7.     char a[M],b[M];  
  8.     int c[M],d[M],e[M],f[M];  
  9.     int i,j,num;  
  10. 10.     while(scanf("%s",a)!=EOF&&scanf("%s",b)!=EOF)  
  11. 11.     {  
  12. 12.         j=0;  
  13. 13.         num=0;  
  14. 14.         memset(c,0,sizeof(c));  
  15. 15.         memset(e,0,sizeof(e));  
  16. 16.         memset(d,0,sizeof(d));  
  17. 17.         for(i=strlen(a)-1;i>=0;i--)  
  18. 18.         {  
  19. 19.             c[j++]=a[i]-'0';  
  20. 20.         }  
  21. 21.         j=0;  
  22. 22.         for(i=strlen(b)-1;i>=0;i--)  
  23. 23.         {  
  24. 24.             d[j++]=b[i]-'0';  
  25. 25.         }  
  26. 26.         for(i=0;i<strlen(a);i++)  
  27. 27.         {  
  28. 28.             e[i]+=c[i]+d[i];  
  29. 29.             if(e[i]>=10)  
  30. 30.             {  
  31. 31.                 e[i]-=10;  
  32. 32.                 e[i+1]+=1;  
  33. 33.             }  
  34. 34.             else  
  35. 35.             {  
  36. 36.                 continue;  
  37. 37.             }  
  38. 38.         }  
  39. 39.         num=strlen(a)-1;  
  40. 40.         if(e[strlen(a)]>0)  
  41. 41.             num=num+1;  
  42. 42.         i=num;  
  43. 43.         while(e[i]==0) i--;  
  44. 44.         if(i<0) printf("0");  
  45. 45.         else  
  46. 46.         {  
  47. 47.         for(;i>=0;i--)  
  48. 48.         {  
  49. 49.             printf("%d",e[i]);  
  50. 50.         }  
  51. 51.         }  
  52. 52.         printf(" ");  
  53. 53.         memset(e,0,sizeof(e));  
  54. 54.         for(i=0;i<strlen(a);i++)  
  55. 55.         {  
  56. 56.             e[i]+=c[i]-d[i];  
  57. 57.             if(e[i]<0)  
  58. 58.             {  
  59. 59.                 e[i]+=10;  
  60. 60.                 e[i+1]--;  
  61. 61.             }  
  62. 62.         }  
  63. 63.         num=strlen(a);  
  64. 64.         i=num-1;  
  65. 65.         while(e[i]==0) i--;  
  66. 66.         if(i<0) printf("0");  
  67. 67.         for(;i>=0;i--)  
  68. 68.             printf("%d",e[i]);  
  69. 69.         printf(" ");  

70. }  

71. return 0;  

72. }  

E.矩形覆盖

题型：模拟

题意：

一个8*8的矩阵，该矩阵每个位置上的值都为非负数，且小于等于255。在处理这个矩阵时，需要提取一个特征矩阵，用这个矩阵覆盖原8*8矩阵中所有的非零的点.

 

思路：

有多种方法

1.获得所有非零点，然后进行多次排序(分别获得x,y的最大值和最小值)

2.无须知道具体的点，只需要对应的边界。即我们只需要知道特征矩阵的第一行和最后一行，第一列与最后一列。

代码：/*代码来自Assassin*/

[cpp] view plaincopy

  1. /*排序版本*/  
  2. #include <iostream>  
  3. #include <cstdio>  
  4. #include <algorithm>  
  5. #include <vector>  
  6. using namespace std;  
  7. typedef struct{  
  8.     int x;  
  9.     int y;  

10. }POINT;  

11. vector<POINT> v;  

12. int sortX(const POINT &a, const POINT &b){  

  1. 13.     return a.x < b.x;  

14. }  

15. int sortY(const POINT &a, const POINT &b){  

  1. 16.     return a.y < b.y;  

17. }  

18. int main()  

19. {  

  1. 20.     POINT p;  
  2. 21.     int data;  
  3. 22.     for(int i = 1; i <= 8; ++i){  
  4. 23.         for(int j = 1; j <= 8; ++j){  
  5. 24.             cin >> data;  
  6. 25.             if(data){  
  7. 26.                 p.x = i;  
  8. 27.                 p.y = j;  
  9. 28.                 v.push_back(p);  
  10. 29.             }  
  11. 30.         }  
  12. 31.     }  
  13. 32.     int x1, x2, y1, y2;  
  14. 33.     sort(v.begin(), v.end(), sortX);  
  15. 34.     x1 = v[0].x, x2 = v[v.size()-1].x;  
  16. 35.     sort(v.begin(), v.end(), sortY);  
  17. 36.     y1 = v[0].y, y2 = v[v.size()-1].y;  
  18. 37.     printf("%d %d %d %d ", x1, y1, x2, y2);  
  19. 38.     return 0;  

39. }  

[cpp] view plaincopy

  1. /*模拟版本*/  
  2. #include <iostream>  
  3. #include <cstdio>  
  4. #include <algorithm>  
  5. #include <cstring>  
  6. using namespace std;  
  7. int main()  
  8. {  
  9.     int data[9][9];  
  10. 10.     int row[9];  
  11. 11.     int col[9];  
  12. 12.     int x1, y1, x2, y2;  
  13. 13.     memset(data, 0, sizeof(data));  
  14. 14.     memset(row, 0, sizeof(row));  
  15. 15.     memset(col, 0, sizeof(col));  
  16. 16.     for(int i = 1; i <= 8; ++i){  
  17. 17.         for(int j = 1; j <= 8; ++j){  
  18. 18.             cin >> data[i][j];  
  19. 19.             row[i] += data[i][j];  
  20. 20.             col[j] += data[i][j];  
  21. 21.         }  
  22. 22.     }  
  23. 23.     for(int i = 1; i <= 8; ++i){  
  24. 24.         if(row[i] != 0){  
  25. 25.             x1 = i;  
  26. 26.             break;  
  27. 27.         }  
  28. 28.     }  
  29. 29.     for(int i = 8; i >= 1; --i){  
  30. 30.         if(row[i] != 0){  
  31. 31.             x2 = i;  
  32. 32.             break;  
  33. 33.         }  
  34. 34.     }  
  35. 35.     for(int i = 1; i <= 8; ++i){  
  36. 36.         if(col[i] != 0){  
  37. 37.             y1 = i;  
  38. 38.             break;  
  39. 39.         }  
  40. 40.     }  
  41. 41.     for(int i = 8; i >= 1; --i){  
  42. 42.         if(col[i] != 0){  
  43. 43.             y2 = i;  
  44. 44.             break;  
  45. 45.         }  
  46. 46.     }  
  47. 47.     printf("%d %d %d %d ", x1, y1, x2, y2);  
  48. 48.     return 0;  

49. }  

 

F. 铁轨问题

题型：数据结构

题意：

每辆火车都从A方向驶入车站，再从B方向驶出车站，同时它的车厢可以进行某种形式的重新组合。假设从A方向驶来的火车有n节车厢(n<1000)，分别按顺序编号为1，2，...,n。假定在进入车站之前每节车厢之间都是不连着的，并且它们可以自行移动，直到处在B方向的铁轨上。另外假定车站C里可以停放任意多节的车厢。但是一旦当一节车厢进入车站C，它就不能再回到A方向的铁轨上了，并且一旦当它进入B方向的铁轨后，它就不能再回到车站C。负责车厢调度的工作人员需要知道能否使它以a1，a2，...，an的顺序从B方向驶出。
        请写一个程序，用来判断能否得到指定的车厢顺序。

 

思路：

用栈来模拟即可，用数组来实现栈。

 

代码：/*代码来自42号参赛队伍*/

[cpp] view plaincopy

  1. #include<stdio.h>  
  2.    
  3. #define MAXN 1010  
  4. int n,target[MAXN],m;  
  5.    
  6. int main()  
  7. {  
  8.    
  9.     while(scanf("%d%d",&m,&n)!=EOF)  
  10. 10.     {  
  11. 11.         int A=1,B=1;  
  12. 12.         int stack[MAXN],top=0;  
  13. 13.         for(int i=m;i<=n;i++)  
  14. 14.         {  
  15. 15.         scanf("%d",&target[i]);  
  16. 16.         }  
  17. 17.         int ok=1;  
  18. 18.         while(B<=n)  
  19. 19.         {  
  20. 20.             if(A==target[B]) {A++; B++;}  
  21. 21.             else if(top&&stack[top]==target[B]) {top--;B++;}  
  22. 22.             else if(A<=n) stack[++top]=A++;  
  23. 23.             else {ok=0; break;}  
  24. 24.         }  
  25. 25.         printf("%s ",ok ? "YES": "NO");  
  26. 26.     }  
  27. 27.     return 0;  

28. }  

 

G. 团队博弈

题型：博弈问题

题意：

ACM团队的招新面试到了最后一轮，有两个能力相当的人（Alice & Bob），可是只有ACM团队只剩最后一个名额了。因此无奈下只能考验Alice & Bob的聪颖程度。现假设Alice & Bob都随身携带着无数个硬币，他们轮流向一个空箱子内投入硬币，投入的硬币数量一个是个正整数，并且每人每次投入不超过m个(1<=m<=10)。最先使空盒子内硬币的数量大于或者等于n(0<n<10000)的一方胜出。Alice & Bob都非常渴望加入ACM团队，而且都是非常聪明的人。假设Alice先手。

 

思路：

当n == K(m+1)  K为正整数

每次Alice拿a个，Bob都可以拿(m+1-a)个，使剩余目标量为(K-1)(m+1)...直到最后Bob获胜

当N != K(m+1) K为正整数

Alice可以拿a个，使得 N == K(m+1)， 使Bob进入上述困境

 

代码：/*代码来自37号参赛队伍*/

[cpp] view plaincopy

  1. #include<stdio.h>  
  2. int main()  
  3. {  
  4.     int n,m,s,i=1;  
  5.     scanf("%d",&s);  
  6.     while(i<=s){  
  7.         scanf("%d%d",&n,&m);  
  8.             if(n%(m+1)==0)  
  9.                 printf("Bob ");  
  10. 10.             else  
  11. 11.                 printf("Alice ");  
  12. 12.             i++;  
  13. 13.     }  
  14. 14.     return 0;  

15. }  

 

 

H. 五柳先生传

题型：搜索，BFS

题意：

 五柳先生"性嗜酒,家贫,不能常得,亲旧知其如此,或置酒而招之。"可是经考古发现，五柳先生是个处女座，有极度强迫症。他每次只喝一杯酒，且这杯酒里有且仅有一定体积的酒，他才会喜欢喝。
        五柳先生家有两个无刻度标志的酒壶，分别可装 x 升和 y 升 （ x,y 为整数且均不大于 100 ）的酒。设另有一酒缸，可用来向酒壶灌酒或接从酒壶中倒出的酒， 两酒壶间，酒也可以相互倾倒。已知 x 升壶为空壶， y 升壶为空壶。问如何通过倒酒或灌酒操作， 用最少步数能在x或y升的壶中量出 z （ z ≤ 100 ）升的酒来。

 

思路：

http://blog.csdn.net/neeeeew/article/details/19207181

在本博客中的“简易搜索”博文内有详细提及，此题略去了输出步骤

代码：/*代码来自Assassin*/

[cpp] view plaincopy

  1. #include<iostream>  
  2. #include<cstring>  
  3. #define min(a, b) (a)>(b)?(b):(a)  
  4. using namespace std;  
  5. const int Max = 101;  
  6. struct node{  
  7.     int ope;  int a;  int b;  node* pre;  
  8. } que[Max * Max];  
  9. bool vis[Max][Max];  

10. char str[6][10] = {"FILL(1)", "FILL(2)", "DROP(1)", "DROP(2)", "POUR(1,2)", "POUR(2,1)"};  

11. void print(node now){  

  1. 12.     if (now.pre != NULL){  
  2. 13.         print(*now.pre);                /*这种输出路径的方法很值得学习*/  
  3. 14.         cout << str[now.ope] << endl;  
  4. 15.     }  

16. }  

17. void bfs(int a, int b, int c){  

  1. 18.     int steps = 0;  
  2. 19.     int head = 0, tail = 1;  
  3. 20.     que[0].a = que[0].b = 0;  
  4. 21.     que[0].pre = NULL;  
  5. 22.     while (tail - head > 0)     {  
  6. 23.         int count = tail - head;        /*head表示队列中的首元素*/  
  7. 24.                                         /*tail表示队列中的尾元素*/  
  8. 25.         while (count --){  
  9. 26.             node now = que[head];  
  10. 27.             if (now.a == c || now.b == c){  
  11. 28.                 cout << steps << endl;  
  12. 29.                 //print(now);  
  13. 30.                 return;  
  14. 31.             }  
  15. 32.             if (!vis[a][now.b]){        /*fill(1)*/  
  16. 33.                 que[tail].ope = 0;  
  17. 34.                 que[tail].a = a;  
  18. 35.                 que[tail].b = now.b;  
  19. 36.                 que[tail].pre = &que[head];  
  20. 37.                 vis[a][now.b] = true;  
  21. 38.                 tail++;  
  22. 39.             }  
  23. 40.             if (!vis[now.a][b]){        /*fill(2)*/  
  24. 41.                 que[tail].ope = 1;  
  25. 42.                 que[tail].a = now.a;  
  26. 43.                 que[tail].b = b;  
  27. 44.                 que[tail].pre = &que[head];  
  28. 45.                 vis[now.a][b] = true;  
  29. 46.                 tail++;  
  30. 47.             }  
  31. 48.             if (!vis[0][now.b]){     /*drop(1)*/  
  32. 49.                 que[tail].ope = 2;  
  33. 50.                 que[tail].a = 0;  
  34. 51.                 que[tail].b = now.b;  
  35. 52.                 que[tail].pre = &que[head];  
  36. 53.                 vis[0][now.b] = true;  
  37. 54.                 tail ++;  
  38. 55.             }  
  39. 56.             if (!vis[now.a][0]){        /*drop(2)*/  
  40. 57.                 que[tail].ope = 3;  
  41. 58.                 que[tail].a = now.a;  
  42. 59.                 que[tail].b = 0;  
  43. 60.                 que[tail].pre = &que[head];  
  44. 61.                 vis[now.a][0] = true;  
  45. 62.                 tail ++;  
  46. 63.             }  
  47. 64.             int wat1 = min(now.a, b - now.b);  
  48. 65.             if (!vis[now.a - wat1][now.b + wat1]){  /*pour(1,2)*/  
  49. 66.                 que[tail].ope = 4;  
  50. 67.                 que[tail].a = now.a - wat1;  
  51. 68.                 que[tail].b = now.b + wat1;  
  52. 69.                 que[tail].pre = &que[head];  
  53. 70.                 vis[now.a - wat1][now.b + wat1] = true;  
  54. 71.                 tail ++;  
  55. 72.             }  
  56. 73.             int wat2 = min(a - now.a, now.b);  
  57. 74.             if (!vis[now.a + wat2][now.b - wat2]){      /*pour(2,1)*/  
  58. 75.                 que[tail].ope = 5;  
  59. 76.                 que[tail].a = now.a + wat2;  
  60. 77.                 que[tail].b = now.b - wat2;  
  61. 78.                 que[tail].pre = &que[head];  
  62. 79.                 vis[now.a + wat2][now.b - wat2] = true;  
  63. 80.                 tail ++;  
  64. 81.             }  
  65. 82.             head ++;  
  66. 83.         }  
  67. 84.         steps ++;  
  68. 85.     }  
  69. 86.     cout << "impossible" << endl;  

87. }  

  1. 88.   

89. int main()  

90. {  

  1. 91.     int a, b, c;  
  2. 92.     cin >> a >> b >> c;  
  3. 93.     memset(vis, false, sizeof(vis));  
  4. 94.     vis[0][0] = true;  
  5. 95.     bfs(a, b, c);  
  6. 96.     return 0;  

97. }  

 

I. 进击的海怪

题型：搜索，DFS， FLOOD FILL

题意：

WA海怪是一种独居的海怪,具有很强的进攻性，因此在一块连通域(上下、左右连通)内有且仅有一只WA海怪。现在我们想知道这片AC海洋中有多少只WA海怪。

 

思路：

http://blog.csdn.net/neeeeew/article/details/19207181

在本博客中的“简易搜索”博文内有详细提及

代码：/*代码来自56号参赛队伍*/

[cpp] view plaincopy

  1. #include <iostream>  
  2. #include <cstdio>  
  3. #include <cstdlib>  
  4. #include <cstring>  
  5. using namespace std;  
  6. #define MIN(x,y) (x<y?x:y)  
  7. #define MAX(x,y) (x>y?x:y)  
  8.   
  9. char map[1010][1010];  

10. bool visit[1010][1010];  

11. int ans = 0;  

12. int tx[] = {0,1,0,-1};  

13. int ty[] = {1,0,-1,0};  

14. int m,n;  

  1. 15.   

16. void dfs(int x, int y){  

  1. 17.     if(x<0||x>=m||y<0||y>=n)  
  2. 18.         return;  
  3. 19.     visit[x][y] = true;  
  4. 20.     map[x][y] = '.';  
  5. 21.     for(int i=0; i<4; ++i){  
  6. 22.         int tmpx = x+tx[i];  
  7. 23.         int tmpy = y+ty[i];  
  8. 24.         if(!visit[tmpx][tmpy]&&map[tmpx][tmpy]=='#')  
  9. 25.             dfs(tmpx, tmpy);  
  10. 26.     }  

27. }  

  1. 28.   

29. int main(){  

  1. 30.     scanf("%d%d",&m,&n);  
  2. 31.     int i,j;  
  3. 32.     for(i=0; i<m; ++i){  
  4. 33.         scanf("%s", map[i]);  
  5. 34.     }  
  6. 35.     memset(visit, false, sizeof(visit));  
  7. 36.     for(i=0; i<m; ++i){  
  8. 37.         for(j=0; j<n; ++j){  
  9. 38.             if(map[i][j] != '.'){  
  10. 39.                 ++ans;  
  11. 40.                 dfs(i,j);  
  12. 41.             }  
  13. 42.         }  
  14. 43.     }  
  15. 44.     printf("%d ", ans);  
  16. 45.     return 0;  

46. }  

 

J. 最大合成数

题型：贪心

题意：

  ACM团队里有这么一群人，茶余饭后，总能想出一些奇怪的游戏。刚刚考完数据结构的石头突然想到一个游戏：他随机给出n个整数，让Hacker将这组整数串成一个多位数。请问，最大的多位数是多少？ 。

 

思路：

首先很常见的就是对字符串进行排序。然后就来了一个很大的漏洞 20 2。如果按照排序合成的202，可是我们可以很明显的看出来220更大。因此，当两个数字其中为其一个数字的前缀时，我们可以对这两个数进行拼接，查看那种拼接方式能获得更大解。

代码：/*代码来自Assassin*/

[cpp] view plaincopy

  1. #include <iostream>  
  2. #include <cstring>  
  3. #include <cstdio>  
  4. #include <algorithm>  
  5. using namespace std;  
  6. typedef struct{  
  7.     char str[1000];  
  8. }NUM;  
  9. NUM number[25];  

10. int cmp(const NUM &a, const NUM &b){  

11. //    return strcmp(a.str, b.str) < 0;  

12. //    printf("%s %s %d ", a.str, b.str, strcmp(a.str, b.str));  

  1. 13.     char stra[1000], strb[1000];  
  2. 14.     strcpy(stra, a.str);  
  3. 15.     strcpy(strb, b.str);  
  4. 16.     bool flag = true;  
  5. 17.     for(int i = 0; i < strlen(a.str) && i < strlen(b.str); ++i){  
  6. 18.         if(a.str[i] != b.str[i]){  
  7. 19.             flag = false;  
  8. 20.             break;  
  9. 21.         }  
  10. 22.     }  
  11. 23.     if(!flag){  
  12. 24.         return strcmp(a.str, b.str) < 0;  
  13. 25.     }  
  14. 26.     else{  
  15. 27.         return strcmp(strcat(stra, strb), strcat(strb, stra)) < 0;  
  16. 28.     }  

29. }  

30. int main(){  

  1. 31.     int cas;  
  2. 32.     cin >> cas;  
  3. 33.     for(int i = 0; i < cas; ++i){  
  4. 34.         scanf("%s", number[i].str);  
  5. 35.     }  
  6. 36.     sort(number, number+cas, cmp);  
  7. 37.     for(int i = cas-1; i >= 0; --i){  
  8. 38.         printf("%s", number[i].str);  
  9. 39.     }  
  10. 40.     printf(" ");  
  11. 41.     return 0;  

42. }  

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/ghostTao/p/3716558.html