Codeforces Round #573 (Div. 2)

A：Tokitsukaze and Enhancement

当时看错条件了。。以为A>C>B>D。就胡写了判断条件。

 #include<bits/stdc++.h>

 using namespace std;

 bool work(int a,int b) {

     if(a==-) return false;

     if(b==-) return true;

     if(a==&&(b==||b==||b==)) return true;

     if(a==&&(b==||b==)) return true;

     if(a==&&b==) return true;

     return false;

 }

 map<int,char> mp;

 int main() {

     mp[]='A';

     mp[]='C';

     mp[]='B';

     mp[]='D';

     int x;

     scanf("%d",&x);

     int ans=-,pos=-;

     char strans;

     for(int i=;i<=;i++) {

         int tmp=(x+i)%;

         if(work(tmp,ans)) {

             ans=tmp;

             pos=i;

             strans=mp[tmp];

         }

     }

     printf("%d %c",pos,strans);

 }

胡搞

看了题解，感觉还是思考太少。

根据余数，取最好的即可。

 #include <bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const int maxn=1e5+;

 int main() {

     int x;

     scanf("%d",&x);

     x%=;

     if(x==) printf("%d %c\n",,'A');

     else if(x==) printf("%d %c\n",,'B');

     else if(x==) printf("%d %c\n",,'A');

     else printf("%d %c\n",,'A');

 }

B：Tokitsukaze and Mahjong

数字对应放到s,m,p组里，然后暴力找胜利的最少添加数。

 #include<bits/stdc++.h>

 using namespace std;

 string s1,s2,s3;

 vector<int> t[];

 int id(char c) {

     if(c=='s') return ;

     if(c=='m') return ;

     if(c=='p') return ;

 }

 int a[];

 int main() {

     cin>>s1>>s2>>s3;

     int id1,id2,id3;

     id1=id(s1[]);

     id2=id(s2[]);

     id3=id(s3[]);

     t[id1].push_back(s1[]-'');

     t[id2].push_back(s2[]-'');

     t[id3].push_back(s3[]-'');

     int ans=;

    // for(int i=0;i<t[1].size();i++) printf("%d ",t[1][i]);

     for(int i=;i<=;i++) {

         memset(a,,sizeof(a));

         for(int j=;j<t[i].size();j++) {

             a[t[i][j]]++;

         }

         for(int j=;j<=;j++) {

             //printf("%d\n",a[j]);

             ans=min(ans,-a[j]);

         }

         int cnt;

         for(int j=;j<=;j++) {

             cnt=;

             for(int k=j;k<=j+&&k<=;k++) {

                 if(a[k]>) cnt++;

             }

             //printf("%d**\n",cnt);

             ans=min(ans,-cnt);

         }

     }

     printf("%d\n",ans);

 }

C：Tokitsukaze and Discard Items

删除的数字是递增的，处理出当前要删除数字所在块的最后一个数字，然后删除，直到全部删除。

 #include <bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const int maxn=1e5+;

 ll n,m,k,a[maxn];

 int main() {

     scanf("%lld%lld%lld",&n,&m,&k);

     for(int i=;i<=m;i++) scanf("%lld",&a[i]);

     int sum=; //删除总数

     int ans=;

     int now=;

     while(now<=m) {

         // 没想到

         ll r=((a[now]-sum-)/k+)*k+sum;

         while(now<=m&&a[now]<=r) {

             sum++;

             now++;

         }

         ans++;

     }

     printf("%d\n",ans);

 }

D：Tokitsukaze, CSL and Stone Game

博弈果断一点不会。分析：

首先判断先手必败的条件

1、有三堆及以上数量相等的石头，即 x x x

2、有两对及以上两堆数量相等的石头，即 x x y y

3、有两堆及以上的空堆，即 0 0 0

4、有相等的堆且存在数量减一的堆，即 x x x-1

除了以上情况，最后会变成这样的状态 (先手必胜)

0 1 2 3 …… n-1

所以判断形成这样的步数的奇偶即可。

 #include <bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const int maxn=1e5+;

 int n,a[maxn];

 map<int,int> mp;

 int main() {

     scanf("%d",&n);

     int ok=;

     for(int i=;i<=n;i++) {

         scanf("%d",&a[i]);

         mp[a[i]]++;

         ok&=(mp[a[i]]<=);  // x x x

     }

     int cnt=;

     map<int,int>::iterator it;

     for(it=mp.begin();it!=mp.end();it++) {

         if(it->second>=) cnt++; // x x y y

     }

     ok&=(cnt<=);

     for(it=mp.begin();it!=mp.end();it++) {

         if(it->second==) {

             ok&=(mp.count(it->first-)==); // x x x-1

             if(it->first==) ok=; // 0 0

         }

     }

     if(!ok) return *puts("cslnb");

     // 0 1 2 3 …… n-1

     sort(a+,a+n+);

     ll s=;

     for(int i=;i<=n;i++) {

         s+=a[i]-(i-);

     }

     s%=;

     return *puts(s?"sjfnb":"cslnb");

 }

E：Tokitsukaze and Duel

分析：

先手如果第一步不能获胜，以后就不可能获胜。

后手如果第一步不能获胜，以后也不可能获胜，因为对方可以反转相同的维持局面。

先手获胜：可以通过前缀和预处理出先手是否必胜。

如果后手想要获胜，那么

1、k != 1 无限跳转

2、2*k >= n 因为到后手必定有一段连续的k个0或1，如果后手能获胜，必须能覆盖掉整个串

然后先手若不能第一步获胜，他必定会取中间的k个连续位置，所以要处理左右两个区间a、b

int len = n - k - 1;

a[1]==a[n] || a[len] == a[len+1] || a[n-len] == a[n-len+1] 时后手也不能获胜

不是太懂，画图。。。

 #include <bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 const int maxn=1e5+;

 int n,k,a[maxn],sum[maxn];

 int query(int l,int r) {

     if(l>r) return ;

     return sum[r]-sum[l-];

 }

 bool check1() {

     for(int i=;i+k-<=n;i++) {

         int tmp=query(,i-)+query(i+k,n);

         if(tmp==||tmp+k==n) return true;

     }

     return false;

 }

 bool check2() {

     if(k==||*k<n) return false;

     int len=n-k-;

     for(int i=;i<=len;i++) {

         if(a[i]!=a[i-]||a[n-i+]!=a[n-i+]) return false;

     }

     if(a[]==a[n]||a[len]==a[len+]||a[n-len]==a[n-len+]) return false;

     return true;

 }

 int main() {

     scanf("%d%d",&n,&k);

     for(int i=;i<=n;i++) scanf("%1d",&a[i]);

     for(int i=;i<=n;i++) sum[i]=sum[i-]+a[i];

     if(check1()) puts("tokitsukaze");

     else if(check2()) puts("quailty");

     else puts("once again");

     return ;

 }

巴特西

Codeforces Round #573 (Div. 2)

最新文章

热门文章