2023NOIP A层联测10-子序列

2023-10-13 03:28

文章标签 序列联测 2023noip

本文主要是介绍2023NOIP A层联测10-子序列，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

给定一个长为 $n$ 的仅有小写英文字母构成字符串 $S=S_1S_2\cdots S_n$ 。我们定义一个字符串是好的，当且仅当它可以用两个不同的字母 x 和 y 表示成 xyxyxyx... 的形式。例如，字符串 abab、tot、z 是好的，但字符串 abc、aa 不是好的。

现在有 $q$ 组询问，每次给定 $\le l \le r \le n$ ，你想要求出，对于串 $S$ 的子串 $\cdots r]$ ，它最长的一个好的子序列的长度是多少，以及它可以被哪两个不同字符 x 和 y 来表示。如果有多个最长的串，则输出字典序最小的一个串的 x 与 y。

预处理出 $pre_{i,j},nxt_{i,j}$ 分别表示第 $i$ 个字符前/后第一个字符 $j$ 的出现位置。

对于每个字符 $S_i$ ，考虑在只保留它时序列被分成了若干段（?????i?i??i????i?? ），预处理出 $sum_{i,j}$ 表示以 $j$ 字符为分隔点，将序列分成若干段， $S_i$ 所在的段及其之后的段含有 $S_i$ 的个数减一。不懂？放个图就懂了。

在这里插入图片描述可以递推求出 $sum_{i,j}$ 。

$sum_{i,j}=sum_{nxt_{i,S_i}}+[nxt_{i,S_i}>nxt_{i,j}]$

意思就是如果 $j$ 夹在 $S_i$ 中间，就可以从后面转移过来。

对于每一次询问，枚举答案的两个字符 $c_1,c_2$ ，找出区间内第一次和最后一次 $c_1$ 出现的位置 $L, R$ 。 $2(sum_{L,c_1}-sum_{R,c_1})+1+[pre_{r+1,c_2}>R]$ 就是最长的好子序列长度。这样就求出了答案。

具体实现看代码

#include<bits/stdc++.h>
using namespace std;
const int N=1.5e6+2;
char a[N];
int m,pre[N][26],nxt[N][26],sum[N][26];
int main()
{freopen("seq.in","r",stdin);freopen("seq.out","w",stdout);scanf("%s",a+1);int n=strlen(a+1);for(int i=1;i<=n+1;i++){for(int j=0;j<26;j++){if(a[i-1]==j+97) pre[i][j]=i-1;else pre[i][j]=pre[i-1][j];}}for(int i=0;i<26;i++) nxt[n+1][i]=n+1;for(int i=n;i>=0;i--){for(int j=0;j<26;j++){if(a[i+1]==j+97) nxt[i][j]=i+1;else nxt[i][j]=nxt[i+1][j];}for(int j=0;j<26;j++){sum[i][j]=sum[nxt[i][a[i]-97]][j]+(nxt[i][a[i]-97]>nxt[i][j]);}}scanf("%d",&m);for(int i=1,l,r;i<=m;i++){scanf("%d%d",&l,&r);int maxn=-1;char c1=0,c2=0;for(int i=0;i<26;i++){for(int j=0;j<26;j++){if(i==j) continue;if(nxt[l-1][i]>r) continue;int L=nxt[l-1][i],R=pre[r+1][i];int ans=(sum[L][j]-sum[R][j])*2+1+(pre[r+1][j]>R);if(ans>maxn) maxn=ans,c1=i+97,c2=j+97;}}printf("%d %c%c\n",maxn,c1,c2);}
}