Codeforces Round #573 (Div. 2)

浅浅的花香味﹌ 2021-09-29 13:10 407阅读 0赞























Sloved A B C D E F
6/6 O O O O Ø Ø
  • O for passing during the contest
  • Ø for passing after the contest
  • ! for attempted but failed
  • · for having not attempted yet

A.Tokitsukaze and Enhancement(0:05,+1)

签到题，读题找规律即可

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define rep(i,a,n) for (int i=a;i<n;i++)
  4. #define per(i,a,n) for (int i=n-1;i>=a;i--)
  5. #define pb push_back
  6. #define mp make_pair
  7. #define all(x) (x).begin(),(x).end()
  8. #define fi first
  9. #define se second
  10. #define SZ(x) ((int)(x).size())
  11. typedef vector<int> VI;
  12. typedef long long ll;
  13. typedef pair<int,int> PII;
  14. const ll mod=1000000007;
  15. ll powmod(ll a,ll b) { ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){ if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
  16. ll gcd(ll a,ll b) {  return b?gcd(b,a%b):a;}
  18. int n;
  19. int main(int argc, char const *argv[])
  20. { 
  21.     ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  22.     cin >> n;
  23.     int x = n % 4;
  24.     if(x == 1)
  25.     { 
  26.         cout << 0  << " " << "A"<< endl;
  27.     }
  28.     if(x == 2)
  29.     { 
  30.         cout << 1  << " " << "B"<< endl;
  31.     }
  32.     if(x == 3)
  33.     { 
  34.         cout << 2  << " " << "A"<< endl;
  35.     }
  36.     if(x == 0)
  37.     { 
  38.         cout << 1  << " " << "A"<< endl;
  39.     }
  40.     return 0;
  41. }

B.Tokitsukaze and Mahjong(0:24,+3)

模拟，注意1m 3m 5m的情况

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define rep(i,a,n) for (int i=a;i<n;i++)
  4. #define per(i,a,n) for (int i=n-1;i>=a;i--)
  5. #define pb push_back
  6. #define mp make_pair
  7. #define all(x) (x).begin(),(x).end()
  8. #define fi first
  9. #define se second
  10. #define SZ(x) ((int)(x).size())
  11. typedef vector<int> VI;
  12. typedef long long ll;
  13. typedef pair<int,int> PII;
  14. const ll mod=1000000007;
  15. ll powmod(ll a,ll b) { ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){ if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
  16. ll gcd(ll a,ll b) {  return b?gcd(b,a%b):a;}
  18. string str[10];
  19. int cnt[5][10];
  20. int main(int argc, char const *argv[])
  21. { 
  22.     ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  23.     rep(i,0,3)
  24.     { 
  25.         cin >> str[i];
  26.         if(str[i][1] == 's')
  27.         { 
  28.             cnt[0][str[i][0]-'0']++;
  29.         }
  30.         else if(str[i][1] == 'p')
  31.         { 
  32.             cnt[1][str[i][0]-'0']++;
  33.         }
  34.         else
  35.         { 
  36.             cnt[2][str[i][0]-'0']++;
  37.         }
  38.     }
  39.     int ans = 2;
  40.     //
  41.     rep(i,0,3)
  42.     { 
  43.         rep(j,1,10)
  44.         { 
  45.             if(cnt[i][j])
  46.             { 
  47.                 ans = min(ans,3-cnt[i][j]);
  48.             }
  49.         }
  50.     }
  51.     int s = 0;
  52.     rep(i,0,3)
  53.     { 
  54.         s = 0;
  55.         rep(j,1,10)
  56.         { 
  57.             if(cnt[i][j])
  58.             { 
  59.                 s+=1;
  60.             }
  61.             else
  62.             { 
  63.                 ans = min(ans,3-s);
  64.                 s = 0;
  65.             }
  66.         }
  67.         ans = min(ans,3-s);
  68.     }
  69.     rep(i,0,3)
  70.     { 
  71.         rep(j,1,8)
  72.         { 
  73.             if(cnt[i][j] && cnt[i][j+2])
  74.             { 
  75.                 ans = min(ans,1);
  76.             }
  77.         }
  78.     }
  79.     cout << ans << endl;
  80.     return 0;
  81. }

C.Tokitsukaze and Discard Items(00:48,+1)

直接O(n)遍历模拟即可，不要想复杂

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define rep(i,a,n) for (int i=a;i<n;i++)
  4. #define per(i,a,n) for (int i=n-1;i>=a;i--)
  5. #define pb push_back
  6. #define mp make_pair
  7. #define all(x) (x).begin(),(x).end()
  8. #define fi first
  9. #define se second
  10. #define SZ(x) ((int)(x).size())
  11. typedef vector<int> VI;
  12. typedef long long ll;
  13. typedef pair<int,int> PII;
  14. const ll mod=1000000007;
  15. ll powmod(ll a,ll b) { ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){ if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
  16. ll gcd(ll a,ll b) {  return b?gcd(b,a%b):a;}
  17. const int maxn = 1e5+100;
  20. ll n,m,k;
  21. ll p;
  22. int main(int argc, char const *argv[])
  23. { 
  24.     ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  25.     cin >> n >> m >> k;
  26.     ll ans = 0;
  27.     ll t = 0;//dz
  28.     ll s = 0;//-
  29.     ll s1 = 0;
  30.     rep(i,0,m)
  31.     { 
  32.         cin >> p;
  33.         p -= s;
  34.         if((p%k == 0 && p / k == t)||(p%k != 0 && p / k + 1 == t))
  35.         { 
  36.             s1++;
  37.         }
  38.         else
  39.         { 
  40.             p -= s1 - s;
  41.             s = s1;
  42.             ans++;
  43.             //cout << i << "----" << endl;
  44.             if(p % k == 0)
  45.             { 
  46.                 t = p / k;
  47.             }
  48.             else
  49.                 t = p / k + 1;
  50.             s1++;
  51.         }
  52.     }
  53.     cout << ans << endl;
  54.     return 0;
  55. }

D.Tokitsukaze, CSL and Stone Game(01:35,+2)

考虑几种情况

  • 2 2 3和1 2 2，后一种cslnb
  • 计算数的个数大于2的总数，cnt >= 2，则cslnb（包括 3 3 3这种情况）
  • 一些显然得到答案的方案

最后特判完，假如还没有得到结果，则最后的局面应为 0 1 2 3 … n-1，直接作差，%2判断即可

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define rep(i,a,n) for (int i=a;i<n;i++)
  4. #define per(i,a,n) for (int i=n-1;i>=a;i--)
  5. #define pb push_back
  6. #define mp make_pair
  7. #define all(x) (x).begin(),(x).end()
  8. #define fi first
  9. #define se second
  10. #define SZ(x) ((int)(x).size())
  11. typedef vector<int> VI;
  12. typedef long long ll;
  13. typedef pair<int,int> PII;
  14. const ll mod=1000000007;
  15. ll powmod(ll a,ll b) { ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){ if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
  16. ll gcd(ll a,ll b) {  return b?gcd(b,a%b):a;}
  17. const int maxn = 1e5 + 1000;
  19. ll n;
  20. ll a[maxn];
  21. int main(int argc, char const *argv[])
  22. { 
  23.     ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  25.     cin >> n;
  27.     ll sum = 0;
  28.     int zero = 0;
  29.     rep(i,0,n)
  30.     { 
  31.         cin >> a[i];
  32.         if(a[i] == 0)
  33.         { 
  34.             zero++;
  35.         }
  36.         sum += a[i];
  37.     }
  38.     if(sum == 0)
  39.     { 
  40.         cout << "cslnb" << endl;
  41.         return 0;
  42.     }
  44.     if(zero >= 2)
  45.     { 
  46.         cout << "cslnb" << endl;
  47.         return 0;    
  48.     }
  50.     if(n == 1) // judge only
  51.     { 
  52.         if(sum % 2 == 0)
  53.         { 
  54.             cout << "cslnb"<<endl;
  55.         }
  56.         else
  57.         { 
  58.             cout << "sjfnb"<<endl;
  59.         }
  60.         return 0;
  61.     }
  63.     sort(a,a+n);
  65.     int cnt = 0;
  66.     int t = 0;
  67.     int wz = 0;
  68.     rep(i,0,n)
  69.     { 
  70.         if(a[i] == a[i+1])
  71.         { 
  72.             cnt++;
  73.             t = a[i];
  74.             wz = i;
  75.         }
  76.     }
  77.     if(cnt >= 2)
  78.     { 
  79.            cout <<"cslnb" << endl;
  80.            return 0;
  81.     }
  82.     else if(cnt == 1)
  83.     { 
  84.         if(wz == 0 || a[wz-1] < t-1)
  85.         { 
  86.             sum -= (0+n-1)*n/2;
  87.             if(sum % 2 == 0)
  88.             { 
  89.                 cout << "cslnb"<<endl;
  90.             }
  91.             else
  92.             { 
  93.                 cout << "sjfnb"<<endl;
  94.             }
  95.             return 0;
  96.         }
  97.         else
  98.         { 
  99.             cout << "cslnb" << endl;
  100.             return 0;
  101.         }
  102.     }
  103.     else
  104.     { 
  105.         sum -= (0+n-1)*n/2;
  106.         if(sum % 2 == 0)
  107.         { 
  108.             cout << "cslnb"<<endl;
  109.         }
  110.         else
  111.         { 
  112.             cout << "sjfnb"<<endl;
  113.         }
  114.     }
  115.     return 0;

E.Tokitsukaze and Duel

找出第一个和最后一个1，第一个和最后一个0
sjf胜利的条件很简单，zero2 - zero1 < k || one2- one1 < k
难点在qls的回合判断
现在设计一个数组a，元素为zero2 ， zero1 ， one2， one1，并排序

  • 已知在qls的回合，qls不可能输，顶多once again

qls胜利，条件为a2-a0 <= k and a3-a1 <= k

  • 已经判断了第一回合，则a1和a2不可能同是0或1，即a0和a3为0和1
  • 无论sjf选择哪一段，必包括a1和a2
  • 假设sjf把那一段变成1，qls可以把边缘的0到中间一段变成1，同理假设sjf把那一段变成0，qls可以把边缘的1到中间一段变成0
  • 重点在于无论如何，当满足条件时，sjf无论如何操作都覆盖到了中间的0和1

假设不满足这个条件，则sjf必定可以选择一段不覆盖中间的0和1，qls只能选择once again
具体要理解清楚可能需要自己举一些例子，或者严格证明一下

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define rep(i,a,n) for (int i=a;i<n;i++)
  4. #define per(i,a,n) for (int i=n-1;i>=a;i--)
  5. #define pb push_back
  6. #define mp make_pair
  7. #define all(x) (x).begin(),(x).end()
  8. #define fi first
  9. #define se second
  10. #define SZ(x) ((int)(x).size())
  11. typedef vector<int> VI;
  12. typedef long long ll;
  13. typedef pair<int,int> PII;
  14. const ll mod=1000000007;
  15. ll powmod(ll a,ll b) { ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){ if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
  16. ll gcd(ll a,ll b) {  return b?gcd(b,a%b):a;}
  18. int n,k;
  19. string str;
  20. int one1,one2;
  21. int zero1,zero2;
  23. int a[10];
  24. int main(int argc, char const *argv[])
  25. { 
  26.     cin >> n >> k;
  27.     cin >> str;
  29.     rep(i,0,n)
  30.     { 
  31.         if(str[i] == '0')
  32.         { 
  33.             if(zero1 == 0)
  34.             { 
  35.                 zero1 = i + 1;
  36.             }
  37.                 zero2 = i + 1;
  38.         }
  39.         if(str[i] == '1')
  40.         { 
  41.             if(one1 == 0)
  42.             { 
  43.                 one1 = i + 1;
  44.             }
  45.                 one2 = i + 1;
  46.         }
  47.     }
  48.     if(zero2 - zero1 < k || one2 - one1 < k)
  49.     { 
  50.         cout << "tokitsukaze" << endl;
  51.         return 0;
  52.     }
  53.     a[0] = zero1;
  54.     a[1] = zero2;
  55.     a[2] = one1;
  56.     a[3] = one2;
  57.     sort(a,a+4);
  58.     if(a[3] - a[1] <= k && a[2] - a[0] <= k)
  59.     { 
  60.         cout << "quailty" << endl;
  61.         return 0;
  62.     }
  63.     cout << "once again" << endl;
  64.     return 0;
  65. }

F.Tokitsukaze and Strange Rectangle

扫描线+离散化

  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define rep(i,a,n) for (int i=a;i<n;i++)
  4. #define per(i,a,n) for (int i=n-1;i>=a;i--)
  5. #define pb push_back
  6. #define mp make_pair
  7. #define all(x) (x).begin(),(x).end()
  8. #define fi first
  9. #define se second
  10. #define SZ(x) ((int)(x).size())
  11. typedef vector<int> VI;
  12. typedef long long ll;
  13. typedef pair<int,int> PII;
  14. const ll mod=1000000007;
  15. ll powmod(ll a,ll b) { ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){ if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
  16. ll gcd(ll a,ll b) {  return b?gcd(b,a%b):a;}
  17. //树状数组
  18. struct Bit
  19. { 
  20.     vector<int> a;
  21.     int sz;
  22.     void init(int n)
  23.     { 
  24.         sz=n+5;
  25.         for(int i=1;i<=n+5;i++)
  26.             a.push_back(0);
  27.     }
  28.     int lowbit(int x)
  29.     { 
  30.         return x&(-x);
  31.     }
  32.     int query(int x)
  33.     { 
  34.         int ans = 0;
  35.         for(;x;x-=lowbit(x))ans+=a[x];
  36.         return ans;
  37.     }
  38.     int query(int l ,int r)
  39.     { 
  40.         return query(r) - query(l-1);
  41.     }
  42.     void update(int x,int v)
  43.     { 
  44.         for(;x<sz;x+=lowbit(x))
  45.             a[x]+=v;
  46.     }
  47. }bit;
  49. const int maxn = 2e5 + 100;
  50. VI x[maxn],y; // lsy x, unique y
  52. map<int,int> lsx,lsy,cntx;// id of discrete x,y , number of x
  54. int n;
  55. int main(int argc, char const *argv[])
  56. { 
  57.     ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
  58.     cin >> n;
  59.     bit.init(n);
  62.     int sum = 0;
  63.     rep(i,0,n)
  64.     { 
  65.         int xx,yy;
  66.         cin >> xx >> yy;
  67.         if(!lsy.count(yy))
  68.         { 
  69.             lsy[yy] = sum++;
  70.             y.pb(yy);
  71.         }
  72.         x[lsy[yy]].pb(xx);
  73.         cntx[xx]++;
  74.     }
  75.     sort(all(y));
  76.     // for(auto v : y)
  77.     // { 
  78.     // sort(all(x[lsy[v]]));
  79.     // }
  81.     int s = 0;
  82.     for(auto v:cntx)
  83.     { 
  84.         s++;
  85.         lsx[v.fi] = s;
  86.         bit.update(s,1);
  87.     }
  89.     ll ans = 0;
  90.     for(auto v : y)
  91.     { 
  92.         sort(all(x[lsy[v]]));        
  93.         int pre = 1; 
  94.         for(auto u : x[lsy[v]])
  95.         { 
  96.             ans += 1ll * bit.query(pre,lsx[u]) * bit.query(lsx[u],s);
  97.             //cout << pre << " "<< lsx[u] <<" " << bit.query(pre,lsx[u]) << "---" << endl;
  98.             //cout << s << " " << bit.query(lsx[u],s) << endl;
  99.             pre = lsx[u] + 1;
  100.             cntx[u]--;
  101.             if(cntx[u] == 0)
  102.             { 
  103.                 //cntx.erase(u);
  104.                 bit.update(lsx[u],-1);
  105.             }                                                    
  106.         }
  107.     }
  108.     cout << ans << endl;
  109.     return 0;
  110. }

发表评论

表情：
评论列表 （有 0 条评论，407人围观）

还没有评论，来说两句吧...

相关阅读

    相关 codeforces-round375-div2

    题目链接：[codeforces round 375 div2][] A题： 读一遍题目就知道是超级水的题目，，就是给你三个坐标，求三个坐标汇集到一个点所走的路程

    亦凉亦凉/ 0 赞/ 287 阅读