洛谷 P7377 分析（别看）

科技起源的小号1

2026-09-09 21:09:47

发布于：天津

4阅读

0回复

0点赞

原题链接

1 题目

1.1 题目所需求出内容

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

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

背景：
有 $n$ 个长度为 $m$ 的参数化单词

参数化单词：只包含小写字母和问号的单词

允许：

两个参数化单词是相似的，当且仅当通过使用小写字母替换问号可以使它们完全相同

求有多少对参数化单词是相似的

1.3 题目数据范围与猜测

$n \le 5\times 10^4,m\le 6\longrightarrow O(nm)$

1.4 一句话概括题意

求有多少组相似单词

2 题目破题推导

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

正向：枚举所有字符对并进行一一匹配，时间复杂度 $O(n^2m)$
逆向：对于所有字符串，用一种方法经过一轮遍历筛出来所有和他相似的单词，猜测时间复杂度 $O(nm)$

2.2 第二步：大拆小小组大

拆：把“两个字符串相似”拆成 $m$ 位分别考虑相似性
组：用二进制将 $m$ 位上的 $?$ 和 $a\sim z$ 都压缩

2.3 第三步：分情况讨论

对于每个字符串，初始认为所有字符串（包括它自己）和它都可以匹配上（为 $1$ ），遍历 $m$ 位

当前这一位是 $?$ ，不管，该是 $1$ 还是 $1$ ，该是 $0$ 还是 $0$
当前这一位是小写字母 $c$ ，对方这一位必须也是 $c$ 或者 $?$ ，否则就变成了 $0$

最后只有还为 $1$ 的位置才说明与其能成为相似单词

2.4 第四步：边界思想

那么现在我们通过一轮 $O(nm)$ 时间复杂度的遍历得到了一些二进制串（当然每轮结束后会被覆盖）
第 $i$ 串代表第 $i$ 个字符串与其他字符串全部 $m$ 位上的匹配情况
比如串有这些（举个例子，每次开始遍历新字符串会覆盖）

那么答案应该如何计算呢？
答案是累加一个变量ans
对于每个二进制串 $s$ ， $ans=ans+(count(s)-1)$ ，最终答案是 $ans\div 2$
其中 $count(x)$ 代表二进制串 $x$ 中 $1$ 的数量

为什么要 $-1$ ？
因为自己和自己永远能匹配上，但是问题要求找“两个参数化单词”组成一对，所以要减去自己的这一种
为什么最终要 $\div 2$ ？
因为假如 $(1,3)$ 能匹配上，则 $(3,1)$ 也一定能匹配上
而我们要求“多少对”，肯定不能把它们算作两组

3 模型匹配

bitset可以快速解决很多位二进制的问题

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

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

int n, m;
const int N = 5e4 + 10, M = 10, K = 27;
string s[N];
bitset<N> ch[M][K];
bitset<N> q[M];
bitset<N> all;

int main(){

    cin >> n >> m;
    for (int i = 1;i <= n;i++){
        cin >> s[i];
    }
    for (int i = 1;i <= n;i++){
        for (int j = 0;j < m;j++){
            if (s[i][j] == '?'){
                q[j].set(i);
            } else {
                ch[j][s[i][j] - 'a'].set(i);
            }
        }
    }
    for (int i = 1;i <= n;i++){
        all.set(i);
    }
    int ans = 0;
    for (int i = 1;i <= n;i++){
        bitset<N> temp = all;
        for (int j = 0;j < m;j++){
            if (s[i][j] != '?'){
                int c = s[i][j] - 'a';
                temp &= (ch[j][c] | q[j]);
            }
        }
        ans += temp.count() - 1;
    }
    cout << ans / 2;
    
    return 0;
}