蔚来杯2022牛客暑期多校训练营10 题解

D. Mi Re Do Si La? So Fa!

[NOI2016] 优秀的拆分 原题。

枚举周期 \(k\)， 并将位置为 \(k\) 的倍数的点设为关键点。枚举相邻两个点 \(i,i+k\)，并求出 \(lcp(S[i...n],S[i+k...n])\) 和 \(lcs(S[1...i],S[1...i+k])\)，其中 \(lcp\) 为最长前缀，\(lcs\) 为最长后缀。我们需要求出以 \([i,i+k)\) 内的点为终点的周期为 \(k(k != |T|)\) 的所有子串 \(T\) 数量，所以将 \(lcp=min(lcp,k)\)。

得子串 \(T\) 数量为 \(lcp \cdot \lfloor \frac{lcs}{k} \rfloor+max(0,lcp+lcs\%k+1-k)\)。

再加上 \(k=|T|\) 的情况，有 \(n-k+1\) 个。

即可得出长度为 \(k\) 时有多少个子串满足条件。

复杂度为调和级数 \(O(nlogn)\)

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;

const int MAXN = 1e6 + 7;

int oldrk[MAXN * 2], cnt[MAXN], id[MAXN], tmp[MAXN], n, m;
char S[MAXN];
int rk[2][MAXN * 2], sa[2][MAXN * 2], height[2][MAXN][21];

void SuffixArray(int pos, int m = 26) {
	for(int i = 0; i <= n; ++i) height[pos][i][0] = 0;
	for(int i = 0; i <= 2 * n; ++i) rk[pos][i] = sa[pos][i] = oldrk[i] = 0;
	for(int i = 0; i <= m; ++i) cnt[i] = 0;
	
	for(int i = 1; i <= n; i++) cnt[ rk[pos][i] = S[i] ]++;
	for(int i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
	for(int i = n; i; i--) sa[pos][ cnt[ S[i] ]-- ] = i;
	
	int len = 1, maxx = 0;
	while(maxx < n) {
		int k = 0;
		for(int i = n - len + 1; i <= n; i++) id[++k] = i;
		for(int i = 1; i <= n; i++) if(sa[pos][i] > len) id[++k] = sa[pos][i] - len;
		for(int i = 0; i <= m; i++) cnt[i] = 0;
		for(int i = 1; i <= n; i++) cnt[ tmp[i] = rk[pos][ id[i] ] ]++;
		for(int i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
		for(int i = n; i; i--) sa[pos][ cnt[ tmp[i] ]-- ] = id[i];
		for(int i = 1; i <= n; i++) oldrk[i] = rk[pos][i];
		int p = 1; rk[pos][ sa[pos][1] ] = 1;
		for(int i = 2; i <= n; i++) {
			if(oldrk[ sa[pos][i] ] != oldrk[ sa[pos][i - 1] ] || oldrk[ sa[pos][i] + len ] != oldrk[ sa[pos][i - 1] + len ]) p++;
			rk[pos][ sa[pos][i] ] = p;
		}
		len <<= 1; maxx = m = p;
	}
	
	for(int i = 1, k = 0; i <= n; ++i) {
		if(k) --k;
		while(S[i + k] == S[ sa[pos][ rk[pos][i] - 1 ] + k ]) ++k;
		height[pos][ rk[pos][i] ][0] = k;
	}
	
	//for(int i = 1; i <= n; ++i) printf("%d ", sa[i]); printf("sa\n");
	//for(int i = 1; i <= n; ++i) printf("%d ", rk[i]); printf("rk\n");
	//for(int i = 1; i <= n; ++i) printf("%d ", height[i][0]); printf("height\n");

	for(int k = 1; (1 << k) <= n; ++k) {
		for(int i = 1; i + (1 << k) - 1 <= n; ++i) height[pos][i][k] = min(height[pos][i][k - 1], height[pos][i + (1 << k - 1)][k - 1]);
	}
}

int QueryLCP(int pos, int l, int r) {
	if(l < 1 || r < 1 || l > n || r > n) return 0;
	l = rk[pos][l], r = rk[pos][r];
	if(l == r) return n + 1 - l;
	if(l > r) swap(l, r);
	l++;
	int t = floor( log2(r - l + 1) );
	return min(height[pos][l][t], height[pos][r - (1 << t) + 1][t]);
}

signed main()
{
	//ios::sync_with_stdio(false); cin.tie(0);
	int T; scanf("%d", &T);
	long long res = 0, cnt = 0;
	int l, r, lcp, lcs;	
	while(T--) {
		scanf("%s", S + 1); n = strlen(S + 1); //m = max(n, 300);
		for(int i = 1; i <= n; i++) S[i] = S[i] - 'a' + 1;
		SuffixArray(0);	//LCP
		reverse(S + 1, S + n + 1);
		SuffixArray(1);	//LCS
		res = 0, cnt = 0;
		for(int len = 1; len <= n; ++len) res += (long long)(n - len + 1) * len;
		for(int len = 1; len <= n / 2; ++len) {
			cnt = 0;
			for(int i = len; i + len <= n; i += len) {
				l = i, r = i + len;
				lcp = min(len, QueryLCP(0, l, r) );
				lcs = QueryLCP(1, n + 1 - (l - 1), n + 1 - (r - 1) );
				cnt += lcp * (lcs / len);
				lcs %= len;
				if(lcp + lcs >= len) cnt += (lcp + lcs - len + 1);
			}
			res += cnt * len;
		}
		printf("%lld\n", res);
	}
	return 0;
}

F. Shannon Switching Game?

设 \(st_i\) 表示先手必胜还是必败。这个游戏我们最多进行 \(O(n)\) 轮，且 \(O(n)\) 轮中每轮至少更新一个点，若没有更新点则直接退出判断结果。

先将终点设为必胜态，对每轮游戏中，对于每个点 \(u\)，若有至少两条出边 \(u->v\) 满足 \(st_v\) 为必胜态，则可以将 \(u\) 纳入必胜态。

最后判断起点是不是必胜态即可。

#include<bits/stdc++.h>
#pragma GCC optimize(2)
#define pii pair<int, int>
#define fi first
#define se second
using namespace std;

const int MAXN = 105;
const int MAXM = 1e4 + 5;

int n, m, s, t, st[MAXN];
map<int, int> G[MAXN];

void Solve() {
	cin >> n >> m >> s >> t;
	for(int i = 1; i <= n; i++) G[i].clear();
	for(int i = 1; i <= m; i++) {
		int u, v; cin >> u >> v;
		G[u][v]++;
        G[v][u]++;
	}
	for(int i = 1; i <= n; i++) st[i] = 0;
	st[t] = 1;
	for(int k = 1; k <= n; k++) {
		int cnt;
		for(int i = 1; i <= n; i++) {
			cnt = 0;
			for(auto &j : G[i]) if(st[j.fi]) cnt += j.se;
			if(cnt >= 2) st[i] = 1;
		}
	}
	if(st[s]) cout << "Join Player\n";
	else cout << "Cut Player\n";
}

signed main()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int T; cin >> T;
	while(T--) Solve();
	return 0;
}

I. Yet Another FFT Problem?

如果 \(a,b\) 各有一对相同数字可直接输出方案。

除去这个情况后，我们可以对于 \(a,b\) 去重并排序，这样的情况是两数组中数字两两不相同且条件中绝对值可去掉。

移项，有 \(a_i+b_l=a_j+b_k\)。我们可以直接用两层循环枚举 \(sum=a_i+b_l\)，枚举过程中发现先前被枚举到的 \(sum\) 和当前 \(sum\) 相同可直接输出方案。

对于 \(-1\) 的情况，发现 \(a_i+b_l\) 的上界为 \(2e7\)，则最多只会有 \(2e7\) 个值被枚举到，接下来无论枚举到哪个值，都可以根据抽屉原理得出合法方案。

#include<bits/stdc++.h>
#pragma GCC optimize(2)
#define pii pair<int, int>
#define fi first
#define se second
using namespace std;

const int MAXN = 1e6 + 5;
const int MAXM = 2e7 + 5;

int n, m, c[MAXM];
pii a[MAXN], b[MAXN], pos[MAXM];

signed main()
{
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin >> n >> m;
	for(int i = 1; i <= n; i++) cin >> a[i].fi, a[i].se = i;
	for(int i = 1; i <= m; i++) cin >> b[i].fi, b[i].se = i;
	sort(a + 1, a + 1 + n);
	sort(b + 1, b + 1 + m);
	int pos1 = 0, pos2 = 0;
	for(int i = 2; i <= n; i++) if(a[i].fi == a[i - 1].fi) pos1 = i;
	for(int i = 2; i <= m; i++) if(b[i].fi == b[i - 1].fi) pos2 = i;
	if(pos1 > 0 && pos2 > 0) {
		cout << a[pos1 - 1].se << " " << a[pos1].se << " " << b[pos2 - 1].se << " " << b[pos2].se << "\n";
		return 0;
	} 
	int cnt = 0; 
	for(int i = 1; i <= n; i++) if(i == 1 || a[i].fi != a[i - 1].fi) a[++cnt] = a[i];
	n = cnt; cnt = 0;
	for(int i = 1; i <= m; i++) if(i == 1 || b[i].fi != b[i - 1].fi) b[++cnt] = b[i];
	m = cnt;
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= m; j++) {
			int v = a[i].fi + b[j].fi;
			if(c[v] == 0) {
				c[v] = 1;
				pos[v] = {a[i].se, b[j].se};
			} else {
				cout << pos[v].fi << " " << a[i].se << " " << pos[v].se << " " << b[j].se << "\n";
				return 0;
			}
		}
	}
	cout << "-1";
	return 0;
}