AtCoder Beginner Contest 243(A-G)

数学不行，摆烂。

A. Shampoo

三个人 F, M, T 按顺序洗澡，其中洗发液用量分别是 $A, B, C$。

现在洗发液的量 $V$，问谁先无法洗澡？

分析

第一次没认真读，WA 了一发。

int main() {
	int V, A, B, C;
	cin >> V >> A >> B >> C;
	V %= A + B + C;
	if (V < A) {
		cout << "F";
	} else if (V < A + B) {
		cout << "M";
	} else {
		cout << "T";
	}
	return 0;
}

全部代码请看：Atcoder/ABC243/ABC243A.cpp。

B. Hit and Blow

给定两个长为 $N$ 的无重复的整数序列 $\{A_i\},\{B_i\}$。找到满足以下条件的数量：

对于 $i$，使得 $A_i = B_i$。问 $i$ 有多少个。
对于 $(i,j)$，使得 $A_i = B_j$ 且 $i \neq j$。问 $(i,j)$ 有多少个。

分析

因为 $N$ 只有 $10^3$，可以非常暴力的计算。

int main() {
	int n;
	cin >> n;
	vector<int> a(n), b(n);
	for (auto &ai : a)
		cin >> ai;
	for (auto &bi : b)
		cin >> bi;
	int ans1 = 0;
	for (int i = 0; i < n; i++)
		ans1 += a[i] == b[i];
	int ans2 = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (j == i)
				continue;
			ans2 += a[i] == b[j];
		}
	}
	cout << ans1 << "\n" << ans2;
	return 0;
}

全部代码请看：Atcoder/ABC243/ABC243B.cpp。

C. Collision 2

给定 $N$ 个人的座标 $(x_i, y_i)$，并且每个人有两个行走的方向 $L,R$。问是否存在一个时间，使得两个人互相碰面？

分析

考虑所有 $y$ 座标相同的人，只需考虑最左侧的 $R$ 和最右侧的 $L$ 是否有碰面机会。

using int3 = tuple<int, int, int>;

int main() {
	int n;
	cin >> n;
	vector<int> x(n), y(n);
	for (int i = 0; i < n; i++) {
		cin >> x[i] >> y[i];
	}
	string s;
	cin >> s;

	vector<int3> v(n + 1);
	for (int i = 0; i < n; i++) {
		v[i] = {x[i], y[i], s[i]};
	}
	v[n] = {-1, -1, -1};
	sort(v.begin(), v.end(), [](int3 a, int3 b) {
		return std::get<1>(a) < std::get<1>(b);
	});

	int l = -2E9, r = 2E9;
	for (int i = 0; i < n - 1; i++) {
		auto [x1, y1, s1] = v[i];
		auto [x2, y2, s2] = v[i + 1];
		if (y1 != y2) {
			l = -2E9, r = 2E9;
		}
		if (s2 == 'L') {
			l = max(l, x2);
		} else {
			r = min(r, x2);
		}
		if (l > r) {
			cout << "Yes";
			exit(0);
		}
	}
	cout << "No";
	return 0;
}

全部代码请看：Atcoder/ABC243/ABC243C.cpp。

D. Moves on Binary Tree

你现在有一个数字 $X$，做 $N$ 次操作：

如果是 $U$，则变成 $X \gets X / 2$。
如果是 $L$，则变成 $X \gets 2X$。
如果是 $R$，则变成 $X \gets 2X + 1$。

保证 $X$ 和答案不超过 $10^{18}$。

分析

注意到 $LU$ 和 $RU$ 可以消去，用栈不断的弹即可。

int main() {
	ll N, X;
	string S;
	cin >> N >> X >> S;
	string v;
	for (auto si : S) {
		if (si == 'U' && !v.empty() && v.back() != 'U') {
			v.pop_back();
		} else {
			v.push_back(si);
		}
	}
	for (auto vi : v) {
		if (vi == 'L')
			X = X * 2;
		else if (vi == 'R')
			X = X * 2 + 1;
		else
			X /= 2;
	}
	cout << X;
	return 0;
}

全部代码请看：Atcoder/ABC243/ABC243D.cpp。

E. Edge Deletion

给定一个 $N$ 个点、$M$ 条边的图 $G$。你对这个图任意的删边得到 $G’$，但是要满足以下条件：

这张图仍是连通的。
任意两点 $s,t$ 在 $G’$ 中的最短距离仍是 $G$ 中的最短距离。

分析

贪心很好想到，证明不会。对于一条边，如果存在别的路径比这条边短（或一样长），那么这条边就可以去掉。

显然经过变换后图仍是连续的，因为最短路仍存在且未改变。

const int N = 300 + 10;
const ll INF = 0x3f3f3f3f3f3f3f3f;

ll G[N][N], f[N][N];
void floyd(int n);

int main() {
	int n, m;
	cin >> n >> m;
	memset(G, 0x3f, sizeof(G));
	memset(f, 0x3f, sizeof(f));
	for (int i = 0; i < m; i++) {
		ll ai, bi, ci;
		cin >> ai >> bi >> ci;
		G[ai][bi] = G[bi][ai] = ci;
		f[ai][bi] = f[bi][ai] = ci;
	}
	for (int i = 1; i <= n; i++) {
		f[i][i] = G[i][i] = 0;
	}

	floyd(n);

	int ans = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = i + 1; j <= n; j++) {
			if (G[i][j] == INF)
				continue;
			bool flag = false;
			for (int k = 1; k <= n; k++) {
				if (i == k || j == k)
					continue;
				if (f[i][k] + f[k][j] <= G[i][j])
					flag = true;
			}
			ans += flag;
		}
	}
	cout << ans;

	return 0;
}

全部代码请看：Atcoder/ABC243/ABC243E.cpp。

F. Lottery

一幅画可以获得 $N$ 种奖中的一种，每种中奖的概率是 $p_i = \frac{W_i}{\sum W_i}$。

问 $K$ 幅画获得恰好 $M$ 种不同的奖的概率是多少。

分析

我往容斥想了好久，没想明白。正解是用 DP 计算组合数。

若我们假定第 $i$ 种奖获得了 $c_i$ 次，那么其机率是

$$ \frac{K!}{\prod c_i!} \prod p_i^{c_i} = K! \prod_{i=1}^n\frac{p_i^{c_i}}{c_i!} $$

考虑 $DP[n][m][k]$，表示有 $n$ 种奖、获得了 $k$ 次奖、有 $m$ 种不同的奖。令 $S$ 是所有奖的全集，那么我们计算的是

$$ DP[n][m][k] = \sum_{C \subset S, |C| = m} K! \prod_{i=1}^n\frac{p_i^{c_i}}{c_i!} $$

可以观察多了第 $n$ 种奖时 DP 的转移情况，有刷表的转移方程（我将不清楚）。

const int N = 60;

int dp[N][N][N];

int main() {
	pre_all(N * 10);

	int n, m, k;
	cin >> n >> m >> k;
	vector<int> p(n);
	int tsum = 0;
	for (int i = 0; i < n; i++) {
		cin >> p[i];
		tsum = (tsum + p[i]) % P;
	}
	int iv_sum = qpow(tsum);
	vector<int> pw[N];
	for (int i = 0; i < n; i++) {
		p[i] = 1ll * p[i] * iv_sum % P;

		pw[i].resize(N);
		pw[i][0] = 1;
		int pi = p[i];
		for (int j = 1; j < N; j++) {
			pw[i][j] = 1ll * pi * ifac[j] % P;
			pi = 1ll * pi * p[i] % P;
		}
	}

	dp[0][0][0] = 1;
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < n; j++) {
			for (int x = 0; x <= k; x++) {
				dp[i][j][x] = mo(dp[i][j][x] + dp[i - 1][j][x]);
				for (int y = 1; y <= k - x; y++) {
					ll mul = 1ll * dp[i - 1][j][x] * pw[i - 1][y];
					dp[i][j + 1][x + y] = (dp[i][j + 1][x + y] + mul) % P;
				}
			}
		}
	}
	cout << 1ll * dp[n][m][k] * fac[k] % P;
	return 0;
}

全部代码请看：Atcoder/ABC243/ABC243F.cpp。

G. Sqrt

初始给定仅有一个数字的序列 $A = (X)$。设 $Y$ 是这个序列的最后一个数，你可以在后面压入 $1$ 到 $\lfloor\sqrt{Y}\rfloor$ 中的任何一个整数，如此操作 $10^{100}$ 次。

问最终序列 $A$ 有多少可能性。

分析

令 $f_n$ 是其解，容易得到

$$ f_n = \sum_{i=1}^{\lfloor\sqrt{n}\rfloor} f_i = f_{\lfloor n\rfloor^2} $$

因此答案只和 $\lfloor \sqrt{n} \rfloor$ 有关。现在的范围是 $3 \times 10^9$，仍需要优化。

令 $g_n = f_{n^2}$，可以得到

$$ g_n = g_{n-1} + g_{\lfloor \sqrt{n} \rfloor} = g_{\lfloor \sqrt{n} \rfloor^2} + (n - \lfloor \sqrt{n} \rfloor^2) g_{\lfloor \sqrt{n} \rfloor} $$

因此

$$ g_{(n+1)^2} = g_{(n+1)^2 - 1} + g_{n+1} = g_{n^2} + 2 n g_n + g_{n+1} $$

故可以预处理平方，复杂度再降到 4 次根号。还需注意 sqrt 精度问题，最好手写二分开根。

ll lsqrt(ll x); // 二分开根

const ll N = 1E5;

vector<ll> v1, v2;

void pre(ll n) {
	v1.resize(n + 1), v2.resize(n + 1);
	v2[1] = v1[1] = 1;
	ll u = 2;
	for (ll i = 2; i <= n; i++) {
		if (u * u == i)
			u++;
		v1[i] = v1[i - 1] + v1[u - 1];
		v2[i] = v2[i - 1] + 2 * (i - 1) * v1[i - 1] + v1[i];
	}
}

int main() {
	int T;
	cin >> T;
	pre(N);
	while (T--) {
		ll x;
		cin >> x;
		ll n = lsqrt(x), sn = lsqrt(n), ret = v2[sn];
		cout << ret + (n - sn * sn) * v1[sn] << "\n";
	}
	return 0;
}

全部代码请看：Atcoder/ABC243/ABC243G.cpp。

A. Shampoo#

分析#

B. Hit and Blow#

分析#

C. Collision 2#

分析#

D. Moves on Binary Tree#

分析#

E. Edge Deletion#

分析#

F. Lottery#

分析#

G. Sqrt#

分析#