E

我的做法

对于每个串枚举他的答案，然后直接 hash 硬干就完了。

卡一卡就过去了

#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long ull;
const int N = 5e5 + 10;
const ull P1 = 31;
const ull P2 = 29;
char s[N];
vector<char> t[N];
int n;
map<ull, int> st;

int main() {
	srand((unsigned) time(0));

	ull rd = 1ull * rand() * rand();
	ull bt = rand() % 4;

	scanf("%d", &n);
	for (int i = 1; i <= n; i ++) {
		scanf("%s", s + 1);
		int len = strlen(s + 1);
		ull hsh1 = 0, hsh2 = 0;
		for (int j = 1; j <= len; j ++) 
			t[i].push_back(s[j]), hsh1 = hsh1 * P1 + s[j] - 'a' + 1, hsh2 = hsh2 * P2 + s[j] - 'a' + 1, st[1ull * hsh1 * hsh2] ++;
	}
	for (int i = 1; i <= n; i ++) {
		int cnt = 0;
		bool flag = false;
		ull hsh1 = 0, hsh2 = 0;
		// printf("string: %d\n", i);
		for (char ch : t[i]) {
			hsh1 = hsh1 * P1 + ch - 'a' + 1, hsh2 = hsh2 * P2 + ch - 'a' + 1, st[1ull * hsh1 * hsh2] --;

			// printf("pos: %d map: %d hsh1: %llu hsh2: %llu tot hsh: %llu\n", cnt + 1, st[hsh1 ^ hsh2], hsh1, hsh2, hsh1 ^ hsh2);
			if (st[1ull * hsh1 * hsh2] <= 0) {
				flag = true;
				printf("%d\n", cnt);
				break;
			}

			++ cnt;
		}
		if (!flag) printf("%d\n", cnt);

		hsh1 = 0, hsh2 = 0;
		for (int j = 0; j <= cnt; j ++) hsh1 = hsh1 * P1 + t[i][j] - 'a' + 1, hsh2 = hsh2 * P2 + t[i][j] - 'a' + 1, st[1ull * hsh1 * hsh2] ++;
	}
	return 0;
}

官方做法

应该类似于建一个 trie 树，然后判断 size 是否大于 \(1\)。

F

我们可以考虑进行一个类似于树上背包的计数 dp。

设 \(f_{u,j,0/1}\) 表示在点 \(u\)，当前有 \(j\) 个连通块，且 \(u\) 选/不选 的方案数。

转移我们分几类，记 \(v\) 是 \(u\) 的儿子。

• \(f_{v,k,0} \times f_{u,j,0} -> f_{u,k+j,0}\)
• \(f_{v,k,1} \times f_{u,j,0} -> f_{u,k+j,0}\)
• \(f_{v,k,0} \times f_{u,j,1} -> f_{u,k+j,1}\)
• \(f_{v,k,1} \times f_{u,j,1} -> f_{u,k+j-1,1}\)

然后就完事了，复杂度也是类似于树上背包的 \(\mathcal{O}(n^2)\)。

#include <bits/stdc++.h>
using namespace std;

const int N = 5010;
typedef long long ll;
const ll MOD = 998244353;
ll f[N][N][2];
int n, head[N], nxt[N * 2], to[N * 2], tot, sze[N];
void add(int x, int y) { nxt[++ tot] = head[x]; head[x] = tot; to[tot] = y; }

void dfs(int x, int fa) {
	sze[x] = 1;
	f[x][0][0] = 1;
	f[x][1][1] = 1;
	for (int i = head[x]; i; i = nxt[i]) {
		int y = to[i];
		if (y != fa) {
			dfs(y, x);

			for (int k = sze[x]; k >= 0; k --) {
				for (int j = sze[y]; j >= 1; j --) {
					f[x][k + j][0] = (f[x][k + j][0] + (f[y][j][0] + f[y][j][1]) % MOD * f[x][k][0] % MOD) % MOD;
					if (k) {
						f[x][k + j][1] = (f[x][k + j][1] + f[y][j][0] * f[x][k][1] % MOD) % MOD;
						if (j)	
							f[x][k + j - 1][1] = (f[x][k + j - 1][1] + f[y][j][1] * f[x][k][1] % MOD) % MOD;
					}
				}
			}

			sze[x] += sze[y];
		}
	}
}

int main() {
	scanf("%d", &n);
	for (int i = 1, u, v; i < n; i ++) scanf("%d%d", &u, &v), add(u, v), add(v, u);
	dfs(1, 1);
	for (int i = 1; i <= n; i ++) printf("%lld\n", (f[1][i][0] + f[1][i][1]) % MOD);
	return 0;
}

G

首先我们将可能的牌的分数离散化。

然后我们考虑如何去处理询问。

我们每次二分一个最小的 \(l\) 使得 \([l,+ \infty)\) 内牌的数量小于限制。

因为是一个类似于前缀和的东西，我们可以将序列倒过来然后直接用树状数组加二分处理出来。

不难发现操作 \(1\) 和操作 \(2\) 也很好维护。

然后我们就可以愉快的解决这道题了。

感觉细节比较多，代码待会再补。

EX

考虑进行 bitset 优化的 floyed，我们记录起点和中间最大的转移位置，然后把终点压在一个 bitset 中，每次询问二分回答即可。