AtCoder Regular Contest 108

2024-03-08 10:53:45

题目传送门：AtCoder Regular Contest 108。

目录

A - Sum and Product

要求 \(x + y = S\) 且 \(x \times y = P\)，枚举 \(P\) 的所有因数进行检查。时间复杂度为 \(\mathcal O (\sqrt{M})\)。

#include <cstdio>

typedef long long LL;

LL N, M;

int main() {
	scanf("%lld%lld", &N, &M);
	for (LL x = 1; x * x <= M; ++x) if (M % x == 0)
		if (x + M / x == N) return puts("Yes"), 0;
	puts("No");
	return 0;
}

B - Abbreviate Fox

维护一个栈，每当栈顶连续三个是 fox 就弹栈三次。时间复杂度为 \(\mathcal O (N)\)。

#include <cstdio>

const int MN = 200005;

int N, tp;
char stk[MN];

int main() {
	scanf("%d", &N);
	for (int i = 1; i <= N; ++i) {
		char s[3];
		scanf("%1s", s);
		stk[++tp] = *s;
		if (tp >= 3 && stk[tp - 2] == 'f' && stk[tp - 1] == 'o' && stk[tp] == 'x') tp -= 3;
	}
	printf("%d\n", tp);
	return 0;
}

C - Keep Graph Connected

考察一棵生成树，仅需对树构造解即可。同时也显示了没有无解的情况。

随意钦点一个点为根，把它的权值设为任意值，然后自顶向下赋权。

如果该点的双亲结点的权值与连接它们的边权相同则该点赋一个与其不同的权，否则赋该边边权。

显然树中所有边均得到保留。时间复杂度为 \(\mathcal O (N + M)\)。

#include <cstdio>
#include <vector>

const int MN = 100005, MM = 200005;

int N, M;
int eu[MM], ev[MM], ew[MM];
std::vector<int> G[MN];
int col[MN];

void DFS(int u) {
	for (int i : G[u]) {
		int v = u ^ eu[i] ^ ev[i];
		if (col[v]) continue;
		col[v] = ew[i];
		if (col[v] == col[u])
			col[v] = col[v] % N + 1;
		DFS(v);
	}
}

int main() {
	scanf("%d%d", &N, &M);
	for (int i = 1; i <= M; ++i) {
		scanf("%d%d%d", &eu[i], &ev[i], &ew[i]);
		G[eu[i]].push_back(i);
		G[ev[i]].push_back(i);
	}
	col[1] = 1, DFS(1);
	for (int i = 1; i <= N; ++i) printf("%d\n", col[i]);
	return 0;
}

D - AB

只有 \(16\) 种不同的输入，写个暴力找规律即可。有三种分类：

其中一种是全 \(1\)，一种是除了 \(N = 2\) 外全 \(2^{N - 3}\)，一种是 \(\mathrm{Fibonacci}[N - 3]\)。时间复杂度为 \(\mathcal O (N)\) 或 \(\mathcal O (\log N)\)。

#include <cstdio>

const int Mod = 1000000007;

int N;
char AA[3], AB[3], BA[3], BB[3];

void pow2() {
	int n = N - 3;
	int res = 1;
	for (int i = 1; i <= n; ++i)
		res = res * 2 % Mod;
	printf("%d\n", res);
}

void fib() {
	int n = N - 3;
	int a1 = 1, a2 = 1;
	for (int i = 1; i <= n; ++i) {
		int tmp = (a1 + a2) % Mod;
		a1 = a2, a2 = tmp;
	}
	printf("%d\n", a2);
}

int main() {
	scanf("%d%1s%1s%1s%1s", &N, AA, AB, BA, BB);
	int s = (*AA == 'B') << 3 | (*AB == 'B') << 2 | (*BA == 'B') << 1 | (*BB == 'B');
	if (N <= 3) return puts("1"), 0;
	if (s == 4 || s == 10 || s == 11 || s == 12) pow2();
	else if (s == 6 || s == 8 || s == 9 || s == 14) fib();
	else puts("1");
	return 0;
}

E - Random IS

补充 \(a_0 = 0\) 以及 \(a_{N + 1} = N + 1\)。并且假设现在钦点选中了 \(0\) 和 \(N + 1\) 这两个位置上的数。

考虑 \(\operatorname{dp}(i, j)\) 表示只考虑 \(i \sim j\) 之间的元素，钦点选中了 \(a_i\) 和 \(a_j\)，其他都还没选，问最终期望选多少个（不包括 \(a_i\) 和 \(a_j\)）。

则答案即为 \(\operatorname{dp}(0, N + 1)\)。考虑类似区间 DP 的转移，即枚举中间第一次选择了 \(a_k\)。但是两侧如何合并？

实际上两侧的贡献可以看作独立。因为虽然概率会互相影响，但是仅关心每一部分内的相对概率已经足够了，因为两侧具体选择了什么不会产生影响，影响的只有概率，但是概率只需考虑每侧相对的即可。所以有：

\[\operatorname{dp}(i, j) = 1 + \frac{1}{c} \sum_{\substack{k \\ a_i < a_k < a_j}} (\operatorname{dp}(i, k) + \operatorname{dp}(k, j)) \]

其中 \(c\) 为合法的 \(k\) 的数量，必须至少为 \(1\)。如果 \(c = 0\) 则 \(\operatorname{dp}(i, j) = 0\)。

所以我们可以分别考虑 \(\displaystyle \sum_{k} \operatorname{dp}(i, k)\) 和 \(\displaystyle \sum_{k} \operatorname{dp}(k, j)\)，然而它们其实是对称的。

也就是，我们可以按照 \(j - i\) 递增计算（正常的区间 DP 都是如此）。然后
对于一个 \((i, j)\) 仅需要计算满足 \(a_k < a_j\) 的 \(\operatorname{dp}(i, k)\) 之和，这可以使用树状数组维护。

对于 \(c\) 的计算可以使用二维前缀和。时间复杂度为 \(\mathcal O (N^2 \log N)\)。

#include <cstdio>

typedef long long LL;
const int Mod = 1000000007;
const int MN = 2005;

int N, A[MN], S[MN][MN], Inv[MN];
int bit1[MN][MN], bit2[MN][MN];

inline void Add(int *b, int i, int x) {
	for (; i <= N; i += i & -i) b[i] -= Mod - x, b[i] += b[i] >> 31 & Mod;
}
inline int Qur(int *b, int i) {
	int s = 0;
	for (; i; i -= i & -i) s -= Mod - b[i], s += s >> 31 & Mod;
	return s;
}

int main() {
	scanf("%d", &N);
	for (int i = 1; i <= N; ++i) {
		for (int j = 1; j <= N; ++j) S[i][j] = S[i - 1][j];
		scanf("%d", &A[i]);
		for (int j = A[i]; j <= N; ++j) ++S[i][j];
	}
	Inv[1] = 1;
	for (int i = 2; i <= N; ++i) Inv[i] = (LL)(Mod - Mod / i) * Inv[Mod % i] % Mod;
	A[0] = 0, A[N + 1] = N + 1;
	for (int dif = 2; dif <= N + 2; ++dif) {
		for (int i = 0; i + dif <= N + 1; ++i) {
			int j = i + dif;
			if (A[i] > A[j]) continue;
			int c = S[j - 1][A[j] - 1] - S[j - 1][A[i]] - S[i][A[j] - 1] + S[i][A[i]];
			if (!c) continue;
			int v = ((LL)(Qur(bit1[i], A[j] - 1) + Qur(bit2[j], N - A[i])) * Inv[c] + 1) % Mod;
			if (j <= N) Add(bit1[i], A[j], v);
			if (i >= 1) Add(bit2[j], N - A[i] + 1, v);
			if (i == 0 && j == N + 1) printf("%d\n", v);
		}
	}
	return 0;
}

F - Paint Tree

考察这棵树的某一条直径，假设其两端点分别为 \(u_1\) 和 \(u_2\)。钦点 \(u_1\) 的颜色为黑色，最后答案乘 \(2\) 即可。

如果 \(u_2\) 的颜色与 \(u_1\) 相同则 niceness 为直径长度，向答案贡献 \(2^{N - 2}\) 倍。

如果 \(u_2\) 的颜色与 \(u_1\) 不同则易证 niceness 一定是 \(u_1\) 与某个点或 \(u_2\) 与某个点之间的距离。

处理出其他 \(N - 2\) 个点与 \(u_1\) 和 \(u_2\) 之间的距离，相当于每个点选择其一进行染色，niceness 为其中最大值。

要计算 niceness 之和，考虑：

\[\begin{aligned} \sum \mathrm{niceness} &= \sum_{x = 1}^{\infty} \# [\mathrm{niceness} \ge x] \\ &= \sum_{x = 1}^{N} \# [\mathrm{niceness} \ge x] \\ &= \sum_{x = 1}^{N} (2^{N - 2} - \# [\mathrm{niceness} < x]) \\ &= N 2^{N - 2} - \sum_{x = 1}^{N} \# [\mathrm{niceness} < x] \end{aligned} \]

所以答案（乘 \(2\) 前）为 \(\displaystyle (N + \mathrm{diameter}) 2^{N - 2} - \sum_{x = 1}^{N} \# [\mathrm{niceness} < x]\)。

要计算后者，注意到每个结点独立，方案数为 \(0\) 或 \(1\) 或 \(2\)。

可以把 \(\operatorname{dis}(v, u_1)\) 和 \(\operatorname{dis}(v, u_2)\) 算一下，记在桶里拉个链，然后扫描线处理，见代码。时间复杂度为 \(\mathcal O (N)\)。

#include <cstdio>
#include <algorithm>
#include <vector>

typedef long long LL;
const int Mod = 1000000007;
const int MN = 200005;

int N, pw2[MN];
std::vector<int> G[MN], V[MN];

int dep[MN], dep1[MN], dep2[MN];
void DFS(int u, int p) {
	dep[u] = dep[p] + 1;
	for (int v : G[u]) if (v != p) DFS(v, u);
}

int c[MN];
int main() {
	dep[0] = -1, pw2[0] = 1;
	scanf("%d", &N);
	for (int i = 1; i <= N; ++i) pw2[i] = pw2[i - 1] * 2 % Mod;
	for (int i = 1, x, y; i < N; ++i)
		scanf("%d%d", &x, &y),
		G[x].push_back(y),
		G[y].push_back(x);
	DFS(1, 0);
	int u1 = std::max_element(dep + 1, dep + N + 1) - dep;
	DFS(u1, 0);
	for (int i = 1; i <= N; ++i) dep1[i] = dep[i];
	int u2 = std::max_element(dep + 1, dep + N + 1) - dep;
	DFS(u2, 0);
	for (int i = 1; i <= N; ++i) dep2[i] = dep[i];
	for (int i = 1; i <= N; ++i) if (i != u1 && i != u2)
		V[dep1[i]].push_back(i),
		V[dep2[i]].push_back(i);
	int Ans = (LL)pw2[N - 2] * (dep1[u2] + N) % Mod;
	int Val = 1, cnt = N - 2;
	for (int i = 1; i <= N; ++i) {
		if (!cnt) Ans = (Ans - Val + Mod) % Mod;
		for (int u : V[i]) {
			if (c[u]) Val = Val * 2 % Mod;
			else --cnt;
			++c[u];
		}
	}
	printf("%d\n", Ans * 2 % Mod);
	return 0;
}
上一篇：[ARC101C] Ribbons On the Tree


下一篇：[CF1370E] Binary Subsequence Rotation - 贪心