徐皓天 / 博客
← 全部文章

USACO 2018-2019 Platinum 题解

题解更新于 2020 年 7 月 28 日

本文目录（15 节）
  1. 2018 December Contest
  2. Balance Beam
  3. Sort It Out
  4. The Cow Gathering
  5. 2019 January Contest
  6. Redistricting
  7. Exercise Route
  8. Train Tracking 2
  9. 2019 February Contest
  10. Cow Dating
  11. Moorio Kart
  12. Mowing Mischief
  13. 2019 US Open Contest
  14. Compound Escape
  15. Valleys

USACO

2018 December Contest

Balance Beam

单调栈求一个上凸壳即可。

卡精度，要用 __int128。

const int N = 1e5 + 7;
int n;
__int128 a[N];
vi s(1, 0);

inline bool pd(int i, int j, int k) {
	return (a[j] - a[i]) * (k - i) <= (a[k] - a[i]) * (j - i);
}

int main() {
	rd(n);
	for (int i = 1; i <= n + 1; i++) {
		if (i != n + 1) rd(a[i]), a[i] *= 1e5;
		while (s.size() > 1u && pd(s[s.size()-2], s.back(), i))
			s.pop_back();
		s.pb(i);
	}
	for (ui i = 1; i < s.size(); i++) {
		int l = s[i-1], r = s[i];
		for (int k = l + 1; k < r; k++)
			print(((k - l) * a[r] + (r - k) * a[l]) / (r - l));
		if (r != n + 1) print(a[r]);
	}
	return 0;
}

Sort It Out

首先题意可以转化为第 kk 大最长上升子序列 (LIS)。

先考虑如何求 LIS 的数量，设 fi,j,gi,jf_{i,j},g_{i,j} 分别表示考虑前 ii 个数，最后一个元素为 jj 的 LIS 长度以及数量。

这可以用建立在值域上的树状数组优化，时间复杂度 O(nlog⁡n)\mathcal O(n \log n)。

那么求第 kk 大 LIS，先预处理出每个位置开头的 LIS 长度及数量，然后从前往后找即可。

时间复杂度 O(nlog⁡n)\mathcal O(n \log n)。

const int N = 1e5 + 7;
const ll inf = 1e18;
int n, m, a[N], b[N];
ll k, c[N];
bool v[N];
vi e[N];

struct T {
	int x;
	ll c;
	inline T() {}
	inline T(int x, ll c) : x(x), c(c) {}
	inline friend void operator += (T &a, const T &b) {
		if (a.x < b.x) a.x = b.x, a.c = b.c;
		else if (a.x == b.x) a.c = min(inf, a.c + b.c);
	}
} t[N];

inline void add(int x, T y) {
	while (x) t[x] += y, x -= x & -x;
}

T ask(int x) {
	T y = T(0, 1);
	while (x <= n) y += t[x], x += x & -x;
	return y;
}

int main() {
	rd(n), rd(k);
	for (int i = 1; i <= n; i++) rd(a[i]), b[a[i]] = i;
	for (int i = n; i; i--) {
		T o = ask(b[i] + 1);
		e[++o.x].push_back(i), c[i] = o.c, add(b[i], o);
	}
	m = ask(1).x;
	int now = -1;
	for (int i = m; i; i--)
		for (int j : e[i])
			if (b[j] >= now) {
				if (k <= c[j]) {
					v[j] = 1, now = b[j];
					break;
				} else k -= c[j];
			}
	print(n - m);
	for (int i = 1; i <= n; i++)
		if (!v[i]) print(i);
	return 0;
}

The Cow Gathering

显然每次只能删叶子。

对于点 ii，考虑以 ii 为根的内向树加上限制构成的图，若图无环则可以为最后一个点，否则不可以，这样就 O(n(n+m))\mathcal O(n(n+m)) 了。

注意到每一条限制会砍掉一棵子树，这棵子树中的点必不可以。

最后剩下的点的答案一定是相同的，O(n+m)\mathcal O(n+m) 判一下即可。

#define Fail { for (int i = 1; i <= n; i++) print(0); return 0; }
const int N = 1e5 + 7;
int n, m, b[N], f[N][21], d[N], rt;
vi e[N];
pi p[N];
bool v[N], ans[N];

void dfs(int x) {
	d[x] = d[f[x][0]] + 1;
	for (int i = 0; f[x][i]; i++)
		f[x][i+1] = f[f[x][i]][i];
	for (int y : e[x])
		if (y != f[x][0])
			f[y][0] = x, dfs(y);
}

inline int jump(int x, int d) {
	while (d) x = f[x][b[d&-d]], d -= d & -d;
	return x;
}

inline bool pd(int x, int y) {
	if (d[y] < d[x]) return 0;
	return jump(y, d[y] - d[x]) == x;
}

void dfs1(int x) {
	if (v[x]) return;
	ans[x] = 1;
	for (int y : e[x])
		if (y != f[x][0]) dfs1(y);
}

namespace work {
	int d[N], c[N];
	vi e[N];
	bool v[N];
	
	void dfs(int x, int f) {
		for (int y : ::e[x])
			if (y != f) d[y] = d[x] + 1, dfs(y, x);
	}
	
	inline bool main(int rt) {
		d[rt] = 1, dfs(rt, 0);
		for (int x = 1; x <= n; x++)
			for (int y : ::e[x])
				if (d[x] > d[y]) e[x].pb(y), ++c[y];
		for (int i = 1; i <= m; i++)
			e[p[i].fi].pb(p[i].se), ++c[p[i].se];
		queue<int> q;
		for (int i = 1; i <= n; i++)
			if (!c[i]) q.push(i);
		while (q.size()) {
			int x = q.front();
			q.pop();
			for (int y : e[x])
				if (!--c[y]) q.push(y);
		}
		for (int i = 1; i <= n; i++)
			if (c[i]) return 0;
		return 1;
	}
}

int main() {
	rd(n, m);
	for (int i = 1, t = 2; t < n; i++, t <<= 1) b[t] = i;
	for (int i = 1, x, y; i < n; i++)
		rd(x, y), e[x].pb(y), e[y].pb(x);
	dfs(rt = 1);
	for (int i = 1; i <= m; i++) {
		rd(p[i].fi, p[i].se);
		if (pd(p[i].fi, p[i].se)) {
			int x = jump(p[i].se, d[p[i].se] - d[p[i].fi] - 1);
			if (pd(rt, x)) rt = x;
			else if (!pd(x, rt)) Fail;
		} else {
			if (pd(rt, p[i].fi)) {
				if (rt == p[i].fi) Fail;
				v[p[i].fi] = 1;
			} else if (pd(p[i].fi, rt)) Fail;
		}
	}
	if (work::main(rt)) {
		dfs1(rt);
		for (int i = 1; i <= n; i++) print(ans[i]);
	} else Fail;
	return 0;
}

2019 January Contest

Redistricting

线段树优化 DP，时间复杂度 O(nlog⁡n)\mathcal O(n \log n)。

const int N = 3e5 + 7, inf = 1e9;
int n, k, a[N], f[N];
char s[N];

struct SGT {
	struct T {
		int l, r, x;
	} t[N<<3|1];
	multiset<int> st[N<<1|1];

	inline void update(int p) {
		t[p].x = min(t[ls].x, t[rs].x);
	}

	void build(int p, int l, int r) {
		t[p].l = l, t[p].r = r;
		if (l == r) return t[p].x = inf, void();
		build(ls, l, md), build(rs, md + 1, r);
		update(p);
	}

	void ins(int p, int x, int k) {
		if (t[p].l == t[p].r) {
			st[x].insert(k);
			t[p].x = *st[x].begin();
			return;
		}
		ins(x <= md ? ls : rs, x, k);
		update(p);
	}

	void del(int p, int x, int k) {
		if (t[p].l == t[p].r) {
			st[x].erase(st[x].find(k));
			t[p].x = st[x].size() ? *st[x].begin() : inf;
			return;
		}
		del(x <= md ? ls : rs, x, k);
		update(p);
	}

	int ask(int p, int l, int r) {
		if (t[p].l >= l && t[p].r <= r) return t[p].x;
		int ret = inf;
		if (l <= md) ret = min(ret, ask(ls, l, r));
		if (r > md) ret = min(ret, ask(rs, l, r));
		return ret;
	}
} t;

int main() {
	rd(n, k), rds(s, n);
	for (int i = 1; i <= n; i++) a[i] = a[i-1] + (s[i] == 'G');
	for (int i = 0; i <= n; i++) a[i] = 2 * a[i] - i + n + 1;
	t.build(1, 1, n * 2 + 2);
	t.ins(1, a[0], 0);
	for (int i = 1; i <= n; i++) {
		if (i > k) t.del(1, a[i-k-1], f[i-k-1]);
		f[i] = min(t.ask(1, 1, a[i]) + 1, t.ask(1, a[i] + 1, n * 2 + 2));
		t.ins(1, a[i], f[i]);
	}
	print(f[n]);
	return 0;
}

Exercise Route

两条非树边合法当且仅当它们在树上的路径有边交。

考虑如何计数，首先把一条路径从 LCA 处断开，对两段分别计数，再减去同时与两段有交的个数。

后者很好算，考虑如何计算前者。

对于一条祖先到孩子的路径 PP，与其有交的路径个数为祖先在 PP 孩子之上的数量减去孩子在 PP 祖先之上的数量。

那么树上差分一下就好了。

Train Tracking 2

先考虑所有限制都相同的情况。

设大于限制的数有 xx 个，限制的区间长度为 kk。

考虑 DP，设 fif_i 表示 ii 个数的答案，则有 fi=(x+1)fi−1−xkfi−k−1f_i = (x+1)f_{i-1} - x^kf_{i-k-1}。

解释一下就是，第 ii 个数有 x+1x+1 种填法，而其中 i−k+1∼ii-k+1\sim i 都大于限制的情况不合法，而在这种情况下 i−ki-k 处必须等于限制。

现在考虑限制不同的情况，若相邻两个限制不同，一定可以确定一个数。

对每一个相同限制的段，去掉确定的数之后计算即可。

const int N = 1e5 + 7, inf = 1e9;
int n, k, a[N];
modint f[N], ans = 1;

inline modint calc(modint x, int n) {
	modint w = x ^ k;
	f[0] = f[1] = 1;
	for (int i = 2; i <= n; i++)
		f[i] = (x + 1) * f[i-1] - (i - k - 1 >= 0 ? w * f[i-k-1] : 0);
	return f[n];
}

int main() {
	rd(n, k), rda(a, n + 1 - k);
	for (int i = 1; i <= n + 1 - k; i++) a[i] = inf - a[i];
	for (int i = 1, j = 1; i <= n + 1 - k; i = ++j) {
		while (j < n - k + 1 && a[j+1] == a[i]) ++j;
		int m = j - i + k + 1;
		if (i != 1 && a[i-1] < a[i]) m -= k;
		if (j != n - k + 1 && a[j+1] < a[i]) m -= k;
		if (m > 1) ans = 1ll * ans * calc(a[i], m);
	}
	print(ans);
	return 0;
}

2019 February Contest

Cow Dating

推一下式子就会发现，答案就是对于每个 ll 找到最近的 rr 满足 ∑i=lrpi1−pi≥1\sum_{i=l}^r \frac{p_i}{1-p_i} \ge 1，然后用 (∏i=lr(1−pi))(∑i=lrpi1−pi)\left(\prod_{i=l}^r(1-p_i)\right)\left(\sum_{i=l}^r \frac{p_i}{1-p_i}\right) 去更新答案。

two pointers 即可，时间复杂度 O(n)\mathcal O(n)。

const int N = 1e6 + 7;
int n;
ld a[N], A = 1, B, ans;

int main() {
	rd(n);
	for (int i = 1, x; i <= n; i++) rd(x), a[i] = x / 1e6;
	for (int l = 1, r = 0; l <= n; A /= 1 - a[l], B -= a[l] / (1 - a[l]), l++) {
		while (r < n && B < 1) ++r, A *= 1 - a[r], B += a[r] / (1 - a[r]);
		ans = max(ans, A * B);
	}
	print((int)(ans * 1e6));
	return 0;
}

Moorio Kart

这题目说了个啥......

读一年没读懂题目系列，扔了。

Mowing Mischief

题目太神仙了，先咕咕咕着。

2019 US Open Contest

Compound Escape

咕。

Valleys

咕。

标签：DP、Two Pointers、凸包、前缀和/差分、单调栈、树状数组、线段树、组合计数

评论

    填写昵称即可留言。评论经站主审核后公开，请勿提交私人信息。

    正在连接评论服务…