https://codeforces.com/contest/1120

A. Diana and Liana

 

题意：m个数，k个一组，取前n组，要求删除一些数，使得取的n组中至少一组满足存在给定的需要的数。删除的数个数任意，但必须剩下至少n组。

枚举

遍历每个位置，考虑从它开始构造一组满足条件的数。找到它开始的最短的满足含有所有需要的数的区间。再考虑删除前面的数，使得这个位置成为一组的开头，且在n组内，再删除组内的数，直到个数为k。判断删除后剩下至少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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const int N = 5e5 + 10;
int m, k, n, s;
int a[N], b[N], nx[N];
vector<int>vc[N];
int main() {
	scanf("%d%d%d%d", &m, &k, &n, &s);
	for (int i = 1; i <= m; i++)scanf("%d", &a[i]), vc[a[i]].push_back(i);
	for (int i = 1; i <= s; i++) {
		int x;
		scanf("%d", &x);
		b[x]++;
	}
	int mx = 0;
	for (int i = 1; i <= 500000; i++) {
		if (b[i]) {
			if ((int)vc[i].size() >= b[i])mx = max(mx, vc[i][b[i] - 1]);
			else {
				mx = INF; break;
			}
		}
	}
	nx[1] = mx;
	for (int i = 2; i <= m; i++) {
		if (b[a[i - 1]]) {
			int p = lower_bound(vc[a[i - 1]].begin(), vc[a[i - 1]].end(), i) - vc[a[i - 1]].begin();
			p = p + b[a[i - 1]] - 1;
			if (p >= (int)vc[a[i - 1]].size())nx[i] = INF;
			else nx[i] = max(mx, vc[a[i - 1]][p]);
			mx = max(mx, nx[i]);
		}
		else nx[i] = mx;
	}
	for (int i = 1; i <= m; i++) {
		int p = 0, t = 0;
		if (i > n*k)p = t = i - 1 - n*k;
		else p = t = (i - 1) % k;
		p += max(0, nx[i] - i + 1 - k);
		if (m - p >= n * k) {
			printf("%d\n", p);
			for (int j = 1; j <= t; j++)printf("%d ", j);
			int cnt = nx[i] - i + 1 - k;
			for (int j = i; j <= nx[i] && cnt > 0; j++) {
				if (b[a[j]] <= 0) {
					printf("%d ", j);
					cnt--;
				}
				else b[a[j]]--;
			}
			return 0;
		}
	}
	puts("-1");
	return 0;
}

 

C. Compress String

 

题意：从空字符串开始，花费a加入一个字符，或者花费b加入一个字符串，且加入的字符串是前面字符串的子串。问构造出给定串的最小花费。

容易想到dp，问题在于怎么找到是前面字符串子串的串。

最重要的一点是，要发现 dp[i]dp[i] 一定是单调非递减的，因为假设 dp[i]dp[i] 由 dp[k]+bdp[k]+b 得到，也就是说 s[k+1,i]s[k+1,i] 是 s[1,k]s[1,k] 的子串，设有一个 j<ij<i, 那么 s[k+1,j]s[k+1,j] 是 s[k+1,is[k+1,i] 的子串，则一定也是 s[1,k]s[1,k] 的子串，所以 dp[j]dp[j] 也一定可以由 dp[k]+bdp[k]+b 得到，则 dp[j]dp[j] 一定不大于 dp[i]dp[i]。造成这样的原因还是因为每次操作不论长度，花费都可以一样。

所以 dp[i]=dp[j]+bdp[i]=dp[j]+b 时，一定是 jj 越小越好，那么就是一定要找当前串最长的属于前面串子串的后缀。

所以 r[i][j]r[i][j] 维护串s的长为i的前缀和长为j的前缀的最长公共后缀，转移方程也容易得到。

还要注意两个串不能相交，所以遍历时不能直接用r值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const int N = 5e3 + 10;
int n, a, b;
char s[N];
int dp[N], r[N][N];
int main() {
	scanf("%d%d%d", &n, &a, &b);
	scanf("%s", s + 1);
	memset(dp, 0x3f, sizeof(dp));
	dp[1] = a;
	for (int i = 2; i <= n; i++) {
		dp[i] = dp[i - 1] + a;
		for (int j = 1; j < i; j++) {
			r[i][j] = (s[i] == s[j] ? r[i - 1][j - 1] + 1 : 0);
			int len = min(r[i][j], i - j);
			dp[i] = min(dp[i], dp[i - len] + b);
		}
	}
	printf("%d\n", dp[n]);
	return 0;
}

 

D. Power Tree

 

题意：给定一棵1为根的树，每点有点权，初始给每个叶子赋值，并选一些点组成点集。每次操作选择点集中一点，把它子树中的叶子的值都加或减任意数，使得不论给每个叶子赋初值多少，都能通过有限次操作使得最终所有叶子值为0。每次操作的花费为操作的点的点权，要求输出最小花费，对于一个点，若存在一种最优方案包含它，则输出。

树形dp/最小生成树+差分

dp[u][0/1]dp[u][0/1] 表示节点u的子树中所有叶子都被覆盖/未都被覆盖。

都被覆盖，有两种可能：选节点u且恰好一个子节点未被覆盖，或者所有子节点都被覆盖。

未被覆盖，则恰好一个子节点未被覆盖。

最终结果为 dp[1][0]dp[1][0]。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void dfs(int u, int _fa) {
	if ((int)G[u].size() == 1 && u != 1) {
		dp[u][0] = a[u];
		dp[u][1] = 0;
		return;
	}
	for (int v : G[u]) {
		if (v == _fa)continue;
		dfs(v, u);
		sum[u] += dp[v][0];
	}
	dp[u][0] = sum[u]; dp[u][1] = inf;
	for (int v : G[u]) {
		if (v == _fa)continue;
		dp[u][0] = min(dp[u][0], sum[u] - dp[v][0] + dp[v][1] + a[u]);
		dp[u][1] = min(dp[u][1], sum[u] - dp[v][0] + dp[v][1]);
	}
}

但是要输出方案实在是太烦了，最后还是没写出来。

 

把所有叶子按照dfs序排序，则对于节点u操作相当于对于一个区间内的叶子同时操作。

所以要考虑差分，每次在差分数组上 LL 上 +t+t，在 R+1R+1 上$ -t$，最终必须要能够对任意两个 (L,R+1)(L,R+1) 操作，所以再把每次操作看作从 LL 向 R+1R+1 连一条边权为 a[i]a[i] 的无向边，最终必须要任意连点联通，求最小花费，也就是最小生成树。

再考虑输出方案。如果一条边可能在某个最小生成树上，则它代表的操作的点就要输出。

把边排序后，相同边权的边如果加入后不会有环，则可能在最小生成树上，并且求最小生成树时相同边权的边加入的顺序可能影响最终的连边，但是不会影响集合的联通性，即无论怎么加边，应该在同一集合的点一定在同一集合，所以加边顺序不会影响后面的判断。

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const ll inf = 0x3f3f3f3f3f3f3f3f;
const int N = 2e5 + 10;
int n;
int a[N];
ll ans;
vector<int>G[N];
int L[N], R[N], clk, ok[N], cnt;
struct E
{
	int u, v, w, rt;
	bool operator<(const E& a)const {
		return w < a.w;
	}
};
vector<E>es;
void dfs(int u, int _fa) {
	L[u] = INF, R[u] = 0;
	if ((int)G[u].size() == 1 && u != 1) {
		L[u] = R[u] = ++clk;
	}
	for (int v : G[u]) {
		if (v == _fa)continue;
		dfs(v, u);
		L[u] = min(L[u], L[v]);
		R[u] = max(R[u], R[v]);
	}
	es.push_back(E{ L[u],R[u] + 1,a[u],u });
}
int par[N];
void init(int n) { for (int i = 0; i <= n; i++)par[i] = i; }
int find(int x) { return par[x] == x ? x : par[x] = find(par[x]); }
void uni(int x, int y) { par[find(x)] = find(y); }
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)scanf("%d", &a[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);
	init(clk);
	sort(es.begin(), es.end());
	for (int i = 0, j = 0; i < n; i = j) {
		while (j < n&&es[j].w == es[i].w)j++;
		for (int k = i; k < j; k++) {
			if (find(es[k].u) != find(es[k].v))ok[es[k].rt] = 1, cnt++;
		}
		for (int k = i; k < j; k++) {
			if (find(es[k].u) != find(es[k].v)) {
				uni(es[k].u, es[k].v);
				ans += es[k].w;
			}
		}
	}
	printf("%lld %d\n", ans, cnt);
	for (int i = 1; i <= n; i++)if (ok[i])printf("%d ", i);
	puts("");
	return 0;
}