The 2021 CCPC Guilin Onsite 补题+总结

• A. Hero Named Magnus

  题意：签到输出2n-1；

  #include<bits/stdc++.h>
  using namespace std;
  typedef long long ll;
  #define f(a,b,c) for(ll a=b;a<c;a++)
  void solve(){
  	ll x;
  	cin>>x;
  	cout<<x*2-1;
  }
  int main(void){
  	ios::sync_with_stdio;
  	cin.tie(0);
  	cout.tie(0);
  	ll t=1;
  	cin>>t;
  	while(t--){
  		solve();
  		if(t)cout<<'\n';
  	}
  }

​

• I. PTSD

  题意：规律签到；

  代码：

  #include<bits/stdc++.h>
  using namespace std;
  typedef long long ll;
  #define f(a,b,c) for(ll a=b;a<c;a++)
  void solve(){
  	ll n;
  	string s;
  	cin>>n>>s;
  	ll ans=0;
  	int len=1;
  	for(int i=n-2;i>=0;--i){
  		len++;
  		if(s[i]=='0')continue;
  		if(len>=2){
  			ans+=i+1;
  			// cout<<"ans:"<<ans<<"\n";
  			len-=2;
  		}
   
  	}
  	cout<<ans;
   
  }
  int main(void){
  	ios::sync_with_stdio(false);
  	cin.tie(0);
  	cout.tie(0);
  	ll t=1;
  	cin>>t;
  	while(t--){
  		solve();
  		if(t)cout<<'\n';
  	}
  }

• G. Occupy the Cities

  题意：给出一串01字符串，其中每个1每次操作可以向左一位或向右一位将临近的0变为1，问最少多少次操作能将字符串变为全一。

  解题过程：一开始想的找规律，看到题意时我就有了一个想法：首先计算最外层两一间最大的两一位置差maxv，例如 001000100100 -> maxv=3，这时只要操作满足了这个最大差，那么该区间内的其他零也都能覆盖，处理完双一内圈后再处理外围零。但是最后发现要加不少特判遂作罢。然后y同学和w同学直接想到和题解一样的方法，但是找不到处理第一步的方法。赛后看了别人都用的二分答案才恍然大悟，记录一下我对此种解法的理解：直接对答案做二分，拿答案ANS去遍历字符串看是否符合题目要求，也就是每个0的最近左1或右1距离不超过ANS，此时就可以保证该零在该种操作数下可以被覆盖，如果该ANS完全符合，再次缩小ANS判断。

  代码：

  #include<bits/stdc++.h>
  using namespace std;
  typedef long long ll;
  #define u(a,b,c) for(int a=b;a<c;a++)
  #define d(a,b,c) for(int a=b-1;a>=c;a--)
  const int N=1e6+10;
  ll n;
  string s;
  vector<ll> lo(N),ro(N);//lo记录每个0左边1的位置，ro记录每个0右边1的位置
  bool ck(ll p){//判断操作数p是否符合
      vector<ll>f(n,0);//f记录1s'f
      u(i,0,n){
          if(s[i]=='1')continue;
          if(p>=min(i-lo[i],ro[i]-i)+1)continue;
          if(lo[i]>=0&&lo[i]<n&&!f[lo[i]]&&p>=i-lo[i]){
              f[lo[i]]=1;
              continue;
          }
          if(ro[i]>=0&&ro[i]<n&&!f[ro[i]]&&p>=ro[i]-i){
              f[ro[i]]=1;
              continue;
          }
          return 0;
      }
      return 1;
  }
  void solve(){
      cin>>n>>s;
      ll l=0,r=n-1;
      ll x=-1e9;
      u(i,0,n){
          lo[i]=x;
          if(s[i]=='1')x=i;
      }
      x=1e9;
      d(i,n,0){
          ro[i]=x;
          if(s[i]=='1')x=i;
      }
      while(l<r){
          ll mid=l+r>>1;
          if(ck(mid)){
              r=mid;
          }else{
              l=mid+1;
          }
      }
      cout<<l;
  }
  int main(void){
      ios::sync_with_stdio(false);
      cin.tie(0);
      cout.tie(0);
      int t=1;
      cin>>t;
      while(t--){
          solve();
          if(t)cout<<'\n';
      }
  }