Educational Codeforces Round 170 (Rated for Div. 2)

写博客还是颇能倒逼自己学习的，终于让自己的训练步入正轨了，之后要越来越频繁的补题才可以。不过最近考试多起来了，要开始突击了。哎，上大学就是屁事多。

A.Two Screens

签到题，有两种操作，一种操作是从头复制一个字符串，一种操作是在指定的字符串后面加字符串。不难发现最少的操作时间是求出最长公共前缀数量 – 1就好

void solve(){
  std::string s1,s2;
  cin >> s1 >> s2;
  int len = std::min(s1.size(),s2.size());
  int cnt = 0;
  for(int i = 0;i < len;i++){
      if(s1[i] == s2[i])cnt++;
      else break;
  }
  if(cnt) cnt--; 
  cout << s1.size() + s2.size() - cnt << '\n';
}

B.Binomial Coefficients, Kind Of

模拟发现答案为 $2^k$ ,直接输出

void solve(){
  int n;
  cin >> n;
  for(int i = 1,x;i <= n;i++){
      cin >> x;
  }
  for(int i = 1,x;i <= n;i++){
    cin >> x;
    cout << qpow(2,x) << ' ';
  }
}

C.New Game

题意很明显，就是有n个卡牌，同一个数值的卡牌我可以任意选取，不同数值的卡牌我最多能选取k个，如果我第一回合拿的数量大小是x，则下一回合能拿的就是x + 1。考虑双指针做法。

每一个卡牌的数值都找到他能找到的最右端点，找完这个数值就让l向右移动找下一个数值，注意，一定要记得如果l比r大要把r置成l。

void solve(){
  int n,k;
  cin >> n >> k;
  for(int i = 1;i <= n;i++){
      cin >> a[i];
  }
  std::sort(a + 1,a + n + 1);
  int ans = 0,l = 1,r = 1;
  while(l <= n){
      r = std::max(l,r);
      while(r < n && a[r + 1] - a[r] <= 1 && a[r + 1] - a[l] < k) r++;
      ans = std::max(ans,r - l + 1);
      while(l < n && a[l + 1] == a[l]) l++;
      l++;
  }
  cout << ans << '\n';
}

D. Attribute Checks

告诉你你总共有m个属性点，有n次的属性检查，分别检查的是力量和和智力，问最多通过检查的次数。

双指针做法，将非0的部分用前缀和表示

dp的状态用 $f[i]$ 表示有i个点给力量n – i个点给智力，思路就是找中间出现的0，然后在力量和智力中间进行状态的转移无非是每一次出现非0的元素{S,T}->{S,T+1} 或者 {S,T}->{S+1,T}，取max就好

void solve(){
  int n,m;
  cin >> n >> m;
  for(int i = 0;i < n;i++){
      cin >> a[i];
  }
  int x = 0,l = 0;
  while(l < n && a[l] != 0) l++;
  while(l < n){
      int r = l + 1;
      while(r < n && a[r] != 0){ //找下一个检查点
          if(a[r] > 0) t[a[r]]++; //智力的前缀和
          else s[-a[r]]++;
          r++;
      }
       for(int i = 1;i <= m;i++){
          s[i] += s[i-1];
          t[i] += t[i-1];
      } 
      for(int i = 0;i <= x + 1;i++){
          g[i] = f[i];
          g[i] = std::max(g[i],f[i - 1]); //每次加点有两种情况，一种是给智力加点，一种是给力量加点
      }
      x++;
      //加上新增的0
      for(int i = 0;i <= x;i++){
          f[i] = g[i] + s[i] + t[x-i];
      }
      for(int i = 0;i <= m;i++) s[i] = t[i] = 0;
      l = r ;
  }
  int ans = 0;
  for(int i = 1;i <= m;i++){
      ans = std::max(ans,f[i]);
  }
  cout << ans << '\n';
}