这场感觉好卡。

A - Digit Machine

如果当前数字是 $k$，按下一次后会变成 $a_k$。求按 $3$ 次后的数字。

分析

模拟即可。

int main() {
	vector<int> v(10);
	for (auto &vi : v)
		cin >> vi;
	int x = 0;
	for (int i = 0; i < 3; i++)
		x = v[x];
	cout << x;
	return 0;
}

全部代码请看：Atcoder/ABC241/ABC241A.cpp。

B - Pasta

把数组 $\{b_m\}$ 的数字映射到 $\{a_n\}$ 上，不能重复。问是否能够完全映射。

分析

用 mutiset<int> 模拟即可。

int main() {
	int n, m;
	cin >> n >> m;
	multiset<int> s;
	for (int i = 0; i < n; i++) {
		int t;
		cin >> t;
		s.insert(t);
	}
	for (int i = 0; i < m; i++) {
		int t;
		cin >> t;
		if (s.count(t) == 0) {
			cout << "No";
			return 0;
		}
		s.erase(s.find(t));
	}
	cout << "Yes";
	return 0;
}

全部代码请看：Atcoder/ABC241/ABC241B.cpp。

C - Connect 6

给定一个地图，你可以把两个位置改为 #，问是否能够产生连续的 $6$ 个 #。横、竖、斜皆可。

分析

对于每个点，暴力搜一遍即可。

int main() {
	int n;
	cin >> n;
	vector<string> m(n);
	for (auto &mi : m) {
		cin >> mi;
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			auto sharp = [&](int x, int y) {
				int ti = i, tj = j;
				int sum = 0;
				for (int u = 0; u < 6; u++) {
					if (ti < 0 || tj < 0 || ti >= n || tj >= n) {
						return false;
					}
					sum += m[ti][tj] == '#';
					ti += x, tj += y;
				}
				return sum >= 4;
			};

			bool flag = false;
			flag = flag || sharp(1, 0) || sharp(1, 1) || sharp(0, 1) || sharp(-1, 1);
			flag = flag || sharp(-1, 0) || sharp(-1, -1) || sharp(0, -1) || sharp(1, -1);
			if (flag) {
				cout << "Yes";
				return 0;
			}
		}
	}
	cout << "No";
	return 0;
}

全部代码请看：Atcoder/ABC241/ABC241C.cpp。

D - Sequence Query

给定一个空序列 $A$，和 $Q$ 个询问

  • 1 x，把 $x$ 插入 $A$。
  • 2 x k，在所有小于等于 $x$ 的数中，找出第 $k$ 大数。
  • 3 x k，在所有大于等于 $x$ 的数中，找出第 $k$ 小数。

其中 $k \leqslant 5$。

分析

我还楞了一会，发现 mutiset<ll> 好像可以直接秒。

int main() {
	int Q;
	cin >> Q;
	multiset<ll> s;
	while (Q--) {
		ll op, x, k;
		cin >> op >> x;
		if (op == 1) {
			s.insert(x);
		} else {
			cin >> k;
			auto iter = s.begin();
			bool flag = false;
			if (op == 2) {
				iter = s.upper_bound(x);
				while (iter != s.begin() && k--)
					iter--;
				flag = k > 0;
			} else {
				iter = s.lower_bound(x);
				k--;
				while (iter != s.end() && k--)
					iter++;
				flag = iter == s.end();
			}
			if (flag)
				cout << "-1\n";
			else
				cout << *iter << "\n";
		}
	}
}

全部代码请看：Atcoder/ABC241/ABC241D.cpp。

E - Putting Candies

给定一个长为 $N$ 的序列 $A$，初始数字 $X = 0$。

  • 每次让 $X \gets X + A_{(X \bmod N)}$。

问 $K$ 次操作后有答案是多少。

分析

我第一想法是倍增，然后想了想存在循环节，就不写倍增了。

注意到当值为 $X$ 时，其下一个位置和增加的量仅与 $X \bmod N$ 有关，故取值最多 $n$ 种，必然存在循环。

把环判出来，首尾额外处理一下即可。

int main() {
	ll n, k;
	cin >> n >> k;
	vector<ll> v(n), vis(n);
	for (auto &vi : v)
		cin >> vi;

	auto get = [&](ll u, const ll p = 0) {
		ll ans = p, pos = p % n;
		while (u--) {
			ans += v[pos];
			pos = ans % n;
		}
		return ans - p;
	};

	ll cnt = 0, pos = 0, tsum = 0;
	while (!vis[pos]) {
		vis[pos] = cnt++;
		tsum += v[pos];
		pos = tsum % n;
	}
	ll crc = cnt - vis[pos], left = k - vis[pos];
	ll ans = 0;
	if (left < 0) {
		ans += get(k);
	} else {
		ans = get(crc, pos) * (left / crc) + get(vis[pos] + left % crc);
	}
	cout << ans;
	return 0;
}

全部代码请看：Atcoder/ABC241/ABC241E.cpp。