Codeforces Round #173 (Div. 2)

A题水题

 1     #include<iostream>
 2     #include<stdio.h>
 3     #include<algorithm>
 4     using namespace std;
 5     
 6     int main( )
 7     {
 8             int i,N;char str[11];
 9             while( scanf("%d",&N) != EOF )
10             {
11                   int res = 0;
12                   for( i = 1; i <= N; i++ )
13                   {
14                              scanf("%s",&str);
15                                if( str[0] == '-')res--;
16                                 else
17                                 if( str[0] == '+')res++;
18                                 else
19                                 if( str[1] == '-')res--;
20                                 else              res++; 
21                   }
22                   cout<<res<<endl;
23              }
24           return 0;
25     }

B 题目神题没想到结果是无论如何走都可以使得答案 <= 500; 因为一旦选择 A 进行+ 运算超过 500 这时就放弃选择A而选择用 B 减去得到的结果；

 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 
 7 int a[1000006],b[1000006];
 8 
 9 int main( )
10 {
11    int i,N,res;
12    while( scanf("%d",&N) != EOF )
13    {               
14         res = 0;
15         for( i = 1; i <= N; i++ )
16            scanf("%d%d",&a[i],&b[i]);
17         for( i = 1; i <= N; i++ )
18         if( res + a[i] >= 500 )
19         {
20            res -= b[i],printf("G");
21         }
22         else 
23         {
24            res += a[i],printf("A");
25         }
26            cout<<endl;
27    }
28    return 0;
29 }

C题一开始一个观点错误以为 0^0 == 1 发现错了之后就 A 了如果存在 10 那么这个 10 可以变成 11 然后变成 01 所以可以给每一位都变成至少一个 1 的状态；那么这个 10 就可以经过变换转换到边边上，然后从左到右依次变换；得到想要的 01串，但 01 状态无法变成 00 状态而 00 状态也无法变成 10 状态所以特判这两种状态就行了

 1 #include<iostream>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<stdio.h>
 5 using namespace std;
 6 
 7 char str[1234567],cha[1234567];
 8 
 9 int main( )
10 {
11     while( scanf("%s%s",&str,&cha) != EOF )
12     {
13         int len1 = strlen( str );
14         int len2 = strlen( cha );
15         int res1 = 0,res2 = 0;
16         if( len1 != len2 ) 
17         {
18             printf("NO\n");
19             continue;
20         }
21         for( int i = 0; i < len1; i++ )
22         {
23             if( str[i] == '1' )res1++;
24             if( cha[i] == '1' )res2++;
25         }
26         if( ( res1 == 0 && res2 ) || ( res1 && res2 == 0 ) )
27              printf("NO\n");
28         else printf("YES\n");
29     }
30     return 0;
31 }

D题博弈论博弈先去看看文章再做题吧！考虑 N == 3 时为什么会是 Nim 博弈呢！因为根据定义发现 N N N

这是一个必胜利状态；可以变成必败状态 0 0 0；而一个必败状态比如说 x y z 同时取走 t 个时平衡破坏；还是可以通过改变 x y z 中的值来使得 x ^y^z = 0 不知道对不对；～～

 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<cmath>
 6 using namespace std;
 7 
 8 int main( )
 9 {
10     int N,a,b,c;
11     while( scanf("%d",&N) != EOF )
12     {
13         scanf("%d",&a);
14         if( N == 1 ) 
15         {
16             if( a ) printf("BitLGM\n");
17             else    printf("BitAryo\n");
18             continue;
19         }
20         scanf("%d",&b);
21         if( a > b ) swap( a,b );
22         if( N == 2 )
23         {
24             if( int((b-a)*(1+sqrt(5))/2.0) == a ) printf("BitAryo\n");
25             else                                  printf("BitLGM\n");
26             continue;
27         }
28         scanf("%d",&c);
29         if( N == 3 )
30         {
31             if( (a^b^c) == 0 )  printf("BitAryo\n");
32             else                printf("BitLGM\n");
33         } 
34     }
35     return 0;
36 }

E题这题真是让我长见识了哈哈好题啊 tree 树还能这么用；

 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 
 7 struct tree
 8 {
 9     tree *son[2];
10     long long val;
11 }*root;
12 long long arr[112345],res,ans;
13 int cnt[49];
14 
15 tree *Creat_node( )
16 {
17     tree *temp = new tree;
18           temp->son[0] = NULL;
19           temp->son[1] = NULL;
20           temp->val    = 0;
21    return temp;
22 }
23 
24 void Insert( long long num )
25 {
26     long long k = 0;
27     memset( cnt,0,sizeof(cnt) );
28     for( int i = 0; i <= 44; i++ )
29     cnt[i] = 1&(num>>i);
30     tree *temp = root;
31     for( int i = 44; i >= 0; i-- )
32     {
33         if( temp->son[cnt[i]] == NULL )
34             temp->son[cnt[i]] =  Creat_node();
35             temp = temp->son[cnt[i]];
36     }
37             temp->val = num;
38 }
39 long long Query( long long num )
40 {
41     long long k = 0;
42     memset( cnt,0,sizeof(cnt) );
43     for( int i = 0; i <= 44; i++ )
44     cnt[i] =1&(num>>i);
45     tree *temp = root;
46     for( int i = 44; i >= 0; i-- )
47     {
48         if(  temp->son[0] == NULL )
49               temp = temp->son[1];
50         else if( temp->son[1] == NULL )
51                 temp = temp->son[0];
52              else if( cnt[i] )
53                       temp = temp->son[0];
54                      else temp = temp->son[1];
55     }
56     return num^(temp->val);
57 }
58 int main( )
59 {
60     int N;
61     while( scanf("%d",&N) != EOF )
62     {
63         root = Creat_node();
64          res = 0,ans = 0;
65         for( int i = 1; i <= N; i++ )
66         {
67             scanf("%I64d",&arr[i]);
68             ans^=arr[i];
69             Insert( ans );
70             res = max( res,ans );
71         }
72         ans = 0;
73         Insert(0);
74         for( int i = N; i >= 1; i-- )
75         {
76            ans ^= arr[i];
77            res = max( res,Query(ans) );
78         }
79         printf("%I64d\n",res);
80     }
81     return 0;
82 }