WOJ 7 智商

感觉Dasin去年的毒瘤题质量都挺好的，果然还是我太菜了。

以下假设划横线部分都相等，字符$c$代表一个小写字母。

分类讨论：

$#1$ 先考虑$n == m$的情况：

　　$#1.1 :$

　　　　　　A: ?

　　　　　　B: ?

　　　　首先考虑两个问号的填法，A串中填的字符比B串中填的字符字典序小的方案有$(25 + 24 + 23 + ... + 1) = (1 + 25) * 25 / 2 = 325$种，如果这样子填，那么后面的问号可以随意填，后面问号随意填的方案数（假设后面A串+B串的问号数量有$k$个）有$26^{k}$，还有26中填法使A和B到这个问号为止字典序都相同的方案，那么我们考虑乘上后面合法的方案数。

　　$#1.2 :$

　　　　　　A: ?

　　　　　　B: c

　　　　有$c - 'a'$种方案使A串的字典序一定小于B串，有一种填法能使A串和B串到这个位置为止字典序相同，我们再次考虑乘上后面合法的方案数。

　　$#1.3 :$

　　　　　　A: c

　　　　　　B: ?

　　　　有$'z' - c$种方案能使A串的字典序一定小于B串，有一种填法能使A串和B串到这个位置为止字典序相同，操作同$#1.2$。

　　$#1.4 :$

　　　　　　A: c1

　　　　　　B: c2

　　　　单纯考虑到c1和c2不同的情况，如果$c1 < c2$ 那么后面填法随意，如果$c1 > c2$那么后面不用填了，因为一定不合法。

$#2$ 考虑一下$m != n$ 的情况

　　$#2.1$ $ n < m$ 其实不用填了，因为我们知道到长度为n的时候A的字典序是严格等于B的，那么后面不管怎么填，A的字典序都不会小于B。

　　$#2.2$ $n > m$ 只可能在B的比A长的部分中出现问号，那么随便填就好了。

我们假设区间$[l, max(n, m)]$的答案为$solve(l)$，去分治就好了，特别的，当当前处理的串都没有字符$?$时，返回一个0

如果直接暴力算后面还有多少个问号的话，时间会是$O(n ^ {2})$级别的，不能承受，我们可以处理串A和串B的问号出现次数后缀和，然后再预处理26的幂，就可以$O(1)$计算。

我就是因为只预处理到$1e5$然后WA了三次

考虑到每一个位置都在一层递归中访问的一次，所以时间复杂度是$O(n)级别的$，但是……跑的慢a

Code：

#include <cstdio>

#include <cstring>

using namespace std;

const int N = 1e5 + ;

const int P = ;

int testCase, n, m, suma[N], sumb[N], p26[N << ];

char a[N], b[N];

inline int max(int x, int y) {

    return x > y ? x : y;

}

int solve(int l) {

    for(int i = l; i <= max(n, m);i++) {

        if(a[i] != '?' && b[i] != '?') {

//            if(b[i] == 0) return 0;

//            if(a[i] == 0) return p26[sumb[i]];

            if(a[i] > b[i]) return ;

            if(a[i] < b[i])

                return p26[suma[i + ] + sumb[i + ]];

        }

        if(a[i] == '?' && b[i] == '?')

            return ( * p26[suma[i + ] + sumb[i + ]]% P +  * solve(i + ) % P) % P;

        if(a[i] == '?' && b[i] != '?') {

            if(b[i] != )

                return ((b[i] - 'a') * p26[suma[i + ] + sumb[i + ]] % P + solve(i + )) % P;

            else return ;

        } 

        if(a[i] != '?' && b[i] == '?') {

            if(a[i] != )

                return (('z' - a[i]) * p26[suma[i + ] + sumb[i + ]] % P + solve(i + )) % P;

            else return p26[sumb[i]];

        }

    }

    return ;

}

int main() {

//    freopen("Sample.txt", "r", stdin);

    for(int i = p26[] = ; i <= ; i++)

        p26[i] = p26[i - ] *  % P;

    for(scanf("%d", &testCase); testCase--; ) {

        scanf("%d%d", &n, &m);

        scanf("%s%s", a + , b + );

        memset(suma, , sizeof(suma));

        memset(sumb, , sizeof(sumb));

        for(int i = n; i >= ; i--)

            suma[i] = suma[i + ] + (a[i] == '?');

        for(int i = m; i >= ; i--)

            sumb[i] = sumb[i + ] + (b[i] == '?');

        printf("%d\n", solve());

    }

    return ;

}

我应该是只会写这种级别的数数了

巴特西

WOJ 7 智商

最新文章

热门文章