思维题1

发表于 更新于 分类于 ， 阅读次数： Waline： 本文字数： 345 阅读时长 ≈ 1 分钟

题意

题意：给一个数字字符串，要求按相对序构建不带前导零的偶数，求这些数字的多重集的大小

题解

题解：维护两个值，cnt，ans，cnt表示当前能构造出的不带前导零的数字的多重集size，ans表示偶数多重集size。处理前导零的思维是，cnt所代表的多重集中不含0这个数字，也就保证了cnt在计算过程中的不含前导零，具象到代码中则是在s[i]=='0'时，将cnt-1，而ans保持相同计算。cnt->ans，cnt在每一位上的计算非常简单不再赘述，即ans=(ans+cnt+1)%MOD,cnt=(cnt*2+1)%MOD。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void slove(){
    cin>>n;
    string s;
    cin>>s;
    int cnt = 0,ans = 0;

    for(int i=0;i<n;i++){
        if(s[i]=='0'){
            ans=(ans+cnt+1)%MOD;
            cnt=(cnt*2)%MOD;
        }else if(s[i]&1){
            cnt=(cnt*2+1)%MOD;
        }else{
            ans=(ans+cnt+1)%MOD;
            cnt=(cnt*2+1)%MOD;
        }
    }
    cout<<ans<<endl;
}

这题并不难，但我陷入了错误的贡献法思想，如果你想看，如下。

对于每一个偶数计算它的贡献值为\(2^{i-1}\)，对于每一个0计算它的贡献为\(-2^{n-i}\)，这样的错误在于，0的贡献并不准确，同时计算了奇数的前导零数量。虽然说应该可以修正这一点，但这样就繁琐了。。