CSP模拟53联测15 D. 子序列

CSP模拟53联测15 D. 子序列

题目大意

（seq / 3s / 512 MiB）

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

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

思路

观察时限发现大概是 $O(26n)$ 的做法

我们预处理两个数组 $pre{v}_i,nex{t}_i$ 分别表示第 $i$ 为的上一个、下一个字符 $j$ 在什么位置。

再维护 $an{s}_{i,j}$ 表示 $i\to n$ 里类似于 $s[i],j$ 这样的排列的数量

考虑这个怎么维护。

从后往前枚举 $i$ 和字符 $j$ ，用 $nex{t}_{i,j}$ 转移就好了

对于每个询问 $l,r$ ，直接从小到枚举答案，用类似前缀和的方法求答案就好了。

前缀和的时候要考虑是否最后的那组字符都在区间内。

注意判断一下有没有多出来一个字符的情况。

code

#include 
#define fu(x , y , z) for(int x = y ; x <= z ; x ++)
#define fd(x , y , z) for(int x = y ; x >= z ; x --)
using namespace std;
const int N = 1500005;
int n , lst[27] , pre[N][27] , nxt[N][27] , ans[N][27] , l , r;
char s[N] , c1 , c2;
int main () {
    freopen ("seq.in" , "r" , stdin);
    freopen ("seq.out" , "w" , stdout);
    scanf ("%s" , s + 1);
    n = strlen (s + 1);
    fu (i , 1 , n) {
        lst[s[i] - 'a' + 1] = i;
        fu (j , 1 , 26) pre[i][j] = lst[j]; 
    }
    fu (i , 1 , 26) lst[i] = 0;
    fd (i , n , 1) {
        lst[s[i] - 'a' + 1] = i;
        fu (j , 1 , 26) nxt[i][j] = lst[j];
    }
    int now , k;
    fd (i , n , 1) {
        now = s[i] - 'a' + 1;
        fu (j , 1 , 26) {
            if (now == j) continue;
            k = nxt[i][j];
            if (k) ans[i][j] = 2 + ans[nxt[k][now]][j];
            else ans[i][j] = 1;
        }
    }
    int ans1 , ans2 , T , p , x , y;
    scanf ("%d" , &T);
    while (T --) {
        ans2 = 0;
        scanf ("%d%d" , &l , &r);
        fu (i , 1 , 26) {
            fu (j , 1 , 26) {
                if (i == j) continue;
                p = nxt[l][i];
                if (p > r) continue;
                x = pre[r][i] , y = pre[r][j];
                if (x > y) 
                    ans1 = ans[p][j] - ans[x][j] + 1;
                else
                    ans1 = ans[p][j] - ans[nxt[r][i]][j];
                if (ans2 < ans1) {
                    ans2 = ans1;
                    c1 = i + 'a' - 1;
                    c2 = j + 'a' - 1;
                }
            }
        }
        printf ("%d %c%c\n" , ans2 , c1 , c2);
    }
    return 0;
}
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
45
46
47
48
49
50
51
52
53
54
55
56
57