AtCoder Grand Contest 024 题解

AtCoder Grand Contest 024

Fairness

每一轮会从 $(a,b,c)$ 变成 $(b+c,a+c,a+c)$，第 $1,2$ 个数之差取反。

所以如果 $k$ 为奇数答案为 $b-a$，否则为 $a-b$。

int main() {
	int a, b, c;
	ll k;
	rd(a, b, c), rd(k);
	print(k & 1 ? b - a : a - b);
	return 0;
}

Backfront

找到最长的区间 $[l,r]$ 满足 $l \sim r$ 在序列中为正序，则答案为 $n-(r-l+1)$。

const int N = 2e5 + 7;
int n, a[N], p[N], ans;

int main() {
	rd(n), rda(a, n);
	for (int i = 1; i <= n; i++) p[a[i]] = i;
	for (int i = 1, c = 0; i <= n; i++)
		if (i == n || p[i+1] < p[i]) ans = max(ans, ++c), c = 0;
		else ++c;
	print(n - ans);
	return 0;
}

Sequence Growing Easy

如果 $a_i \ge i$ 或者 $a_i - a_{i-1} > 1$ 就无解。

否则我们每次可以使用 $t$ 次操作造出来一个 $0,1,2,\cdots,t$ 的序列。

const int N = 2e5 + 7;
int n, a[N];
ll ans;

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

Isomorphism Freak

题意

• 给定一棵 $n$ 个点的树。
• 你可以添加若干个新点，每次可以将其与某个已有的点相连。
• 要求最小化这棵无根树在以每个点为根对应的有根树中本质不同的树的数量，在此基础上最小化叶子的数量。
• $n \le 100$。

题解

设直径为 $d$，本质不同的有根树的数量有下界：

• 若 $d$ 为奇数，下界为 $\frac {d+1}2$。
• 若 $d$ 为偶数，下界为 $\frac d2$。

显然这个下界是可以取到的，设为 $ans$。

考虑如何最小化叶子的数量，显然叶子的数量也有一个下界，大致上为 $\prod_{i=1}^{ans-1} c_i$，其中 $c_i$ 为所有深度为 $i$ 的点的儿子数量的 $\max$（真实值还要根据 $d$ 的奇偶性分类讨论进行微调）。

显然这个下界也是可以取到的。

时间复杂度 $\mathcal O(n^2 \sim n^3)$。

代码

const int N = 107;
int n, d[N], f[N], ans;
vi e[N];

void dfs(int x) {
	for (int y : e[x])
		if (y != f[x]) f[y] = x, d[y] = d[x] + 1, dfs(y);
}

inline ll calc(int x) {
	d[x] = 1, f[x] = 0, dfs(x);
	static int c[N];
	for (int i = 1; i <= ans; i++) c[i] = 0;
	for (int i = 1; i <= n; i++)
		c[d[i]] = max(c[d[i]], (int)e[i].size());
	ll ret = e[x].size();
	for (int i = 2; i < ans; i++) ret *= c[i] - 1;
	return ret;
}

inline ll calc(int x, int y) {
	d[x] = 1, f[x] = y, dfs(x);
	d[y] = 1, f[y] = x, dfs(y);
	static int c[N];
	for (int i = 1; i <= ans; i++) c[i] = 0;
	for (int i = 1; i <= n; i++)
		c[d[i]] = max(c[d[i]], (int)e[i].size()); 
	ll ret = 1;
	for (int i = 1; i < ans; i++) ret *= c[i] - 1;
	return ret * 2;
}

int main() {
	rd(n);
	for (int i = 1, x, y; i < n; i++)
		rd(x, y), e[x].pb(y), e[y].pb(x);
	d[1] = 1, f[1] = 0, dfs(1);
	int x = max_element(d + 1, d + n + 1) - d;
	d[x] = 1, f[x] = 0, dfs(x);
	int y = max_element(d + 1, d + n + 1) - d;
	int c = d[y];
	if (c & 1) {
		ans = (d[y] + 1) / 2;
		while (d[y] != ans) y = f[y];
		x = y;
		ll now = calc(x);
		for (int y : e[x])
			now = min(now, calc(x, y));
		print((ll)ans, now);
	} else {
		ans = d[y] / 2;
		while (d[y] != ans + 1) y = f[y];
		x = f[y];
		print((ll)ans, calc(x, y));
	}
	return 0;
}

Sequence Growing Hard

题意

• 求以序列为元素的满足下列条件的 $n+1$ 元组 $a_{0\dots n}$ 的组数：
  • 对于 $i \in [0,n]$，$a_i$ 长度为 $i$，其包含的元素为 $[1,k]$ 中的整数。
  • 对于 $i \in [1,n]$，$a_{i-1}$ 为 $a_i$ 的子序列。
  • 对于 $i \in [1,n]$，$a_i$ 的字典序 $>a_{i-1}$。
• $n,k \le 300$，答案对 $P$ 取模。

题解

考虑从小到大插入数，这样当插入 $i$ 时，插在所有位置都是合法的。

但是这样会算重复，规定相同数只能插在最后即可。

考虑 DP，设 $f_{i,j,k}$ 表示当前插入到第 $i$ 个数，插入的数为 $j$，有 $k$ 个数之后可以放（即有 $k+1$ 个位置可以放）。

转移是 $\mathcal O(1)$ 的，时间复杂度 $\mathcal O(n^3)$。

代码

const int N = 307;
int n, m;
modint f[N][N][N];

int main() {
	rd(n, m, P);
	f[0][1][0] = 1;
	for (int i = 0; i <= n; i++)
		for (int j = 1; j <= m; j++)
			for (int k = i; ~k; k--)
				if (!!f[i][j][k]) {
					if (k) f[i][j][k-1] += f[i][j][k];
					else f[i][j+1][i] += f[i][j][k];
					f[i+1][j][k] += f[i][j][k] * (k + 1);
				}
	print(f[n][m][0]);
	return 0;
}

Simple Subsequence Problem

题意

• 给定一个 $0/1$ 字符串组成的集合 $s$ 和一个整数 $k$。
• 求出最长的字符串 $t$，满足 $t$ 是 $s$ 中至少 $k$ 个字符串的子序列，在最长的基础上最小化字典序。
• $s$ 并不直接给出，而是通过以下方式给出：
  • 给定 $n$ 和 $n+1$ 个 $0/1$ 字符串 $x_{0\dots n}$，其中对于 $i \in [0,n]$，$x_i$ 的下标从 $0$ 开始，长度为 $2^i$。
  • 对于每对满足 $i \in [0,n], j \in [0,2^i)$ 的二元组 $(i,j)$，若 ${x_i}_j = 1$ 则 $j$ 的 $i$ 个字符的二进制表示（可能有前导零）$\in s$，否则 $\not\in s$。
  • $s$ 中不存在长度 $>n$ 的字符串。
• $n \le 20$，$k \le |s|$。

题解

考虑直接枚举所有可能的 $0/1$ 串，计算它们是多少个 $s$ 中的串的子序列，设串 $a$ 的答案为 $ans_a$。

考虑对于每个 $c \in s$，将 $c$ 的所有子序列 $a$ 的 $ans_a$ 都 $+1$。

考虑 DP 完成这个过程，令 $f(a|b)$ 表示使用 $a$ 去匹配某个原串 $c \in s$，匹配剩下的串为 $b$ 的方案数。

比如 $f(00 | 110110101)$ 可以转移到：

• 匹配了一个 $0$：$f(000 | 110101)$。
• 匹配了一个 $1$：$f(001 | 10110101)$。
• 停止匹配：$f(00 |)$。

则 $ans_a = f(a | )$，边界为 $f(| c) = 1(c \in s)$。

因为 $|a|+|b| \le n$，所以状态数为 $\mathcal O(n2^n)$，转移为 $\mathcal O(1)$。

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

代码

const int N = 21;
int n, k, b[1<<N|1], t[1<<N|1][2], f[N][1<<N|1], ans = 1;
char c;

int main() {
	rd(n, k);
	for (int i = 0; i <= n; i++)
		for (int x = 0; x < 1 << i; x++)
			rdc(c), f[i][1<<i^x] = c - '0';
	b[0] = -1;
	for (int x = 1; x < 2 << n; x++) b[x] = b[x>>1] + 1;
	for (int x = 2; x < 2 << n; x++)
		if (x >> (b[x] - 1) & 1) t[x][1] = x ^ 1 << b[x], t[x][0] = t[t[x][1]][0];
		else t[x][0] = x ^ 3 << (b[x] - 1), t[x][1] = t[t[x][0]][1];
	for (int i = n; i; i--)
		for (int x = 1 << i; x < 2 << n; x++)
			if (f[i][x]) {
				int o = x >> i, B = (x & ((1 << i) - 1)) ^ 1 << i;
				if (t[B][0]) f[b[t[B][0]]][(o<<1^1)<<b[t[B][0]]^t[B][0]] += f[i][x];
				if (t[B][1]) f[b[t[B][1]]][(o<<1^0)<<b[t[B][1]]^t[B][1]] += f[i][x];
				f[0][o] += f[i][x];
			}
	for (int x = 2; x < 2 << n; x++)
		if (f[0][x] >= k && b[x] > b[ans]) ans = x;
	int i = n;
	while (!(ans >> i & 1)) i--;
	while (i--) printc((ans >> i & 1) + '0');
	return 0;
}