专栏文章

P7758 [COCI 2012/2013 #3] HERKABE 题解

HHanson2024
P7758题解参与者 2已保存评论 3

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
3 条
当前快照
1 份
快照标识符
@mio5vvhu
此快照首次捕获于
2025/12/02 13:52
3 个月前
此快照最后确认于
2025/12/02 13:52
3 个月前
查看原文
Link：洛谷
这里介绍两种方法。

方法一

将字符串先排序，那么相邻两两字符串之间肯定有着最长的公共前缀（LCP，Longest Common Prefix）。
设函数 solve(x,l,r)solve(x,l,r) 表示现在要将区间 [l,r][l,r] 中字符串分组，依据为第 xx 个字符。
那么当 sis_i 的第 xx 个字符与 sjs_j 的第 xx 个字符不相等时，说明就可以将 ii 和 jj 分为独立的一组，继续递归求解。
如果最终能被分为 cntcnt 组，因为这些组之间相互独立，可以任意排列，所以最终乘上 cntcnt 的阶乘即可。
代码就不放了，题解区里全是。

方法二 （人类智慧）

——by cjh
也是一样先排序，意义如上。
那么可以求出相邻两两之间的 LCP 的长度，就像样例二一样：
CPP
MARICA MARTA MATO MARA MARTINA
排完序后：
CPP
MARA MARICA MARTA MARTINA MATO
求出相邻两两之间的 LCP 的长度：
3 3 4 2 03 \ 3 \ 4 \ 2 \ 0
后面添上一个 00 的作用等会再说。
设 lcpilcp_i 为 ii 和 i+1i+1 的字符串 LCP 的长度。
我们想，现在一个字符串 si+1s_{i+1} 能合法地移动到一个位置 j(i≤j)j(i \le j) 的后面，当且仅当：
  1. ∀k∈[i,j−1],lcpi≤lcpk\forall k \in[i,j-1],lcp_i \le lcp_k。
    即：对于 ii 来说，夹在它中间的 LCP 的长度都要大于它和 i−1i-1 的 LCP 的长度。注意：不动也是可以的。
  2. lcpi≥lcpjlcp_i \ge lcp_j。
    即：ii 被夹在 jj 和 j+1j+1 中间，也要满足 1 的限制。
举个栗子吧，就比如说将上面的 MARA 插进 MARICA 和 MARTINA 后都是合法的，插进 MATO 和 MARTA 是不合法的。
那么，00 的作用就显而易见了。目的是：为了可以让每个字符串可以插到最后一个字符串的后面。
所以，我们只需要求出对于每一个 ii，找出第一个 j(i≤j)j(i \le j) 使得 lcpi>lcpjlcp_i > lcp_j。
然后，在区间 [i,j][i,j] 中找有多少个 ll 满足 lcpi≤lcpllcp_i \le lcp_l 即可，记满足的 ll 有 pip_i 个。
最终的答案就是 ∏pi\prod p_i（也是因为相互独立，乘法原理）。
这种方法常数很小，代码也好写。
代码
Code by cjh
CPP
#include<bits/stdc++.h>
#define rint register int
#define LL long long
using namespace std;
const int N=3e3+5,mod=1e9+7;
int a[N];
LL ans=1,cnt;
int n,x;
string s[N];
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin>>n;
	for(rint i=1;i<=n;++i) cin>>s[i];
	sort(s+1,s+n+1);
	for(rint i=2;i<=n;++i){
		x=min(s[i].size(),s[i-1].size());
		for(rint j=0;j<x;++j){
			if(s[i][j]!=s[i-1][j]) break;
			a[i-1]++;
		}
	}
	for(rint i=1;i<n;++i){
		cnt=0,x=i;
		while(x<=n){
			if(a[x]<=a[i]) ++cnt;
			if(a[x]<a[i]) break;
			x++;
		}
		ans=ans*cnt%mod;
	}
	cout<<ans;
	return 0;
}

评论

共 3 条评论，欢迎与作者交流。

正在加载评论...