[关闭]
@994495jj 2017-05-31T11:47:17.000000Z 字数 8199 阅读 1142

FZU周练-0529新队员场题解

（ACM）数学----博弈论 （ACM）贪心 （ACM）构造

题目链接

A. CodeForces 787C Berzerk（博弈论）

题意

题解

代码

  1. #include<cstdio>
  2. #include<queue>
  3. #include<cstring>
  4. using namespace std;
  5. #define mp make_pair
  7. const int N=7005;
  8. queue<pair<int,int> > q;
  9. int k[2],a[2][N],f[2][N],deg[2][N];
  11. void print(int x) {
  12.     if(x==1) printf("Win ");
  13.     else if(x==0) printf("Lose ");
  14.     else printf("Loop ");
  15. }
  17. int main() {
  18.     int n;
  19.     while(~scanf("%d",&n)) {
  20.         ///init
  21.         memset(f,-1,sizeof(f));
  22.         int tt=q.size();
  23.         while(tt--) q.pop();
  25.         ///read
  26.         scanf("%d",&k[0]);
  27.         for(int i=1;i<=k[0];++i) scanf("%d",&a[0][i]);
  28.         scanf("%d",&k[1]);
  29.         for(int i=1;i<=k[1];++i) scanf("%d",&a[1][i]);
  31.         ///get deg
  32.         for(int i=0;i<n;++i) deg[0][i]=k[0];
  33.         for(int i=0;i<n;++i) deg[1][i]=k[1];
  35.         ///bfs
  36.         f[0][n-1]=f[1][n-1]=0;
  37.         q.push(mp(0,n-1));
  38.         q.push(mp(1,n-1));
  39.         while(!q.empty()) {
  40.             int now=q.front().first;
  41.             int pos=q.front().second;
  42.             q.pop();
  44.             int prn=1-now;
  45.             for(int i=1;i<=k[prn];++i) {
  46.                 int prp=(pos-a[prn][i]+n)%n;
  47.                 if(f[prn][prp]!=-1) continue;
  48.                 if(f[now][pos]) {
  49.                     --deg[prn][prp];
  50.                     if(deg[prn][prp]==0) {
  51.                         f[prn][prp]=0;
  52.                         q.push(mp(prn,prp));
  53.                     }
  54.                 } else {
  55.                     f[prn][prp]=1;
  56.                     q.push(mp(prn,prp));
  57.                 }
  58.             }
  59.         }
  61.         ///print
  62.         for(int i=0;i<=1;++i) {
  63.             for(int j=0;j<n-1;++j) {
  64.                 print(f[i][j]);
  65.             }
  66.             puts("");
  67.         }
  68.     } 
  69.     return 0;
  70. }

B. CodeForces 794C Naming Company（贪心）

题意

题解

代码

  1. #include<cstdio>
  2. #include<cmath>
  3. #include<cstring>
  4. #include<algorithm>
  5. using namespace std;
  7. const int N=300005;
  8. char s1[N],s2[N],s[N];
  10. int main() {
  11.     int n,h;
  12.     while(~scanf("%s%s",s1,s2)) {
  13.         int n=strlen(s1);
  14.         sort(s1,s1+n);
  15.         sort(s2,s2+n);
  17.         ///zeng
  18.         int n2=n/2,n1=n-n2;
  19.         s1[n1]='\0';
  21.         ///jian
  22.         for(int i=0;i<n2;++i) s2[i]=s2[n-i-1];
  23.         s2[n2]='\0';
  25.         int p=0,p1=0,p2=0;
  26.         for(;p<n;++p) {
  27.             if(s1[p1]>=s2[p2]) break;
  28.             if(p&1) {
  29.                 s[p]=s2[p2++];
  30.             } else {
  31.                 s[p]=s1[p1++];
  32.             }
  33.         }
  34.         int q=n-1,q1=n1-1,q2=n2-1;
  35.         for(;p<n;++p) {
  36.             if(p&1) {
  37.                 s[q--]=s2[q2--];
  38.             } else {
  39.                 s[q--]=s1[q1--];
  40.             }
  41.         }
  42.         s[n]='\0';
  43.         printf("%s\n",s);
  44.     }
  45.     return 0;
  46. }

C. CodeForces 798A Mike and palindrome（水题）

题意

题解

注意

代码

  1. #include<cstdio>
  2. #include<cstring>
  3. #include<vector>
  4. #include<map>
  5. #include<iostream>
  6. #include<cstring>
  7. #include<queue>
  8. using namespace std;
  9. #define mp make_pair
  10. #define fi first
  11. #define se second
  13. int main() {
  14.     string s;
  15.     while(cin>>s) {
  16.         int len=s.length();
  17.         int cnt=0;
  18.         for(int i=0;;++i) {
  19.             int j=len-1-i;
  20.             if(i>=j) break;
  21.             if(s[i]!=s[j]) ++cnt;
  22.         }
  23.         if(cnt==1||(cnt==0&&(len&1))) puts("YES");
  24.         else puts("NO");
  25.     }
  26.     return 0;
  27. }

D. CodeForces 798B Mike and strings（水题）

题意

题解

注意

代码

  1. #include<cstdio>
  2. #include<algorithm>
  3. #include<string>
  4. #include<iostream>
  5. using namespace std;
  7. const int N=55;
  8. string s[N],tmp[N][N];
  9. int n,len;
  11. void gettmp(int t) {
  12.     tmp[t][0]=s[t];
  13.     for(int i=1;i<len;++i) {
  14.         tmp[t][i]="";
  15.         for(int j=i;j<len;++j) tmp[t][i]=tmp[t][i]+s[t][j];
  16.         for(int j=0;j<i;++j) tmp[t][i]=tmp[t][i]+s[t][j];
  17.     }
  18. }
  20. int solve() {
  21.     int ans=n*len;
  22.     for(int i=0;i<len;++i) {
  23.         int res=0;
  24.         for(int j=1;j<=n;++j) {
  25.             int k;
  26.             for(k=0;k<len;++k) {
  27.                 if(tmp[j][k]==tmp[1][i]) break;
  28.             }
  29.             if(k==len) return -1;
  30.             res=res+k;
  31.         }
  32.         ans=min(ans,res);
  33.     }
  34.     return ans;
  35. }
  38. int main() {
  39.     while(~scanf("%d",&n)) {
  40.         ///read
  41.         for(int i=1;i<=n;++i) cin>>s[i];
  43.         ///get len
  44.         len=s[1].length();
  46.         ///get tmp
  47.         for(int i=1;i<=n;++i) gettmp(i);
  49.         ///print
  50.         printf("%d\n",solve());
  51.     }
  52.     return 0;
  53. }

E. CodeForces 798C Mike and gcd problem

题意

题解

代码

  1. #include<cstdio>
  3. const int N=100005;
  4. int a[N];
  6. int gcd(int a,int b) {
  7.     if(b==0) return a;
  8.     return gcd(b,a%b);
  9. }
  11. int main() {
  12.     int n;
  13.     while(~scanf("%d",&n)) {
  14.         ///read
  15.         for(int i=1;i<=n;++i) scanf("%d",a+i);
  17.         ///get d
  18.         int d=a[1];
  19.         for(int i=2;i<=n;++i) {
  20.             d=gcd(d,a[i]);
  21.         }
  23.         ///
  24.         if(d>1) {
  25.             puts("YES\n0");
  26.             continue;
  27.         }
  29.         ///solve
  30.         int ans=0,now=0;
  31.         for(int i=1;i<=n+1;++i) {
  32.             if( a[i]%2 && a[i-1]%2 ) {
  33.                 ++now;
  34.             } else if( a[i]%2 && a[i-1]%2==0 ) {
  35.                 now=1;
  36.             } else if( a[i]%2==0 && a[i-1]%2 ) { 
  37.                 ans=ans+now/2;
  38.                 if(now&1) ans+=2;
  39.             }
  40.         }
  42.         ///print
  43.         printf("YES\n%d\n",ans);
  46.     }
  47.     return 0;
  48. }

F. CodeForces 798D Mike and distribution（构造）

题意

题解

代码

  1. #include<cstdio>  
  2. #include<algorithm>  
  3. using namespace std;  
  5. struct Node {  
  6.     int a,b,i;  
  7.     bool operator < (const Node &tmp) const {  
  8.         if(a==tmp.a) return i<tmp.i;  
  9.         return a>tmp.a;  
  10.     }  
  11. }a[100005];  
  13. int main() {  
  14.     ///  
  15.     int n;scanf("%d",&n);  
  17.     ///init  
  18.     for(int i=1;i<=n;++i) a[i].i=i;  
  20.     ///read  
  21.     for(int i=1;i<=n;++i) scanf("%d",&a[i].a);  
  22.     for(int i=1;i<=n;++i) scanf("%d",&a[i].b);  
  24.     ///solve  
  25.     sort(a+1,a+1+n);  
  26.     printf("%d\n%d",n/2+1,a[1].i);  
  27.     if(n%2==0) printf(" %d",a[n].i);  
  28.     for(int i=2;i+1<=n;i+=2) {  
  29.         printf(" %d",(a[i].b>a[i+1].b)?a[i].i:a[i+1].i);  
  30.     }  
  31.     puts("");  
  33.     return 0;  
  34. }

G. CodeForces 765A Neverending competitions（水题）

题意

题解

代码

  1. #include <algorithm>
  2. #include <iostream>
  3. #include <cstring>
  4. #include <vector>
  5. #include <cstdio>
  6. #include <string>
  7. #include <cmath>
  8. #include <queue>
  9. #include <set>
  10. #include <map>
  11. using namespace std;
  12. typedef long long ll;
  13. typedef unsigned long long ull;
  14. typedef pair<int,int> pii;
  15. typedef pair<ll,ll> pll;
  16. #define mp make_pair
  17. #define pb push_back
  18. #define fi first
  19. #define se second
  20. #define lson l,m,rt<<1
  21. #define rson m+1,r,rt<<1|1
  22. #define de(x) cout << #x << "=" << x << endl
  23. int main() {
  24.     int n;string s;scanf("%d",&n);
  25.     for(int i=0;i<=n;++i) cin>>s;
  26.     if(n&1) puts("contest");
  27.     else puts("home");
  28.     return 0;
  29. }

H. CodeForces 765B Code obfuscation（水题）

题意

题解

代码

  1. #include <algorithm>
  2. #include <iostream>
  3. #include <cstring>
  4. #include <vector>
  5. #include <cstdio>
  6. #include <string>
  7. #include <cmath>
  8. #include <queue>
  9. #include <set>
  10. #include <map>
  11. using namespace std;
  12. typedef long long ll;
  13. typedef unsigned long long ull;
  14. typedef pair<int,int> pii;
  15. typedef pair<ll,ll> pll;
  16. #define mp make_pair
  17. #define pb push_back
  18. #define fi first
  19. #define se second
  20. #define lson l,m,rt<<1
  21. #define rson m+1,r,rt<<1|1
  22. #define de(x) cout << #x << "=" << x << endl
  23. const int N=505;
  24. char s[N];
  25. int main() {
  26.     scanf("%s",s);
  27.     int n=strlen(s);
  28.     int now='a';//现在要找的是now 
  29.     bool ans=1;
  30.     for(int i=0;i<n;++i) {
  31.         if(s[i]>now) {
  32.             ans=0;
  33.             break;
  34.         }
  35.         if(s[i]==now) ++now;
  36.     }
  37.     if(ans) puts("YES");
  38.     else puts("NO");
  39.     return 0;
  40. }

I. CodeForces 765C Table Tennis Game 2（水题）

题意

题解

代码

  1. #include <algorithm>
  2. #include <iostream>
  3. #include <cstring>
  4. #include <vector>
  5. #include <cstdio>
  6. #include <string>
  7. #include <cmath>
  8. #include <queue>
  9. #include <set>
  10. #include <map>
  11. using namespace std;
  12. typedef long long ll;
  13. typedef unsigned long long ull;
  14. typedef pair<int,int> pii;
  15. typedef pair<ll,ll> pll;
  16. #define mp make_pair
  17. #define pb push_back
  18. #define fi first
  19. #define se second
  20. #define lson l,m,rt<<1
  21. #define rson m+1,r,rt<<1|1
  22. #define de(x) cout << #x << "=" << x << endl
  23. int main() {
  24.     int k,a,b;
  25.     cin>>k>>a>>b;
  26.     int ansa=a/k,ansb=b/k;
  27.     if(a%k&&!ansb||b%k&&!ansa) {
  28.         puts("-1");
  29.         return 0;
  30.     } else {
  31.         printf("%d\n",ansa+ansb);
  32.     }
  33.     return 0;
  34. }

J. CodeForces 794B Cutting Carrot（水题）

题意

题解

注意

代码

  1. #include<cstdio>
  2. #include<cmath>
  4. int main() {
  5.     int n,h;
  6.     while(~scanf("%d%d",&n,&h)) {
  7.         for(int i=1;i<n;++i) {
  8.             printf("%.12lf%c",sqrt(i*1.0/n)*h,(i==n-1)?'\n':' ');
  9.         }
  10.     }
  11.     return 0;
  12. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注