Codeforces Round #228 (Div. 2)

做codeforces以来题目最水的一次

A题：

题意:就是用一堆数字来回减，直到减到最小值为止，再把所有最小值加，求这个值

sol: 简单数论题目，直接求所有数字的最大公约数即可

ps: 以前cf出过这道题目啊，出题人没救了 5分钟300人过

1 #include <cstdio>
2 #include <algorithm>
3 #include <cstring>
4 using namespace std;
5 const int MAX =1000 ;
6 int num[MAX];
7 int gcd(int a,int b)
8 {
9     return b==0? a : gcd(b,a%b);
10 }
11 int main()
12 {
13     int n;
14     while(scanf("%d",&n)>0)
15     {
16         for(int i=0;i<n;i++) scanf("%d",&num[i]);
17         int ans=num[0];
18         for(int i=1;i<n;i++)
19         {
20             ans=gcd(ans,num[i]);
21         }
22         printf("%d ",ans*n);
23     }
24     return 0;

25 }

B题

Fox and Cross

题意：求网格中的‘#’是不是全部恰好属于某一个红十字

sol：直接模拟即可

1 #include <cstdio>
2 #include <algorithm>
3 #include <cstring>
4 using namespace std;
5 const int MAX =100 ;
6 char map[MAX][MAX];
7 int vis[MAX][MAX];
8 int main()
9 {
10     int n;
11     while(scanf("%d",&n)>0)
12     {
13         memset(vis,0,sizeof(vis));
14         for(int i=0;i<n;i++)
15         {
16             getchar();
17             for(int j=0;j<n;j++)
18             scanf("%c",&map[i][j]);
19         }
20         for(int i=1;i<n-1;i++)
21         {
22             for(int j=1;j<n-1;j++)
23             {
24                 if(map[i][j]=='#'&&!vis[i][j])
25                 if(map[i-1][j]=='#'&&!vis[i-1][j])
26                 if(map[i+1][j]=='#'&&!vis[i+1][j])
27                 if(map[i][j-1]=='#'&&!vis[i][j-1])
28                 if(map[i][j+1]=='#'&&!vis[i][j+1])
29                 {
30                     vis[i][j]=1; vis[i-1][j]=1; vis[i+1][j]=1
31                     vis[i][j+1]=1; vis[i][j-1]=1
32                 }
33             }
34         }
35         int flag=1;
36         for(int i=0;i<n;i++)
37         {
38             for(int j=0;j<n;j++)
39             if(!vis[i][j]&&map[i][j]=='#')
40             flag=0;
41         }
42         if(flag) printf("YES ");
43         else printf("NO ");
44     }
45     return 0;

46 }

C题：

Fox and Box Accumulation

给出一堆箱子，和每个箱子的power值（即每个箱子的上方最多能放的箱子）经过叠放之后看最后最少剩下多少堆。

sol ：很简单的贪心题目，wa了3次（怕死贪心了>_<）很容易想到如果先从上向下叠放的话叠放一次重量加1只要找到能足以承担

该重量的即可，因此从小到大排个序然后顺着取就可以了。

1 #include <cstdio>
2 #include <algorithm>
3 #include <cstring>
4 using namespace std;
5 const int MAX = 100 +10;
6 const int inf = 0x3f3f3f3f;
7 int num[MAX],use[MAX];
8 int main()
9 {
10     int n,ans,ret;
11     while(scanf("%d",&n)>0)
12     {
13         ans=0; int tot=0;
14         for(int i=0;i<n;i++) scanf("%d",&num[i]);
15         sort(num,num+n);
16         memset(use,0,sizeof(use));
17         while(tot!=n)
18         {
19             int i;
20             for(i=0;i<n;i++) if(!use[i])
21             {
22                 use[i]=1;
23                 ans++;
24                 tot++;
25                 break;
26             }
27             ret=1;
28             for(int j=i+1;j<n;j++)
29             {
30                 if(!use[j]&&num[j]>=ret&&num[j]>0)
31                 {
32                     tot++;
33                     use[j]=1; ret++;
34                 }
35             }
36         }
37         printf("%d ",ans);
38     }
39     return 0;

40 }

D：

Fox and Minimal path

给出点1与点2之间最短路径的总数构建一个图的邻接矩阵。

sol：开始想把路径都构成长为2的，再一看k真么大果断超时。之后想到了二分，之后就没然后了.

这题主要是利用二分和二进制思想（其实都差不多）主要看怎么构图。具体见代码（参考别人的呵呵）。

1 #include<cstdio>
2 #include<cstdlib>
3 #include<cstring>
4 #include<algorithm>
5 #include<cmath>
6 using namespace std;
7 #define INF 100000000
8 int k, dp[110][110], node;
9 int main()
10 {
11     memset(dp,0,sizeof(dp));
12     scanf("%d", &k);
13     dp[1][3]=dp[3][4]=dp[3][5]=1;
14     dp[64][66]=dp[65][66]=f[100][2]=1;
15     for (int i=4; i<=63; i++)
16     {
17         if (i%2!=0) dp[i][i+1]=dp[i][i+2]=1;
18         else dp[i][i+2]=dp[i][i+3]=1;
19     }
20     for (int i=67; i<=99; i++)
21     f[i][i+1]=1;
22     for (int i=31; i>=0; i--)
23     if (k&(1<<i)) node=(i+2)*2,dp[node][67+i]=1;
24     for (int i=1; i<=100; i++)
25     for (int j=1; j<=100; j++) if (dp[i][j]) dp[j][i]=1;
26     printf("%d ",100);
27     for (int i=1;i<=100;i++)
28     {
29         for (int j=1;j<=100;j++)
30         if (dp[i][j]) printf("Y");
31         else printf("N");
32         printf(" ");
33     }

34 }

E题：

Fox and Card Game

又是一个贪心题目。就是给好几堆排然后第一个人取上层的，第二个人取底层的求两个人都采取最优策略能得到分数的最大值

还以为是个dp题目，但是维数太高果断贪心，但是怎么维护最大值又成了卡人的地方，原来这个题只要对半取就可以了，因为可以这么想

假设某堆牌的中上层有一个数大那么第一个人一定会想尽办法先拿到它，同理如果在中下层那么第二个人又会想办法先拿到它，总之：只要是在中上层的第一个人一定能拿到

所以只要对半分就可以了，只要稍微处理下排数为奇数的即可

34 }