Day6

暴力赛

T1

倒序考虑

若在复制位置的前面，则此次无效

在里面，则相应地变换

在后面，则减去复制的长度

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define gt getchar
using namespace std;
inline ll read(){
	ll x=0,f=1;char ch=gt();
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=gt();}
	while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gt();}
	return x*f;}
const int N = 1010500;
ll n, k, m, l[N], r[N], c[N];
char s[N];
int main() 
{
	n = read(), m = read(), k = read();
	cin >> s;
	for (int i = 1;i <= m; ++ i)
		l[i] = read(), r[i] = read(), c[i] = read();
	for (int i = m;i >= 1; -- i)
	{
		int len = r[i] - l[i] + 1, L = c[i] + 1, R = c[i] + len;
		if (L <= k && k <= R) k += l[i] - L;
		else if (k > R) k -= len;
	}
	cout << s[(k - 1) % n] << '\n';
	return 0;
}

T2

考虑两个串的比较

记录每个字符和这个字符上次出现的距离，变为新的数组

两串相等是新数组相等的充要条件

KMP

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define gt getchar
using namespace std;
inline ll read(){
	ll x=0,f=1;char ch=gt();
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=gt();}
	while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gt();}
	return x*f;}
const int N = 1000500;
char s[N];
int f[N], nxt[N], T[31], n;
ll ans;
void KMP()
{
	int j = 0;
	for(int i = 2;i <= n; ++ i)
	{
		while(j && f[j + 1] != min(f[i], j + 1))j = nxt[j];
		if(f[j + 1] == min(f[i], j + 1)) ++ j;
		nxt[i] = j, ans += j;
	}
}

int main()
{
	scanf("%s", s + 1);
	n = strlen(s + 1);
	for (int i = 1;i <= n; ++ i) 
		f[i] = i - T[s[i] - 'a'], T[s[i] - 'a'] = i;
	KMP();
	cout << ans << '\n';
    return 0;
}

T3

考虑一段区间可以开 \(k\) 次根号当且仅当区间乘起来以后每个质因子的幂次都是 \(k\) 的倍数。

维护一个串，第 \(i\) 个串为表示第 \(i\) 个质数的幂次模 \(k\) 的余数，当这个串全 \(0\) 时即为可以开 \(k\) 次根号。

考虑哈希维护这个串，用 map 存一下左端点，在右端点处询问即可。

注意用自然溢出而不是普通哈希。

#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define gt getchar
using namespace std;
inline ll read(){
	ll x=0,f=1;char ch=gt();
	while(!isdigit(ch)){if(ch=='-')f=-1;ch=gt();}
	while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gt();}
	return x*f;}
const int P = 1e9 + 9;
const int N = 10050000;
int e[N], pr[N], a[N], num, v[N], n, k;
ll mi[N / 10];
void work(int n = 1e7)
{
	mi[0] = m1[0] = 1;
	for (int i = 2;i <= n; ++ i)
	{
		if (!e[i]) pr[e[i] = ++num] = i;
		for (int j = 1;j <= e[i] && pr[j] * i <= n; ++ j)
			e[pr[j] * i] = j;
	}
	for (int i = 1;i <= num; ++ i)
	{
		mi[i] = mi[i - 1] * 27ull;
		m1[i] = m1[i - 1] * 137ll % P;
	}
}
map<pair<ll, int> , int> mp;
int main()
{
	n = read(), k = read();
	work();
	ll all = 0, ans = 0, a2 = 0;
	mp[{all, a2}] = 1;
	for (int i = 1;i <= n; ++ i)
	{
		int x = read()
		while(x != 1)
		{
			int t = e[x];
			all = (all + mi[t]);
			a2 = (a2 + m1[t]) % P;
			if (++ v[t] == k)
			{
				v[t] = 0, all = (all - mi[t] * k);
				a2 = (a2 - 1ll * m1[t] * k % P + P) % P;
			}
			x /= pr[t];
		}
		ans += mp[{all, a2}] ++;
	}
	cout << ans << '\n';
	return 0;
}

T4

考虑题目所求为两者权值之差，考虑令串 \(s_i\) 的权值为 \(v_i + \frac{1}{2}\sum_{j}LCP(s_i, s_j)\)

那么如果两个串都被一个人选中，LCP 恰好被加了两遍

如果分别被两个人选中，一相减恰好消除。

所以直接对这个权值排序，从大到小以此选择即可。

讲课

KMP

与T2有关

考虑一个短串和比它长1的长串

长串的border可以由短串更新

P2375 [NOI2014] 动物园

给出一个字符串，求 \(\sum(num_i + 1)\)

对于字符串的前个字符构成的子串，既是其前缀又是其后缀，同时满足该前缀和后缀不重叠，这种字符串的数量记作 \(num_i\)

正常做一遍 KMP，再做一遍求答案，这一次维护指针 \(j\)，当 \(j\) 大于 \(i\) 的一半时额外跳一次 \(next\)。

P3193 [HNOI2008] GT考试

题面

阿申准备报名参加 GT 考试，准考证号为 \(N\) 位数\(X_1,X_2…X_n\ (0\le X_i\le 9)\)，他不希望准考证号上出现不吉利的数字。
他的不吉利数字\(A_1,A_2,\cdots, A_m\ (0\le A_i\le 9)\) 有 \(M\) 位，不出现是指 \(X_1,X_2\cdots X_n\) 中没有恰好一段等于 \(A_1,A_2,\cdots ,A_m\)，\(A_1\) 和 \(X_1\) 可以为 \(0\)。

阿申想知道不出现不吉利数字的号码有多少种，输出模 \(K\) 取余的结果。

4 3 100
111

out

对于全部数据，\(N\leq10^9\)，\(M\leq 20\)，\(K\leq1000\)。

solution

设 \(dp[i][j]\) 表示前 \(i\) 位数，匹配了 \(A\) 前 \(j\) 位的方案数。

枚举下一位填什么，\(dp[i][ch[j][c]] += dp[i - 1][j], ch[j][c]\)表示当前匹配 \(A\) 了的前 \(j\) 位，再加一个字符 \(c\) 会匹配多少位。

发现可以矩阵优化，时间复杂度 \(O(M^3\log N)\)

P4696 [CEOI2011]Matching

对于整数序列 \((a_1,a_2,\cdots,a_n)\) 和 \(1\sim n\) 的排列 \((p_1,p_2,\cdots,p_n)\)，称 \((a_1,a_2,\cdots,a_n)\) 符合 \((p_1,p_2,\cdots,p_n)\)，当且仅当：

\(\{a\}\) 中任意两个数字互不相同；
将 \((a_1,a_2,\cdots,a_n)\) 从小到大排序后，将会得到 \((a_{p_1},a_{p_2},\cdots,a_{p_n})\)。

现在给出 \(1\sim n\) 的排列 \(\{p\}\) 和序列 \(h_1,h_2,\cdots,h_m\)，请你求出哪些 \(\{h\}\) 的子串符合排列 \(\{p\}\)。

5 10
2 1 5 3 4
5 6 3 8 12 7 1 10 11 9

out

2
2 6

对于 \(100\%\) 的数据，有 \(2\le n\le m\le 1\ 000\ 000;1\le h_i\le 10^9;1\le p_i\le n\)，保证 \(\{h\}\) 中的元素互不相同，且 \(\{p\}\) 是一个排列。

在这题当中，首先将由记录第 k 大对应什么位置变成第 k 个位置是第几大。

题目条件等价于将的子串离散化之后和完全相同。

例如 \(s = \{21,45,23,7,8,4,43\} = \{4,7,5,2,3,1,6\}\)

考虑匹配跳 nxt 的时候，这个排列是变了的，但是如果最后一个字符在之前的串中的排名相同，那么这个字符就是可以

加入末尾的，即使其他数的排名变化了也是依然是相等的。

所以现在我们只需要快速判断一个数的排名，可以先预处理出 p 这个排列中每个数的前驱和后继，

注意这里的前驱（后继）是位置在自己前面的前驱和后继。

那么在 h 这个串上匹配的时候，只用查看对应 p 上的前驱后继是不是真正的前驱后继即可。

P5537 【XR-3】系统设计

小 X 需要你设计一个系统。

这个系统首先需要输入一棵 \(n\) 个点的有根树和一个长度为 \(m\) 的序列 \(a\)，接下来需要实现 \(q\) 个操作。

操作分两种：

1 x l r 表示设定起点为有根树的节点 \(x\)，接下来依次遍历 \(l \sim r\)。当遍历到 \(i\) 时，从当前节点走向它的编号第 \(a_i\) 小的儿子。如果某一时刻当前节点的儿子个数小于 \(a_i\)，或者已经遍历完 \(l \sim r\)，则在这个点停住，并输出这个点的编号，同时停止遍历。
2 t k 表示将序列中第 \(t\) 个数 \(a_t\) 修改为 \(k\)。