牛客IOI周赛24-普及组 部分题题解

由于冲突没打上比赛，赛后只做了前两题。

• A 二进制？十进制！

题目大意：
给两个十进制数，把它们转换成二进制以后再以十进制的运算方法相加。
思路：
水题。
直接转换十进制转二进制存到数组中，按位相加即可。没有进位，直接输出。

代码：

#include<bits/stdc++.h>
using namespace std;
int A[111],B[111];
int main()
{
    int a,b;
    cin>>a>>b;
    int t1,t2;
    t1=t2=0;
    while(a){
        A[++t1]=a%2;
        a=a/2;
    }
    while(b){
        B[++t2]=b%2;
        b=b/2;
    }
    for(int i=1;i<=max(t1,t2);i++)A[i]+=B[i];
    for(int i=max(t1,t2);i>=1;i--)cout<<A[i];
    return 0;
}

• B 数字串

题目大意 ：
给一个数字串s（每个字符都由0-9组成），给定两个正整数L和R，现在你可以从s中任意取一段连续的子串s[l,r]，子串可以组成数字k。问有多少种取子串的方式，满足L<=k<=R。注意如果取出的子串存在前导0，以取的左右端点为一种独立的方式。即取出来的最终数字即使有相同的，如果左右端点不同依然认为不是两种不同的方案。
字符串长度len<=5*10^5，1<=L,R<=10^25

思路：
数据范围还是比较大的，初看的时候以为是数位dp啥的。
首先本题要求满足[L,R]中的数字个数，那么可以转换成求[1，R]-[1,L-1]。
那么我们只要考虑取出来的数字是否小于等于某个数就可以了。
首先我们考虑[1,R]，显然地，我们知道若取出来的子串长度x<len，那么k<R一定成立。
我们其实只需要枚举长度x=len的情况就可以了，那么我们可以枚举起点然后按位比较。
但是这里我们要注意的是存在前导0的情况，例如s=10015478，R=100
我们枚举x=3的子串，我们实际上只能取到"100","001,"015"三种情况。
实际上我们还可以取一个"0015"的情况，但是这个长度为4，我们是不会去枚举的。
因此，我们需要在枚举长度为3的时候，就把前导零的结果也计算进去了。
我们可以想到，假设枚举的一个子串的k<=R成立，那么我们往前看一下这个子串前面有多少个前导0就好了。由于起点和终点固定，那么我们的计算方案是不会重复的。
这个前导0显然可以预处理。
复杂度为O(510^525)
还有一个点是，计算[1,L-1]，由于L,R范围较大，我们必须以字符串形式输入，因此L-1的时候需要考虑是否会有前导0的存在，要把它去掉。例如L=100，L-1以后变成099，因此我们要去第一个0.
代码：

#include<bits/stdc++.h>
using namespace std;
string l,r;
string s;
int slen,ling[500050];
long long solve(string x){
    int len=x.size();
    long long ans=0;
    for(int i=1;i<len;i++)ans+=(slen-i+1);
    for(int i=0;i+len-1<slen;i++){
        bool flag=true;
        for(int j=0;j<len;j++){
            if(s[i+j]==x[j])continue;
            else if(s[i+j]<x[j]){
                flag=true;
                break;
            }
            else {flag=false;break;}
        }

        if(flag){
            int t=ling[i];
            if(t&&s[i]=='0')t--;
            ans+=t;
            ans++;
        }
    }
    return ans;
}

int main()
{
    cin>>l>>r;
    cin>>s;
    slen=s.size();
    if(s[0]=='0')ling[0]=1;
    for(int i=1;i<slen;i++){
        if(s[i]=='0'&&s[i-1]=='0')ling[i]=ling[i-1]+1;
        if(s[i]!='0'&&s[i-1]=='0')ling[i]=ling[i-1];
        if(s[i]=='0'&&s[i-1]!='0')ling[i]=1;
    }//预处理前导0
    l[l.size()-1]--; //要计算[1,L-1]，因此先对L-1处理
    int now=l.size()-1;
    while(l[now]<'0'){
        l[now]='9';
        l[--now]--;
    }
    if(l[0]=='0'&&l.size()>1){
        l.erase(l.begin());
    }  //L-1后可能存在前导0，需要去掉
    cout<<solve(r)-solve(l);
    return 0;
}