The 2nd Universal Cup. Stage 3: Binjiang

发布时间 2023-12-21 10:46:29作者: came11ia

比赛链接

没做完。

A. Almost Prefix Concatenation

给定字符串 \(S,T\)。称一个串是好的,当且仅当可以通过修改不超过一个字符使其成为 \(T\) 的前缀。

称一个把 \(S\) 划分成 \(n\) 个非空子串 \(S_1,S_2,\cdots,S_n\) 的方案是合法的,当且仅当对于任意 \(1 \le i \le n\),串 \(S_i\) 都是好的。定义合法划分方案的权值为 \(n^2\)

求所有合法划分方案的权值和对 \(998244353\) 取模后的值。

\(1 \le |S|,|T| \le 10^6\)


预处理出从每个位置开始最长的合法串长度。这等价于先求一次 LCP,跳过下一位,然后再求一次 LCP,可以直接二分哈希。计数是简单的,考虑 \((x+1)^2 = x^2+2x+1\),我们直接 DP 出每一项的系数即可。转移可以使用前缀和优化,时间复杂度 \(\mathcal{O}(n \log n)\)

code
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair <int, int> pi;
#define fi first
#define se second
constexpr int N = 1e6 + 5, mod = 998244353;
constexpr int B = 233, mod0 = 1e9 + 7, mod1 = 1e9 + 9;
bool Mbe;
void add(int &x, int y) {
	x = x + y >= mod ? x + y - mod : x + y;
}
int n, m, h[N][2], sval[N][2], tval[N][2];
char s[N], t[N];
int f[N][3], sum[N][3], R[N];
pi get_hash(int val[N][2], int l, int r) {
	pi res;
	res.fi = (val[r][0] + mod0 - 1LL * val[l - 1][0] * h[r - l + 1][0] % mod0) % mod0;
	res.se = (val[r][1] + mod1 - 1LL * val[l - 1][1] * h[r - l + 1][1] % mod1) % mod1;
	return res;
}
int lcp(int i, int j) {
	if (i > n || j > m) return 0;
	int l = 1, r = min(n - i + 1, m - j + 1);
	int res = 0;
	while (l <= r) {
		int mid = l + r >> 1;
		if (get_hash(sval, i, i + mid - 1) == get_hash(tval, j, j + mid - 1)) l = mid + 1, res = mid;
		else r = mid - 1;
	}
	return res;
}
bool Med;
int main() {
//	fprintf(stderr, "%.9lf\n", 1.0 * (&Mbe - &Med) / 1048576.0);
	ios :: sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> s + 1;
	cin >> t + 1;
	n = strlen(s + 1), m = strlen(t + 1);
	h[0][0] = h[0][1] = 1;
	for (int i = 1; i <= n; i++) {
		sval[i][0] = (1LL * sval[i - 1][0] * B % mod0 + (s[i] - 'a')) % mod0;
		sval[i][1] = (1LL * sval[i - 1][1] * B % mod1 + (s[i] - 'a')) % mod1;
		tval[i][0] = (1LL * tval[i - 1][0] * B % mod0 + (t[i] - 'a')) % mod0;
		tval[i][1] = (1LL * tval[i - 1][1] * B % mod1 + (t[i] - 'a')) % mod1;
		h[i][0] = 1LL * h[i - 1][0] * B % mod0;
		h[i][1] = 1LL * h[i - 1][1] * B % mod1;
	}
	for (int i = 1; i <= n; i++) {
		int l1 = 0, l2 = 0;
		l1 = lcp(i, 1);
		if (i + l1 - 1 == n || l1 == m) R[i] = i + l1 - 1;
		else {
			l2 = lcp(i + l1 + 1, 1 + l1 + 1);
			R[i] = i + l1 + 1 + l2 - 1;
		}
	}
//	for (int i = 1; i <= n; i++) cout << i << " " << R[i] << "\n";
	f[n + 1][0] = sum[n + 1][0] = 1;
	for (int i = n; i >= 1; i--) {
		int s0 = (sum[i + 1][0] + mod - sum[R[i] + 2][0]) % mod;
		int s1 = (sum[i + 1][1] + mod - sum[R[i] + 2][1]) % mod;
		int s2 = (sum[i + 1][2] + mod - sum[R[i] + 2][2]) % mod;
		f[i][0] = s0;
		f[i][1] = (s0 + s1) % mod;
		f[i][2] = (1LL * s0 + 2LL * s1 % mod + 1LL * s2) % mod;
		for (int j = 0; j < 3; j++)
			sum[i][j] = (sum[i + 1][j] + f[i][j]) % mod;
 	}
 	cout << f[1][2] << "\n";
//	cerr << 1e3 * clock() / CLOCKS_PER_SEC << "ms\n";
	return 0; 
}
/*
ababaab
aba
*/

B. Palindromic Beads

给定一颗 \(n\) 个点的树,点 \(i\) 有元素 \(c_i\)。定义一条路径的权值为路径上元素的最长回文子序列的长度。求最大权值。

\(1 \le n \le 2 \times 10^5\)保证每种元素出现不超过 \(2\)


先不考虑单点。把所有链按照长度排序,这样可以发现一条链只可能被前面的链包含。考虑直接 DP,设 \(f_i\) 为考虑了前 \(i\) 条链的答案,转移找到所有包含 \(i\) 的链 \(j\),令 \(f_i \gets f_j + 2\)。然后可以发现对于一条链 \(i\),包含它的链 \(j\) 在 DFS 序上是一个矩形,所以其实就是单点修改矩形求 \(\max\),树套树维护即可。

最后考虑单点,它只可能在最后出现一次。容易将包含点 \(u\) 的链拆分成 \(\mathcal{O}(deg_u)\) 个 DFS 序上的矩形,直接查就行了。总时间复杂度 \(\mathcal{O}(n \log^2 n)\)

code
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair <int, int> pi;
#define fi first
#define se second
constexpr int N = 2e5 + 5, M = N * 200;
bool Mbe;
void chkmx(int &x, int y) {
	x = x > y ? x : y;
}
int n, c[N], st[N], ed[N], tim, dep[N], f[N], g[N], ans;
vector <int> e[N], v[N];
namespace SGT2 {
	#define m ((l + r) >> 1)
	int tot, root[N << 2], tr[M], ls[M], rs[M];
	void mdf(int &x, int l, int r, int p, int v) {
		if (!x) x = ++tot;
		chkmx(tr[x], v);
		if (l == r) return;
		if (p <= m) mdf(ls[x], l, m, p, v);
		else mdf(rs[x], m + 1, r, p, v);
	}
	int qry(int x, int l, int r, int ql, int qr) {
		if (ql <= l && qr >= r) return tr[x];
		if (qr <= m) return qry(ls[x], l, m, ql, qr);
		if (ql > m) return qry(rs[x], m + 1, r, ql, qr);
		return max(qry(ls[x], l, m, ql, qr), qry(rs[x], m + 1, r, ql, qr));
	}
	#undef m
}
namespace SGT1 {
	#define m ((l + r) >> 1)
	void mdf(int x, int l, int r, int p, int y, int z) {
		SGT2 :: mdf(SGT2 :: root[x], 1, n, y, z);
		if (l == r) return;
		if (p <= m) mdf(x << 1, l, m, p, y, z);
		else mdf(x << 1 | 1, m + 1, r, p, y, z);
	}
	int qry(int x, int l, int r, int L1, int R1, int L2, int R2) {
		if (L1 <= l && R1 >= r) return SGT2 :: qry(SGT2 :: root[x], 1, n, L2, R2);
		if (R1 <= m) return qry(x << 1, l, m, L1, R1, L2, R2);
		if (L1 > m) return qry(x << 1 | 1, m + 1, r, L1, R1, L2, R2);
		return max(qry(x << 1, l, m, L1, R1, L2, R2), qry(x << 1 | 1, m + 1, r, L1, R1, L2, R2));
	}
	int qry(int L1, int R1, int L2, int R2) {
		if (L1 > R1 || L2 > R2) return 0;
		return qry(1, 1, n, L1, R1, L2, R2);
	}
	#undef m
}
void dfs(int u, int ff) {
	for (auto it = e[u].begin(); it != e[u].end(); it++) 
		if (*it == ff) {
			e[u].erase(it);
			break;
		}
	st[u] = ++tim, dep[u] = dep[ff] + 1;
	for (auto v : e[u])
		if (v != ff) dfs(v, u);
	ed[u] = tim;
}
int climb(int x, int y) {
	return *prev(upper_bound(e[y].begin(), e[y].end(), x, [&](int x, int y) {
		return st[x] < st[y];
	}));
}
void upd(int x) {
//	cerr << x << "!\n";
	chkmx(ans, 1 + SGT1 :: qry(1, st[x], st[x], ed[x]));
	for (auto y : e[x]) chkmx(ans, 1 + SGT1 :: qry(st[y], ed[y], ed[y] + 1, n));
}
bool Med;
int main() {
//	fprintf(stderr, "%.9lf\n", 1.0 * (&Mbe - &Med) / 1048576.0);
	ios :: sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> c[i], v[c[i]].emplace_back(i);
	for (int i = 1; i < n; i++) {
		int x, y;
		cin >> x >> y;
		e[x].emplace_back(y);
		e[y].emplace_back(x);
	}	
	dfs(1, 0);
	for (int i = 1; i <= n; i++) {
		f[i] = i;
		sort(v[i].begin(), v[i].end(), [&](int x, int y) {
			return st[x] < st[y];
		});
		for (auto it : v[i]) g[i] = max(g[i], dep[it]);
	}
	sort(f + 1, f + n + 1, [&](int x, int y) {
		return g[x] > g[y];
	});
//	for (int i = 1; i <= n; i++) cerr << f[i] << " \n"[i == n];
//	for (int i = 1; i <= n; i++) cerr << st[i] << " " << ed[i] << "\n";
	for (int i = 1; i <= n; i++) {
		int cur = f[i];
		if (!g[cur] || v[cur].size() < 2) continue;
		int x = v[cur][0], y = v[cur][1];
//		cerr << x << " " << y << "\n";
		int val = 0;
		upd(x), upd(y);
		if (st[x] <= st[y] && ed[y] <= ed[x]) {
			int r = climb(y, x);
			chkmx(val, SGT1 :: qry(1, st[r] - 1, st[y], ed[y]));
			chkmx(val, SGT1 :: qry(st[y], ed[y], ed[r] + 1, n));
		} else chkmx(val, SGT1 :: qry(st[x], ed[x], st[y], ed[y]));
		val += 2;
		SGT1 :: mdf(1, 1, n, st[x], st[y], val);
		chkmx(ans, val);
	}
	for (int i = 1; i <= n; i++)
		if (v[c[i]].size() == 1) upd(i);
	cout << ans << "\n";
//	cerr << 1e3 * clock() / CLOCKS_PER_SEC << "ms\n";
	return 0; 
}
/*
4
1 1 2 2
1 2
2 3
2 4
*/

H. Hurricane

给定一张 \(n\) 个点 \(m\) 条边的无向图,所有边边权均为 \(1\)

\(k = 1 \sim n\) 求出有多少无序二元组 \((u,v)\) 满足在补图中 \(u\)\(v\) 的最短距离恰为 \(k\)

\(2 \le n \le 10^5\)\(0 \le m \le 2 \times 10^5\)


注意到,对于两个点 \(u\)\(v\),如果满足 \(deg_u + deg_v < n\),那么一定有 \(dis(u, v) ≤ 2\),这是因为补图中一定存在至少一个点与 \(u\)\(v\) 均相连。

考虑从所有满足 \(2deg_u ≥ n\)\(u\) 出发跑一次单源补图最短路,这样的 \(u\) 只有 \(\mathcal{O}(\frac{m}{n}) \le \mathcal{O}(\sqrt m)\) 个,其余所有点对之间的最短路长度都不超过 \(2\),并且当且仅当两个点之间有边直接相连时,两点之间的最短路长度为 \(2\)。总时间复杂度 \(\mathcal{O}( (n+m)\sqrt {m})\)

code
include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair <int, int> pi;
#define fi first
#define se second
constexpr int N = 1e5 + 5, mod = 998244353;
bool Mbe;
int n, m, vis[N], dis[N], deg[N]; LL ans[N];
vector <int> e[N];
void bfs(int s) {
	vector <int> cur;
	queue <int> q;
	for (int i = 1; i <= n; i++) {
		if (i == s) q.push(i), dis[i] = 0;
		else cur.emplace_back(i), dis[i] = n + 1; 
		vis[i] = 0;
	}
	while (!q.empty()) {
		int u = q.front();
		q.pop();
		for (auto v : e[u]) vis[v] = u;
		for (int i = 0; i < cur.size(); i++) {
			int v = cur[i];
			if (vis[v] == u) continue;
			dis[v] = dis[u] + 1;
			q.push(v);
			swap(cur[i], cur.back()), cur.pop_back(), i--; 
		}
	}
}
bool Med;
int main() {
//	fprintf(stderr, "%.9lf\n", 1.0 * (&Mbe - &Med) / 1048576.0);
	ios :: sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= m; i++) {
		int u, v;
		cin >> u >> v;
		e[u].emplace_back(v);
		e[v].emplace_back(u);
		deg[u]++;
		deg[v]++;
	}
	ans[1] = 1LL * n * (n - 1) / 2 - m;
	for (int u = 1; u <= n; u++) {
		if (deg[u] >= n / 2) {
			bfs(u);
			for (auto v : e[u]) {
				if (deg[v] >= n / 2 && v < u) continue;
				ans[dis[v]]++;
			}
		} else {
			for (auto v : e[u]) {
				if (deg[v] >= n / 2 || v < u) continue;
				ans[2]++;
			}
		}
	}
	for (int i = 1; i < n; i++) cout << ans[i] << " ";
//	cerr << 1e3 * clock() / CLOCKS_PER_SEC << "ms\n";
	return 0; 
}
/*
4 2
1 2
3 4
*/

L. Partially Free Meal

给定长为 \(n\) 的序列 \(a,b\)。对于子序列 \(p_1,p_2,\cdots,p_k\),定义其代价为 \(\sum \limits_{i=1}^k a_{p_i} + \max\limits_{i=1}^k b_{p_i}\)

\(k = 1 \sim n\) 求出所有长为 \(k\) 的子序列的最小代价。

\(1 \le n \le 10^5\)\(1 \le a_i,b_i \le 10^9\)


首先考虑如何计算固定的 \(k\) 的答案。将所有元素按照 \(b\) 从小到大排序,枚举第 \(x (k ≤ x ≤n)\) 个元素作为选中的 \(b\) 最大的元素,那么剩下的 \(k − 1\) 个显然是贪心选择前 \(x − 1\) 个元素中 \(a\) 最小的 \(k − 1\) 个。\(k\) 固定的情况可以用堆维护,如果多次给定 \(k\)\(x\),可以通过可持久线段树 \(\mathcal{O}(\log n)\) 求出对应方案的值 \(w(k, x)\)

接下来的想法很牛。令 \(f(k)\) 表示使 \(k\) 取到最优解的 \(x\)。对于两个不同的决策 \(x, y (x < y)\),若 \(w(k, x) ≥ w(k, y)\),那么增大 \(k\) 之后由于 \(y\) 的可选择范围严格包含了 \(x\) 的可选择范围,因此 \(y\) 新选的 \(a\) 值一定不大于 \(x\) 所选的,即 \(w(k', x) ≥ w(k', y)\) 对于 \(k ≤ k' ≤ n\) 恒成立。由此可得 \(f(1) ≤ f(2) \cdots ≤ f(n)\),即最优决策具有单调性,分治即可做到 \(\mathcal{O}(n \log^2 n)\)

code
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair <int, int> pi;
#define fi first
#define se second
constexpr int N = 2e5 + 5, M = N << 5;
constexpr LL inf = 1e18;
bool Mbe;
int n, m; LL val[N], ans[N];
struct dat {
	LL a, b;
	bool operator < (const dat &p) const {
		return b < p.b;
	}
} c[N];
#define m ((l + r) >> 1)
int root[N], tot, ls[M], rs[M], cnt[M]; LL sum[M];
int build(int l, int r) {
	int x = ++tot;
	if (l == r) return x;
	ls[x] = build(l, m);
	rs[x] = build(m + 1, r);
	return x;
}
int mdf(int pre, int l, int r, int p) {
	int x = ++tot;
	ls[x] = ls[pre], rs[x] = rs[pre], cnt[x] = cnt[pre], sum[x] = sum[pre];
	if (l == r) {
		cnt[x]++;
		sum[x] += val[p];
		return x;
	}
	if (p <= m) ls[x] = mdf(ls[pre], l, m, p);
	else rs[x] = mdf(rs[pre], m + 1, r, p);
	cnt[x] = cnt[ls[x]] + cnt[rs[x]];
	sum[x] = sum[ls[x]] + sum[rs[x]];
	return x;
}
LL qry(int x, int l, int r, int k) {
	if (!k) return 0;
	if (l == r) return 1LL * k * val[l];
	if (cnt[ls[x]] > k) return qry(ls[x], l, m, k);
	return qry(rs[x], m + 1, r, k - cnt[ls[x]]) + sum[ls[x]];
}
#undef m
LL qry(int x, int k) {
	if (x < k) return inf;
	return qry(root[x], 1, m, k);
}
void solve(int l, int r, int ql, int qr) {
	if (l > r || ql > qr) return;
	if (ql == qr) {
		for (int i = l; i <= r; i++) ans[i] = c[ql].b + qry(ql, i);
		return;
	}
	LL res = inf, pos = ql;
	int mid = l + r >> 1;
	for (int i = ql; i <= qr; i++) {
		LL val = c[i].b + qry(i, mid);
		if (val < res) res = val, pos = i;
	}
	ans[mid] = res;
	solve(l, mid - 1, ql, pos);
	solve(mid + 1, r, pos, qr);
}
bool Med;
int main() {
//	fprintf(stderr, "%.9lf\n", 1.0 * (&Mbe - &Med) / 1048576.0);
	ios :: sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> c[i].a >> c[i].b;
		val[i] = c[i].a;
	}
	sort(c + 1, c + n + 1);
	sort(val + 1, val + n + 1);
	m = unique(val + 1, val + n + 1) - val - 1;
	root[0] = build(1, n);
	for (int i = 1; i <= n; i++) {
		int pos = lower_bound(val + 1, val + m + 1, c[i].a) - val;
		root[i] = mdf(root[i - 1], 1, m, pos);
	}
	solve(1, n, 1, n);
	for (int i = 1; i <= n; i++) cout << ans[i] << "\n";
//	cerr << 1e3 * clock() / CLOCKS_PER_SEC << "ms\n";
	return 0; 
}
/*
3
2 5
4 3
3 7
*/