洛谷 P2580 分析（别看）

科技起源的小号1

2026-10-01 16:54:40

发布于：天津

3阅读

0回复

0点赞

原题链接

1 题目

1.1 题目所需求出内容

对于本题，最终要求：若干个字符串

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

背景：
班级中有 $n$ 个人，他们的名字互不相同

允许：
有一个教练会点 $m$ 次名，对于：当前这一次点的名字出现过、当前这一次点的名字没出现过、当前这一次点的名字不是班级中含有的名字，需要分别输出他们对应的答案

1.3 题目数据范围与猜测

$n \le 10^4, m\le 10^5,|s| \le 50\longrightarrow O(26 \times n|s|)$

1.4 一句话概括题意

给定一个含有 $n$ 个互不相同的字符串的序列 $S$
接着给出 $m$ 个字符串 $s_i$
对于每个 $s_i$ ，检查它们的状态：

若 $s_i$ 不属于 $S$
若 $s_i$ 属于 $S$ ，且前 $i-1$ 个 $s$ 中未出现过 $s_i$
若 $s_i$ 属于 $S$ ，但前 $i-1$ 个 $s$ 中出现过 $s_i$

2 题目破题推导

2.1 第一步：正向思维转逆向思维

正向：记录字符串本身，瓶颈：时间复杂度 $O(nm|s|)$
逆向：
为了优化掉一个一个匹配，争取一次遍历直接得到结果，所以只能将字符串记录一次
因此先记录字符串本身及每个字符串在询问中最后一位的出现次数
如果能匹配上一定会沿着字符串的每一位走到最后一位，那么对于最后一位可以分情况讨论

2.2 第二步：分情况讨论

对于询问的每个字符串最后一位出现次数：
为 $0$ 则未出现过
为 $1$ 则此次为出现的第一次
$\ge 1$ 则此次为出现的第若干（非 $1$ ）次

3 模型匹配

刚刚我们提到“先记录字符串本身，再记录每个字符串在询问中最后一位的出现次数”
这天然为字典树的性质

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

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

int n, m;
const int N = 1e4 + 10, M = 26;
int trie[N * 55][M];
int ed[N * 55];
int cnt[N * 55];
int idx;

int get(char c){
	return c - 'a';
}
void insert(string s){
    int now = 0;
    int len = s.size();
    for (int i = 0;i < len;i++){
        int ch = get(s[i]);
        if (trie[now][ch] == 0){
            trie[now][ch] = ++idx;
        }
        now = trie[now][ch];
    }
    ed[now]++;
}
int query(string s){
	int now = 0;
	int len = s.size();
	for (int i = 0;i < len;i++){
		int ch = get(s[i]);
		if (trie[now][ch] == 0){
			return 0;
		}
		now = trie[now][ch];
	}
    if (ed[now] != 1){
        return 0;
    }
    cnt[now]++;
    if (cnt[now] == 1){
        return 1;
    }
	return 2;
}

int main(){

    cin >> n;
    for (int i = 1;i <= n;i++){
        string s;
        cin >> s;
        insert(s);
    }
    cin >> m;
    while(m--){
        string s;
        cin >> s;
        int ret = query(s);
        if (ret == 0){
            cout << "WRONG\n";
        } else if (ret == 1){
            cout << "OK\n";
        } else {
            cout << "REPEAT\n";
        }
    }
    
    return 0;
}

错误点：

这题trie数组开小了或开大了都不行
如果只开 $10^5,26$ -- $n=10^5$ 的情况下每个字符串长度不超过 $50$ ，所以是 $5 \times 10^6$
如果开大了 -- $5\times 10^6$ 只能支持下一维为 $26\times10$ ，但是字典树并不需要这样，下一维只需要开 $26$ 足够