当前位置：首页 > news >正文

WOJ 7 智商

news 来源：原创 2024/5/2 13:08:10

感觉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 + 5;
const int P = 1984;

int testCase, n, m, suma[N], sumb[N], p26[N << 1];
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 0;
            if(a[i] < b[i]) 
                return p26[suma[i + 1] + sumb[i + 1]];
        }
        if(a[i] == '?' && b[i] == '?') 
            return (325 * p26[suma[i + 1] + sumb[i + 1]]% P + 26 * solve(i + 1) % P) % P;
        if(a[i] == '?' && b[i] != '?') {
            if(b[i] != 0)
                return ((b[i] - 'a') * p26[suma[i + 1] + sumb[i + 1]] % P + solve(i + 1)) % P;
            else return 0;
        } 
            
        if(a[i] != '?' && b[i] == '?') {
            if(a[i] != 0)
                return (('z' - a[i]) * p26[suma[i + 1] + sumb[i + 1]] % P + solve(i + 1)) % P;
            else return p26[sumb[i]];
        }    
    }
    return 0;
}

int main() {
//    freopen("Sample.txt", "r", stdin);
    
    for(int i = p26[0] = 1; i <= 200000; i++)
        p26[i] = p26[i - 1] * 26 % P;
    
    for(scanf("%d", &testCase); testCase--; ) {
        scanf("%d%d", &n, &m);
        scanf("%s%s", a + 1, b + 1);
        
        memset(suma, 0, sizeof(suma));
        memset(sumb, 0, sizeof(sumb));
        for(int i = n; i >= 1; i--) 
            suma[i] = suma[i + 1] + (a[i] == '?');
        for(int i = m; i >= 1; i--)
            sumb[i] = sumb[i + 1] + (b[i] == '?');
        
        printf("%d\n", solve(1));
    }
    
    return 0;
}