题目链接
计蒜客传送
题意
求s中字典序大于t的最长子序列长度
注意
sebsequence是子序列,可以不连续,substring才是子串,必须连续
题解
对于答案来说,一定是
- 前i-1个字符和t的前i个一样,然后第i个字符比t的大
- 前缀为t,然后长度比t长
对于第一种情况,枚举这个 i ,然后找最小的 p 可以使得从(s[1]~s[p]) 中产生($t1$,$t_2$ 到 $t{i-1}$) ,然后在(s[p+1,n])中找最左边的比(t[i]) 大的字符,假如 找到了(s[pos]),那么后面的(s[pos+1,n]) 都可以加到答案后面(因为(s[pos] > t[i]) 已经保证答案大于t了)
对于第二种,根据求第一种的方法,不难求出
如何找最小的p?预处理一个(sf[i][c]) 数组,表示(s[i]) 后面第一个字符(c)在哪里即可
如何找pos? 也是用预处理的数组循环最多26次即可
复杂度(O(n*26))
AC代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
| #include <bits/stdc++.h> using namespace std; const int N = 1e6+10; int sf[N][26];
char s[N],t[N];
int n,m; int main(){ scanf("%d%d",&n,&m); scanf("%s%s",s+1,t+1); for(int i=0;i<26;i++) sf[n][i] = n+1;
for(int i=n-1;i>=0;i--){ memcpy(sf[i],sf[i+1],sizeof sf[i]); sf[i][s[i+1]-'a'] = i+1; }
int p = 0,res = -1; for(int i=1;i<=m;i++){ int pos = n+1; for(int j=t[i]-'a'+1;j<26;j++){ pos = min(pos,sf[p][j]); } if(pos != n+1) res = max(res,i+n-pos); p = sf[p][t[i]-'a']; if(p == n+1)break; } if(p < n) res = max(res,n-p+m); printf("%d\n",res); return 0; }
|
借鉴
https://www.codetd.com/article/7223660
每天一句叨叨
有时候不试一下,永远都不知道自己有多垃圾!不过没有关系,至少我永远向上生长,这就是生命!保持乐观,积极生活,因为人相对于宇宙来说是很渺小的,所以静静观察自己的生活,享受生活吧!