Educational Codeforces Round 72 (Rated for Div. 2)

墨蓝 2023-06-18 06:00 3阅读 0赞

###  ###

*  A. Creating a Character（思维）
 *  B. Zmei Gorynich（贪心）
 *  C. The Number Of Good Substrings

# A. Creating a Character（思维） #

> **原题链接：**[https://codeforces.com/contest/1217/problem/A][https_codeforces.com_contest_1217_problem_A]

*  **题意：** 给定 str，int，exp，将 exp 分配给 str 和 int 保证 m > n，问有多少种分法。
 *  **思路：** 只要求出最少要加几点str使str>int就可以求出答案了。

**Code1：** 比赛时的思路比较直接，把所有的情况都列了出来。

#include <iostream>
    using namespace std;
    int main(){ 
        int t;  cin>>t;
        while(t--){ 
            int s,i,e;  cin>>s>>i>>e;
            if(s<i){ 
                int x=i-s;
                if(x>=e)    cout<<0<<endl;
                else{ 
                    e-=x;
                    if(e%2==0)  cout<<e/2<<endl;
                    else    cout<<e/2+1<<endl;
                }
            }else if(s==i){ 
                if(e%2==0)  cout<<e/2<<endl;
                else    cout<<e/2+1<<endl;
            }else{ 
                int x=s-i;
                if(x>e) cout<<e+1<<endl;
                else if(x==e)   cout<<e<<endl;
                else    cout<<e-(e-x)/2<<endl;
            }
        }
    }

**Code2：** 二分做法

#include <iostream>
    using namespace std;
    int main(){ 
        int t;  cin>>t;
        while(t--){ 
            int a,b,c;  cin>>a>>b>>c;
            int l=0,r=c;
            while(l<=r){ 
                int mid = (l+r)/2;
                if(a+mid>b+c-mid)   r=mid-1;
                else    l=mid+1;
            }
            cout<<c-l+1<<endl;
        }
        return 0;
    }

# B. Zmei Gorynich（贪心） #

> **原题链接：**[https://codeforces.com/contest/1217/problem/B][https_codeforces.com_contest_1217_problem_B]

*  **题意：** 有一个怪物初始有x个头，你有n种攻击方式，每种攻击方式可以砍掉怪物 min(d,x) 个头。如果怪物头的数目依然大于0，那么他就会在你攻击之后重新生成 h 个头。你可以任意次数，任何顺序地选择每一种攻击，求最小的攻击次数能使怪物死亡。
 *  **思路：** 先找出最大的攻击能力 maxd 和最大的攻击能力与再生能力间隔 maxdh。如果最大攻击能力 maxd 大于怪物初始头数 x，则一次就能使怪物死亡。maxdh 初始化为0，如果在寻找后 maxdh 仍为0，就说明每种攻击都比再生能力差，就永远砍不死。因为最后一次攻击砍死了怪物，所以最后一次没有再生能力，也就是最后一次要用 maxd 来攻击，剩下的全部用 maxdh 来攻击。

**Code（C++）：**

#include <iostream>
    #include <algorithm>
    using namespace std;
    int main(){ 
        int t;  cin>>t;
        while(t--){ 
            int n,x;    cin>>n>>x;
            int maxd=0,maxdh=0;
            int d,h;
            for(int i=1;i<=n;++i){ 
                cin>>d>>h;
                maxd=max(maxd,d);   //找出攻击力最大的
                maxdh=max(maxdh,d-h);   //找出攻击力与再生力间隔最大的
            }
            if(maxd>=x){     //砍一次能砍死的情况
                cout<<1<<endl;
                continue;
            }
            if(!maxdh){  //如果每种攻击都比再生能力差，就永远砍不死
                cout<<-1<<endl;
                continue;
            }
            /* int ans=0; x-=maxd, ans++; //最后一次不会再生，所以最后一次用攻击力最大的攻击 if(x%maxdh) cout<<ans+x/maxdh<<endl; //剩下的都用间隔最大的攻击 else cout<<ans+x/maxdh<<endl; */
            cout<<(x-maxd+maxdh-1)/maxdh+1<<endl;  //以上代码可以简化成一行
        }
        return 0;
    }

# C. The Number Of Good Substrings #

> **原题链接：**[https://codeforces.com/contest/1217/problem/C][https_codeforces.com_contest_1217_problem_C]

*  **题意：** 给一个二进制的字符串，问给定的二进制字符串中，有多少个子串，其所表示的十进制数，正好等于该子串的位数（可以包含前导零）。
 *  **思路：** 2e5 的二进制位最多才 18 位，所以可以直接暴力枚举。枚举每一段连续 0，num\_0 为连续0的个数，0 后面的数值为 res。如果 res >= 二进制下区间长度 len 并且 res <= len+num\_0，则会产生答案，因为前导0可以增加长度，否则直接break，因为区间是以 1 个单位增加的，但二进制的值至少以二倍增加的。

**Code（C++）：**

#include <iostream>
    #define ll long long
    using namespace std;
    int main(){ 
        int t;  cin>>t;
        while(t--){ 
            string str; cin>>str;
            int num_0=0;    //连续0的个数
            ll ans=0ll;
            for(int i=0;i<str.length();i++){ 
                if(str[i]=='0') num_0++;
                else{ 
                    int res=0;  //出现1后的值
                    for(int j=i;j<str.length()&&res<=(num_0+j-i+1);j++){ 
                        res=res*2+str[j]-'0';   //二进制转换为十进制
                        if(res>=(j-i+1)&&res<=(num_0+j-i+1))    ans++;
                        else    break;
                    }
                    num_0=0;
                }
            }
            cout<<ans<<endl;
        }
        return 0;
    }

[https_codeforces.com_contest_1217_problem_A]: https://codeforces.com/contest/1217/problem/A
[https_codeforces.com_contest_1217_problem_B]: https://codeforces.com/contest/1217/problem/B
[https_codeforces.com_contest_1217_problem_C]: https://codeforces.com/contest/1217/problem/C