Codeforces Round #173 (Div. 2) 解题报告
题目链接：
http://codeforces.com/contest/282
A题 Bit++
题意：求出通过一系列自增自减运算最后变量的值。不用考虑前后。水题。
#include<iostream>#include<cmath>#include<cstdio>#include<cstdlib>#include<string>#include<cstring>#include<algorithm>#include<vector>#include<map>#include<stack>#include<queue>#define eps 1e-6#define INF (1<<20)#define PI acos(-1.0)using namespace std;int main(){ int n; char save[5]; while(scanf("%d",&n)!=EOF) { int x=0; while(n--) { scanf("%s",save); if(save[0]=='X') { if(save[1]=='-') x--; else x++; } else { if(save[0]=='+') x++; else x--; } } printf("%d\n",x); } return 0;}
B题 Painting Eggs
题意：n个蛋，两个人对每一个蛋涂漆都有一个价格，要使蛋都涂完，且两个人的付费差不超过500，问怎样分配这n个蛋。
解题思路：对每一个蛋进行贪心，如果如果给第一个人使得两人的差价低于给第二个人两人的差价，则把该蛋分给第一个人。
代码：
#include<iostream>#include<cmath>#include<cstdio>#include<cstdlib>#include<string>#include<cstring>#include<algorithm>#include<vector>#include<map>#include<stack>#include<queue>#define eps 1e-6#define INF (1<<20)#define PI acos(-1.0)using namespace std;char ans[1100000];int main(){ int n; while(scanf("%d",&n)!=EOF) { int a=0,b=0,num=0; int temp1,temp2; while(n--) { scanf("%d%d",&temp1,&temp2); if(abs(a+temp1-b)<abs(b+temp2-a)) { ans[num++]='A'; a+=temp1; } else { ans[num++]='G'; b+=temp2; } } ans[num]='\0'; if(abs(a-b)<=500) printf("%s\n",ans); else printf("-1\n"); } return 0;}
C题 XOR and OR
题意：给两个0、1组成的字符串，可以从第一个字符串任取两个相邻的字符，通过抑或和或运算得到两个数代替取出的两个字符，问经过多次这样的操作以后能否得到第二个字符。
解题思路：找规律。11<->01或10 00<->00 它们之间是等价的。所以只要两串都含1且长度相等，一定可以转换。
代码：
#include<iostream>#include<cmath>#include<cstdio>#include<cstdlib>#include<string>#include<cstring>#include<algorithm>#include<vector>#include<map>#include<stack>#include<queue>#define eps 1e-6#define INF (1<<20)#define PI acos(-1.0)using namespace std;char save1[1100000],save2[1100000];int main(){ while(scanf("%s%s",save1,save2)!=EOF) { bool flag1=false,flag2=false; int len1=strlen(save1),len2=strlen(save2); if(len1!=len2||(len1==1&&strcmp(save1,save2))) { printf("NO\n"); continue; } for(int i=0;i<len1;i++) if(save1[i]=='1') { flag1=true; break; } for(int i=0;i<len2;i++) if(save2[i]=='1') { flag2=true; break; } if((flag1==false&&flag2==true)||(flag1==true&&flag2==false)) printf("NO\n"); else printf("YES\n"); } return 0;}
D题： Yet Another Number Game
题意：有n堆数（n<=3),有两种操作，操作一：把某一堆数减一个不大于它的数。操作二：把每一堆都减一个数m(1<=m<=min(所有数））。两人依次操作，每人都完美表现，最后不能做操作的输，问谁赢。
解题思路：当n=1时，如果数量大于0则先胜，否则先负。
当n=2时,Wythoff game.可以直接用公式,也可以用动归把所有的情况都列出来。
当n=3时，Nim game. 如果三个数的抑或为0（奇异点），则必输，否则为赢。
代码：
#include<iostream>#include<cmath>#include<cstdio>#include<cstdlib>#include<string>#include<cstring>#include<algorithm>#include<vector>#include<map>#include<stack>#include<queue>#define eps 1e-6#define INF (1<<20)#define PI acos(-1.0)using namespace std;int main(){ int n,a,b,c; while(scanf("%d",&n)!=EOF) { if(n==1) { scanf("%d",&a); if(a) printf("BitLGM\n"); else printf("BitAryo\n"); } if(n==2) { scanf("%d%d",&a,&b); bool dp[350][350]; memset(dp,false,sizeof(dp)); for(int i=1;i<=a;i++) dp[i][0]=true; for(int j=1;j<=b;j++) dp[0][j]=true; for(int i=1;i<=a;i++) for(int j=1;j<=b;j++) { int flag=0; if(i==j) //采用第二种方法 { dp[i][j]=true; continue; } else { int Min=min(i,j); for(int k=1;k<=Min;k++) if(dp[i-k][j-k]==false) { dp[i][j]=true; flag=1; break; } } if(flag==1) continue; for(int k=1;k<=i;k++) //采用第一种方法 if(dp[i-k][j]==false) { flag=1; dp[i][j]=true; break; } if(flag==0) { for(int k=1;k<=j;k++) if(dp[i][j-k]==false) { dp[i][j]=true; flag=1; break; } } } if(dp[a][b]==true) printf("BitLGM\n"); else printf("BitAryo\n"); } if(n==3) { scanf("%d%d%d",&a,&b,&c); if(a^b^c) printf("BitLGM\n"); else printf("BitAryo\n"); } } return 0;}
E题 Sausage Maximization
题意:给n(n<=10^5)个数，然后让你求出最大的前p个数和后q个数的抑或和。
解题思路：用Trie树。贪心选择最大值。
//trie树与贪心#include<iostream>#include<cmath>#include<cstdio>#include<cstdlib>#include<string>#include<cstring>#include<algorithm>#include<vector>#include<map>#include<stack>#include<queue>#define eps 1e-6#define INF (1<<20)#define PI acos(-1.0)using namespace std;struct Node{ struct Node * son[2]; long long data;}*root;long long save[110000];struct Node * create(){ struct Node *p=(struct Node *)malloc(sizeof(struct Node)); p->data=0; p->son[0]=p->son[1]=NULL; return p;}void insert(struct Node *cur,long long num){ int bit[50]; struct Node *temp=cur; for(int i=0;i<=40;i++) bit[i]=1&(num>>i); for(int i=40;i>=0;i--) //都保存为50位，无所谓是从低位还是从高位 { if(temp->son[bit[i]]==NULL) temp->son[bit[i]]=create(); temp=temp->son[bit[i]]; } temp->data=num;}long long query(struct Node *cur ,long long num){ int bit[50]; struct Node *temp=cur; for(int i=0;i<=40;i++) bit[i]=1&(num>>i); for(int i=40;i>=0;i--) //从高位开始，贪心算法 { if(temp->son[bit[i]^1]) //如果bit[i]=0 则应该选择son[1];如果bit[i]=1,则应该选择son[0] temp=temp->son[bit[i]^1]; //1与其他抑或得到它的反数 else temp=temp->son[bit[i]]; } return num^(temp->data);}int main(){ int n; while(cin>>n) { root=create(); long long sum=0,ans=0; for(int i=1;i<=n;i++) { cin>>save[i]; sum^=save[i]; insert(root,sum); ans=max(ans,sum); //此时后缀为空 } sum=0; for(int i=n;i>=1;i--) { sum^=save[i]; ans=max(ans,query(root,sum)); } cout<<ans<<endl; } return 0;}