洛谷 P1666 分析（别看）

科技起源的小号1

2026-08-25 11:18:25

发布于：天津

1阅读

0回复

0点赞

原题链接

1 题目

1.1 题目所需求出内容

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

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

背景：
有一个单词集合 $S$
允许：
一组单词是安全的，当且仅当不存在一个单词是另一个单词的前缀
求这个集合中有多少集合使得里面所有单词都互相安全，空集永远是安全的

1.3 题目数据范围与猜测

$O(n^4)$

1.4 一句话概括题意

有一个字符串集合，求这个集合中有多少集合使得里面所有字符串都互相安全，空集永远是安全的

2 题目破题推导

2.1 第一步：数学思考与证明（反证法）

思考单调性：
把所有字符串按字典序排序后，如果对于一组字符串 $i,j,k$ 使得 $j < i,k < j$ 且均不为前缀，则 $k$ 对于 $i$ 一定不为前缀

证明：
假设存在一组字符串 $i,j,k$ 使得 $k < j < i$ 且均不互为前缀，但 $k$ 为 $i$ 的前缀。
那么就说明 $i$ 的开头一部分完全等于 $k$
发现 $k < j$ 说明在某一位会出现 $k_i < j_i$
那么由于 $i$ 的开头一部分完全等于 $k$ ，会出现 $i_i < j_i$ ，因此 $i<j$
但是这时与求证定义矛盾，因此可以证明把所有字符串按字典序排序后，如果对于一组字符串 $i,j,k$ 使得 $j < i,k < j$ 且均不为前缀，则 $k$ 对于 $i$ 一定不为前缀

2.2 第二步：边界意识

因为这里面说了“空集永远是安全的”，因此记录的时候要始终多加 $1$ 代表空集
还有因为 $n\le 50$ ，因此选择的可能性（集合的组合）是 $2^{50}$

3 模型匹配

那就是一个很简单的dp，这里由于是所有方案可能性都要考虑到，所以要注意初始化和累加

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

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

int n;
const int N = 55;
string s[N];
int dp[N];
bool is_zc(string x, string y){
    if (x.size() > y.size()){
        swap(x, y);
    }
    return y.substr(0, x.size()) == x;
}

signed main(){

    cin >> n;
    // cout << is_zc("hello", "hell") << is_zc("hi", "hello") << endl;
    for (int i = 1;i <= n;i++){
        cin >> s[i];
        dp[i] = 1;
    }
    sort(s + 1, s + 1 + n);
    for (int i = 2;i <= n;i++){
        for (int j = i - 1;j >= 0;j--){
            if (!is_zc(s[i], s[j])){
                dp[i] += dp[j];
            }
        }
    }
    int ans = 1;
    for (int i = 1;i <= n;i++){
        ans += dp[i];
    }
    cout << ans;
    
    return 0;
}