Codeforces Round #612 (Div. 1) 题解

Codeforces Round #612 (Div. 1)

Garland

DP 题做成贪心 WA 无数次，不愧是我。

const int N = 107;
int n, a[N], f[N][N][N];

inline void upd(int &x, int y) {
	x = min(x, y);
}

int main() {
	rd(n);
	if (n == 1) return print(0), 0;
	for (int i = 1; i <= n; i++) rd(a[i]);
	memset(f, 0x3f, sizeof(f));
	if (a[1]) {
		if (a[1] & 1) {
			upd(f[1][0][a[1]], 0);
		} else {
			upd(f[1][1][a[1]], 0);
		}
	} else {
		for (a[1] = 1; a[1] <= n; a[1]++) {
			if (a[1] & 1) {
				upd(f[1][0][a[1]], 0);
			} else {
				upd(f[1][1][a[1]], 0);
			}
		}
	}
	for (int i = 2; i <= n; i++) {
		for (int j = 0; j <= min(i - 1, n >> 1); j++)
			for (int k = 1; k <= n; k++) {
				if (a[i]) {
					if (a[i] & 1) {
						if (i - 1 - j == n - (n >> 1)) continue;
						upd(f[i][j][a[i]], f[i-1][j][k] + ((k ^ a[i]) & 1));
					} else {
						if (j == (n >> 1)) continue;
						upd(f[i][j+1][a[i]], f[i-1][j][k] + ((k ^ a[i]) & 1));
					}
				} else {
					for (a[i] = 1; a[i] <= n; a[i]++) {
						if (a[i] & 1) {
							if (i - 1 - j == n - (n >> 1)) continue;
							upd(f[i][j][a[i]], f[i-1][j][k] + ((k ^ a[i]) & 1));
						} else {
							if (j == (n >> 1)) continue;
							upd(f[i][j+1][a[i]], f[i-1][j][k] + ((k ^ a[i]) & 1));
						}
					}
					a[i] = 0;
				}
			}
	}
	int ans = 0x3f3f3f3f;
	for (int i = 1; i <= n; i++) ans = min(ans, f[n][n>>1][i]);
	print(ans);
	return 0;
}

Numbers on Tree

sb 构造题，不特判 WA 到死。

const int N = 2e3 + 7;
int n, a[N], rt, ans[N];
vi e[N], p[N];

void dfs(int x) {
	for (int y : e[x]) {
		dfs(y);
		for (auto z : p[y]) p[x].pb(z);
	}
	if (a[x] > (int)p[x].size()) prints("NO"), exit(0);
	vi o;
	while ((int)p[x].size() > a[x]) o.pb(p[x].back()), p[x].pop_back();
	p[x].pb(x);
	while (o.size()) p[x].pb(o.back()), o.pop_back();
}

int main() {
	rd(n);
	for (int i = 1; i <= n; i++) {
		int f;
		rd(f), rd(a[i]);
		if (f) e[f].pb(i);
		else rt = i;
	}
	dfs(rt);
	for (int i = 1; i <= n; i++) ans[p[rt][i-1]] = i;
	prints("YES");
	for (int i = 1; i <= n; i++) print(ans[i], " \n"[i==n]);
	return 0;
}

Madhouse

一道很屑的交互题。

LCC

线段树维护矩阵套路题。

Fedya the Potter Strikes Back

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

Harry The Potter

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