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;
  }
  
  

```