Codeforces Round #614 (Div. 1) 题解

Codeforces Round #614 (Div. 1)

NEKO's Maze Game

动态维护有多少对格子可以阻碍 $(1,1)$ 和 $(2,n)$ 相连，如果存在则意味着 No，否则为 Yes，模拟即可。

const int N = 1e5 + 7;
int n, q, a[2][N], ans;

inline int pd(int x, int y) {
	if (!a[x][y]) return 0;
	return a[x^1][y-1] + a[x^1][y] + a[x^1][y+1];
}

int main() {
	rd(n), rd(q);
	for (int i = 1; i <= q; i++) {
		int x, y;
		rd(x), rd(y);
		--x;
		ans -= pd(x, y);
		a[x][y] ^= 1;
		ans += pd(x, y);
		prints(ans ? "No" : "Yes");
	} 
	return 0;
}

Aroma's Search

由于 $a > 1$ ，因此范围内的点只有 $\mathcal O(\log w)$ 个，那么枚举选的第一个点和之后的方向即可。

const int N = 107;
int n, ans;
ll ax, ay, bx, by, xs, ys, t, mx, my, x[N], y[N];

int main() {
	rd(x[0]), rd(y[0]), rd(ax), rd(ay), rd(bx), rd(by);
	rd(xs), rd(ys), rd(t), mx = xs + t, my = ys + t;
	while (x[n] <= mx && y[n] <= my)
		++n, x[n] = x[n-1] * ax + bx, y[n] = y[n-1] * ay + by;
	for (int i = 0; i < n; i++)
		for (int j = -1; j <= 1; j += 2) {
			int cnt = 0, now = i;
			ll T = t;
			t -= abs(xs - x[i]) + abs(ys - y[i]);
			while (t >= 0) {
				++cnt;
				now += j;
				if (now < 0 || now >= n) break;
				t -= abs(x[now-j] - x[now]) + abs(y[now-j] - y[now]);
			}
			ans = max(ans, cnt);
			t = T;
		}
	print(ans);
	return 0;
}

Xenon's Attack on the Gangs

考虑 dp，设 $f_{i,j}$ 表示路径 $(i,j)$ 上的最大贡献，转移就是向两端各延伸一个点，类似于树上区间 dp，时间复杂度 $\mathcal O(n^2)$ 。

const int N = 3e3 + 7;
int n, fa[N], s[N], l[N], r[N], k, p[N];
vi e[N];
ll f[N][N], ans;

void dfs2(int x, int fa, int X, int Y) {
	for (auto y : e[x])
		if (y != fa) {
			f[y][X] = f[X][y] = max(f[X][x], f[Y][y]) + s[y] * (n - s[Y]);
			dfs2(y, x, X, Y);
		}
}

void dfs1(int x, int fa) {
	s[x] = 1, l[x] = ++k, p[k] = x;
	for (auto y : e[x])
		if (y != fa) {
			::fa[y] = x;
			dfs1(y, x), s[x] += s[y];
			f[y][x] = f[x][y] = s[y] * (n - s[y]);
			dfs2(y, x, x, y);
		}
	r[x] = k;
	for (auto y : e[x])
		if (y != fa)
			for (auto z : e[x])
				if (z != fa && z != y)
					for (int i = l[y]; i <= r[y]; i++)
						for (int j = l[z]; j <= r[z]; j++)
							f[p[i]][p[j]] = f[p[j]][p[i]] = max(f[p[i]][::fa[p[j]]], f[::fa[p[i]]][p[j]]) + s[p[i]] * s[p[j]];
}

int main() {
	rd(n);
	for (int i = 1, x, y; i < n; i++)
		rd(x), rd(y), e[x].pb(y), e[y].pb(x);
	dfs1(1, 0);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			ans = max(ans, f[i][j]);
	print(ans);
	return 0;
}

Chaotic V.

本题其实很暴力。

主要思路就是，先将点数减小到 $n = 5 \times 10^3$ 。

假设答案为 $1$ ，然后每次往最大的子树走，如果答案能够更优则更新答案，否则输出答案即可。

考虑细节上的问题，第一点是，由于点数太大，图是无法显式建出来的。

如何隐式建图呢？

首先可以将 $1! \sim n!$ 的所有质因数以及幂次数都求出来，具体来说就是求出 $1 \sim n$ 的然后做一个前缀和即可。

然后对于每个 $i$ 建立一个指针 $p_i$ 指向 $i!$ 的最大质因数，特别地如果 $c_i$ （即 $i$ 出现的次数）为零则最大质因数默认为 $1$ 。

那么每次往一棵子树走的时候，动态维护这个指针即可。

接下来考虑时间复杂度。

由于一个点的可重质因子个数是 $\mathcal O(\log n)$ 级别的，因此最多走 $\mathcal O(n \log n)$ 条边。

每走一条边需要均摊 $\mathcal O(n)$ 的时间维护。

总时间复杂度 $\mathcal O(n^2 \log n)$ 。

const int N = 5e3 + 1;
int n, c[N], f[N][N], p[N], s[N];
ll ans, now;

int main() {
	rd(n);
	for (int i = 1, x; i <= n; i++) rd(x), ++c[x];
	for (int i = 2; i < N; i++) {
		memcpy(f[i], f[i-1], sizeof(f[i]));
		for (int j = 2, k = i; j <= k; j++)
			while (k % j == 0) ++f[i][j], k /= j;
	}
	for (int i = 1; i < N; i++)
		if (!c[i]) p[i] = 1;
		else for (int j = 1; j <= i; j++)
			if (f[i][j]) p[i] = j, now += 1ll * f[i][j] * c[i];
	ans = now;
	while (*max_element(p + 1, p + N) > 1) {
		memset(s, 0, sizeof(s));
		for (int i = 0; i < N; i++) s[p[i]] += c[i];
		int o = max_element(s + 1, s + N) - s, w = s[o];
		if (w * 2 <= n || o == 1) break;
		ans = min(ans, now -= w * 2 - n);
		for (int i = 0; i < N; i++) {
			if (p[i] != o) p[i] = 1;
			if (p[i] == 1) continue;
			--f[i][p[i]];
			while (p[i] > 1 && !f[i][p[i]]) --p[i];
		}
	}
	print(ans);
	return 0;
}

Rin and The Unknown Flower

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

Nora's Toy Boxes