Codeforces Round #635 (Div. 1) 题解

Codeforces Round #635 (Div. 1)

Linova and Kingdom

设深度为 $d$，子树大小为 $s$，点 $i$ 对答案的贡献为 $d_i - s_i + 1$，从大到小贪心就好了。

const int N = 2e5 + 7;
int n, k, d[N], s[N];
vi e[N];
ll ans;
pq<pi> q;

void dfs(int x, int f) {
	s[x] = 1;
	for (int y : e[x])
		if (y != f) {
			d[y] = d[x] + 1;
			dfs(y, x);
			s[x] += s[y];
			q.push(mp(d[y] - s[y] + 1, y));
		}
}

int main() {
	rd(n, k);
	for (int i = 1, x, y; i < n; i++)
		rd(x, y), e[x].pb(y), e[y].pb(x);
	dfs(1, 0);
	while (k--) {
		ans += q.top().fi;
		q.pop();
	}
	print(ans);
	return 0;
}

Xenia and Colorful Gems

乱搞，让三个数尽可能接近就行了。

const int N = 1e5 + 7;
int x, y, z;
ll a[N], b[N], c[N], ans;

inline void upd(ll x, ll y, ll z) {
	ans = min(ans, (x - y) * (x - y) + (y - z) * (y - z) + (z - x) * (z - x));
}

inline void work(ll *a, int x, ll *b, int y, ll *c, int z) {
	for (int i = 1, j, k; i <= x; i++) {
		j = lower_bound(b + 1, b + y + 1, a[i]) - b;
		if (j <= y) {
			k = lower_bound(c + 1, c + z + 1, (a[i] + b[j]) >> 1) - c;
			if (k <= z) upd(a[i], b[j], c[k]);
			if (k > 1) upd(a[i], b[j], c[k-1]);
		}
		if (j > 1) {
			k = lower_bound(c + 1, c + z + 1, (a[i] + b[j-1]) >> 1) - c;
			if (k <= z) upd(a[i], b[j-1], c[k]);
			if (k > 1) upd(a[i], b[j-1], c[k-1]);
		}
	}
}

inline void solve() {
	rd(x, y, z), rda(a, x), rda(b, y), rda(c, z);
	sort(a + 1, a + x + 1);
	sort(b + 1, b + y + 1);
	sort(c + 1, c + z + 1);
	ans = 4e18;
	work(a, x, b, y, c, z);
	work(b, y, c, z, a, x);
	work(c, z, a, x, b, y);
	print(ans);
}

int main() {
	int T;
	rd(T);
	while (T--) solve();
	return 0;
}

Kaavi and Magic Spell

正着比较难考虑，反着就容易了。

设 $f_{i,j}$ 表示考虑 $s^r$ 的前 $i$ 个字符，覆盖了要求目标字符串的前 $j$ 个字符和后 $i-j$ 个字符的方案数。

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

const int N = 3e3 + 7;
int n, m;
char s[N], t[N];
modint f[N][N], ans;

int main() {
	rds(s, n), rds(t, m);
	reverse(s + 1, s + n + 1);
	for (int i = 1; i <= n; i++) {
		if (n - i + 1 >= m) f[i-1][0] += 1;
		for (int j = 0; j < i; j++) {
			if (s[i] == t[j+1] || !t[j+1]) f[i][j+1] += f[i-1][j];
			if (s[i] == t[n-i+1+j] || !t[n-i+1+j]) f[i][j] += f[i-1][j];
		}
	}
	for (int j = 0; j <= n; j++) ans += f[n][j];
	print(ans);
	return 0;
}

Yui and Mahjong Set

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

Chiori and Doll Picking

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

Journey

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