Codeforces Round 973 (Div.2) A-E题解

比赛传送门

A. Zhan's Blender 数学

显然答案为 \(\lceil \frac{n}{min(x,y)} \rceil\)。

#include<bits/stdc++.h>

using namespace std;

#define ff first
#define ss second
#define pb push_back
#define all(u) u.begin(), u.end()
#define endl '\n'
#define debug(x) cout<<#x<<":"<<x<<endl;

typedef pair<int, int> PII;
typedef long long LL;
const int inf = 0x3f3f3f3f;
const int N = 1e5 + 10, M = 105;
const int mod = 1e9 + 7;
const int cases = 1;

void Showball(){
   int n,x,y;
   cin>>n>>x>>y;
   int t=min(x,y);
   cout<<(n+t-1)/t<<endl;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int T=1;
    if(cases) cin>>T;
    while(T--)
    Showball();
    return 0;
}

B. Battle for Survive 贪心

最后的赢家一定是最后一个格斗士，因此我们只需要让倒数第二名的等级越低越好，因此只需要让其余格斗士和倒数第二个格斗士都战斗一次，并且被淘汰即可。所以答案为：

\(a[n-1]-(a[n-2]-(sum-a[n-2]-a[n-1]))\)。可自行化简。

void Showball(){
   int n;
   cin>>n;
   vector<int> a(n);
   LL sum=0;
   for(int i=0;i<n;i++){
      cin>>a[i];
      sum+=a[i];
   }
   cout<<a[n-1]-(a[n-2]-(sum-a[n-2]-a[n-1]))<<endl;
}

C. Password Cracking 交互题

每次往我们目前猜的字符串后面接一个字符“0“或”1“ ,询问是否是原串的子串，直到两者都不是子串时，说明我们已经找到了原字符串的一个后缀串。接着我们只需要往前添加字符即可，如果不是”0“ 就直接添加”0“，这样查询次数不超过 \(2\times n\) 次。

void Showball(){
   int n;
   cin>>n;
   auto ask=[&](string s){
      cout<<"? "<<s<<endl;
      int ret;
      cin>>ret;
      return ret;
   };
 
   auto print=[&](string s){
      cout<<"! "<<s<<endl;
   };
 
   string t="";
   while((int)t.size()<n){
      if(ask(t+"0")){
         t+="0";
      }else if(ask(t+"1")){
         t+="1";
      }else break;
   }
 
   while((int)t.size()<n){
      if(ask("0"+t)){
         t="0"+t;
      }else t="1"+t;
   }
   
   print(t);
}

D. Minimize the Difference 二分

操作相当于我们可以将前面的数分给后面，操作后的数组一定是单调不减的。就极差最小值。因此我们可以二分最大值最小和最小值最大。至于 \(check\) 函数，以查找最小值为例，遇到比最小值大的，就可以留着分给后续的数。对于小于最小值的，如果可以补充就补充，否则就直接 \(return\) \(false\)。

void Showball(){
   int n;
   cin>>n;
   vector<LL> a(n);
   for(int i=0;i<n;i++) cin>>a[i];
 
   auto check=[&](LL x){
      LL cur=0;
      for(int i=0;i<n;i++){
         if(a[i]>x) cur+=a[i]-x;
         else{
            if(x-a[i]>cur) return false;
            cur-=x-a[i];
         }
      }
      return true;
   };
 
   auto check2=[&](LL x){
      LL cur=0;
      for(int i=0;i<n;i++){
         if(a[i]>x) cur+=a[i]-x;
         if(a[i]<x) cur-=x-a[i],cur=max(cur,0LL);
      }
      return cur<=0;
   };
 
   LL lo=0,hi=1e12,maxn=0,minn=0;
   while(lo<hi){
      LL mid=(lo+hi+1)>>1;
      if(check(mid)) lo=mid;
      else hi=mid-1;
   }
   minn=lo;
   lo=0,hi=1e12;
   while(lo<hi){
      LL mid=lo+hi>>1;
      if(check2(mid)) hi=mid;
      else lo=mid+1;
   }
   maxn=lo;
   cout<<maxn-minn<<endl;
}

E. Prefix GCD 思维+枚举+贪心

有一个性质：前缀\(gcd\) 最多 \(log\) 次就会变成 \(1\)。

因此，我们可以贪心的选择最小的前缀 \(gcd\)，如果 \(gcd==1\) 时，后面的顺序就不重要了。直接算贡献即可。

首先可以把所有数除去 \(gcd\) ，最后结果再乘回去即可。

void Showball(){
   int n;
   cin>>n;
   vector<int> a(n);
   int g=0;
   for(int i=0;i<n;i++){
      cin>>a[i];
      g=__gcd(g,a[i]);
   }
   for(int i=0;i<n;i++) a[i]/=g;
 
   LL ans=0;
   int cur=0;
   for(int i=0;i<n;i++){
      int minn=inf;
      for(int j=0;j<n;j++) minn=min(minn,__gcd(cur,a[j]));
      cur=minn;
      ans+=cur;
      if(cur==1){
         ans+=n-i-1;
         break;
      }
   }
   cout<<ans*g<<endl;
}