首页 > 其他 > 详细

ICPC Southeast USA 2020 Regional Contest problemI: Longest Common Subsequence(思维)

时间:2021-04-12 15:07:53      阅读:30      评论:0      收藏:0      [点我收藏+]

题目描述

You are given n strings, each a permutation of the first k upper-case letters of the alphabet.
String s is a subsequence of string t if and only if it is possible to delete some (possibly zero)characters from the string t to get the string s.
Compute the length of the longest common subsequence of all n strings.

输入

The first line of input contains two integers n (1 ≤ n ≤ 105 ) and k (1 ≤ k ≤ 26), where n is the number of strings, and the strings are all permutations of the first k upper-case letters of the alphabet.
Each of the next n lines contains a single string t. It is guaranteed that every t contains each of the first k upper-case letters of the alphabet exactly once.

输出

Output a single integer, the length of the longest subsequence that appears in all n strings.

样例输入 Copy

【样例1】
2 3
BAC
ABC
【样例2】
3 8
HGBDFCAE
ADBGHFCE
HCFGBDAE
【样例3】
6 8
AHFBGDCE
FABGCEHD
AHDGFBCE
DABHGCFE
ABCHFEDG
DGABHFCE

样例输出 Copy

【样例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;
}
View Code

 




ICPC Southeast USA 2020 Regional Contest problemI: Longest Common Subsequence(思维)

原文:https://www.cnblogs.com/UpMing/p/14647481.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!