「HNOI2019」JOJO(kmp+border理论)

摘要:
令牌的最大长度。注意段落中特殊判断不匹配指针的情况。换句话说,它的位置不匹配。所以在跳跃的过程中,每一刻都是(m-1)。如果存在长度,则最小长度集为。因此,所有这些都可以表达和验证。之间的长度为。以下证明表明,中的元素可以形成等差序列:取出中最大的元素,其余元素为。

Address

LOJ#3055

Solution

Part 1:不含 2 操作

  • 我们把相邻且相同的字母看作一段,令 (a[i]) 表示第 (i) 段的字母,(b[i]) 表示第 (i) 段的长度。
  • (nxt[i]) 表示 (S[1dots i]) 的最长 ( ext{border}) 长度。
  • 如果 (nxt[i]=j),那么有:(forall kin[1,j],a[k]=a[i-j+k],forall k∈[2,j],b[k]=b[i-j+k],b[1]le b[i-j+1])
  • (nxt) 数组的方法和 ( ext{kmp}) 类似。
  • 如果我们已经求出了 (nxt[1]sim nxt[i-1]),那么可以这样计算第 (i) 段字母增加的答案:
  • 设变量 (maxl),一开始令 (j=nxt[i-1],maxl=0),判断是否 (a[j+1]=a[i])
  • 如果是,那么第 (i) 段字母中,位置 (maxl+1sim b[j+1]) 的失配指针(不是 (nxt) 数组,是题目所求)都在第 (j+1) 段中。
  • 接着令 (maxl=max(maxl,b[j+1]),j=nxt[j]),直到 (j=0)(maxl=b[i])
  • 注意特判失配指针在第 (1) 段的情况。
  • 时间复杂度 (O(n))

Part 2:正解

  • 考虑把所有操作建成一棵树。树上的每个节点都对应某个时刻的字符串。
  • 对于树上的每一条边 (x→y),都有边权 ((a,b)),表示 (y) 是由 (x) 在末尾加上 (b) 个字符 (a) 得到的。
  • 但是 ( ext{kmp}) 的时间复杂度是均摊的,也就是说,直接放在树上做,时间复杂度是错的。
  • 考虑优化 ( ext{kmp})(nxt) 的过程。
  • 一开始令 (ls=i-1)(j=nxt[i-1])
  • 如果 (j+1)(i) 失配了,分情况讨论:
	if (ls - j == j - nxt[j])
	{
		int per = j - nxt[j];
		ls = j % per + per;
		j %= per;
	}
	else ls = j, j = nxt[j];
  • 给出一个结论:把字符串 (S) 的所有 ( ext{border}) 按长度排序后可分为 (O(log |S|)) 段,每段是一个等差数列。(后面会证明)
  • 考虑这样做的正确性:(j+1)(i) 失配了,由于 (ls-j=j-nxt[j]),所以 (S[1dots ls]) 存在长度为 (j-nxt[j]) 的周期。
  • 也就是说,在位置 (j+1-per,j+1-2per......) 还是失配的。所以直接让 (j\%=per) 即可。
  • (nxt[m-1],nxt[nxt[m-1]],......) 都是 (m-1)( ext{border})。所以跳 (nxt) 的过程中,每个时刻的 (j) 都是 (m-1)( ext{border})
  • 而上述情况中,(ls,j,nxt[j],nxt[nxt[j]],......) 形成了一个等差数列。
  • 所以令 (j\%=per) 就直接跳过这个等差数列了。
  • (ls-j e j-nxt[j]) 时,我们可以认为是跳过了 (ls) 所在的等差数列。
  • 因此每次都会跳过一个等差数列,跳的次数上限 (O(log i))
  • 也就是说,( ext{kmp}) 可以做到单次 (O(log n))
  • 总时间复杂度 (O(nlog n))

Part 3:证明结论

  • 首先证明:字符串 (S[1dots n]) 的所有不小于 (frac{n}{2})( ext{border}) 长度组成一个等差数列。
  • (S) 的最小 ( ext{period}) 长度为 (p),若 (ple frac{n}{2}),则存在长度 (ge frac{n}{2})( ext{border})
  • 可得 (S) 有长度为 (kp(1le kle frac{n}{p})) 的周期,也就是说 (S) 有长度为 (n-kp)( ext{border})(k) 可以取 (1sim frac{n}{p}) 中的任意一个。
  • 而最小的 (n-kp) 肯定小于 (frac{n}{2})
  • 因为最小的 (n-kp) 就是 (n\% p),而 (ple frac{n}{2}),所以 (n\% p<frac{n}{2})
  • 因此所有 (ge frac{n}{2})( ext{border}) 都能表示成 (n-kp),证毕。
  • 接下来,将 (S[1dots n])( ext{border}) 按长度分类:([1,1],[2,3],[4,7],dots ,[2^{k-1},2^k-1],[2^k,n-1]),其中 (2^{k+1}>n)
  • 对于两个字符串 (u,v),若 (|u|=|v|),则记 (P(u,v)=left{k:k>frac{|u|}{2},u[1dots k]=v[|v|-k+1dots |v|] ight})
  • 长度在 ([2^{i-1},2^i]) 之间的 ( ext{border})(P(S[1dots 2^i],S[n-2^i+1dots n]))
  • 长度在 ([2^k,n-1]) 之间的 ( ext{border})(P(S,S))
  • 下面证明 (P(u,v)) 中的元素能组成一个等差数列:
  • 取出 (P(u,v)) 中最大的元素 (x),剩下的元素都是 (u[1dots x])( ext{border})
  • 根据:字符串 (S) 的所有不小于 (frac{|S|}{2})( ext{border}) 长度组成一个等差数列,可知 (P(u,v)) 中的元素能组成一个等差数列。
  • 证毕。

Code

#include <bits/stdc++.h>

using namespace std;

#define ll long long

template <class t>
inline void read(t & res)
{
	char ch;
	while (ch = getchar(), !isdigit(ch));
	res = ch ^ 48;
	while (ch = getchar(), isdigit(ch))
	res = res * 10 + (ch ^ 48);
}

template <class t>
inline void print(t x)
{
	if (x > 9) print(x / 10);
	putchar(x % 10 + 48);
}

inline char getch()
{
	char ch;
	while (ch = getchar(), !isalpha(ch));
	return ch;
}

const int e = 2e5 + 5, mod = 998244353;

char c[e], d[e];
int adj[e], lst[e], go[e], num, cnt[e], n, ans[e], pos[e], nxt[e], m, sum[e], len[e];
int pre[e];

inline void add(int &x, int y)
{
	(x += y) >= mod && (x -= mod);
}

inline void link(int x, int y, char z, int t)
{
	lst[++num] = adj[x]; adj[x] = num; go[num] = y;
	c[num] = z; cnt[num] = t;
}

inline int ask(int l, int r)
{
	if (l > r) return 0;
	return (ll)(r - l + 1) * (l + r) / 2 % mod;
}

inline void dfs(int u)
{
	for (int i = adj[u]; i; i = lst[i])
	{
		int v = go[i], x = cnt[i];
		char y = c[i];
		m++; sum[m] = 0; len[m] = x; d[m] = y;
		pre[m] = pre[m - 1] + x;
		if (m != 1)
		{
			int j = nxt[m - 1], ls = m - 1;
			while (j > 0 && (d[j + 1] != d[m] || len[j + 1] != len[m]))
			{
				if (ls - j == j - nxt[j])
				{
					int per = j - nxt[j];
					ls = j % per + per;
					j %= per;
				}
				else ls = j, j = nxt[j];
			}
			if (j > 0 || (d[j + 1] == d[m] && len[j + 1] == len[m])) nxt[m] = j + 1;
			else if (d[1] == d[m] && len[1] <= len[m]) nxt[m] = 1;
			else nxt[m] = 0;
			
			j = nxt[m - 1]; ls = m - 1;
			int mx = 0;
			while (j > 0 && mx < len[m])
			{
				if (d[j + 1] == d[m] && len[j + 1] > mx)
				{
					add(sum[m], ask(pre[j] + mx + 1, pre[j] + min(len[j + 1], len[m])));
					mx = len[j + 1];
				}
				if (ls - j == j - nxt[j])
				{
					int per = j - nxt[j];
					ls = j % per + per;
					j %= per;
				}
				else ls = j, j = nxt[j];
			}
			if (mx < len[m])
			{
				if (d[1] == d[m])
				{
					int mid = min(len[1], len[m]);
					add(sum[m], ask(mx + 1, mid));
					sum[m] = (sum[m] + (ll)(len[m] - max(mx, mid)) * len[1]) % mod;
				}
			}
		}
		else sum[1] = ask(0, len[1] - 1);
		add(sum[m], sum[m - 1]);
		ans[v] = sum[m];
		dfs(v);
		m--;
	}
}

int main()
{
	read(n);
	int i, op, x; char y;
	for (i = 1; i <= n; i++)
	{
		read(op); read(x);
		if (op == 1)
		{
			if (!x)
			{
				pos[i] = pos[i - 1];
				continue;
			}
			y = getch();
			pos[i] = i;
			int z = pos[i - 1];
			link(z, i, y, x);
		}
		else pos[i] = pos[x];
	}
	dfs(0);
	for (i = 1; i <= n; i++) print(ans[pos[i]]), putchar('
');
	return 0;
}

免责声明:文章转载自《「HNOI2019」JOJO(kmp+border理论)》仅用于学习参考。如对内容有疑问,请及时联系本站处理。

上篇FJWC2020 Day4 题解「ZJOI2019」麻将(dp套dp)下篇

宿迁高防,2C2G15M,22元/月;香港BGP,2C5G5M,25元/月 雨云优惠码:MjYwNzM=

相关文章

[html/css]清除浮动的相关技巧

以前只了解得很浅显,转载了一篇不错的文,学习参考 浮动会使当前标签产生向上浮的效果,同时会影响到前后标签、父级标签的位置及 width height 属性。而且同样的代码,在各种浏览器中显示效果也有可能不相同,这样让清除浮动更难了。解决浮动引起的问题有多种方法,但有些方法在浏览器兼容性方面还有问题。下面总结8种清除浮动的方法(测试已通过 ie chrome...

andSelf() V1.2 加入先前所选的加入当前元素中

andSelf() V1.2概述 加入先前所选的加入当前元素中 对于筛选或查找后的元素,要加入先前所选元素时将会很有用。直线电机生产厂家 从jQuery1.8开始,.andSelf()方法已经被标注过时,在jQuery1.8和更高版本中应使用.addBack()。 我们认为对于“添加并返回”以前的结果集合这是一个更好的名字。新方法可以接受一个可选的选择...

Vue实现购物车功能

vue是前端轻量级MVVM框架,入门门槛相对较低,今天用Vue做一个购物车实例,发表以便记录 原理分析和实现 首先,还是先把布局写好,和引入vue,准备vue实例,这个不多说,代码如下 <!DOCTYPE html> <html lang="en"> <head> <meta charset=...

html下拉菜单

<!DOCTYPE ><html><head><meta charset="GBK" /><title>纯html+css导航</title><!-- mulder --><!-- qq:10221408 --><!-- 只支持 chrome firefox...

CSS3属性的兼容 什么是弹性和布局

CSS3新特性,兼容性,兼容方法总结 css3手册css3手册 边框 border-radius 用于添加圆角效果 语法: border-radius:[ <length> | <percentage> ]{1,4} [ / [ <length> | <percentage> ]{1,4} ]?<l...

[LOJ 2022]「AHOI / HNOI2017」队长快跑

[LOJ 2022]「AHOI / HNOI2017」队长快跑 链接 链接 题解 不难看出,除了影响到起点和终点的射线以外,射线的角度没有意义,因为如果一定要从该射线的射出一侧过去,必然会撞到射线 因此,我们可以把射线的方向规约成两类,分成向上与向下的两种。 不难发现,改变射线的方向后,原有的限制条件并未被改变。 要判断一条线是否规约为“垂直向下”,只需判断...

最新文章