22河南省赛 - E. Serval 的俳句（预处理）

https://codeforces.com/gym/103941

题意
给定长度为 n 的包含小写英文字母的字符串 S，需要找到长度为 17 的满足下面条件的一个子序列：

• 前 5 个字符相同，中间 7 个字符相同，最后 5 个字符相同。

输出一个满足的子序列。不存在输出 -1。

$1\le |S|\le 10^6$

思路
这题的思路来源于前几天模拟的一场 22上海市赛 - E. Expenditure Reduction（预处理），预处理出来 每个位置后面，每个字符首次出现的位置 ne[i, j]。

首先遍历第一种字符，然后找到最前面的 5 个，然后遍历第二种字符，找到最前面的 7 个，然后遍历第三种字符，找到最前面的 5 个。三重循环。
每次都贪心找最前面满足的，给后面的字符尽量留更多的位置。

还有一种思路是，边走边记录每个字符出现的次数，如果有一个字符出现 5 次了，那么就满足了，清空次数重新记录，然后找首个出现 7 次的字符作为第二种 …
这样每次找到的也是最前面满足的，满足贪心。

#include
using namespace std;

const int N = 1000010;
int n, m;
char a[N];
int ne[N][30];

int main(){
	cin >> n;
	cin >> a + 1;
	
	for(int i=n-1;i>=0;i--)
	{
		for(int j=1;j<=26;j++) ne[i][j] = ne[i+1][j];
		ne[i][a[i+1]-'a'+1] = i+1;
	}
	
	for(int i=1;i<=26;i++)
	{
		int now1 = ne[0][i];
		if(!now1) continue;
		int cnt = 1;
		while(cnt < 5 && ne[now1][i]) now1 = ne[now1][i], cnt ++;
		if(cnt != 5) continue;
		
		for(int j=1;j<=26;j++)
		{
			int now2 = ne[now1][j];
			if(!now2) continue;
			cnt = 1;
			while(cnt < 7 && ne[now2][j]) now2 = ne[now2][j], cnt ++;
			if(cnt != 7) continue;
			
			for(int k=1;k<=26;k++)
			{
				int now3 = ne[now2][k];
				if(!now3) continue;
				cnt = 1;
				while(cnt < 5 && ne[now3][k]) now3 = ne[now3][k], cnt ++;
				if(cnt != 5) continue;
				
				for(int t=1;t<=5;t++) cout << char('a' + i - 1);
				for(int t=1;t<=7;t++) cout << char('a' + j - 1);
				for(int t=1;t<=5;t++) cout << char('a' + k - 1);
				return 0;
			}
		}
	}
	
	cout << "none";
	
	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