Codeforces Round #607 (Div. 1) 题解

Codeforces Round #607 (Div. 1)

Cut and Paste

模拟...

const int N = 1e6 + 7;
int n, x;
char s[N];
modint f[N];

inline void solve() {
	rd(x), rds(s, n), f[0] = n;
	for (int i = 1; i <= x; i++) {
		int c = s[i] - '1', k = f[i-1].x;
		f[i] = f[i-1] + (f[i-1] - i) * c;
		while (c--)
			for (int j = i + 1; j <= k && n < x; j++)
				s[++n] = s[j];
	}
	print(f[x]);
}
 
int main() {
	int T;
	rd(T);
	while (T--) solve();
	return 0;
}

Beingawesomeism

显然答案只可能是 MORTAL 或 $0 \sim 4$，随便判一下就好了。

const int N = 63;
int n, m;
char s[N][N];

inline bool pd() {
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			if (s[i][j] == 'A') return 0;
	return 1;
}

inline bool pd0() {
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			if (s[i][j] == 'P') return 0;
	return 1;
}

inline bool pd1() {
	bool ok = 1;
	for (int i = 1; i <= n; i++)
		if (s[i][1] == 'P') ok = 0;
	if (ok) return 1;
	ok = 1;
	for (int i = 1; i <= n; i++)
		if (s[i][m] == 'P') ok = 0;
	if (ok) return 1;
	ok = 1;
	for (int i = 1; i <= m; i++)
		if (s[1][i] == 'P') ok = 0;
	if (ok) return 1;
	ok = 1;
	for (int i = 1; i <= m; i++)
		if (s[n][i] == 'P') ok = 0;
	if (ok) return 1;
	return 0;
}

inline bool pd4() {
	for (int i = 1; i <= n; i++)
		if (s[i][1] == 'A' || s[i][m] == 'A') return 0;
	for (int i = 1; i <= m; i++)
		if (s[1][i] == 'A' || s[n][i] == 'A') return 0;
	return 1;
}

inline bool pd2() {
	if (s[1][1] == 'A') return 1;
	if (s[1][m] == 'A') return 1;
	if (s[n][1] == 'A') return 1;
	if (s[n][m] == 'A') return 1;
	for (int i = 2; i < n; i++) {
		bool ok = 1;
		for (int j = 1; j <= m; j++)
			if (s[i][j] == 'P') ok = 0;
		if (ok) return 1;
	}
	for (int j = 2; j < m; j++) {
		bool ok = 1;
		for (int i = 1; i <= n; i++)
			if (s[i][j] == 'P') ok = 0;
		if (ok) return 1;
	}
	return 0;
}

inline void solve() {
	rd(n), rd(m);
	for (int i = 1; i <= n; i++) rds(s[i], m);
	if (pd()) return prints("MORTAL"), void();
	if (pd0()) return print(0), void();
	if (pd1()) return print(1), void();
	if (pd4()) return print(4), void();
	if (pd2()) return print(2), void();
	print(3);
}

int main() {
	int T;
	rd(T);
	while (T--) solve();
	return 0;
}

Jeremy Bearimy

设一条边两端的子树大小分别为 $s_1, s_2$。

最小情况下，一条边的计算次数为 $s_1 \bmod 2$。

最大情况下，一条边的计算次数为 $\min(s_1, s_2)$。

const int N = 2e5 + 7;
int n, s[N];
vector< pi > e[N];
ll A, B;

void dfs(int x, int f) {
	s[x] = 1;
	for (ui i = 0; i < e[x].size(); i++) {
		int y = e[x][i].fi;
		if (y == f) continue;
		dfs(y, x);
		s[x] += s[y];
		A += (s[y] & 1) ? e[x][i].se : 0;
		B += 1ll * min(s[y], n - s[y]) * e[x][i].se;
	}
}

inline void solve() {
	rd(n), n <<= 1, A = B = 0;
	for (int i = 1; i <= n; i++) e[i].clear();
	for (int i = 1, x, y, z; i < n; i++) rd(x), rd(y), rd(z), e[x].pb(mp(y, z)), e[y].pb(mp(x, z));
	dfs(1, 0);
	print(A, ' '), print(B);
}

int main() {
	int T;
	rd(T);
	while (T--) solve();
	return 0;
}

Miss Punyverse

设 $f[x][j]$ 表示把点 $x$ 的子树分成 $j$ 块时满足要求的最大块数，$g[x][j]$ 表示在满足要求的块数最大时 $x$ 所在的那一块的最大贡献。

可以这么设是由于最优情况一定是首先满足块数最大其次满足贡献最大，因为贡献再大也最多在后面加一块。

枚举点 $x$ 的儿子 $y$ 跟 $x$ 是否放在一块里，树上背包，时间复杂度 $\mathcal O(Tn^2)$。

具体实现时可以将 $f,g$ 合为一个 pair，这样可以方便的比较大小。

const int N = 3e3 + 7;
int n, m, s[N];
ll a[N];
pair< int, ll > f[N][N], g[N][N];
vi e[N];

void dfs(int x, int fa) {
	s[x] = 1, f[x][1] = mp(0, a[x]);
	for (ui i = 0; i < e[x].size(); i++) {
		int y = e[x][i];
		if (y == fa) continue;
		dfs(y, x);
		for (int j = 1; j <= s[x] + s[y]; j++) g[x][j] = mp(0, -1e18);
		for (int j = 1; j <= s[x]; j++)
			for (int k = 1; k <= s[y]; k++) {
				g[x][j+k] = max(g[x][j+k], mp(f[x][j].fi + f[y][k].fi + (f[y][k].se > 0), f[x][j].se));
				g[x][j+k-1] = max(g[x][j+k-1], mp(f[x][j].fi + f[y][k].fi, f[x][j].se + f[y][k].se));
			}
		s[x] += s[y];
		for (int j = 1; j <= s[x]; j++) f[x][j] = g[x][j];
	}
}

inline void solve() {
	rd(n), rd(m);
	for (int i = 1; i <= n; i++) rd(a[i]), e[i].clear();
	for (int i = 1, x; i <= n; i++) rd(x), a[i] = x - a[i];
	for (int i = 1, x, y; i < n; i++) rd(x), rd(y), e[x].pb(y), e[y].pb(x);
	dfs(1, 0), print(f[1][m].fi + (f[1][m].se > 0));
}

int main() {
	int T;
	rd(T);
	while (T--) solve();
	return 0;
}

Kirchhoff's Current Loss

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

Intergalactic Sliding Puzzle

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