Education Codeforces Round 72

图片说明

题意：
给出一个龙的初始长度，有n种方案，每种方案可以先砍掉a，然后再让它恢复b，当一刀砍下去长度小于等于0的时候就算成功，问你最少需要砍几次
题解：
贪心，找到最大的a和最大的a-b，每次只用方案a-b最大去砍，贪心的比较每次要砍的时候的的长度和最大的a，如果小于等于，就可以了，注意能不能完全取模。

代码：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll inf = 1e17;
int main()
{
  int t;
  scanf("%d",&t);
  while(t--)
  {
      ll n,x,y,k,cnt = 0,maxx = -inf,maxn = -inf;
      scanf("%lld%lld",&n,&k);
      for(int i=1;i<=n;i++){
          scanf("%lld%lld",&x,&y);
          maxx = max(maxx,x-y);
          maxn = max(maxn,x);
      }
      if(maxn >= k){
          cout<<"1"<<endl;
          continue ;
      }
      if(maxx <= 0){
          cout<<"-1"<<endl;
          continue ;
      }

      k -= maxn;
      ll ans = k/maxx;
      if(k%maxx){
          cout<<ans+2<<endl;
      }else{
          cout<<ans+1<<endl;
      }
  }
  return 0;
}

图片说明

题意：
给出一个字符串定义f(s) = s的二进制，问你一个给出的字符串一共有多少个满足f(s) = strlen(s)
题解:
给出的数据范围要求<=2e5 所以直接枚举向右20范围内的字符

代码：

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxx = 2e5+10;
char s[maxx];
int a[maxx];
int main()
{
  int t;
  scanf("%d",&t);
  while(t--)
  {
      scanf("%s",s+1);
      int n = strlen(s+1);
      for(int i=1;i<=n;i++){
          a[i] = s[i]-'0';
      }
      ll ans = 0,l,last = 0;
      for(int i=1;i<=n;i++){
          if(a[i] == 1)
          {
              int x = 0;
              for(int j=i; j<=n && j <= i+30;j++){
                  x = (x<<1) + a[j];
                  l = j-x+1;
                  if(l <= last)
                      break;
                  ans++;
              }
              last = i;
          }
      }
      cout<<ans<<endl;
  }

  return 0;
}

```