2019/10/24 CSP-S 模拟

T1 tom

题意：

考虑一定是属于\(a\)的在一坨，属于\(b\)的在一坨，找到这条连接\(a\)和\(b\)的边，然后分别直接按\(dfs\)序染色即可

注意属于\(a\)的连通块或属于\(b\)的连通块可能在\(dfs\)树上不都体现为一棵完整的子树，所以需要都判断一下

#include<bits/stdc++.h>

#define N (200000 + 10)

using namespace std;

inline int read() {

	int cnt = 0, f = 1; char c = getchar();

	while (!isdigit(c)) {if (c == '-') f = -f; c = getchar();}

	while (isdigit(c)) {cnt = (cnt << 3) + (cnt << 1) + (c ^ 48); c = getchar();}

	return cnt * f;

}

int n, a, b, x, y, fa[N], siz[N], id[N], val;

int first[N], to[N], nxt[N], tot;

void add (int x, int y) {nxt[++tot] = first[x], first[x] = tot, to[tot] = y;}

void get_siz(int x, int father) {

	siz[x] = 1; fa[x] = father;

	for (register int i = first[x]; i; i = nxt[i]) {

		int v = to[i];

		if (v == father) continue;

		get_siz(v, x), siz[x] += siz[v];

	}

}

void print(int x, int fa, int d) {

	for (register int i = first[x]; i; i = nxt[i]) {

		int v = to[i];

		if (v == fa) continue;

		print(v, x, d);

	}

	val += d;

	id[x] = val;

}

void work () {

	bool ok = 0;

	get_siz(1, 0);

	for (register int i = 1; i <= n; ++i)

		if (siz[i] == a) {

			val = 0;

			print(i, fa[i], 1);

			val = 0;

			print(fa[i], i, -1);

			ok = 1;

		} else if (siz[i] == b) {

			val = 0;

			print(i, fa[i], -1);

			val = 0;

			print(fa[i], i, 1);

			ok = 1;

		}

	if (!ok) puts("-1");

	else for (register int i = 1; i <= n; ++i) printf("%d ", id[i]);

	putchar('\n');

}

int main() {

	n = read(), a = read(), b = read();

	for (register int i = 1; i <= n - 1; ++i) {

		x = read(), y = read();

		add(x, y), add(y, x);

	}

	work();

	return 0;

}

T2 Jerry

首先能发现一个性质，括号结构最多嵌套两层

如果有三层的嵌套可以这样化简

( ( ( ) ) )

↓

( ( ) ( ) )

符号反三层和反一层等价

设\(f[i][0~2]\)表示当前处理到第\(i\)位，前面有\(0/1/2\)个未配对的左括号

在当前数\(>0\)时状态转移考虑补右括号，\(<0\)时考虑先强行在“-”后补一个左括号（如果对答案不优，自然会在后面的更新中去掉：-(a) + b），再进行转移

具体方程看代码

#include<bits/stdc++.h>

#define int long long

using namespace std;

inline int read() {

	int cnt = 0, f= 1;char c = getchar();

	while (!isdigit(c)) {if (c == '-') f = -f; c = getchar();}

	while (isdigit(c)) {cnt = (cnt << 3) + (cnt << 1) + (c ^ 48); c = getchar();}

	return cnt * f;

}

int T, n, a[500010], dp[500010][3];

signed main() {

	T = read();

	while (T--) {

		n = read();

		for (register int i = 1; i <= n; ++i) a[i] = read();

		dp[0][0] = 0, dp[0][1] = dp[0][2] = -1e18;

		for (register int i = 1; i <= n; ++i)

			if (a[i] > 0) {

				dp[i][0] = max(max(dp[i - 1][0] + a[i], dp[i - 1][1] + a[i]), dp[i - 1][2] + a[i]);

				dp[i][1] = max(dp[i - 1][1] - a[i], dp[i - 1][2] - a[i]);

				dp[i][2] = dp[i - 1][2] + a[i];

			} else {

				dp[i][0] = -1e18;

				dp[i][1] = max(max(dp[i - 1][0] + a[i], dp[i - 1][1] + a[i]), dp[i - 1][2] + a[i]);

				dp[i][2] = max(dp[i - 1][1] - a[i], dp[i - 1][2] - a[i]);

			}

		printf("%lld\n", max(max(dp[n][0], dp[n][1]), dp[n][2]));

	}

	return 0;

}

T3太麻烦了不想写，先咕了

巴特西

2019/10/24 CSP-S 模拟

T1 tom

T2 Jerry

最新文章

热门文章