【样例1】
2 3
BAC
ABC
【样例2】
3 8
HGBDFCAE
ADBGHFCE
HCFGBDAE
【样例3】
6 8
AHFBGDCE
FABGCEHD
AHDGFBCE
DABHGCFE
ABCHFEDG
DGABHFCE
【样例1】 2 【样例2】 3 【样例3】 4
就是求n个串的lcs,虽然串有2e5个,但是每个串最长有26而且每个字母只出现一次
在一个串中,我们统计所有的长度为2的子序列,然后从枚举一个字母为lcs的起点然后去找下一个满足的条件的字母,
比如a-b,那么a-b必须出现了n次,也就是我们最开始统计的东西
注意用set去重,因为串太多vector会T
map也可以,能达到去重效果就可以
CODE:
int n,m,ans; int vis[27][27]; set<int>v[27]; void dfs(int x,int dep) { ans = max(ans,dep); for(int y:v[x]) { if(vis[x][y]==n) { dfs(y,dep+1); } } } int main() { n=read(),m=read(); for(int i=1 ; i<=n ; i++) { string s; cin>>s; for(int j=0 ; j<s.size() ; j++) { for(int k=j+1 ; k<s.size(); k++) { int t1 = s[j] -‘A‘ +1; int t2 = s[k] -‘A‘ +1; vis[t1][t2]++; if(vis[t1][t2]==n) ans=1; v[t1].insert(t2); } } } for(int i=1 ; i<=26; i++ ) dfs(i,1); out(ans); return 0; }
ICPC Southeast USA 2020 Regional Contest problemI: Longest Common Subsequence(思维)
原文:https://www.cnblogs.com/UpMing/p/14647481.html