AtCoder Grand Contest 045 题解

AtCoder Grand Contest 045

Xor Battle

倒序考虑，如果在一个 $1$ 处能够成功加入线性基，则说明无论 $1$ 之前的数是什么情况，都可以使 $1$ 之后的数不在线性基内，因此 $1$ 赢，否则 $0$ 赢。

const int N = 207;
int n;
ll a[N], b[61];
char s[N];

inline bool ins(ll x) {
	for (int i = 60; ~i; i--)
		if (x >> i & 1) {
			if (!b[i]) return b[i] = x, 1;
			x ^= b[i];
		}
	return 0;
}

inline void solve() {
	memset(b, 0, sizeof(b));
	rd(n), rda(a, n), rds(s, n);
	reverse(a + 1, a + n + 1);
	reverse(s + 1, s + n + 1);
	for (int i = 1; i <= n; i++)
		if (ins(a[i]) && s[i] == '1') return print(1);
	print(0);
}

int main() {
	int T;
	rd(T);
	while (T--) solve();
	return 0;
}

01 Unbalanced

$0$ 当成 $1$ ， $1$ 当成 $-1$ ，则目标相当于最小化前缀和的极差。

考虑枚举前缀和的最小值 $x$ ，然后从后往前贪心，找到在这个最小值的限制下前缀和最大值的最小值。

然后可以发现 $x$ 只需要检查 $x$ 理论上能够达到的最大值 $m$ 和 $m-1$ 。

时间复杂度 $\mathcal O(n)$ 。

const int N = 1e6 + 7;
int n, p[N], mn, mx;
char s[N];

inline int calc(int o) {
	p[n] = mx = 0;
	for (int i = n; i; i--)
		p[i-1] = max(p[i] + (s[i] == '1' ? 1 : -1), 0);
	for (int i = 1, k = 0; i <= n; mx = max(mx, k), ++i)
		if (s[i] == '?') k += k - 1 - p[i] >= o ? -1 : 1;
		else k += s[i] == '0' ? 1 : -1;
	return mx;
}

int main() {
	rds(s, n);
	for (int i = 1, k = 0; i <= n; i++)
		mn = min(mn, s[i] == '1' ? --k : ++k);
	print(min(calc(mn) - mn, calc(mn - 1) - mn + 1));
	return 0;
}

Range Set

考虑怎样的 $0/1$ 序列不合法，直接给结论：

不妨设 $a \le b$ ，把所有长度 $\ge a$ 的 $0$ 连续段都变成 $1$ 连续段后，不存在长度 $\ge b$ 的 $1$ 连续段，则不合法。

于是考虑 DP，设 $f_{0/1,i}$ 表示以 $i$ 结尾的 $0/1$ 连续段的方案数，提前处理转移系数后可以做到 $\mathcal O(n^2)$ 。

注意首尾比较特殊，要特判一下。

const int N = 5e3 + 7;
int n, a, b;

inline modint F(int n, int m) {
	return binom(n + m - 1, m - 1);
}

modint f[N], g[N], h[2][N], w[N];

int main() {
	rd(n, a, b), init(1e6);
	if (a > b) swap(a, b);
	for (int i = 1; i < a; i++) f[i] = 1;
	for (int i = 1; i < b; i++) {
		for (int j = 0; j * (a + 1) < i; j++)
			g[i] += F(i - j * (a + 1) - 1, j * 2 + 1);
		w[i] = g[i];
		for (int j = 0; j * (a + 1) <= i; j++)
			w[i] += F(i - j * (a + 1), j * 2);
	}
	h[0][0] = h[1][0] = 1;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= i; j++)
			h[0][i] += h[1][i-j] * f[j], h[1][i] += h[0][i-j] * (i == j ? w[j] : (i == n ? w[j] : g[j]));
	}
	print(((modint)2 ^ n) - h[0][n] - h[1][n]);
	return 0;
}

Lamps and Buttons

最优策略一定是：

从左往右选择一盏尚未操作过的亮着的灯 $x$ 。
若 $p_x = x$ ，则 $x$ 不可能再亮起，负。
若 $p_x \ne x$ ，且 $p_x$ 暗下去了，则可以再次操作 $x$ 使其亮回来。
若 $p_x = x$ ，且 $p_x$ 亮起来了，则转而操作 $p_x$ ，将 $x$ 所在的置换环全部点亮。

于是一个排列合法当且仅当：

设 $t$ 是最小的满足 $t \le a$ 且 $p_t = t$ 的位置，若不存在，则 $t = a + 1$ 。
对于所有 $a + 1 \le x \le n$ ， $x$ 所在的置换环上存在一个 $\le t - 1$ 的元素。

然后开始推柿子。

枚举 $t \in [2,a+1]$ ，则相当于我们把这个排列拆成了四段：

$i \in [1,t-1]$ ，这一段中要求 $p_i \ne i$ ，个数为 $x = t - 1$ 。
$i = t$ ，这一段中要求 $p_i = i$ ，注意当 $t = a + 1$ 时这一段不存在。
$i \in [t+1,a]$ ，这一段中没有任何要求，注意这一段可能为空，个数为 $y = \max(a-t,0)$ 。
$i \in [a+1,n]$ ，这一段中要求 $i$ 所在的置换环上存在至少一个 $\in [1,t-1]$ 的元素，个数为 $z = n - a$ 。

第二段的限制条件可以直接扔掉，先暂时忽略第一段的限制条件。

先考虑第一段的 $x$ 个数，显然排列的方案数为 $x!$ 。

再考虑第四段的 $z$ 个数，第 $i$ 个数放入排列中时必须插入某一个置换环中，方案数为 $x+i-1$ 。

最后考虑第三段的 $y$ 个数，第 $i$ 个数放入排列中时可以插入某一个置换环中，也可以自成一个置换环，方案数为 $x+z+i$ 。

因此总方案数为 $\frac{x}{x+z}(x+y+z)!$ 。

再考虑第一段的限制条件，枚举有多少个 $p_i = i$ 然后容斥掉就行了，即： $\sum_{i=0}^x (-1)^x \binom xi \frac{x-i}{x-i+z}(x-i+y+z)!$ 总时间复杂度 $\mathcal O(n + a^2)$ 。

int main() {
	int n, a;
	modint ans;
	rd(n, a), init(n);
	for (int t = 2; t <= a + 1; t++) {
		int x = t - 1, y = max(a - t, 0), z = n - a;
		for (int i = 0; i <= x; i++)
			if (i & 1) ans -= binom(x, i) * (x - i) * v[x-i+z] * p[x-i+y+z];
			else ans += binom(x, i) * (x - i) * v[x-i+z] * p[x-i+y+z];
	}
	print(ans);
	return 0;
}

Fragile Balls

设 $p$ 表示 $a_i \ne b_i$ 的球数。

首先考虑所有 $c_i$ 都为 $1$ 的情况，此时答案要么是 $p$ 要么是 $-1$ 。

考虑对于每个球建边 $a_i \to b_i$ ，注意题目条件保证了每个点的入度都不为 $0$ 。

我们可以将每个连通块（忽略边的方向）分为以下三类：

连通块仅包含一个长度 $=1$ 的环。
连通块仅包含一个长度 $>1$ 的环。
其它。

可以发现，若存在第 2 类连通块，则答案为 $-1$ ，否则由于第 3 类可以直接构造一组合法的方案，所以答案为 $p$ 。

接下来考虑当 $c_i \ge 1$ 的情况，此时即使存在第 2 类连通块，也可能有解。

设第 2 类的连通块个数为 $x$ ，我们只需要考虑 $x \ge 1$ 的情况，同时对于每个连通块我们一定会至少需要 $1$ 步去处理，总共需要 $x$ 步，这 $x$ 步先计算上。

我们要处理第 2 类连通块，必须从连通块外移入一个球 $i$ 到连通块内。先假设这个 $i$ 可以移出来，那么这个 $i$ 有以下几种情况：

$i$ 在第 1 类连通块内，则此时的操作为，把 $i$ 移到某个第 2 类连通块处理，然后移向下一个第 2 类连通块处理，处理了最多 $c_i - 2$ 个连通块之后再移回去，额外花费了 $2$ 步。
$i$ 在第 2 类连通块内，则我们可以在 $i$ 所在的连通块被处理时将 $i$ 移出去处理其余的第 2 类连通块，处理最多 $c_i - 1$ 个连通块之后，将 $i$ 移回去处理所在的连通块，额外花费了 $0$ 步。
$i$ 在第 3 类连通块内，且 $a_i = b_i$ ，则可以处理最多 $c_i - 1$ 个第 2 类连通块，额外花费了 $1$ 步。
$i$ 在第 3 类连通块内，且 $a_i \ne b_i$ ，则可以处理最多 $c_i - 1$ 个第 2 类连通块，额外花费了 $0$ 步。

考虑如何满足 $i$ 能移出来，我们只需要先拿一个第 3 类连通块中的 $i$ 来盘活整个局面。

于是问题变成给定若干个代价 $\le 2$ 的物品，要求总价值 $\ge x$ 的最小代价。

显然所有代价为 $0$ 的物品都贪心地拿，对于代价为 $1$ 和 $2$ 的物品排序后 Two Pointers 一下即可。

时间复杂度 $\mathcal O(n \log n)$ 。

const int N = 1e5 + 7;
int n, m, a[N], b[N], c[N], d[N], f[N], s[N];
bool v[N];
vi p1, p2, p3, p4;
ll ans, cnt, sum, now;

int get(int x) {
	return x == f[x] ? x : (f[x] = get(f[x]));
}

int main() {
	rd(n, m);
	for (int i = 1; i <= n; i++) f[i] = i, v[i] = 1;
	for (int i = 1; i <= m; i++)
		rd(a[i], b[i], c[i]), ++d[a[i]],
		f[get(a[i])] = get(b[i]), ans += a[i] != b[i];
	for (int i = 1; i <= n; i++) {
		++s[get(i)];
		if (d[i] != 1) v[get(i)] = 0;
	}
	for (int i = 1; i <= n; i++)
		cnt += get(i) == i && v[i] && s[i] > 1;
	if (!cnt) return print(ans), 0;
	ans += cnt;
	for (int i = 1; i <= m; i++) {
		if (c[i] == 1) continue;
		int x = get(i);
		if (v[x] && s[x] == 1) p1.pb(c[i] - 2);
		if (v[x] && s[x] > 1) p2.pb(c[i] - 1);
		if (!v[x] && a[i] == b[i]) p3.pb(c[i] - 1);
		if (!v[x] && a[i] != b[i]) p4.pb(c[i] - 1);
	}
	for (int x : p1) sum += x;
	for (int x : p2) sum += x;
	for (int x : p3) sum += x;
	for (int x : p4) sum += x;
	if (sum < cnt || (p3.empty() && p4.empty())) return print(-1), 0;
	sort(p1.begin(), p1.end());
	sort(p2.begin(), p2.end());
	sort(p3.begin(), p3.end());
	sort(p4.begin(), p4.end());
	if (p4.size()) cnt -= p4.back(), p4.pop_back();
	else ++ans, cnt -= p3.back(), p3.pop_back();
	for (int x : p2) cnt -= x;
	for (int x : p4) cnt -= x;
	if (cnt <= 0) return print(ans), 0;
	now = ans, ans = 1e18, sum = 0;
	for (int x : p3) sum += x;
	for (int i = p1.size(), j = 0; ~i; i--) {
		if (i < (int)p1.size()) sum += p1[i];
		while (j < (int)p3.size() && sum - p3[j] >= cnt) sum -= p3[j++];
		if (sum >= cnt) ans = min(ans, now + 2 * ((int)p1.size() - i) + ((int)p3.size() - j));
	}
	print(ans);
	return 0;
}

Division into Multiples

咕。