Biggest Number&&ZOJ 3710 Friends&&Break Standard Weight

Biggest Number

You have a maze with obstacles and non-zero digits in it:

You can start from any square, walk in the maze, and finally stop at some square. Each step, you may only walk into one of the four neighbouring squares (up, down, left, right) and you cannot walk into obstacles or walk into a square more than once. When you finish, you can get a number by writing down the digits you encounter in the same order as you meet them. For example, you can get numbers 9784, 4832145, etc. The biggest number you can get is 791452384, shown in the picture above.

Your task is to find the biggest number you can get.

Input

There will be at most 25 test cases. Each test begins with two integers R and C (2R,C15, R*C30), the number of rows and columns of the maze. The next R rows represent the maze. Each line contains exactly C characters (without leading or trailing spaces), each of them will be either `#' or one of the nine non-zero digits. There will be at least one non-obstacle squares (i.e. squares with a non-zero digit in it) in the maze. The input is terminated by a test case with R = C = 0, you should not process it.

Output

For each test case, print the biggest number you can find, on a single line.

Sample Input

Output for the Sample Input

3 7

##9784#

##123##

##45###

0 0

791452384

这个题目是用搜索来做的，毋庸置疑，但是。。。

  1 #include <cstdio> 
  2 #include <cstring> 
  3 using namespace std;
  4 
  5 int r,c;
  6 char a[20][20];
  7 int used[20][20];//判断是否走过改路径
  8 int ans[100];//存放当前最大数数组 由于该数《=30位 所以用数组存
  9 int ansl;//记录当前最大数位数
 10 int aa[100];//当前数
 11 int zhan[100][2];//呵呵 顾名思义 栈
 12 int used1[20][20];//这个也是判断是否走过路径 下面代码中只用在一处地方 
 13 int neigh[4][2]={{0,1},{1,0},{0,-1},{-1,0}};//查找上下左右位置用的数组
 14 int z;
 15 
 16 void search(int x,int y,int l)//搜索函数
 17 {
 18  int i,j,top,bottom,xx,yy;
 19  if ((l>ansl)||((l==ansl)&&(z==1)))//如果该数大于最大数  z用来判断大小的 注意后面用法 
 20  {
 21   memcpy(ans,aa,sizeof(ans));//aa数组值复制到ans中去
 22   ansl=l;
 23   z=0;
 24  }
 25  memset(used1,0,sizeof(used1));//初始化use1为0  即都没使用过
 26  used1[x][y]=1;
 27  top=0;bottom=1;//下面会用栈来存放后继结点的坐标 为的是记录当前数之后能构成的最长的数
 28  zhan[0][0]=x;
 29  zhan[0][1]=y;
 30  while (top<bottom)//把后继结点都放入栈中  这里是提高速度的一核心
 31  {
 32   for (i=0;i<4;i++)//上下左右
 33   {
 34    xx=zhan[top][0]+neigh[i][0];
 35    yy=zhan[top][1]+neigh[i][1];
 36    if ((xx>=0)&&(xx<r)&&(yy>=0)&&(yy<c)&&(a[xx][yy]!='#')&&(used[xx][yy]==0)&&(used1[xx][yy]==0))
 37    {
 38     zhan[bottom][0]=xx;
 39     zhan[bottom][1]=yy;
 40     used1[xx][yy]=1;
 41     bottom++;
 42    }
 43   }
 44   top++;
 45  }
 46  if (l+top-1<ansl) return;//如果当前长度+后继结点构成最长数长度<最大数长度 直接返回
 47  if ((l+top-1==ansl)&&(z==-1)) return;//长度相等但是比最长数小
 48  for (i=0;i<4;i++)//上下左右递归寻找下一个结点
 49  {
 50   xx=x+neigh[i][0];
 51   yy=y+neigh[i][1];
 52   if ((xx>=0)&&(xx<r)&&(yy>=0)&&(yy<c)&&(a[xx][yy]!='#')&&(used[xx][yy]==0))//下面都是search 注意z的值及其含义
 53   {
 54    aa[l]=a[xx][yy]-'0';
 55    used[xx][yy]=1;
 56    if (z!=0)
 57     search(xx,yy,l+1);
 58    else
 59     if (l>=ansl)
 60     {
 61      z=1;
 62      search(xx,yy,l+1);
 63      z=0;
 64     }
 65     else
 66     {
 67      if (aa[l]>ans[l])
 68      {
 69       z=1;
 70       search(xx,yy,l+1);
 71       z=0;
 72      }
 73      else if (aa[l]==ans[l])
 74      {
 75       z=0;
 76       search(xx,yy,l+1);
 77       z=0;
 78      }
 79      else
 80      {
 81       z=-1;
 82       search(xx,yy,l+1);
 83       z=0;
 84      }
 85     }
 86    used[xx][yy]=0;
 87   }
 88  }
 89 }
 90 
 91 int main()//main里面和search里面大同小异 就是把第一个结点单独拿出来而已 接下来的结点都是遍历过程
 92 {
 93  int i,j;
 94  while (1)
 95  {
 96   scanf("%d%d",&r,&c);
 97   if ((r==0)&&(c==0)) break;
 98   for (i=0;i<r;i++)
 99    scanf("%s",a[i]);
100   memset(ans,0,sizeof(ans));
101   ans[0]=-1;
102   ansl=1;
103   memset(aa,0,sizeof(aa));
104   for (i=0;i<r;i++)
105    for (j=0;j<c;j++)
106     if (a[i][j]!='#')
107     {
108      used[i][j]=1;
109      aa[0]=a[i][j]-'0';
110      if (a[i][j]-'0'>ans[0])
111      {
112       z=1;
113       search(i,j,1);
114      }
115      else if (a[i][j]-'0'==ans[0])
116      {
117       z=0;
118       search(i,j,1);
119      }
120      else
121      {
122       z=-1;
123       search(i,j,1);
124      }
125      used[i][j]=0;
126     }
127   for (i=0;i<ansl;i++)
128    printf("%d",ans[i]);
129   printf("
");
130  }
131  return 0;
132 }

以后慢慢看的！

Friends

%lld & %llu

ZOJ 3710

Description

Alice lives in the country where people like to make friends. The friendship is bidirectional and if any two person have no less than kfriends in common, they will become friends in several days. Currently, there are totally n people in the country, and m friendship among them. Assume that any new friendship is made only when they have sufficient friends in common mentioned above, you are to tell how many new friendship are made after a sufficiently long time.

Input

There are multiple test cases.

The first lien of the input contains an integer T (about 100) indicating the number of test cases. Then T cases follow. For each case, the first line contains three integers n, m, k (1 ≤ n ≤ 100, 0 ≤ m ≤ n×(n-1)/2, 0 ≤ k ≤ n, there will be no duplicated friendship) followed by mlines showing the current friendship. The ith friendship contains two integers u_i, v_i (0 ≤ u_i, v_i < n, u_i ≠ v_i) indicating there is friendship between person u_i and v_i.

Note: The edges in test data are generated randomly.

Output

For each case, print one line containing the answer.

Sample Input

Sample Output

2
0
4
直接上代码，好像是用暴力做的，还是不知道怎么做，看不太懂。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cmath>
 4 #include<cctype>
 5 #include<queue>
 6 #include<stack>
 7 #include<map>
 8 #include<sstream>
 9 #include<cstdlib>
10 #include<list>
11 #include<vector>
12 #include<algorithm>
13 using namespace std;
14 int main()
15 {
16     int t,n,m,k,u,v;
17     int i,j,l,map1[110][110],sum,cnt;
18     scanf("%d",&t);
19     while(t--)
20     {
21        scanf("%d%d%d",&n,&m,&l);
22        memset(map1,0,sizeof(map1));
23        for(i=0;i<m;i++)
24        {
25            scanf("%d%d",&u,&v);
26            map1[u][v]=1;  //初始化，标记本身存在的关系
27            map1[v][u]=1;
28        }
29        sum=0;
30        for(i=0;i<n;i++)  //第i行
31        {
32            for(j=i+1;j<n;j++)   //第j行
33            {
34               cnt=0;
35               if(map1[i][j]==1 ) //本身存在朋友关系，则不用比较
36                   continue;
37               for(k=0;k<n;k++)  //第k列
38               {
39                   if(map1[i][k]==1 && map1[j][k]==1)
40                      cnt++;
41                }
42               if(cnt>=l) //i和j同时拥有相同的l个朋友，则符合条件，有新关系
43               {
44                   sum++;
45                   map1[i][j]=1;  //把新生成的关系加入表中
46                   map1[j][i]=1;
47                   i=-1;  //跳出循环后i++
48                   break;//还要从新再判断！！
49               }
50            }
51        }
52        printf("%d
",sum);
53     }
54     return 0;
55 }

Break Standard Weight http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3706

水题，直接用暴力把每种可能列出来进行比较即可。

 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<set>
 4 #include<cmath>
 5 using namespace std;
 6 int t,MAX,i,a,b;
 7 float x,y,z;
 8 int main()
 9 {
10     set<int> Q;
11     scanf("%d",&t);
12     while(t--)
13     {
14         MAX=0;
15         scanf("%d%d",&a,&b);
16         for(i=1;i<=a/2;i++)
17         {
18             x=a-i;y=i;z=b;
19             Q.insert(x);
20             Q.insert(y);
21             Q.insert(z);
22             Q.insert(x+y);
23             Q.insert(y+z);
24             Q.insert(x+z);
25             Q.insert(x+y+z);
26             if(fabs(x-y)!=0)
27                 Q.insert(fabs(x-y));
28             if(abs(x-z)!=0)
29                 Q.insert(fabs(x-z));
30             if(abs(y-z)!=0)
31                 Q.insert(fabs(y-z));
32             if(abs(x+y-z)!=0)
33                 Q.insert(fabs(x+y-z));
34             if(abs(x+z-y)!=0)
35                 Q.insert(fabs(x+z-y));
36             if(abs(y+z-x)!=0)
37                 Q.insert(fabs(y+z-x));
38             if(Q.size()>MAX)
39                 MAX=Q.size();
40             Q.clear();
41         }
42         for(i=1;i<=b/2;i++)
43          {
44             x=b-i;y=i;z=a;
45             Q.insert(x);
46             Q.insert(y);
47             Q.insert(z);
48             Q.insert(x+y);
49             Q.insert(y+z);
50             Q.insert(x+z);
51             Q.insert(x+y+z);
52             if(fabs(x-y)!=0)
53                 Q.insert(fabs(x-y));
54             if(fabs(x-z)!=0)
55                 Q.insert(fabs(x-z));
56             if(fabs(y-z)!=0)
57                 Q.insert(fabs(y-z));
58             if(abs(x+y-z)!=0)
59                 Q.insert(abs(x+y-z));
60             if(fabs(x+z-y)!=0)
61                 Q.insert(fabs(x+z-y));
62             if(fabs(y+z-x)!=0)
63                 Q.insert(fabs(y+z-x));
64             if(Q.size()>MAX)
65                 MAX=Q.size();
66             Q.clear();
67         }
68         printf("%d
",MAX);
69     }
70     return 0;
71 }//用set<>容器防止有重复的在里面

Biggest Number&&ZOJ 3710 Friends&&Break Standard Weight

Input

Output

相关推荐