https://codeforces.com/contest/1336

A. Linova and Kingdom

 

题意：有n个节点的树，选k个节点作为特殊点，每个特殊点的舒适度为它到根的路径上非特殊点的个数，问怎么选使得所有特殊点的舒适度之和最大。

贪心

一定只有当节点的所有子孙节点都被选了，才会选它，选择一个节点，会使得舒适度增加它的深度，且它的所有子孙节点舒适度都-1，所以要贪心选择深度-子孙节点数最大的节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const int N = 2e5 + 10;
int n, k;
vector<int>G[N];
int siz[N], dep[N], a[N], fa[N];
void dfs(int u, int _fa, int de) {
	fa[u] = _fa;
	dep[u] = de;
	siz[u] = 1;
	for (int v : G[u]) {
		if (v == _fa)continue;
		dfs(v, u, de + 1);
		siz[u] += siz[v];
	}
}
bool cmp(int x, int y) {
	return dep[x] - siz[x] > dep[y] - siz[y];
}
bool vis[N];
void dfs2(int u, int _fa) {
	vis[u] = 1;
	for (int v : G[u]) {
		if (v != _fa)dfs2(v, u);
	}
}
ll ans;
int main() {
	scanf("%d%d", &n, &k);
	for (int i = 1; i <= n; i++)a[i] = i;
	for (int i = 1; i < n; i++) {
		int u, v;
		scanf("%d%d", &u, &v);
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dfs(1, 0, 0);
	sort(a + 1, a + n + 1, cmp);
	for (int i = k; i >= 1; i--) {
		if (!vis[a[i]]) {
			ans += 1ll * dep[a[i]] * siz[a[i]];
			dfs2(a[i], fa[a[i]]);
		}
	}
	printf("%lld\n", ans);
	return 0;
}

 

B. Xenia and Colorful Gems

 

题意：有红绿蓝三种糖，每种有一定个数，每个糖都有值，要红绿蓝各选一个，使得三个糖，满足 (x−y)2+(y−z)2+(z−x)2(x-y)^2+(y-z)^2+(z-x)^2 最小。

x，y，z先确定最小或最大的都不好选，但是如果先确定了中间的，那策略只有只有一个了，都尽量向中间的靠近。

所以可以枚举一个作为中间的，再二分找到最小，最大的。

注意颜色有关系，所以要枚举所有排列情况。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;
const ll inf = 2e18;
int T, nr, ng, nb;
ll r[N], g[N], b[N];
ll dist(ll a, ll b, ll c) {
	return (a - b)*(a - b) + (a - c)*(a - c) + (b - c)*(b - c);
}
ll cal(ll* a, ll* b, ll* c, int n1, int n2, int n3) {
	ll ans = inf;
	for (int i = 0; i < n1; i++) {
		ll x = a[i];
		ll y = b[max(0, upper_bound(b, b + n2, x) - b - 1)];
		ll z = c[min(n3 - 1, lower_bound(c, c + n3, x) - c)];
		ans = min(ans, dist(x, y, z));
	}
	return ans;
}
int main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%d%d%d", &nr, &ng, &nb);
		for (int i = 0; i < nr; i++)scanf("%lld", &r[i]);
		for (int i = 0; i < ng; i++)scanf("%lld", &g[i]);
		for (int i = 0; i < nb; i++)scanf("%lld", &b[i]);
		sort(r, r + nr);
		sort(g, g + ng);
		sort(b, b + nb);
		ll ans = inf;
		ans = min(ans, cal(r, g, b, nr, ng, nb));
		ans = min(ans, cal(r, b, g, nr, nb, ng));
		ans = min(ans, cal(b, r, g, nb, nr, ng));
		ans = min(ans, cal(b, g, r, nb, ng, nr));
		ans = min(ans, cal(g, r, b, ng, nr, nb));
		ans = min(ans, cal(g, b, r, ng, nb, nr));
		printf("%lld\n", ans);
	}
	return 0;
}

 

C. Kaavi and Magic Spell

 

题意：有字符串S和T，长为n和m，和一个空串A，要从S中删掉首，加到空串首或者尾，使得最终T为A的前缀，问有几种操作序列。

区间dp

dp[i][j]dp[i][j] 表示凑出T串 ii 到 jj 的操作序列数。

遍历S串，到第i位一定有i-1位加到A串里了，所以第i位，遍历所有长度为i-1的dp，再看能不能把这一位加到首或者尾，来扩展到长度为i。

如果长为i-1的串要拓展的位置大于m，那任何字符都可以加入，否则要判断S[i]和T对应位置是否相等。

最终结果就是 dp[1][m]+dp[1][m+1]+⋯+dp[1][n]dp[1][m]+dp[1][m+1]+\cdots+dp[1][n]。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int N = 2e5 + 10;
const int INF = 0x3f3f3f3f;
const ll mod = 998244353;
char s[N], t[N];
int n, m;
ll dp[3010][3010], ans;
int main() {
	scanf("%s%s", s + 1, t + 1);
	n = strlen(s + 1); m = strlen(t + 1);
	for (int i = 1; i <= n; i++) {
		if (i > m || t[i] == s[1])dp[i][i] = 2ll;
	}
	for (int i = 2; i <= n; i++) {
		for (int L = 1, R; L <= n - i + 2; L++) {
			R = L + i - 2;
			if (L > 1 && (L - 1 > m || s[i] == t[L - 1]))
				dp[L - 1][R] = (dp[L - 1][R] + dp[L][R]) % mod;
			if (R < n && (R + 1 > m || s[i] == t[R + 1]))
				dp[L][R + 1] = (dp[L][R + 1] + dp[L][R]) % mod;
		}
	}
	for (int i = m; i <= n; i++)ans = (ans + dp[1][i]) % mod;
	printf("%lld\n", ans);
	return 0;
}