AGC007 做题小记

Vexoben

Mar 28, 2019

It takes 10 minutes to read this article.

比赛链接:AGC007

CD是去年做的懒得再看一遍了。就把今天补的EF写写。

E.Shik and Travel

题意

给定 $n$ 个点的有根树，边有边权，每个节点的孩子数量为 $0$ 或 $2$ 。你要进行一次旅行，一开始在根的位置。每一天，你要走到一个没走到的叶子节点，且这一天的费用为经过边权和。你要走到所有的叶子节点，并最终回到根，且使得所有边经过恰好两次。第一天和最后一天不计费用。求费用最大值的最小值。

数据范围： $N,V≤131072$

题解

每条边恰好经过两次说明要退出一棵子树，必须将这棵子树内所有的叶子节点都经过一次。

先二分一个答案 $mid$

对每个点维护一些二元组 $(a,b)$ ，表示存在一种合法方案，使得从这个点的父亲走到它里面的某个叶节点费用是 $a$ ，在在 $dfs$ 完所有叶节点后离开，到达它父亲节点时已经产生了 $b$ 的费用，其中不产生大于 $mid$ 的费用。

需要注意的是： $a,b$ 是可以大于 $mid$ 的，因为从根出发和回到根的那两条路径不计费用。

因为对于每个 $a$ 只需要一个最小的 $b$ ，而 $(a,b)$ 和 $(b,a)$ 是等价状态，设 $siz(u)$ 为 $u$ 这棵子树本质不同的二元组数，那么 $siz(u)≤2*min\{siz(lch),siz(rch)\}$ ，总状态数就是 $O(nlogn)$ ，复杂度就是 $O(n \; log \;answer \; log \; n)$ 。

合并时懒得归并就多一个 $log$

#pragma GCC optimize("2,Ofast,inline")
#include<bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define LL long long
#define pii pair<LL, LL>
using namespace std;
const int N = 2e5 + 10;
 
template <typename T> void read(T &x) {
	int f = 0;
	char c = getchar();
	while (c < '0' || c > '9') f |= (c == '-'), c = getchar();
	for (x = 0; c >= '0' && c <= '9'; c = getchar())
		x = (x << 3) + (x << 1) + (c ^ '0');
	if (f) x = -x;
}
 
int n;
int ch[N][2], val[N][2];
LL L, R, mid, ans;
vector<pii> vec[N];
 
vector<pii> merge(vector<pii> a, vector<pii> b, int pre) {
	vector<pii> ans;
	reverse(a.begin(), a.end());
	reverse(b.begin(), b.end());
	for (int i = 0, p = 0; i < a.size(); ++i) {
		while (p < b.size() && a[i].se + b[p].fi > mid) ++p;
		if (p < b.size() && a[i].se + b[p].fi <= mid) {
			ans.push_back(mp(a[i].fi + pre, b[p].se + pre));
			ans.push_back(mp(b[p].se + pre, a[i].fi + pre));
		}
	}
	swap(a, b);
	for (int i = 0, p = 0; i < a.size(); ++i) {
		while (p < b.size() && a[i].se + b[p].fi > mid) ++p;
		if (p < b.size() && a[i].se + b[p].fi <= mid) {
			ans.push_back(mp(a[i].fi + pre, b[p].se + pre));
			ans.push_back(mp(b[p].se + pre, a[i].fi + pre));
		}
	}
	sort(ans.begin(), ans.end());
	for (int i = 1; i < ans.size(); ++i) {
		if (ans[i].se >= ans[i - 1].se) ans[i] = ans[i - 1];
	}
	ans.erase(unique(ans.begin(), ans.end()), ans.end());
	return ans;
}
 
void dfs(int x, int pre) {
	vec[x].clear();
	if (!ch[x][0]) {
		vec[x].pb(mp(pre, pre));
		return;
	}
	dfs(ch[x][0], val[x][0]);
	dfs(ch[x][1], val[x][1]);
	if (vec[ch[x][0]].size() < vec[ch[x][1]].size())
		vec[x] = merge(vec[ch[x][0]], vec[ch[x][1]], pre);
	else vec[x] = merge(vec[ch[x][1]], vec[ch[x][0]], pre);
}
 
int check() {
	dfs(1, 0);
	return (vec[1].size() > 0);
}
 
int main() {
	read(n);
	for (int i = 2; i <= n; ++i) {
		int f, v;
		read(f); read(v);
		if (!ch[f][0]) {
			ch[f][0] = i;
			val[f][0] = v;
		}
		else {
			ch[f][1] = i;
			val[f][1] = v;
		}
	}
	L = 0, R = 1e15, ans = 1e15;
	while (L <= R) {
		mid = (L + R) >> 1;
		if (check()) {
			ans = mid;
			R = mid - 1;
		}
		else L = mid + 1;
	}
	cout << ans << endl;
	return 0;
}

F.Shik and Copying String

题意

给定字符串 $S_0,T$ 。 $S_i[1]=S_{i-1}[1]$ ， $S_i[j] = S_{i-1}[j]$ 或 $S_i[j] = S_i[j-1]$ ，求最小的 $i$ 使得 $S_i$ 可能等于 $T$ ，无解输出 $-1$

数据范围： $S_0.length ≤ 1000000$

题解

从 $atcoder$ 官方题解里面盗的图。

注意这张图只是起演示作用，但图中画的并不是最优解。

对于 $T$ 中连续的一段，我们可以确定它们对应 $S_0$ 中的那个字符。

从右到左依次确定。每确定一个对应关系就相当于从 $T$ 引一条折线到 $S_0$ ，这条折线只能向上向左，且不能和其它折线相交。

因此折线肯定越靠右靠上越好。

开一个队列维护这些折线。当一条折线不会影响以后加入的直线时将它弹出。

那么一条折线的影响范围应该是 $pos$ 到 $pos-queue.size+1$ ，它会使这一段引出去的折线无法占用最上格而导致网格图的高度必须 $+1$ 来满足折线不相交的要求。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;

int n, m;
int h, t, q[N];
char S[N], T[N];

int main() {
	cin >> n;
	scanf("%s", S + 1);
	scanf("%s", T + 1);
	int flag = 1;
	for (int i = 1; i <= n; ++i) {
		if (S[i] != T[i]) flag = 0;
	}
	if (flag) return 0 * puts("0");
	int pos = n, ans = 0;
	h = 1, t = 0;
	for (int i = n; i >= 1; --i) {
		if (T[i] == T[i - 1]) continue;
		pos = min(pos, i);
		while (pos && T[i] != S[pos]) --pos;
		if (!pos) return 0 * puts("-1");
		while (h <= t && q[h] - (t - h + 1) + 1 > i) ++h;
		q[++t] = pos;
		if (i != pos) ans = max(ans, t - h + 1);
	}
	cout << ans + 1 << endl;
	return 0;
}