https://codeforces.com/contest/1199

E. Matching vs Independent Set

 

题意：给定一个3n个节点，m条边的无向图，求一个包含n条边的匹配，或包含n个点的独立集。

n条边的匹配有2n个点，n个点的独立集有n个点，加起来刚好3n个点，自然要想到两种可以完全分开来。

贪心

直接找匹配，如果边数大于等于n，输出。

否则，剩下的不再匹配里的点之间一定没有边，那就是一个独立集。点数一定大于等于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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const int N = 5e5 + 10;
int T, n, m;
int vis[N];
vector<int>vc;
typedef pair<int, int>pii;
pii e[N];
int main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%d%d", &n, &m);
		fill(vis, vis + 3 * n + 1, 0);
		vc.clear();
		for (int i = 1; i <= m; i++) {
			scanf("%d%d", &e[i].first, &e[i].second);
		}
		for (int i = 1; i <= m; i++) {
			if (!vis[e[i].first] && !vis[e[i].second]) {
				vis[e[i].first] = vis[e[i].second] = 1;
				vc.push_back(i);
			}
		}
		if ((int)vc.size() >= n) {
			puts("Matching");
			for (int i = 0; i < n; i++)printf("%d%c", vc[i], " \n"[i == n - 1]);
		}
		else {
			puts("IndSet");
			int cnt = 0;
			for (int i = 1; i <= 3 * n&&cnt < n; i++) {
				if (!vis[i]) { printf("%d%c", i, " \n"[cnt++ == n - 1]); }
			}
		}
	}
	return 0;
}

F. Rectangle Painting 1

 

题意：给定n*n的网格，每格初始为黑或白，每次可以选一个矩形区域全涂白，花费为矩形长宽最大值，问全变白的最小花费。1≤n≤501\leq n\leq50

二维区间dp

如果区域里有黑色，则需要涂色，第一种操作是直接全涂白，第二种是把每个区域纵向切开或横向切开，分成两个区域，结果就是两个区域的dp之和。

至于为什么可以直接加起来得到答案，可以分类讨论一下，以纵向切开为例，可能两边都以长为最长边，则加起来一定大于直接全涂白；若两边都以宽为最长边，也类似；若一个长一个宽，则和也同样小于大矩形的长或宽。

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
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int INF = 0x3f3f3f3f;
const int N = 5e5 + 10;
int n;
int dp[60][60][60][60], sum[60][60];
int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			char c;
			scanf(" %c", &c);
			if (c == '#')sum[i][j]++;
		}
	}
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
	for (int len1 = 1; len1 <= n; len1++) {
		for (int len2 = 1; len2 <= n; len2++) {
			for (int i = 1; i + len1 - 1 <= n; i++) {
				for (int j = 1; j + len2 - 1 <= n; j++) {
					int u = i + len1 - 1, v = j + len2 - 1;
					if (sum[u][v] - sum[i - 1][v] - sum[u][j - 1] + sum[i - 1][j - 1] == 0)
						continue;
					dp[i][j][u][v] = max(len1, len2);
					for (int mid = i; mid < u; mid++)
						dp[i][j][u][v] = min(dp[i][j][u][v], dp[i][j][mid][v] + dp[mid + 1][j][u][v]);
					for (int mid = j; mid < v; mid++)
						dp[i][j][u][v] = min(dp[i][j][u][v], dp[i][j][u][mid] + dp[i][mid + 1][u][v]);
				}
			}
		}
	}
	printf("%d\n", dp[1][1][n][n]);
	return 0;
}