8-18-Exercise

A.HDU 1172 猜数字

采用枚举~【赤果果的暴力~】

代码：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 
 6 int x[111],y[111],s,ss,vis[4],dis[4];
 7 char a[111][5];
 8 
 9 void find(int b,int c)
10 {
11     if(b==(a[c][0]-'0') && !vis[0])
12     {
13         s++;vis[0]=1;
14         return;
15     }
16     if(b==(a[c][1]-'0') && !vis[1])
17     {
18         s++;vis[1]=1;
19         return;
20     }
21     if(b==(a[c][2]-'0') && !vis[2])
22     {
23         s++;vis[2]=1;
24         return;
25     }
26     if(b==(a[c][3]-'0') && !vis[3])
27     {
28         s++;vis[3]=1;
29         return;
30     }
31 }
32 
33 int main()
34 {
35     int n,i,j,A,B,C,D,AA,BB,CC,DD;
36     while(scanf("%d",&n),n)
37     {
38         for(i=0;i<n;i++)
39             scanf("%s%d%d",a[i],&x[i],&y[i]);
40         int sum=0;
41         for(i=1000;i<=9999;i++)
42         {
43             D=i%10;
44             C=(i/10)%10;
45             B=(i/100)%10;
46             A=i/1000;
47             int k=0;
48             for(j=0;j<n;j++)
49             {
50                 s=0,ss=0;
51                 memset(vis,0,sizeof(vis));
52                 memset(dis,0,sizeof(dis));
53                 if(A==a[j][0]-'0') {ss++;s++;vis[0]=1;dis[0]=1;}
54                 if(B==a[j][1]-'0') {ss++;s++;vis[1]=1;dis[1]=1;}
55                 if(C==a[j][2]-'0') {ss++;s++;vis[2]=1;dis[2]=1;}
56                 if(D==a[j][3]-'0') {ss++;s++;vis[3]=1;dis[3]=1;}
57                 if(ss!=y[j]) break;
58                 if(!dis[0])  find(A,j);
59                 if(!dis[1])  find(B,j);
60                 if(!dis[2])  find(C,j);
61                 if(!dis[3])  find(D,j);
62                 if(s!=x[j]) break;
63                 k++;
64             }
65             if(k==n)
66             {
67                 sum++;
68                 if(sum==2) break;
69                 AA=A;BB=B;CC=C;DD=D;
70             }
71         }
72         if(sum!=1) printf("Not sure
");
73         else
74             printf("%d%d%d%d
",AA,BB,CC,DD);
75     }
76     return 0;
77 }

B.HDU 2112 HDU Today

就是字符串处理麻烦了点~将字符串编号+Dijkstra就可以了~

代码：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 
 6 #define inf 0x3f3f3f3f        //手抽~最开始把inf写的太大了，结果超int了......= =
 7 int map[160][160],vis[160],n,m,s,e;
 8 long dis[160];
 9 char name[160][32];
10 
11 void dijkstra()
12 {
13     memset(vis,0,sizeof(vis));
14     memset(dis,inf,sizeof(dis));
15     dis[s]=0;
16     for(int i=1;i<=m;i++)
17     {
18         int x,minn=inf;
19         for(int j=1;j<=m;j++)
20             if(!vis[j] && dis[j]<minn)
21             {
22                 minn=dis[j];
23                 x=j;
24             }
25         vis[x]=1;
26         for(int y=1;y<=m;y++)
27             dis[y]=min(dis[y],map[x][y]+dis[x]);
28     }
29     return;
30 }
31 
32 int find(char str[32])
33 {
34     int i;
35     for(i=1;i<=m;i++)
36         if(strcmp(name[i],str)==0)
37             return i;
38     if(m==0 || i>m)
39     {
40         m++;
41         strcpy(name[m],str);
42         return m;
43     }
44 }
45 
46 int main()
47 {
48     while(scanf("%d",&n)!=EOF)
49     {
50         if(n==-1) break;
51         char start[32],end[32],s1[32],s2[32];
52         int i,j,a,b,c;
53         scanf("%s%s",start,end);
54         memset(map,inf,sizeof(map));
55         m=0;
56         for(i=1;i<=n;i++)
57         {
58             scanf("%s%s%d",s1,s2,&c);
59             a=find(s1);
60             b=find(s2);
61             if(map[a][b]>c)
62                 map[a][b]=map[b][a]=c;
63         }
64         s=find(start);
65         e=find(end);
66         if(s==e) printf("0
");
67         else
68         {
69             dijkstra();
70             if(dis[e]!=inf)
71                 printf("%ld
",dis[e]);
72             else
73                 printf("-1
");
74         }
75     }
76     return 0;
77 }

//memory：396KB time：687ms

C.POJ 1321 棋盘问题

dfs~还有就是要注意当K<n 时~

代码：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 using namespace std;
 5 
 6 bool chess[9][9],vis[9];
 7 int ans,n,k;
 8 
 9 void dfs(int row,int num)
10 {
11     if(num==k){ans++;return;}
12     if(row>=n) return;
13     for(int i=0;i<n;i++)
14         if(!vis[i] && chess[row][i])
15     {
16         vis[i]=true;
17         dfs(row+1,num+1);
18         vis[i]=false;
19     }
20     dfs(row+1,num);                    //这一步很重要~
21     return;
22 }
23 
24 int main()
25 {
26     while(~scanf("%d%d",&n,&k))
27     {
28         if(n==-1 && k==-1) break;
29         int i,j;
30         memset(chess,false,sizeof(chess));
31         for(i=0;i<n;i++)
32             for(j=0;j<n;j++)
33         {
34             char c;
35             cin>>c;
36             if(c=='#')
37                 chess[i][j]=true;
38         }
39         ans=0;
40         dfs(0,0);
41         printf("%d
",ans);
42     }
43     return 0;
44 }

//memory：708KB time：32ms

E.POJ 3006 Dirichlet's Theorem on Arithmetic Progressions

呃.......就是暴力啦.......

代码：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cmath>
 5 using namespace std;
 6 
 7 bool juge(int x)
 8 {
 9     for(int i=2;i*i<=x;i++)
10         if(x%i==0) return false;
11     return true;
12 }
13 
14 int main()
15 {
16     int a,b,n,i,j;
17     while(scanf("%d%d%d",&a,&b,&n),a,b,n)
18     {
19         int k=0,sum=0;
20         for(i=0;;i++)
21         {
22             sum=a+i*b;
23             if(sum>1 && juge(sum))
24                 k++;
25             if(k==n) break;
26         }
27         printf("%d
",sum);
28     }
29     return 0;
30 }

View Code

//memory：164KB time：250ms