AtCoder Grand Contest 046 题解
Visits: 417
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
咕.
