AtCoder Grand Contest 020 题解

AtCoder Grand Contest 020

Move and Win

答案只与 $a,b$ 是否同奇偶有关。

int main() {
	int n, a, b;
	rd(n, a, b);
	prints((a ^ b) & 1 ? "Borys" : "Alice");
	return 0;
}

Ice Rink Game

倒序考虑即可。

const int N = 1e5 + 7;
int n;
ll a[N], l = 2, r = 2;

int main() {
	rd(n), rda(a, n);
	for (int i = n; i; i--) {
		l = ((l - 1) / a[i] + 1) * a[i], r = r / a[i] * a[i];
		if (l > r) return print(-1), 0;
		r += a[i] - 1;
	}
	print(l, r);
	return 0;
}

Median Sum

设所有元素之和为 $s$ 。

考虑每个非空非全的子集与它的补集之和都等于 $s$ ，加上全集 $s$ 后的中位数，就是最小的 $\ge \lceil \frac s2 \rceil$ 且存在的子集和。

bitset 优化背包时间复杂度 $\mathcal O(\frac{n^3}{w})$ 。

const int N = 2e3 + 7;
int n, a[N], s;
bitset<N*N> b;

int main() {
	rd(n), rda(a, n), b[0] = 1;
	for (int i = 1; i <= n; i++) b |= b << a[i], s += a[i];
	s = (s + 1) >> 1;
	while (!b[s]) ++s;
	print(s);
	return 0;
}

Min Max Repetition

题意

设 $a,b$ 为正整数，定义 $f(a,b)$ 表示满足下列条件的字符串：
- $f(a,b)$ 由恰好 $a$ 个 A 和恰好 $b$ 个 B 构成。
- $f(a,b)$ 最长的字符全相同的子串是满足上述条件的所有字符串中最短的。
- $f(a,b)$ 是满足上述条件的所有字符串中字典序最小的。
给定 $c,d$ ，求 $f(a,b)[c:d]$ 。
$a,b \le 5 \times 10^8$ ， $d-c+1 \le 100$ ，多组数据组数 $T\le 10^3$ 。

题解

最长的字符全相同的子串的长度为 $k = \max(\lceil\frac{a}{b+1}\rceil,\lceil\frac{b}{a+1}\rceil)$ 。

贪心的构造串可以发现答案为 $(\texttt{A}^k\texttt{B})^{\infty}$ 的某个前缀加上 $(\texttt{A}\texttt{B}^k)^{\infty}$ 的某个后缀，二分出分界点即可，时间复杂度 $\mathcal O(T(\log(a+b) + (d-c)))$ 。

代码

int a, b, c, d, k;

inline bool pd(int o) {
	if (!o) return 1;
	if (!(o % (k + 1))) return pd(o - 1);
	int x = a - (o - o / (k + 1)), y = b - o / (k + 1);
	return y <= 1ll * (x + 1) * k;
}

inline void solve() {
	rd(a, b), rd(c, d);
	k = (max(a, b) - 1) / (min(a, b) + 1) + 1;
	int l = 0, r = a + b;
	while (l < r) {
		int mid = (l + r + 1) >> 1;
		if (pd(mid)) l = mid;
		else r = mid - 1;
	}
	for (int i = c; i <= min(l, d); i++)
		printc(i % (k + 1) ? 'A' : 'B');
	for (int i = max(c, l + 1); i <= d; i++)
		printc((a + b - i + 1) % (k + 1) ? 'B' : 'A');
	prints("");
}

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

Encoding Subsets

题意

对于一个 $0/1$ 串，我们可以将其按如下方式编码：
- $0/1$ 串 $0$ 可以被编码为 $\texttt{0}$ ， $0/1$ 串 $1$ 可以被编码为 $\texttt{1}$ 。
- 若 $0/1$ 串 $A$ 可以被编码为 $P$ ， $0/1$ 串 $B$ 可以被编码为 $Q$ ，则 $0/1$ 串 $AB$ 可以被编码为 $PQ$ 。
- 若 $0/1$ 串 $A$ 可以被编码为 $P$ ，对于 $k \ge 2$ ， $0/1$ 串 $A^k$ 可以被编码为 $\texttt{(}P\texttt{x}k\texttt{)}$ 。
显然一个 $0/1$ 串可能有多种编码方案。
定义 $0/1$ 串 $A$ 是 $0/1$ 串 $B$ 的子集，当且仅当 $A$ 和 $B$ 长度，且对于所有 $A_i = 1$ 的 $i$ 满足 $B_i = 1$ 。
给定 $0/1$ 串 $S$ ，求出所有 $S$ 的子集的编码方案数之和。
$|S| \le 100$ ，答案对 $998244353$ 取模。

题解

考虑对于一个固定的 $0/1$ 串如何求解方案数，考虑区间 DP，设 $f_{l,r}$ 表示将区间 $[l,r]$ 编码的方案数， $g_{l,r}$ 表示将区间 $[l,r]$ 编码成单个字符或由一个括号括起来（允许嵌套）的方案数，则转移有： $f_{l,r}=\sum_{k=l}^{r-1}g_{l,k} f_{k+1,r}$

$g_{l,r}=\sum_{d|r-l+1} [d为[l,r]的循环节]f_{l,l+d-1}$

考虑原问题，直接拿字符串来定义状态，在 $g$ 的转移中枚举 $d$ 后对划分出的子串取并进行转移即可。

由于状态数并不多，时间复杂度 $\mathcal O(能过)$ 。

代码

map<string, modint> f, g;

modint F(string s);

modint G(string s) {
	if (g.find(s) != g.end()) return g[s];
	int n = s.size();
	modint ans;
	for (int d = 1; d < n; d++) {
		if (n % d) continue;
		string t = "";
		for (int i = 0; i < d; i++) {
			bool c = 1;
			for (int j = i; j < n; j += d) c &= s[j] - '0';
			t += c + '0';
		}
		ans += F(t);
	}
	return g[s] = ans;
}

modint F(string s) {
	if (f.find(s) != f.end()) return f[s];
	int n = s.size();
	modint ans;
	for (int i = 1; i <= n; i++)
		ans += G(s.substr(0, i)) * F(s.substr(i, n));
	return f[s] = ans;
}

int main() {
	string s;
	rds(s);
	f[""] = 1, g[""] = 1, g["0"] = 1, g["1"] = 2;
	print(F(s));
	return 0;
}

Arcs on a Circle

题意

有一个周长为 $c$ 的圆。
你有 $n$ 条弧，第 $i$ 条弧的弧长为 $l_i$ 。
对于每条弧，你会在圆上随机一个位置作为它的中点放置。
求圆上每个点都被至少一条弧覆盖的概率。
$n \le 6$ ， $c \le 50$ 。

题解

考虑断环为链，以最长弧的一端为端点断开这个环。

由于所有的弧长都是整数，所以我们不关心所有弧起始点的小数部分，我们只关心小数部分之间的大小关系。

我们可以暴力枚举这个大小关系，于是问题变成：在区间 $[0,nc)$ 上，有一条已知长度的从 $0$ 开始的线段，另外还有 $n-1$ 条已知长度，且起点 $\bmod n$ 确定的线段，要求这些线段覆盖整个区间的方案数。

考虑状压 DP，设 $f_{i,j,s}$ 表示当前在点 $i$ ，已经覆盖到了点 $j$ ，使用的线段集合为 $s$ 的方案数，转移时考虑 $i+1$ 是否为某个线段的起点即可。

由于我们一开始选择的是最长的线段，因此因为断开了环而断开的线段在开头处不会有贡献，可以直接忽略掉。

时间复杂度 $\mathcal O((n-1)!n^2c^22^{n-1})$ 。

代码

int n, m, k, l[7], p[7], f[307][307][135];

inline int work() {
	memset(f, 0, sizeof(f));
	f[0][l[n]*n][0] = 1;
	for (int i = 1; i < n * m; i++)
		for (int j = i; j <= n * m; j++)
			for (int s = 0; s <= k; s++)
				if (f[i-1][j][s]) {
					f[i][j][s] += f[i-1][j][s];
					int x = i % n;
					if (!x || s >> (x - 1) & 1) continue;
					f[i][min(n*m,max(j,i+l[p[x]]*n))][s|1<<(x-1)] += f[i-1][j][s];
				}
	return f[n*m-1][n*m][k];
}

int main() {
	rd(n, m), rda(l, n), k = (1 << (n - 1)) - 1;
	sort(l + 1, l + 1 + n), iota(p + 1, p + n, 1);
	ll ans = 0, cnt = 1;
	for (int i = 1; i < n; i++) cnt *= i * m;
	do ans += work();
	while (next_permutation(p + 1, p + n));
	printf("%.20Lf\n", 1.0L * ans / cnt);
	return 0;
}