Codeforces Round #526 (Div. 2) E. The Fair Nut and Strings

E. The Fair Nut and Strings

题目链接：https://codeforces.com/contest/1084/problem/E

题意：

输入n,k，k代表一共有长度为n的多少个字符串。然后给出一个最小字符串s，最大字符串t，满足对于所有的k个字符串有s<=S<=t。

最后求满足条件的k个字符串（自己构造）的不同前缀数量的和。

题解：

这题很巧妙，设dp(i)表示长度为i的前缀的数量和，一开始有dp(1)=0。

后来随着长度的增加，我们每次可以在最后加一个a或者b，所以转移方程为dp(i)=2*dp(i-1)。

但是由于有最大最小字符串的限制，当si=b时，dp(i)会多加一个；当ti=a时，dp(i)也会多加一个。减去即可。

可以用归纳法来证明，假设当前循环到第i层，前缀长度i-1满足限制条件。那么si=b时，dp(i-1)中，只有一个后面加上a时(这个长度为i-1的字符串等于字符串s的前i-1位)，会小于s；对于ti=a也同理。（考虑共同前缀）

最后输出求和min(dp(i),k)。（k个字符串任意长度的前缀最多也只有k个）

注意一下代码的细节。

代码如下：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 5e5+;

ll n,k;

char s[N],t[N];

ll dp[N];

int main(){

    cin>>n>>k;

    scanf("%s%s",s,t);

    dp[]=;

    ll ans = ;

    for(int i=;i<=n;i++){

        char sc = s[i-],tc = t[i-];

        dp[i]=2ll*dp[i-];

        if(sc=='b') dp[i]--;

        if(tc=='a') dp[i]--;

        if(dp[i]>=k){

            dp[i]=k;

            ans+=(n-i)*k;

            break ;

        }

    }

    for(int i=;i<=n;i++) if(dp[i]) ans+=dp[i];

    printf("%I64d",ans);

    return ;

}

还有一种就是把字符串看为二进制的，那么数量就为两个二进制相减。

直接给代码：

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 1e6 ;

char s[N],t[N];

ll n,k;

int main(){

    cin>>n>>k;

    scanf("%s %s",s,t);

    ll a=,b=;

    ll ans =;

    for(int i=;i<n;i++){

        ll now;

        a<<=;b<<=;

        if(s[i]=='b') a++;

        if(t[i]=='b') b++;

        now = b-a+;

        if(now>=k){

            ans+=(n-i)*k;

            break ;

        }

        ans+=now;

    }

    printf("%I64d",ans);

    return ;

}

巴特西

Codeforces Round #526 (Div. 2) E. The Fair Nut and Strings

最新文章

热门文章