在学长的提示下成功做出 D，蓝了，开心。

A. Hard Way

给定一个在第一象限的三角形座标，你可以从 $y=0$ 的任意位置出发，在平面中沿着折线前进但不能穿过三角形。

问三角形的边界上无法到达的位置，其总长度是多少。

分析

题面真 TM 难读，什么玩意。

注意到如果这条边是斜的，那么我们总是可以走一条更斜的线直接到达。如果此边水平，则不能到达。

即输出三角形水平边的长度。

using pii = pair<int, int>;

int main() {
	int T;
	cin >> T;
	while (T--) {
		vector<pii> v(3);
		for (auto &[x, y] : v) {
			cin >> x >> y;
		}
		sort(v.begin(), v.end(), [](pii a, pii b) {
			if (a.second == b.second)
				return a.first < b.first;
			return a.second > b.second;
		});
		if (v[0].second == v[1].second)
			cout << abs(v[0].first - v[1].first) << "\n";
		else
			cout << "0\n";
	}
	return 0;
}

B. Power Walking

有一些能量包，每个小孩的能力增幅是其得到不同种类能量包的个数。

总共有 $n$ 个能量包，其类别分别是 $\{a_i\}$。假如把这些分给 $k$ 个小孩，每个小孩至少得到一个能量包。

求对所有的 $0 \leqslant k \leqslant n$，求这 $k$ 个小孩最小的能量增幅。

分析

设这 $n$ 个能量包中类别不同的共有 $m$ 个。

  • 若 $k \leqslant m$，则至少有 $m$ 的增幅，多出来的 $n-m$ 个可以和相同类别塞给同一个小朋友，没有额外增幅。
  • 若 $k > m$，则至少有 $k$ 的增幅，多出来的 $n-k$ 个仍可以和相同类别合并，没有额外增幅。

总之，最小的能量增幅是 $\max(k, m)$。

int main() {
	int T;
	cin >> T;
	while (T--) {
		int n;
		cin >> n;
		vector<int> a(n);
		for (auto &ai : a)
			cin >> ai;

		int m = n;
		sort(a.begin(), a.end());
		for (int i = 1; i < n; i++)
			m -= a[i] == a[i - 1];

		for (int i = 1; i <= n; i++) {
			cout << max(i, m) << " \n"[i == n];
		}
	}
	return 0;
}

C. Great Sequence

给定 $n$ 个数字 $\{a_i\}$，和一个数字 $x$。如果存在 $a_j$ 满足 $a_j = x a_i$，那么我们可以把这两个数配对。每个数字只能被配对一次。

现在允许往序列 $\{a_i\}$ 中添加数字，问若要让序列中所有数字都被配对，最少添加几个数字。

分析

排序后，双指针配对即可，时间复杂度 $O(n)$。Map 大概也能过，时间复杂度 $O(n \log n)$。

int main() {
	int T;
	cin >> T;
	while (T--) {
		int n;
		ll x;
		cin >> n >> x;
		vector<ll> a(n);
		for (auto &ai : a)
			cin >> ai;
		sort(a.begin(), a.end());
		vector<int> vis(n);
		int l = 0, r = -1;
		while (r < n - 1) {
			r++;
			while (a[l] * x < a[r] || (a[l] * x == a[r] && vis[l]))
				l++;
			if (a[l] * x == a[r])
				vis[l] = vis[r] = true;
		}

		int ans = 0;
		for (auto vi : vis)
			ans += vi;
		cout << n - ans << "\n";
	}
	return 0;
}

D. Repetitions Decoding

给定一个长为 $n$ 的序列 $\{a_i\}$，可以在任意位置插入相同的两个元素 $[c, c]$。

Olya 希望序列能够被分成一系列子序列，并且所有子序列左右重复。

分析

对于左边第一个数 $a_1$，找到右侧与之相同的第一个数 $a_r$，不断在 $a_r$ 右侧插入数字使得 $a[1, r - 1]$ 到 $a[r, 2r - 2]$ 相同。然后再从 $2r-1$ 开始继续操作，直到序列结尾。

若原序列存在数字是出现了奇数次，则一定无解。前述算法一定不能运行到结尾。

注意到当原序列每个数字出现偶数次一定有解。而前述算法每次一定会减少一个数，故一定能找到解。

using pii = pair<int, int>;

int main() {
	int T;
	cin >> T;
	while (T--) {
		int n;
		cin >> n;
		vector<int> v(n);
		for (auto &vi : v)
			cin >> vi;
		bool flag = true;

		vector<pii> ans;
		vector<int> ans2;
		int l = 0;
		while (l < v.size()) {
			int r = -1;
			for (int i = l + 1; i < v.size(); i++) {
				if (v[i] == v[l]) {
					r = i;
					break;
				}
			}
			if (r == -1) {
				flag = false;
				break;
			}

			int len = 1;
			while (l + len < r) {
				v.insert(v.begin() + r + len, {v[l + len], v[l + len]});
				ans.emplace_back(r + len, v[l + len]);
				len++;
			}
			l = r + len;
			ans2.push_back(len * 2);
		}
		if (!flag) {
			cout << "-1\n";
		} else {
			cout << ans.size() << "\n";
			for (auto [x, y] : ans) {
				cout << x << " " << y << "\n";
			}
			cout << ans2.size() << "\n";
			for (auto ai : ans2) {
				cout << ai << " ";
			}
			cout << "\n";
		}
	}
	return 0;
}