Tang-Dreamoon's Blog

bzoj 1535 template

发表于 | 分类于 ， ，

链表+exKMP

　　题目链接：bzoj 1535

　　题意：写 B z o j 的题意就是简单——题意见上……

　　题解：既然这个循环节是某个长度的前缀，所以我们先对于此串求半个扩展 KMP ，得到从每个位置开始的子串能和整个串匹配的长度 Leni 。然后我们考虑从小到大枚举前缀也就是最终的答案 X ，因为操作是将一个模板不断重复喷涂，所以能够接纳这个模板的位置显然只能是那些 Leni≥X 的位置。所以我们每次把 Leni＜X 的点删去，把剩下的点集称为 Ai，如果 Ai 中相邻两点间距离的最大值 ≤X 的话，那么当前的 X 即为一个可行解，而第一个可行解即为最终的最优解。

　　我思故我在：显然在从小到大枚举的时候，每一个点只可能被删去一次，所以我们可以用链表维护当前剩余的点集和它们之间的距离。注意：不要智障到在每次删点的时候遍历整个链表！！！！！

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
58
59
60
61
62
63
64
65
66
67
68
69
70
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
using namespace std;
struct table{
	int last,next;
}map[500500];
char ap[500500];
int len[500500];
vector<int> ve[500500];
inline int max(int a,int b)
{
	return a > b ? a : b ;
}
int main()
{
	scanf("%s",ap+1);
	int n=strlen(ap+1);
	int now=1;
	len[1]=-1;
	for(int i=2;i<=n;i++)
	{
		if(i<=now+len[now])
		{
			int x=i-now+1;
			if(i+len[x]<now+len[now]) len[i]=len[x];
			else
			{
				int j=now+len[now]-i+1;
				while((i+j)<=n&&ap[i+j]==ap[1+j]) j++;
				now=i,len[i]=j-1;
			}
		}
		else
		{
			int j=0;
			while((i+j)<=n&&ap[i+j]==ap[1+j]) j++;
			now=i,len[i]=j-1;
		}
	}
	for(int i=1;i<=n;i++)
	{
		len[i]++,map[i].last=i-1,map[i].next=i+1;
		if(i!=1)
			ve[len[i]+1].push_back(i);
	}
	map[n+1].last=n;
	int ans=1;
	int maxa=1;
	while(1)
	{
		for(int i=0;i<ve[ans].size();i++)
		{
			int x=ve[ans][i];
			maxa=max(maxa,map[x].next-map[x].last);
			map[map[x].next].last=map[x].last;
			map[map[x].last].next=map[x].next;
		}
		if(maxa<=ans&&(n+1-map[n+1].last)<=ans)
		{
			printf("%d\n",ans);
			break;
		}
		ans++;
	}
	return 0;
}