洛谷 P2536 分析（别看）

科技起源‍‍‍‍‍‍‍‍‍‍‍‍

2026-07-21 11:32:34

发布于：北京

13阅读

0回复

0点赞

原题链接

1 题目

1.1 题目所需求出内容

对于本题，最终要求：一个具体值

1.2 题目背景、允许、禁止与限制

背景：有一个只含有a c t g ? * 的病毒模板序列和 $n$ 个DNA片段
允许：

一个 ? 可以代表任意一个 a c t g
一个 * 可以代表任意 $s$ 个 a c t g $注：s \in [0,\infty)$

求有多少个DNA片段不和原病毒模板序列相等（这里的相等并不一定是完全相等，可以是通过 ? 和 *的代替变化而成相等）

禁止：
限制：

1.3 题目数据范围与猜测

$1 \le n \le 500 \longrightarrow O(n^3)$

1.4 一句话概括题意

有一个病毒模板序列和若干个DNA片段，求有多少个DNA片段不和原病毒模板序列相等

2 题目破题推导

2.1 正向思维转逆向思维

问有多少个DNA片段不和原病毒模板序列相等，那我们可以求有多少个DNA片段和原病毒模板序列相等，再用总数减去这个值

2.2 以终为始（化繁为简）

2.2.1 没有 `?` 和 `*` 的情况

可以直接用病毒序列检查每个DNA片段，看是否相等

2.2.2 有 `?` 没有 `*` 的情况

如果不是 ?
那还是和 2.2.1 一样
如果是 ?
因为 ? 必须代表 $1$ 个字母，因此相当于检查每个DNA片段当前这一项能往 $[a,c,t,g]$ 哪块走

2.2.3 有 `?` 也有 `*` 的情况

如果是字母
和 2.2.1 一样
如果是 ?
和 2.2.2 一样
如果是 *
分三种可能：
一种是跳过 *，匹配下一个字符
一种是把 * 看成一个 ?
一种是把 * 看成一个 ? 加一个 *

3 模型匹配

格式为："关键词：...... $\longrightarrow$ $\huge{......}$ "

关键词：字符串匹配算法 $\longrightarrow$ $\huge{字典树}$
关键词：匹配过程往下深入 $\longrightarrow$ $\huge{dfs}$
但是，因为 * 的递归调用太多，因此需要剪枝
记录一个 size 数组记录 $size_i$ 代表以 $i$ 为根节点的字典树子树含有多少没匹配的点，不断更新，直到子树中所有都匹配完毕，则直接停止

4 最终代码（禁止抄袭，仅用于参考）

#include <bits/stdc++.h>
using namespace std;

string bd;
int bd_size;
int n;
const int N = 500 * 500 + 10, M = 5;
int trie[N][M];
int size[N];
int ed[N];
int idx;
int ans;

int get(char c){
    if (c == 'A'){
        return 0;
    }
    if (c == 'C'){
        return 1;
    }
    if (c == 'T'){
        return 2;
    }
    if (c == 'G'){
        return 3;
    }
}
void insert(string s){
    int now = 0;
    int len = s.size();
    for (int i = 0;i < len;i++){
        int ch = get(s[i]);
        size[now]++;
        if (trie[now][ch] == 0){
            trie[now][ch] = ++idx;
        }
        now = trie[now][ch];
    }
    size[now]++;
    ed[now] = 1;
}
void dfs(int pp, int now){
    if (size[now] == 0){
        return ;
    }
    if (pp == bd_size){
        ans += ed[now];    
        size[now] -= ed[now];
        ed[now] = 0;
        return ;
    }
    if (bd[pp] == '?'){
        for (int i = 0;i < 4;i++){
            if (trie[now][i]){
                dfs(pp + 1, trie[now][i]);
            }
        }
    } else if (bd[pp] == '*'){
        dfs(pp + 1, now);
        for (int i = 0;i < 4;i++){
            if (trie[now][i]){
                dfs(pp + 1, trie[now][i]);
                dfs(pp, trie[now][i]);
            }
        }
    } else {
        int ch = get(bd[pp]);
        if (trie[now][ch]){
            dfs(pp + 1, trie[now][ch]);
        }
    }
    size[now] = 0;
    for (int i = 0;i < 4;i++){
        if (trie[now][i]){
            size[now] += size[trie[now][i]];
        }
    }
}

int main(){

    cin >> bd;
    cin >> n;
    bd_size = bd.size();
    for (int i = 1;i <= n;i++){
        string dna;
        cin >> dna;
        insert(dna);
    }
    dfs(0, 0);
    cout << n - ans;
    
    return 0;
}