AtCoder Grand Contest 030 题解

AtCoder Grand Contest 030

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;
}