AtCoder Grand Contest 046 题解

AtCoder Grand Contest 046

Takahashikun, The Strider

相当于要找到最小的正整数 $t$ 满足 $tx \equiv 0 \pmod {360}$ ，暴力即可。

int main() {
	int x;
	rd(x);
	int t = 1;
	while (1) {
		if (t * x % 360 == 0) {
			return print(t), 0;
		}
		++t;
	}
	return 0;
}

Extension

$\mathcal O(n^2)$ DP，转移时容斥一下。

const int N = 3e3 + 7;
int a, b, c, d;
modint f[N][N];

int main() {
	rd(a, b), rd(c, d);
	f[a][b] = 1;
	for (int i = a; i <= c; i++)
		for (int j = b; j <= d; j++) {
			if (i == a && j == b) continue;
			f[i][j] = f[i-1][j] * j + f[i][j-1] * i - f[i-1][j-1] * (i - 1) * (j - 1);
		}
	print(f[c][d]);
	return 0;
}

Shift

设有 $t$ 个 $0$ ，相当于用这 $t$ 个 $0$ 将 $1$ 分成 $t+1$ 堆，然后可以进行 $k$ 次操作，每次操作把一个 $1$ 移到左边某一堆中，求最终的方案数。

考虑 DP，设 $f_{i,j,l}$ 考虑前 $i$ 堆，已经使用了 $k$ 次中的 $j$ 次，前 $i$ 堆中多了 $l$ 个 $1$ 的方案数。

转移时枚举第 $i+1$ 堆的变化量，时间复杂度 $\mathcal O(n^4)$ ，常数很小，注意特判 $t=0$ 的情况。

const int N = 307;
int n, k, c, t, x, p[N];
char s[N];
modint f[N][N][N], ans;

int main() {
	rds(s, n), rd(k);
	for (int i = 1; i <= n; i++) c += s[i] == '1';
	if (c == n) return print(1), 0;
	for (int i = 1; i <= n; i++)
		if (s[i] == '0') {
			++t;
			int j = i;
			while (s[j-1] == '1') --j, ++p[t];
			x = i;
		}
	p[++t] = n - x;
	k = min(k, c - p[1]);
	for (int j = p[1]; j <= min(c, k + p[1]); j++)
		f[1][j-p[1]][j-p[1]] = 1;
	for (int i = 1; i < t - 1; i++)
		for (int j = 0; j <= k; j++)
			for (int l = 0; l <= j; l++)
				if (f[i][j][l].x)
					for (int w = -min(p[i+1], l); w <= k - j; w++)
						f[i+1][j+max(0,w)][l+w] += f[i][j][l];
	for (int j = 0; j <= k; j++)
		for (int l = 0; l <= min(j, p[t]); l++)
			ans += f[t-1][j][l];
	print(ans);
	return 0;
}

Secret Passage

设 $f_{i,j,k}$ 表示从 $s_{1\dots i}$ 中抽出 $j$ 个 $0$ 和 $k$ 个 $1$ 插入到 $s_{i+1\dots n}$ 中的方案数。

注意我们暂时先不考虑 $s_{1\dots i}$ 中能否抽出 $j$ 个 $0$ 和 $k$ 个 $1$ ，只进行计数。

这个 DP 可以 $\mathcal O(1)$ 转移，时间复杂度 $\mathcal O(n^3)$ 。

接下来的问题就是判断 $s_{1\dots i}$ 中能否抽出 $j$ 个 $0$ 和 $k$ 个 $1$ ，如果可以抽出，则将答案加上 $f_{i,j,k}$ 。

注意我们每次操作可以将一个字符插入到 $s_{i+1\dots n}$ 中，也可以将其依旧放在前面。

如果依旧放在前面，若后面依然需要把这个字符插入到 $s_{i+1 \dots n}$ ，那一定比不放在前面直接插入要劣，因此我们不妨要求依旧放在前面的字符唯一的用处是，删除这个字符，以让其他字符能够插入到后面。

于是设 $g_{i,j,k}$ 表示考虑 $s_{1\dots i}$ 已经抽出了 $j$ 和 $0$ 和 $k$ 个 $1$ 时，最多还剩下多少个可以被删除的字符。

这个 DP 同样可以 $\mathcal O(1)$ 转移，时间复杂度 $\mathcal O(n^3)$ 。

最终 $g_{i,j,k} \ge 0$ 的位置，以及其衍生出更劣的位置都是合法的位置。

总时间复杂度 $\mathcal O(n^3)$ ，注意最后需要减去空串。

const int N = 307;
int n;
char s[N];
modint f[N][N][N], ans;
int g[N][N][N];
bool v[N][N][N];

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

int main() {
	rds(s, n);
	f[n][0][0] = 1;
	for (int i = n; i; i--)
		for (int j = 0; j < i; j++)
			for (int k = 0; j + k < i; k++) {
				f[i-1][j][k] += f[i][j][k];
				if (s[i] == '0') f[i][j][k+1] += f[i][j][k];
				else f[i][j+1][k] += f[i][j][k];
			}
	for (int i = 0; i <= n; i++)
		for (int j = 0; j <= n; j++)
			for (int k = 0; k <= n; k++)
				g[i][j][k] = -1;
	g[0][0][0] = 0;
	for (int i = 0; i < n; i++)
		for (int j = 0; j <= (i >> 1); j++)
			for (int k = 0; j + k <= (i >> 1); k++)
				if (~g[i][j][k]) {
					if (s[i+1] == '0') upd(g[i+1][j+1][k], g[i][j][k] - 1);
					else upd(g[i+1][j][k+1], g[i][j][k] - 1);
					if (i + 2 <= n) {
						upd(g[i+2][j][k], g[i][j][k] + 1);
						if (s[i+1] == '0' || s[i+2] == '0')
							upd(g[i+2][j+1][k], g[i][j][k]);
						if (s[i+1] == '1' || s[i+2] == '1')
							upd(g[i+2][j][k+1], g[i][j][k]);
					}
				}
	for (int i = 0; i <= n; i++)
		for (int j = n; ~j; j--)
			for (int k = n; ~k; k--) {
				v[i][j][k] = ~g[i][j][k];
				if (i) v[i][j][k] |= v[i-1][j][k];
				v[i][j][k] |= v[i][j+1][k];
				v[i][j][k] |= v[i][j][k+1];
			}
	for (int i = 0; i <= n; i++)
		for (int j = 0; j <= i; j++)
			for (int k = 0; j + k <= i; k++)
				if (v[i][j][k]) ans += f[i][j][k];
	print(ans - 1);
	return 0;
}

Permutation Cover

显然有解的充要条件为 $\max a_i \le 2 \cdot \min a_i$ 。

看见字典序最小，显然贪心枚举，不同之处在考虑每次加入一段排列（可能与之前的重合），问题转化成一个前缀是否合法。

设此时的前缀为 $S$ ，显然最后 $k$ 个为一个排列，设为 $p$ ，再设 $i$ 还要加入 $b_i$ 个。

此时跟一开始判定唯一的区别为 $\max b_i = 2 \cdot \min b_i + 1$ 时仍然可能有解，此时附加的充要条件为，设 $j$ 满足 $b_j = \max b_i$ ， $k$ 满足 $b_k = \min b_i$ ，则 $j$ 要在 $k$ 之前。

时间复杂度 $\mathcal O(nk^2)$ 。

const int N = 1e3 + 7;
int n, m, s, a[N], p[N], q[N], ans[N];

void work(int k) {
	bool ok1 = 1, ok2 = 0;
	for (int i = 1; i <= k; i++) --a[p[i]];
	int mn = *min_element(a + 1, a + n + 1);
	int mx = *max_element(a + 1, a + n + 1);
	if (mn * 2 >= mx) {
		ok2 = 1;
		copy(p + 1, p + k + 1, q + 1);
		sort(q + 1, q + k + 1);
	} else if (mn * 2 + 1 == mx) {
		int k1 = 0, k2 = 0;
		static int f1[N], f2[N];
		for (int i = 1; i <= k; i++)
			((a[p[i]] == mn || a[p[i]] == mx) ? f1[++k1] : f2[++k2]) = p[i];
		sort(f1 + 1, f1 + k1 + 1, [&](int i, int j) {
			if ((a[i] == mn) == (a[j] == mn)) return i < j;
			return (a[i] == mn) < (a[j] == mn);
		});
		sort(f2 + 1, f2 + k2 + 1);
		int x1 = 1, x2 = 1;
		for (int i = 1; i <= k; i++)
			if (x1 <= k1 && x2 <= k2)
				q[i] = f1[x1] < f2[x2] ? f1[x1++] : f2[x2++];
			else q[i] = x1 <= k1 ? f1[x1++] : f2[x2++];
		ok2 = 1;
		for (int i = k + 1; i <= n; i++)
			if (a[p[i]] == mn) ok2 = 0;
		ok2 |= !x1 || (a[f1[1]] == mx);
	}
	for (int i = 1; i <= k; i++) ++a[p[i]];
	if (!ok1 || !ok2) q[1] = 0;
}

inline bool pd(int *a, int *b) {
	int p = 1;
	while (a[p] == b[p]) ++p;
	return a[p] < b[p];
}

int main() {
	rd(n), rda(a, n);
	for (int i = 1; i <= n; i++) s += a[i];
	int mn = *min_element(a + 1, a + n + 1);
	int mx = *max_element(a + 1, a + n + 1);
	if (mn * 2 < mx) return print(-1), 0;
	iota(p + 1, p + n + 1, 1), work(n);
	for (int i = 1; i <= n; i++) --a[q[i]], ans[++m] = p[i] = q[i];
	while (m != s) {
		static int t[N];
		memset(t, 0, sizeof(t)), t[1] = n + 1;
		int k = 0;
		for (int i = 1; i <= n; i++) {
			work(i);
			if (q[1] && pd(q, t))
				k = i, copy(q + 1, q + i + 1, t + 1);
		}
		for (int i = 1; i + k <= n; i++) p[i] = p[i+k];
		for (int i = 1; i <= k; i++)
			ans[++m] = p[n-k+i] = t[i], --a[t[i]];
	}
	printa(ans, m);
	return 0;
}

Forbidden Tournament

咕.