濮阳免费网站制作,中国建筑工程网施工资料,江门网站建设方案报价,石家庄建站软件CSP模拟53联测15 D. 子序列 文章目录 CSP模拟53联测15 D. 子序列题目大意思路code 题目大意
#xff08;seq / 3s / 512 MiB#xff09;
给定一个长为 n n n 的仅有小写英文字母构成字符串 S S 1 S 2 ⋯ S n SS_1S_2\cdots S_n SS1S2⋯Sn。我们定义一个字符串是好…CSP模拟53联测15 D. 子序列 文章目录 CSP模拟53联测15 D. 子序列题目大意思路code 题目大意
seq / 3s / 512 MiB
给定一个长为 n n n 的仅有小写英文字母构成字符串 S S 1 S 2 ⋯ S n SS_1S_2\cdots S_n SS1S2⋯Sn。我们定义一个字符串是好的当且仅当它可以用两个不同的字母 x 和 y 表示成 xyxyxyx... 的形式。例如字符串 abab、tot、z 是好的但字符串 abc、aa 不是好的。
现在有 q q q 组询问每次给定 1 ≤ l ≤ r ≤ n 1 \le l \le r \le n 1≤l≤r≤n你想要求出对于串 S S S 的子串 S [ l ⋯ r ] S[l \cdots r] S[l⋯r]它最长的一个好的子序列的长度是多少以及它可以被哪两个不同字符 x 和 y 来表示。如果有多个最长的串则输出字典序最小的一个串的 x 与 y。
思路
观察时限发现大概是 O ( 26 n ) O(26n) O(26n) 的做法
我们预处理两个数组 p r e v i , n e x t i prev_i , next_i previ,nexti 分别表示第 i i i 为的上一个、下一个字符 j j j 在什么位置。
再维护 a n s i , j ans_{i , j} ansi,j 表示 i → n i\to n i→n 里类似于 s [ i ] , j s[i] , j s[i],j 这样的排列的数量
考虑这个怎么维护。
从后往前枚举 i i i 和字符 j j j 用 n e x t i , j next_{i , j} nexti,j 转移就好了
对于每个询问 l , r {l , r} l,r 直接从小到枚举答案用类似前缀和的方法求答案就好了。
前缀和的时候要考虑是否最后的那组字符都在区间内。
注意判断一下有没有多出来一个字符的情况。
code
#include bits/stdc.h
#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;elseans1 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;
}
