Codeforces Round 972 (Div. 2)

一万一参赛，VP赛时136

A. Simple Palindrome

简单构造题。字母集是 5 ，相同字母间一定构成若干回文子串。

将相同字母排列在一起，则只有相同字母可以构成回文子串。

显然，优先添加较少的字母即可。

#include<bits/stdc++.h>
using namespace std;
int T, n;
char s[5] = {'a', 'e', 'i', 'o', 'u'};

int main() {
	scanf("%d", &T);
	while(T --) {
		scanf("%d", &n);
		int flag = 0;
		int t = n / 5;
		int res = n % 5;
		for(int i = 0; i < 5; i ++) {
			if(i < res) flag = 1;
			else flag = 0;
			for(int j = 1; j <= t + flag; j ++)
				putchar(s[i]);
		}
		putchar('\n');
	}
	return 0;
}

B2. The Strict Teacher (Hard Version)

Easy Version 直接原代码提交即可。

简单模拟题。将猫和老鼠一起按位置排个序。

对于相邻猫之间的所有老鼠，他们的生存时间是相同的，都为相邻猫距离的一半（注意细节）。

注意讨论第一只猫前面的老鼠和最后一只猫后面的老鼠即可。

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int T, n, m, q, ans[N];

struct Node {
	int pos, id;
	bool operator < (const Node &t) const {
		return pos < t.pos;
	}
}a[N * 2];

int main() {
	scanf("%d", &T);
	while(T --) {
		scanf("%d%d%d", &n, &m, &q);
		for(int i = 1; i <= m; i ++)
			scanf("%d", &a[i].pos), a[i].id = 0;
		for(int i = 1; i <= q; i ++)
			scanf("%d", &a[i + m].pos), a[i + m].id = i;
		sort(a + 1, a + m + q + 1);
		vector<int> p;
		int ls = 0;
		for(int i = 1; i <= m + q; i ++) {
			if(!a[i].id) {
				for(int t = 0; t < p.size(); t ++) {
					int j = p[t];
					if(!ls) ans[a[j].id] = a[i].pos - 1;
					else ans[a[j].id] = (a[i].pos - ls) / 2;
				}
				ls = a[i].pos;
				p.clear();
			}
			else p.push_back(i);
		}
		for(int i = 0; i < p.size(); i ++) {
			int j = p[i];
			ans[a[j].id] = n - ls;
		}
		for(int i = 1; i <= q; i ++)
			printf("%d\n", ans[i]);
	}
	return 0;
}

C - Lazy Narek

各字串按顺序拼接，可取可不取，求最大可能权值。用 dp 维护即可。

具体的，f[i][j]，表示考虑了前 i 个子串，当前结尾字母为第 j 个字母的最大权值。

答案为 max(f[n][j] - j) 。

#include<bits/stdc++.h>
using namespace std;
const int N = 1010;
int T, n, m, f[N][5];
char s[N], S[5] = {'n', 'a', 'r', 'e', 'k'};

int main() {
	scanf("%d", &T);
	while(T --) {
		scanf("%d%d", &n, &m);
		f[0][0] = 0;
		for(int j = 1; j < 5; j ++)
			f[0][j] = -1e9;
		for(int i = 1; i <= n; i ++) {
			scanf("%s", s);
			for(int j = 0; j < 5; j ++)
				f[i][j] = f[i - 1][j];
			for(int j = 0; j < 5; j ++) {
				int t = j, res = 0;
				for(int k = 0; k < m; k ++) {
					if(s[k] == S[t]) {
						t = (t + 1) % 5;
						if(!t) res += 5;
					}
					else {
						for(int p = 0; p < 5; p ++)
							if(s[k] == S[p]) res --;
					}
				}
				f[i][t] = max(f[i][t], f[i - 1][j] + res);
			}
		}
		int ans = 0;
		for(int i = 0; i < 5; i ++)
			ans = max(ans, f[n][i] - i);
		printf("%d\n", ans);
	}
	return 0;
}

E1. Subtangle Game (Easy Version)

数据范围 n，m，l 均为 300 ，全局状态数仅为 n³ ，记搜即可。

具体的，f[i][j][k] 表示当前选到序列第 i 个数，在表格的 （j，k） 位置，最后是谁赢。

最后答案显然是 f[1][0][0] 。

#include<bits/stdc++.h>
using namespace std;
const int N = 305;
int T, l, n, m, a[N], s[N][N];
int f[N][N][N];

bool dfs(int cur, int r, int c) {
	if(cur == l + 1) { f[cur][r][c] = !(cur & 1); return !(cur & 1); }
	if(r == n || c == m) { f[cur][r][c] = !(cur & 1); return !(cur & 1);  }
	if(f[cur][r][c] != -1) return f[cur][r][c];
	for(int i = r + 1; i <= n; i ++)
		for(int j = c + 1; j <= m; j ++) {
			if(s[i][j] == a[cur]) {
				bool flag = dfs(cur + 1, i, j);
				if(flag == (cur & 1)) {
					f[cur][r][c] = (cur & 1);
					return (cur & 1);
				}
			}
		}
	f[cur][r][c] = !(cur & 1);
	return !(cur & 1);
}

int main() {
	scanf("%d", &T);
	while(T --) {
		scanf("%d%d%d", &l, &n, &m);
		for(int i = 1; i <= l; i ++)
			scanf("%d", &a[i]);
		for(int i = 1; i <= n; i ++)
			for(int j = 1; j <= m; j ++)
				scanf("%d", &s[i][j]);
		for(int i = 0; i <= l; i ++)
			for(int j = 0; j <= n; j ++)
				for(int k = 0; k <= m; k ++)
					f[i][j][k] = -1;
		bool ans = dfs(1, 0, 0);
		puts(ans ? "T" : "N");
	}
	return 0;
}