咕了好久。

A. Alexey and Train

奇怪的模拟。略。

全部代码请看：Codeforces/CF1501/CF1501B.cpp。

B. Napoleon Cake

略。

全部代码请看：Codeforces/CF1501/CF1501B.cpp。

C. Going Home

给定一个数组，请给出是否存在四元组使得

$$ a_w + a_v = a_x + a_y $$

分析

这题很诈骗。注意到 $x+y$ 最多只有 $5 \times 10^6$ 种情况，暴力即可。

int main() {
	int n;
	cin >> n;
	vector<int> a(n);
	for (auto &ai : a) {
		cin >> ai;
	}
	vector<pii> u(N + 1);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < i; j++) {
			int sum = a[i] + a[j];
			if (u[sum] != pii{0, 0}) {
				auto [x, y] = u[sum];
				if (x == i || x == j || y == i || y == j)
					continue;
				printf("YES\n%d %d %d %d", x + 1, y + 1, i + 1, j + 1);
				exit(0);
			}
			u[sum] = {i, j};
		}
	}
	printf("NO");
	return 0;
}

全部代码请看：Codeforces/CF1501/CF1501C.cpp。

D. Two chandeliers

给定两个序列 $\{a_i\}, \{b_i\}$，分别长 $n$ 和 $m$。令无限序列 $\{A_i\}, \{b_i\}$ 是其不断循环。

问第 $k$ 对 $A_i \neq B_i$ 在哪个位置。

分析

考察其相同时刻，显然 $\operatorname{lcm}(n, m)$ 是一个周期，而在一个周期内至多只有 $\min(n, m)$ 次相同。

因此可以用桶得到两个相同的位置 $x, y$，再通过 excrt（我的板子还不知道为啥假了）解方程

$$ p \equiv x \pmod n, p \equiv y \pmod m $$

可以反推出位置 $p$。最后考虑二分答案即可。

int main() {
	ll n, m, k;
	cin >> n >> m >> k;
	vector<int> a(n), b(m);
	for (auto &ai : a) {
		cin >> ai;
	}
	for (auto &bi : b) {
		cin >> bi;
	}
	ll cyc = n * m / std::__gcd(n, m);
	vector<int> tong(2 * (n + m + 1), -1);
	for (int i = 0; i < n; i++) {
		tong[a[i]] = i;
	}
	vector<ll> pos;
	for (int i = 0; i < m; i++) {
		int num = tong[b[i]];
		if (num == -1)
			continue;
		ll p = excrt({num, i}, {n, m});
		if (p != -1)
			pos.push_back(p);
	}
	sort(pos.begin(), pos.end());
	auto get = [&](ll p) -> ll {
		if (pos.empty())
			return 0;
		ll rem = p % cyc;
		ll sum = lower(1, pos.size(), [&](int i) {
			return pos[i - 1] <= rem;
		});
		return p / cyc * pos.size() + sum;
	};
	cout << upper(1, 1E18, [&](ll x) {
		return x - get(x - 1) >= k;
	});

	return 0;
}

全部代码请看：Codeforces/CF1501/CF1501D.cpp。