Codeforces Round #606 (Div. 1, based on Technocup 2020 Elimination Round 4) 题解

Codeforces Round #606 (Div. 1, based on Technocup 2020 Elimination Round 4)

As Simple as One and Two

贪心：碰到 twone 删 o，碰到 two 删 w，碰到 one 删 n。

const int N = 1.5e5 + 7;
const string t[] = {"twone", "two", "one"};
const int l[] = {5, 3, 3};
int n, v[N];
char s[N];

inline void solve() {
	vi ans;
	rds(s, n);
	for (int i = 1; i <= n; i++) v[i] = 0;
	for (int j = 0; j < 3; j++)
		for (int i = 1; i <= n; i++) {
			bool ok = 1;
			for (int k = 0; ok && k < l[j]; k++)
				if (v[i+k] || s[i+k] != t[j][k]) ok = 0;
			if (ok) {
				for (int k = 0; k < l[j]; k++) v[i+k] = 1;
				ans.pb(i + (j ? 1 : 2));
			}
		}
	print(ans.size());
	for (ui i = 0; i < ans.size(); i++)
		print(ans[i], " \n"[i+1==ans.size()]);
}

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

Two Fairs

由于保证图连通，所以 dfs 找出从一个点出发不经过另外一个点无法到达的点数，两个答案相乘即可。

const int N = 2e5 + 7;
int n, m, a, b, v[N];
vi e[N];

void dfs(int x, int z) {
	v[x] = 1;
	for (ui i = 0; i < e[x].size(); i++) {
		int y = e[x][i];
		if (v[y] || y == z) continue;
		dfs(y, z);
	}
}

inline void solve() {
	rd(n), rd(m), rd(a), rd(b);
	for (int i = 1; i <= n; i++) e[i].clear();
	for (int i = 1, x, y; i <= m; i++) rd(x), rd(y), e[x].pb(y), e[y].pb(x);
	int c = 0, d = 0;
	for (int i = 1; i <= n; i++) v[i] = 0;
	dfs(a, b);
	for (int i = 1; i <= n; i++) c += !v[i];
	for (int i = 1; i <= n; i++) v[i] = 0;
	dfs(b, a);
	for (int i = 1; i <= n; i++) d += !v[i];
	print(1ll * (c - 1) * (d - 1));
}

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

Beautiful Rectangle

不妨设 $r \le c$ 。

根据抽屉原理，若选择的数中重复个数最多为 $k$ ，则一个矩阵 $r \times c$ 有解当且仅当：

$r \times c \le n$
$k \le r$

必要性显然，充分性可以构造证明。

考虑将所有选择的数从小到大依次斜项填入矩阵中，可以发现这样不会造成冲突。

const int N = 4e5 + 7;
int n, a[N], b[N], d[N], t;
map< int, int > c;
set< pi > s;

inline int get() {
	if (!b[t]) --t;
	return --b[t], a[t];
}

int main() {
	rd(n);
	for (int i = 1, x; i <= n; i++) rd(x), ++c[x];
	for (auto x : c) s.insert(mp(x.se, x.fi));
	for (auto x : s) a[++t] = x.se, b[t] = x.fi;
	for (int i = 1; i <= t; i++) d[i] = d[i-1] + b[i];
	int ans = 0, p, q;
	for (int i = 1; i * i <= n; i++) {
		int o = upper_bound(b + 1, b + t + 1, i) - b - 1, x = d[o] + (t - o) * i;
		x = x / i * i;
		if (x / i >= i && ans < x) ans = x, p = i;
	}
	print(ans), print(p, ' '), print(q = ans / p);
	for (int i = 1; i <= t; i++) b[i] = min(b[i], p);
	vi e[p];
	for (int i = 0; i < p; i++) e[i].resize(q);
	for (int j = 0; j < q; j++)
		for (int i = 0; i < p; i++)
			e[i][(i+j)%q] = get();
	for (int i = 0; i < p; i++)
		for (int j = 0; j < q; j++)
			print(e[i][j], " \n"[j+1==q]);
	return 0;
}

Tree Elimination

首先，不同的序列数量等同于消除标记的方案数。

考虑树形 dp。我们称一个点被一条边覆盖，表示这个点在考虑到这条边时选择消除了这个点上的标记。

设 $f_{x,0/1/2/3}$ 分别表示：点 $x$ 是被自己的父亲边之前的边覆盖的、点 $x$ 是被自己的父亲边覆盖的、点 $x$ 是被自己的父亲边之后的边覆盖的、点 $x$ 没有被覆盖。

那么对于点 $y \in \operatorname{son}_ x$ ，考虑 $f_ {x,0/2}$ ：

点 $y$ 不能被覆盖，即 $f_{y,2/3}$ 。
定义点 $z (\in \operatorname{son}_ x) < y$ 是指边 $(x,z)$ 在边 $(x,y)$ 之前，则点 $z$ 一定要被覆盖，即 $f_ {z,0/1}$ 。
定义点 $z (\in \operatorname{son}_ x) > y$ 是指边 $(x,z)$ 在边 $(x,y)$ 之后，则点 $z$ 可以被覆盖也可以不被覆盖，但不能被边 $(x,z)$ 覆盖，即 $f_ {z,0/2/3}$ 。

因此有转移：

$f_ {x, 0/2} = \sum_ {y \in \operatorname{son}_ x} \left( f_ {y, 2 / 3} * \prod_ {z<y} f_ {z, 0 / 1} * \prod_ {z>y} f_ {z, 0 / 2 / 3} \right)$

考虑 $f_{x,1}$ ，有转移：

$f_{x, 1} = \prod_{y < fa_x} f_{y, 0 / 1} * \prod_{y > fa_x} f_{y, 0 / 2 / 3}$

考虑 $f_{x,3}$ ，有转移：

$f_{x,3} = \prod_{y} f_{y,0/1}$

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

const int N = 2e5 + 7;
int n, m, k;
vi e[N];
modint f[N][4], a[N], b[N], c[N];

void dfs(int x, int fa) {
	for (int y : e[x]) if (y != fa) dfs(y, x);
	a[m=k=0] = 1;
	for (int y : e[x])
		if (y == fa) k = m;
		else  ++m, a[m] = a[m-1] * (f[y][0] + f[y][1]), b[m] = f[y][2] + f[y][3], c[m] = f[y][0] + b[m];
	c[m+1] = 1;
	for (int i = m; i; i--) c[i] *= c[i+1];
	for (int i = 1; i <= m; i++) f[x][(i>k)<<1] += a[i-1] * b[i] * c[i+1];
	f[x][1] = a[k] * c[k+1], f[x][3] = a[m];
}

int main() {
	rd(n);
	for (int i = 1, x, y; i < n; i++) rd(x), rd(y), e[x].pb(y), e[y].pb(x);
	dfs(1, 0), print(f[1][0] + f[1][2] + f[1][3]);
	return 0;
}

Four Stones

题目太神仙了，先咕咕咕着。

Asterisk Substrings