AtCoder Grand Contest 030 题解
Visits: 365
Poisonous Cookies
$ans = \min(a+b+1,c) + b$。
int main() {
ll a, b, c;
rd(a, b, c);
print(min(a + b + 1, c) + b);
return 0;
}
Tree Burning
贪心，最终的方案一定是先走到某个点，然后后面每碰到一个点就调头。
前缀和一下就可以 $\mathcal O(n)$ 了。
const int N = 2e5 + 7;
int n, l, a[N], b[N];
ll sa[N], sb[N], ans;
#define Sa(l, r) (sa[r] - sa[l-1])
#define Sb(l, r) (sb[r] - sb[l-1])
inline ll calc() {
ll ret = 0;
for (int i = n; i; i--) {
int y = (n - i) >> 1, x = n - i - y;
ret = max(ret, ((n - i) & 1 ? b[n-y] : a[n-x]) + (Sb(n - y + 1, n) + Sa(i, i + x - 1)) * 2);
}
return ret;
}
int main() {
rd(l, n), rda(a, n);
for (int i = 1; i <= n; i++)
b[i] = l - a[i], sa[i] = sa[i-1] + a[i], sb[i] = sb[i-1] + b[i];
ll now = calc();
for (int i = 1; i <= n; i++) a[i] = b[n+1-i];
for (int i = 1; i <= n; i++)
b[i] = l - a[i], sa[i] = sa[i-1] + a[i], sb[i] = sb[i-1] + b[i];
print(max(now, calc()));
return 0;
}
Coloring Torus
题意
- 对于一个 $n \times n$ 的网格，下标从 $0$ 开始，且第 $0$ 行在第 $n-1$ 行下面，列同理。
- 你要用 $k$ 种颜色对这个矩阵染色，需要满足以下条件：
- 每个格子被染成 $k$ 种颜色之一。
- $k$ 种颜色都染了至少一个格子。
- 对于任意两种颜色 $i,j$，满足所有颜色为 $i$ 的格子，其上下左右相邻的颜色 $j$ 的格子数相同（如果一个格子出现多次也会被计算多次）。
- 给定 $k$，要求构造一种网格染色方案。
- $k \le 10^3$，$n \le 500$。
题解
设颜色为 $[0,k-1]$，考虑 $n$ 为偶数的情况，构造 $c_{i,j} = ((i + j) \bmod n)$。
注意到如果将某一种颜色加入一个新颜色与之交替，同样是合法的。
因此特判 $k = 1$ 的情况，令 $n = 2\lceil \frac k4 \rceil$ 即可。
代码
int main() {
int k;
rd(k);
if (k == 1) return prints("1\n1"), 0;
int n = (k + 3) / 4 * 2;
print(n);
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
int c = (i + j) % n;
if ((i & 1) && c + n < k) c += n;
print(c + 1, " \n"[j==n-1]);
}
return 0;
}
Inversion Sum
题意
- 给定一个序列 $a_{1\dots n}$。
- 有 $q$ 次操作，每次操作会交换两个位置上的数，你都可以选择是否执行。
- 求所有情况下最终序列的逆序对数之和。
- $n,q \le 3 \times 10^3$，答案对 $10^9+7$ 取模。
题解
令 $f_{i,j}$ 表示 $a_i > a_j$ 的概率，这样每次转移只会修改 $\mathcal O(n)$ 对 $(i,j)$，时间复杂度 $\mathcal O(n(n+q))$。
代码
const int N = 3e3 + 7;
const modint v2 = (modint)1 / 2;
int n, q, a[N];
modint f[N][N], ans;
inline void work(modint &x, modint &y) {
x = y = (x + y) * v2;
}
int main() {
rd(n, q), rda(a, n);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
f[i][j] = a[i] > a[j];
for (int i = 1, x, y; i <= q; i++) {
rd(x, y), work(f[x][y], f[y][x]);
for (int j = 1; j <= n; j++)
if (j != x && j != y)
work(f[j][x], f[j][y]), work(f[x][j], f[y][j]);
}
for (int i = 1; i <= n; i++)
for (int j = i + 1; j <= n; j++)
ans += f[i][j];
print(ans * ((modint)2 ^ q));
return 0;
}
Less than 3
题意
- 给定两个长度为 $n$ 的 $0/1$ 串 $s,t$，其中相同字符构成的连续段长度 $<3$。
- 你可以对 $s$ 进行单点取反操作，要求每次操作后仍然满足相同字符构成的连续段长度 $<3$。
- 求将 $s$ 变成 $t$ 的最小操作次数。
- $n \le 5 \times 10^3$。
题解
注意到一段相同字符不会消失，否则一定会出现一个长度至少为 $3$ 的相同字符连续段。
考虑所有的 $01$ 分界线和 $10$ 分界线，则一次合法的操作只有下面三种情况：
- 将某个分界线朝某个方向移动一个字符。
- 将两端的分界线移出。
- 在某一端加入一条分界线。
在过程中要求相邻两个分界线的距离为 $1$ 或 $2$。
考虑 $s$ 和 $t$ 分界线的对应关系，一共只有 $\mathcal O(n)$ 种，每种的答案就是对应分界线的距离之和。
时间复杂度 $\mathcal O(n^2)$。
代码
const int N = 5e3 + 7;
int n, a[N], b[N], c, d;
char s[N], t[N];
int main() {
rd(n), rds(s, n), rds(t, n);
for (int i = 1; i < n; i++)
if (s[i] != s[i+1]) a[++c] = i;
for (int i = 1; i < n; i++)
if (t[i] != t[i+1]) b[++d] = i;
int ans = 1e9;
for (int i = -c - 1; i <= d + 1; i++)
if ((i & 1) ^ (s[1] == t[1])) {
int now = 0;
for (int j = min(1, 1 - i); j <= max(c, d - i); j++)
now += abs(((j < 0) ? 0 : ((j > c) ? n : a[j])) - ((i + j < 0) ? 0 : ((i + j > d) ? n : b[i+j])));
ans = min(ans, now);
}
print(ans);
return 0;
}
Permutation and Minimum
题意
- 有一个 $1 \sim 2n$ 的排列 $a$，有些位置上的数不确定。
- 根据排列 $a$ 可以生成序列 $b_{1\dots n}$，其中 $b_i = \min(a_{2i-1}, a_{2i})$。
- 求 $b$ 的方案数。
- $n \le 300$，答案对 $10^9+7$ 取模。
题解
先把 $(x,x)$ 的去掉，剩下的就是 $(x,-1)$ 和 $(-1,-1)$ 两种。
对于 $(-1,-1)$，先忽略其位置关系，最后再乘上个数的阶乘即可。
考虑从大到小 DP，设 $f_{i,j,k}$ 表示当前考虑到 $i$，有 $j$ 个 $-1$ 没有匹配，有 $k$ 个 $x$ 没有匹配。
转移分是否确定讨论一下即可，时间复杂度 $\mathcal O(n^3)$。
代码
const int N = 607;
int n, m, k, a[N], v[N];
bool w[N];
modint f[N][N][N], ans;
int main() {
rd(n), m = 2 * n, rda(a, m);
for (int i = 1; i <= n; i++)
if (a[2*i-1] > 0 && a[2*i] > 0)
v[a[2*i-1]] = v[a[2*i]] = 1, m -= 2;
for (int i = 1; i <= 2 * n; i++) v[i] += v[i-1];
for (int i = 1; i <= n; i++)
if (a[2*i-1] > 0 && a[2*i] < 0) w[a[2*i-1]-v[a[2*i-1]]] = 1;
else if (a[2*i-1] < 0 && a[2*i] > 0) w[a[2*i]-v[a[2*i]]] = 1;
else if (a[2*i-1] < 0 && a[2*i] < 0) ++k;
f[m+1][0][0] = 1;
for (int i = m; i; i--)
for (int j = 0; j < m; j++)
for (int k = 0; k < m; k++)
if (!!f[i+1][j][k]) {
if (w[i]) {
f[i][j+1][k] += f[i+1][j][k];
if (k) f[i][j][k-1] += f[i+1][j][k];
} else {
f[i][j][k+1] += f[i+1][j][k];
if (j) f[i][j-1][k] += f[i+1][j][k] * j;
if (k) f[i][j][k-1] += f[i+1][j][k];
}
}
ans = f[1][0][0];
for (int i = 1; i <= k; i++) ans *= i;
print(ans);
return 0;
}
