2023NOIP A层联测10-子序列

题目

预处理出 $pr{e}_{i,j},nx{t}_{i,j}$ 分别表示第 $i$ 个字符前/后第一个字符 $j$ 的出现位置。

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

可以递推求出 $su{m}_{i,j}$。

$su{m}_{i,j}=su{m}_{nx{t}_{i,S_i}}+[nx{t}_{i,S_i}>nx{t}_{i,j}]$

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

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

具体实现看代码

#include
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);
    }
}
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
37
38
39
40
41
42
43
44