AtCoder Grand Contest 041 题解

AtCoder Grand Contest 041

Table Tennis Training

如果 $a,b$ 奇偶性相同，那么一起往中间走即可。

否则，走到某一端，浪费一次步数之后再一起往中间走。

int main() {
	ll n, a, b;
	rd(n, a, b);
	if ((a ^ b) & 1) print(min((a + b - 1) >> 1, (n - a + n - b + 1) >> 1));
	else print((b - a) >> 1); 
	return 0;
}

Voting Judges

贪心，考虑清楚合法条件，需要前缀和一下。

const int N = 1e5 + 7;
int n, m, v, p, a[N];
ll s[N];
 
int main() {
	rd(n, m), rd(v, p), rda(a, n);
	sort(a + 1, a + n + 1);
	for (int i = 1; i <= n; i++) s[i] = a[i] + s[i-1];
	for (int i = 1; i <= n; i++) {
		int c = n + 1 - (upper_bound(a + 1, a + n + 1, a[i] + m) - a);
		if (c + 1 > p) continue;
		int d = (upper_bound(a + 1, a + n + 1, a[i]) - a) - 2;
		ll o = 1ll * m * (v - 1 - c - d) - (1ll * (a[i] + m) * (n - 1 - c - d) - (s[n-c] - s[d+1]));
		if (o <= (s[n-c] - s[n-p+1]) - 1ll * (p - 1 - c) * a[i]) {
			print(n - i + 1);
			break;
		}
	}
	return 0;
}

Domino Quality

$n \le 2$ 无解，手玩出 $n=3/4/5/6/7$ ，用 $4/5/6/7$ 去凑出后面的数。

const string S4[4] = {"abcc", "abdd", "ccab", "ddab"};
const string S5[5] = {"abbcc", "ad..a", "bd..a", "b.eez", "oorrz"};
const string S6[6] = {"oorrzz", ".a.b.c", ".a.b.c", "d.e.f.", "d.e.f.", "oorrzz"};
const string S7[7] = {".oorrzz", "oabb...", "oa.c...", "rddc...", "r...abb", "z...a.c", "z...ddc"};

const int N = 1e3 + 7;
int n;
char s[N][N];

inline void solve(int &n, int x) {
	if (x == 4)
		for (int i = 0; i < x; i++)
			for (int j = 0; j < x; j++)
				s[n+i][n+j] = S4[i][j];
	if (x == 5)
		for (int i = 0; i < x; i++)
			for (int j = 0; j < x; j++)
				s[n+i][n+j] = S5[i][j];
	if (x == 6)
		for (int i = 0; i < x; i++)
			for (int j = 0; j < x; j++)
				s[n+i][n+j] = S6[i][j];
	if (x == 7)
		for (int i = 0; i < x; i++)
			for (int j = 0; j < x; j++)
				s[n+i][n+j] = S7[i][j];
	n += x;
}

int main() {
	rd(n);
	if (n <= 2) return print(-1), 0;
	if (n == 3) return prints("a.."), prints("a.."), prints(".bb"), 0;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			s[i][j] = '.';
	int m = 1;
	solve(m, n % 4 + 4);
	while (m <= n) solve(m, 4);
	for (int i = 1; i <= n; i++) prints(s[i], n);
	return 0;
}

Problem Scores

限制相当于要求前 $k+1$ 个数的和大于后 $k$ 个数的和。

注意到如果 $k > \lfloor \frac {n-1}2 \rfloor$ 会有重复的部分，把重复的部分去掉之后就变成 $k \le \lfloor \frac {n-1}2 \rfloor$ 的情况，因此我们只用考虑 $k \le \lfloor \frac {n-1}2 \rfloor$ 的情况。

又当 $k \le \lfloor \frac {n-1}2 \rfloor$ 时，若 $k$ 满足条件，则 $k-1$ 一定满足条件，因此我们只用考虑 $k = \lfloor \frac {n-1}2 \rfloor$ 的情况。

先考虑 $n$ 为偶数的情况，此时有且仅有 $a_{k+2}$ 既不在前 $k+1$ 个数中，又不在后 $k$ 个数中。

考虑枚举 $a_{k+2} = x$ ，先将所有数都设为 $x$ ，此时前 $k+1$ 个数的和比后 $k$ 个数的和大 $x$ 。

然后我们可以做的就是让前 $k+1$ 个数的若干个前缀同时 $-1$ ，后 $k$ 个数的若干个后缀同时 $+1$ ，使得：

前 $k+1$ 个数最多进行 $x-1$ 次 $-1$ 。
后 $k$ 个数最多进行 $n-x$ 次 $+1$ 。
前 $k+1$ 个数减掉的总数与后 $k$ 个数加上的总数之和 $< x$ 。

设 $f_{j,l}$ 表示前 $k+1$ 个数进行了 $j$ 次 $-1$ ，共减掉 $l$ 的方案数， $g_{j,l}$ 表示后 $k$ 个数进行了 $j$ 次 $+1$ ，共加上 $l$ 的方案数。

则答案为： $\sum_{x=1}^n \sum_{p=0}^{x-1} \sum_{q=0}^{n-x} \sum_{i=0}^{x-1} \sum_{j=0}^{x-1-i} f_{p,i} g_{q,j}$ 这玩意儿在求出 $f,g$ 之后借助前缀和可以做到 $\mathcal O(n^2)$ 。

由于 $f,g$ 定义类似，这里只考虑如何求 $f$ 。

在 $[1,k+1]$ 的范围内从大到小枚举 $i$ ，表示此时 $-1$ 会导致总共 $-i$ ，再枚举一个状态 $f_{j,l}$ ，转移到 $f_{j+1,l+i}$ 。

乍看之下复杂度为 $\mathcal O(n^3)$ ，但仔细观察可以发现 $l$ 只需要从 $ij$ 开始枚举即可，又 $ij < n$ ，因此有效的 $i,j$ 只有 $\mathcal O(n \log n)$ 种，总时间复杂度 $\mathcal O(n^2 \log n)$ 。

最后是当 $n$ 为奇数的情况，唯一的区别就是变成枚举 $a_{k+1}$ ，其它的都很类似，事实上只需要将求 $f$ 时枚举 $i$ 的范围从 $[1,k+1]$ 改成 $[1,k]$ 即可。

const int N = 5e3 + 7;
int n, k;
modint f[N][N], g[N][N], ans;

int main() {
	rd(n, P), k = (n - 1) >> 1;
	f[0][0] = g[0][0] = 1;
	for (int i = k + !(n & 1); i; i--)
		for (int j = 0; i * (j + 1) < n; j++)
			for (int l = i * j; l + i < n; l++)
				f[j+1][l+i] += f[j][l];
	for (int i = k; i; i--)
		for (int j = 0; i * (j + 1) < n; j++)
			for (int l = i * j; l + i < n; l++)
				g[j+1][l+i] += g[j][l];
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			f[i][j] += (i ? f[i-1][j] : 0),
			g[i][j] += (i ? g[i-1][j] : 0) + (j ? g[i][j-1] : 0) - ((i && j) ? g[i-1][j-1] : 0);
	for (int x = 1; x <= n; x++)
		for (int i = 0; i < x; i++)
			ans += f[x-1][i] * g[n-x][x-1-i];
	print(ans);
	return 0;
}

Balancing Network

对于 $T = 1$ ，设 $a_{i,j}$ 表示 $j$ 是否能到达 $i$ ，则依次考虑每个操作 $(x,y)$ ，相当于将 $a_x$ 和 $a_y$ 取并，bitset 即可，时间复杂度 $\mathcal O(\frac {nm}w)$ 。

对于 $T = 2$ ，注意到 $n=3$ 时必然有解，于是怎么搞都行了。

const int N = 5e4 + 7, M = 1e5 + 7;
int n, m, t, x[M], y[M];
bitset<N> a[N];
bool v[N];
int b[N], c[N];
char s[M];

int main() {
	rd(n, m, t);
	if (t == 1) {
		for (int i = 1; i <= n; i++) a[i][i] = 1;
		for (int i = 1; i <= m; i++)
			rd(x[i], y[i]), a[x[i]] = a[y[i]] |= a[x[i]];
		for (int i = 1; i <= n; i++)
			if ((int)a[i].count() == n) {
				v[i] = 1;
				for (int i = m; i; i--)
					if (v[x[i]]) s[i] = '^', v[y[i]] = 1;
					else if (v[y[i]]) s[i] = 'v', v[x[i]] = 1;
					else s[i] = '^';
				prints(s, m);
				return 0;
			}
		print(-1);
	} else {
		if (n == 2) return print(-1), 0;
		for (int i = 1; i <= n; i++) b[i] = i, c[i] = 1;
		for (int i = 1; i <= m; i++) rd(x[i], y[i]);
		for (int i = m; i; i--)
			if (b[x[i]] == b[y[i]]) s[i] = '^';
			else {
				if (c[b[x[i]]] <= 1) swap(x[i], y[i]), s[i] = '^';
				else s[i] = 'v';
				--c[b[x[i]]], b[x[i]] = b[y[i]], ++c[b[x[i]]];
			}
		prints(s, m);
	}
	return 0;
}

Histogram Rooks

咕