The Preliminary Contest for ICPC Asia Xuzhou 2019
题意:给你两个串a,b,让你找出字典序严格大于b的a的子序列的最大长度。
思路:这道题一看就是模拟嘛,枚举子序列从哪一位后开始字典序严格大于b,找到那一位在a中满足的最左的坐标,然后把后面的也全算上加上前面枚举到的长度就是当前解,对于每个解取个max即可。
那么我们首先开个s数组来预处理一下i位置后26种字母出现的最小下标,0的话则表示不存在这种字母在后面了
for(int i=n-1;i>=0;i--){ for(int j=0;j<26;j++){ if(j==a[i+1]-'a'){ s[i][j]=i+1;//如果下一位就是那直接取i+1 } else{ s[i][j]=s[i+1][j];//如果下一位不是那这个值跟i+1的值肯定还是一样 } } }
然后我们开始模拟,假设我前i-1位与t相等,那我只要找到一个最近的比b[i]大的字母位置,那么当前的子序列字典序便已经严格大于b了,直接把后面剩下的所有字符也接上就是最长解了。
设pos为子序列的第i位所在位置的话,那我这个子序列能达到的长度显然为i+(n-pos)
求完当前解后,我们把子序列移到下一位,而如果下一位置已经不存在就直接跳出循环
for(int i=1;i<=m;i++){ int x=b[i]-'a'; for(int j=x+1;j<26;j++){//如果我子序列的位置选的是比x大的字符,那我字典序肯定已经大于b if(s[pos][j]>0){//如果后面还存在这种字符 ans=max(ans,i+n-s[pos][j]); } } pos=s[pos][x]; if(pos==0){ flag=0; break; } }
除此之外还有一种情况,就是前m位与b完全相同,但是长度比b长的子序列,那我们可以判断一下是否存在这种子序列,因此我加了一个flag进行判断,还有一点要注意就是如果pos已经等于n了那我就无法构成比b长的序列了。
if(flag&&pos!=n){ ans=max(ans,m+n-pos); }
完整代码:
#include <bits/stdc++.h> using namespace std; const int maxn=1e6+10; char s[maxn],t[maxn]; int f[maxn][30]; int n,m,ans,pos,flag; int main() { scanf("%d%d", &n, &m); scanf("%s", s + 1); scanf("%s", t + 1); for (int i = n - 1; i >= 0; i--) { for (int j = 0; j < 26; j++) { if (j == s[i + 1] - 'a') f[i][j] = i + 1; else f[i][j] = f[i + 1][j]; } } for (int i = 1; i <= m; i++) { int x = t[i] - 'a'; for (int j = x + 1; j < 26; j++) { if (f[pos][j] > 0) ans = max(ans, i + n - f[pos][j]); } pos = f[pos][x]; if (pos == 0) { flag = 1; break; } } if (flag == 0 && pos != n) ans = max(ans, m + n - pos); if (ans == 0) printf("-1\n"); else printf("%d\n", ans); }