题意:
给定 n 个字符串,然后给定 q 种字典序规则,在这q种字典序规则下求出这n个字符串的逆序对数量。
思路:
我们发现 q 很大,对于每一种排序规则都遍历一遍 n 个字符串去求逆序对的数量复杂度太高,所以考虑预处理。我们知道要判断两个字符串字典序的大小关系,只需要知道它们第一个不同的字母,而这样的对应关系最多只有 26$\times$26 种,于是我们不妨先把这些对应关系给处理出来,然后在每种字典序规则下统计逆序对的数量,这样的时间复杂度是 26 \(\times\) 26 \(\times\) q 的。
我们假设 cnt[a][b] 表示由字符对 (a,b) 影响的且 a 所在字符串编号小于 b 所在字符串编号的字符串对数量,那么如果在当前字典序规则下 a 的字典序大于 b 的字典序,那么 (a,b) 就会对答案贡献 cnt[a][b]。
接下来的问题就是 cnt[a][b] 如何计算,由于两个字符串比较,我们假设前 i-1 个字符都是相同的,从第 i 个字符串开始不同,我们可以建 tire 树,加入当前字符串的时候,将它的每一位都尝试去遍历一下其它的字母,我们可以知道在同一父亲节点的两个不同的子节点处,就是两个字符串判断出字典序大小的位置,而且我们按照题目所给顺序插入字符串,那么此前已经加入 trie 树的节点所在字符串的编号一定小于当前字符串,则 cnt[a][b] 可以在此处累加,同时将当前节点表示的字符串数量 +1 。
注意:有可能会出现字符串 abc 和字符串 abcd 比较字典序的情况,这里我们可以在每个字符串的后面都添加一个小于所有小写字母的字符,比如 'a'-1,这样就可以正常比较了。
由于本人太菜了,可能对字符串和 trie 树的理解还不太深刻,表达也不是特别清楚 QAQ,下面是AC代码~~
代码
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
const int N = 2e6 + 10;
int son[N][30],sum[N][30];
int cnt[1003];
int idx;
void insert(string s)
{
int p=0;
for(int i=0;i<s.size();i++)
{
int k=s[i]-'a'+1;
if(!son[p][k])son[p][k]=++idx;
for(int j=0;j<27;j++)cnt[(j+1)*27+k+1]+=sum[p][j];
sum[p][k]++;
p=son[p][k];
}
}
void solve()
{
int n,q;
cin>>n>>q;
for(int i=1;i<=n;i++)
{
string s;
cin>>s;
char c='a'-1;
s+=c;
insert(s);
}
int pos[30];
while(q--)
{
string s;
cin>>s;
char c='a'-1;
s=c+s;
int ans=0;
for(int i=0;i<27;i++)pos[s[i]-'a'+1]=i;
for(int i=0;i<27;i++)
{
for(int j=0;j<27;j++)
{
if(pos[i]>pos[j])
{
ans+=cnt[(i+1)*27+j+1];
}
}
}
cout<<ans<<endl;
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int T=1;
// cin>>T;
while(T--)
{
solve();
}
return 0;
}
标签:Both,cnt,Contest,int,Regional,26,字符串,节点,字典
From: https://www.cnblogs.com/Charlie983/p/18459381