牛客周赛 Round 72

怎么全是01串

A

枚举除了末尾的字符，判断下一个是否与它不同，不同则对答案的贡献++

B

找一个连续子串是好串，如果我们找到长度为len的子串，那么从中任意截取一段均为好串

长度为len的子串 1个
长度为len-1的子串 2个
.....
长度为2的子串 len-1个

用等差数列公式
一个长度为len的好串子串的个数为\(\sum_{i=1}^{len-1}=\frac{len*(len-1)}{2}\)

C

构造一个解的情况还是很容易的，但是一些情况需要特判

以下情况都不能构成

• \(k==0\) 此时有0有1则不可能构造
• \(a==b && k>min(a,b)*2-1\) 此时的a个0和b个1，形成的01串最多有min(a,b)*2-1对不相邻的01，因为，长度为a+b的串最多有a+b-1对01，而此时a==b
• \(a!=b && k>min(a,b)*2\) 假设此时b>a ,那么可以拿a个0和b个1构成上述的a*2-1对字符串，而此时1有多余的，还可以加入到字串末尾多形成一对01

可以构造的情况就简单了
先生成足够01，然后将多余的0，1放在两边

#include<bits/stdc++.h>
using namespace std;
int t;
int a,b,k;

int main(){
    cin>>t;
    while(t--){
        cin>>a>>b>>k;
        if(k==0){
            if(a && b){
                cout<<-1<<endl;
            }
            else {
                while(a){--a;cout<<"0";}
                while(b){--b,cout<<"1";}
                cout<<endl;
            }
        }
        else {
                if(a==b && k>min(a,b)*2-1) cout<<-1<<endl;
                else if(a!=b && k>min(a,b)*2){
                    cout<<"-1"<<endl;
                }
                else {
                    if(k&1){
                        int mid=k+1;
                        for(int i=1;i<=a-mid/2;++i) cout<<0;
                        for(int i=1;i<=mid/2;++i) cout<<"01";
                        for(int i=1;i<=b-mid/2;++i) cout<<1;
                    }
                    else {
                        int mid=k;
                        if(a>=b){
                            for(int i=1;i<=a-mid/2-1;++i) cout<<0;
                            for(int i=1;i<=mid/2;++i) cout<<"01";//只有k-1对01
                            for(int i=1;i<=b-mid/2;++i) cout<<1;
                            cout<<0;  //补上一个
                        }
                        else{
                            cout<<1;//前面补上
                            for(int i=1;i<=a-mid/2;++i) cout<<0;
                            for(int i=1;i<=mid/2;++i) cout<<"01";//只有k-1对
                            for(int i=1;i<=b-mid/2-1;++i) cout<<1;

                        }
                    }cout<<endl;
                }
                
        }
        
    }return 0;
}

D

一眼DP，但是状态转移时顺序错误了
应该从后往前转移

由题可知，只能转移最近相同字符和不同字符，

如果按照顺序来转移，举例00110，转移到第二个1时，最近的0是第一个1前一个，但因为0只能转移到最近的1，所以不能从这个0转移
这里的错误在于，忽略了01之间存在其他的有效转移，导致转移出错

如果按照逆序来转移，同样的例子，转移第一个1前面的0时，只能第一个1转移，末尾的0转移，这样逆转过来的顺序便不会出错
再深究一点，因为每一个位置，只有唯一的向后转移的顺序，所以反过来找时唯一的

#include<bits/stdc++.h>

using namespace std;

int n;
const int maxn=1e5+10;
int x,y;
int l1=-1,l0=-1;
string s;
long long  f[maxn];
int main(){
    cin>>n>>x>>y;
    cin>>s;
    for(int i=0;i<=n;++i) f[i]=1e15+10;
    f[n-1]=0;
    if(s[n-1]=='0') l0=0;
    else l1=0;
    for(int i=n-1;i>=0;--i){
        if(s[i]=='0'){
            if(l0!=-1)f[i]=min(f[i],f[l0]+x);
            if(l1!=-1)f[i]=min(f[i],f[l1]+y) ;   
            l0=i;
        }
        else{
            if(l0!=-1)f[i]=min(f[i],f[l0]+y);
            if(l1!=-1)f[i]=min(f[i],f[l1]+x);    
            l1=i;
        }
     
    }cout<<f[0]<<endl;
    return 0;
}

E

首先，不要误解题目，01串代表的正整数，不是二进制数
根据同余的性质,同乘性和同加性，一个数从高位乘到低位，余数不变

定义
\(