AtCoder Grand Contest 022 题解

AtCoder Grand Contest 022

Diverse Word

分类讨论一下即可。

int main() {
	string s;
	cin >> s;
	if ((int)s.size() == 26) {
		string t = s;
		if (next_permutation(t.begin(), t.end())) {
			int i = 0;
			while (s[i] == t[i]) ++i;
			while ((int)t.size() > i + 1) t.pop_back();
			cout << t << endl;
		} else print(-1);
	} else {
		map<char, bool> v;
		for (char c : s) v[c] = 1;
		for (char i = 'a'; i <= 'z'; i++)
			if (!v[i]) {
				cout << s + i << endl;
				break;
			}
	}
	return 0;
}

GCD Sequence

如果 $n=3$ ，题目已经给出一组构造。

否则，注意到 $\le 30000$ 且是 $2$ 的倍数或 $3$ 的倍数的数恰好有 $20000$ 个，我们只使用这些数。

先选择 $2,3,4,9$ ，然后将其它数按 $\bmod 6$ 分类，在保证和为 $6$ 的倍数的情况下选剩下的数就能满足条件。

int main() {
	int n;
	rd(n);
	if (n == 3) return prints("2 5 63"), 0;
	vi ans = {2, 3, 4, 9};
	set<int> s[6];
	for (int i = 6; i <= 30000; i++)
		if (!(i % 2) || !(i % 3)) s[i%6].insert(i);
	s[3].erase(9);
	n -= 4;
	while (n > 1 && s[2].size() && s[4].size())
		n -= 2,
		ans.pb(*s[2].begin()), s[2].erase(s[2].begin()),
		ans.pb(*s[4].begin()), s[4].erase(s[4].begin());
	while (n > 1 && s[3].size() > 1u)
		n -= 2,
		ans.pb(*s[3].begin()), s[3].erase(s[3].begin()),
		ans.pb(*s[3].begin()), s[3].erase(s[3].begin());
	while (n && s[0].size())
		n--,
		ans.pb(*s[0].begin()), s[0].erase(s[0].begin());
	for (int x : ans) print(x, ' ');
	return 0;
}

Remainder Game

本质上就是一张 $51$ 个点的有向图，问所有 $a_i$ 能否到达 $b_i$ 。

由于代价是 $2^i$ ，因此直接贪心即可，时间复杂度 $\mathcal O(n^4)$ 。

const int N = 51;
int n, a[N], b[N];
bool v[N];
ll ans;

bool dfs(int x, int t, ll o) {
	if (x == t) return 1;
	if (v[x]) return 0;
	v[x] = 1;
	for (int i = 1; i < N; i++)
		if ((o >> i & 1) && dfs(x % i, t, o)) return 1;
	return 0;
}

inline bool pd(ll o) {
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < N; j++) v[j] = 0;
		if (!dfs(a[i], b[i], o)) return 0;
	}
	return 1;
}

int main() {
	rd(n), rda(a, n), rda(b, n);
	for (int i = 1; i < N; i++) ans |= 1ll << i;
	if (!pd(ans)) return print(-1), 0;
	for (int i = N - 1; i; i--)
		if (pd(ans ^ 1ll << i)) ans ^= 1ll << i;
	print(ans);
	return 0;
}

Shopping

题意

数轴上按顺序有 $n+2$ 个点，第 $0$ 个点在 $0$ 处，第 $i(\in [1,n])$ 个点在 $x_i$ 处，第 $n+1$ 个点在 $L$ 处。
有一辆每秒行驶一个单位的车，一开始在 $0$ 处，然后不断在 $0,L$ 之间往返。
你一开始也在 $0$ 处，你可以随时上下车。
你需要在每个点下车一次，而且必须在第 $i$ 个点停留 $t_i$ 秒后才能再次上车。
最后你要回到 $0$ 处，求最短耗时。
$n \le 3 \times 10^5$ 。

题解

首先答案一定是 $2L$ 的整数倍。

其次可以先把 $\lfloor \frac{t_i}{2L} \rfloor$ 加入答案，然后把 $t_i$ 模上 $2L$ ，显然答案不变，同时保证 $t_i < 2L$ 。

考虑答案的一个上界，顺次走到 $x_1,x_2,\cdots,x_n$ ，走到每个点停留 $2L$ 然后走到下一个点，这样答案是 $n+1$ 。

考虑如何更优，设 $l_i$ 表示从左边到 $i$ ，车在下次从右边经过 $i$ 时是否停留够了 $t_i$ ，即 $l_i = [2(L-x_i) \ge t_i]$ ；类似定义 $r_i = [2x_i \ge t_i]$ 。

对于 $l_i = r_i = 0$ 的点，我们完全无法优化，可以直接忽略掉。

对于 $t_i = 0$ 的点，可以将答案 $-1$ ，然后直接忽略掉。

对于点 $n$ ，如果 $l_n = 1$ ，可以将答案 $-1$ ，否则无法优化，无论是否 $-1$ 都可以直接忽略掉。

对于 $[1,n)$ 的点，如果存在 $i,j$ 满足 $i < j$ 且 $r_i = l_j = 1$ ，那么我们可以再经过 $i$ 时先不停留，到 $j$ 时在一轮中先完成 $j$ 后完成 $i$ ，可以将答案 $-1$ 。

于是就相当于再减掉一个最大匹配数。

又发现如果 $(l,r) = (1,0)$ 的点一定在 $(l,r) = (0,1)$ 的点的左边（根据定义式可以推出来），因此这两类点不可能匹配上。

因此我们就是要用 $(l,r) = (1,1)$ 的点先尽量和上述两类点匹配，然后剩余的两两匹配就是最大匹配了。

时间复杂度 $\mathcal O(n)$ 。

代码

const int N = 3e5 + 7;
int n, L, x[N], t[N];
ll ans;
bool l[N], r[N], v[N];
vi p;

int main() {
	rd(n, L), rda(x, n), rda(t, n), ans = n + 1;
	for (int i = 1; i <= n; i++) {
		ans += t[i] / (2 * L), t[i] %= 2 * L;
		l[i] = 2 * (L - x[i]) >= t[i], r[i] = 2 * x[i] >= t[i];
		if (!t[i]) --ans, v[i] = 1;
		else if (!l[i] && !r[i]) v[i] = 1;
		else if (i == n && l[i]) --ans;
	}
	for (int i = 1; i < n; i++)
		if (!v[i]) {
			if (l[i] && r[i]) p.pb(i);
			else if (l[i] && !r[i] && p.size())
				--ans, v[i] = 1, v[p.back()] = 1, p.pop_back();
		}
	p.clear();
	for (int i = n - 1; i; i--)
		if (!v[i]) {
			if (l[i] && r[i]) p.pb(i);
			else if (!l[i] && r[i] && p.size())
				--ans, v[i] = 1, v[p.back()] = 1, p.pop_back();
		}
	ans -= p.size() / 2;
	print(ans * 2 * L);
	return 0;
}

Median Replace

题意

给定一个长度为 $n$ 的 $0/1$ 串 $s$ ，保证 $n$ 为奇数，其中有些位置上的字符不确定。
请你求出有多少个 $s$ 满足执行下列操作 $\frac {n-1}2$ 次后能使 $s$ 为 1：
- 选择 $s$ 的三个连续的字符，将它们替换为这三个数的中位数。
$n \le 3 \times 10^5$ ，答案对 $10^9+7$ 取模。

题解

考虑如何判断一个 $0/1$ 串是否合法。

维护一个栈，这个栈从栈底到栈顶由一段连续的 $1$ 和一段连续的 $0$ 组成。

对于一个新加字符 $c$ ：

若 $c=0$ ：由于三个 $0$ 抵消为一个 $0$ 严格不劣，因此若原来栈顶有两个 $0$ 则抵消为一个，否则加一个 $0$ 。
若 $c=1$ ：如果栈顶是 $0$ ，可以直接将这个 $0$ 与新加的 $1$ 抵消（因为无论和另外哪个数取中位数，答案都是另外那个数）；如果栈顶为 $1$ ，若已经有两个 $1$ 了，那么这个串一定合法，因此直接忽略掉这个 $1$ 就可以了，否则加一个 $1$ 。

根据这个过程可以知道栈 $0/1$ 的个数只有 $0 \sim 2$ 这三种，总共只有 $9$ 种情况。

考虑根据这个判定方法进行 DP，时间复杂度 $\mathcal O(n)$ 。

代码

const int N = 3e5 + 7;
int n;
char s[N];
modint f[N][3][3], ans;

int main() {
	rds(s, n), f[0][0][0] = 1;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < 3; j++)
			for (int k = 0; k < 3; k++)
				if (!!f[i][j][k]) {
					if (s[i+1] != '0') {
						if (k) f[i+1][j][k-1] += f[i][j][k];
						else f[i+1][min(j+1,2)][k] += f[i][j][k];
					}
					if (s[i+1] != '1') {
						if (k == 2) f[i+1][j][1] += f[i][j][k];
						else f[i+1][j][k+1] += f[i][j][k];
					}
				}
	for (int i = 0; i < 3; i++)
		for (int j = 0; j <= i; j++)
			ans += f[n][i][j];
	print(ans);
	return 0;
}

Checkers

题意

令 $x = 10^{100}$ 。
数轴上有 $n$ 个点，第 $i$ 个点的坐标为 $x^i$ 。
你会进行下列操作 $n-1$ 次，最终只剩下一个点：
- 选择两个点 $a,b$ ，将 $a$ 移动到关于 $b$ 的对称点。
- 移除 $b$ 。
求可能的最终点的坐标的数量。
$n \le 50$ ，答案对 $10^9+7$ 取模。

题解

由于 $x$ 很大，只用考虑每个数的贡献，贡献不同的方案对应的坐标也不同，显然每个数的贡献形如 $\pm 2^k$ 。

对于每次操作选择的 $a,b$ ，将 $b$ 的父亲设为 $a$ ，这样会得到一颗有根树，点 $i$ 贡献中的 $k$ 就是它的深度（根的深度为 $0$ ）。

考虑正负号，设点 $i$ 有 $c$ 个儿子，则会有 $\lfloor \frac c2 \rfloor$ 个儿子和 $i$ 异号，剩下的同号。

考虑 DP，设 $f_{i,j}$ 表示已经有 $i$ 个点，其中有 $j$ 个奇数个儿子的点的方案数，枚举这一层的点数 $k$ ，那么不考虑这一层的点的儿子的影响，有 $\frac {k-j}{2}$ 个点和父亲不同，再枚举实际有 $x$ 个点和父亲不同，则意味着有 $|\frac {k-j}2 - x|$ 个点有奇数个儿子。

时间复杂度 $\mathcal O(n^4)$ 。

代码

const int N = 57;
int n;
modint f[N][N];

int main() {
	rd(n), init(n), f[1][0] = f[1][1] = n;
	for (int i = 1; i < n; i++)
		for (int j = 0; j <= i; j++)
			for (int k = max(j, 1); k <= n - i; k++) {
				if ((k - j) & 1) continue;
				int y = (k - j) / 2;
				for (int x = 0; x <= k; x++)
					f[i+k][abs(y-x)] += f[i][j] * binom(n - i, k) * binom(k, x);
			}
	print(f[n][0]);
	return 0;
}