Current supplement to D

A. Equidistant Letters

Title Description: give you a string \ (s \), which only contains lowercase letters, and each letter does not appear more than \ (2 \) times. Let you rearrange \ (s \) so that the subscript difference of each pair of characters that appear twice is the same.

Idea: sort \ (s \) so that the subscript difference of each pair of characters that appear twice is \ (1 \).

Time complexity: \ (O (tnlog) \), \ (n \) is the length of the string.

Reference code:

string s;
void solve() {
	cin >> s;
	sort(s.begin(), s.end());
	cout << s << '\n';
	return;
}

B. Minor Reduction

Title Description: give you a decimal number with a length of \ (n \), which is represented by a string. You need to select a subscript \ (I, 1 \ Leq I < n \), and then replace the position of \ (s_i, s_{I + 1} \) with \ (s_i + s_{i + 1} \), and ask the maximum value that can be obtained after this operation.

Data range: \ (1 \ Leq t \ Leq 10 ^ 4, 2 \ Leq n \ Leq 10 ^ {200000}, \ sum n \ Leq 2 \ times 10 ^ 5 \)

Idea: scan backwards first. If there is \ (s_i + s_{i + 1} \geq 10 \), change the position into the sum of the two, otherwise merge \ (s_1, s_2 \).

Time complexity: \ (O(n) \)

Reference code:

string s;
void solve() {
	cin >> s;
	int n = static_cast<int>(s.size());
	for (int i = n - 2; i >= 0; --i) {
		int dx = s[i] - '0' + s[i + 1] - '0';
		if(dx >= 10) {
			s[i] = '1';
			s[i + 1] = '0' + (dx % 10);
			cout << s << '\n';
			return;
		}
	}
	int dx = s[0] - '0' + s[1] - '0';
	cout << dx << s.substr(2, n - 2) << '\n';
	return;
}

C. Monsters And Spells

Title Description: there are \ (n \) monsters with blood strips \ (h_i \) at the time of \ (k_i \). Assuming that the energy of \ (0 \) is released without releasing energy, you can release more energy than the previous time or release \ (1 \) energy each time. Monsters can be killed only when the released energy is not less than \ (h_i \). Ask the minimum energy release number to kill all monsters.

Data range: \ (1 \ Leq t \ Leq 10 ^ 4, 1 \ Leq n \ Leq 100, 1 \ Leq k_i \ Leq 10 ^ 9, 1 \ Leq h_i \ Leq k_i \ Leq 10 ^ 9, \ sum n \ Leq 10 ^ 4 \)

Idea: consider being greedy backwards. For each monster that appears at the \ (k_i \) node, it should at least start increasing from \ (1 \) at the time of \ (k_i - h_i + 1 \). Therefore, traverse backwards. For the current \ (I \), find a \ (J \; (J < I) \) each time, so that \ (k_j < \ mathop {min} \ limits {P = j + 1} ^ {I} \ {k_p-h_p + 1 \} \). Remember \ (need \) indicates the minimum start time to kill the \ (I \) monster. It is necessary to update \ (need \) during the above search, where \ (need = \ mathop {min} \ limits {P = j + 1} ^ {I} \ {k_p-h_p + 1 \} \)

Time complexity: \ (O(\sum n) \)

Reference code:

void solve() {
	int n(0);
	cin >> n;
	vector<int>k(n + 1, 0), h(n + 1, 0);
	for (int i = 1; i <= n; ++i) cin >> k[i];
	for (int i = 1; i <= n; ++i) cin >> h[i];
	long long res = 0;
	int need = 0;
	int idx = n;
	while(idx){
		need = k[idx] - h[idx] + 1;
		long long dx = k[idx];
		--idx;
		while (idx && k[idx] >= need) {
			int dy = k[idx] - h[idx] + 1;
			need = min(need, dy);
			--idx;
		}
		dx = dx - need + 1;
		res += dx * (dx + 1) >> 1;
	}
	cout << res << '\n';
	return;
}

D. Martial Arts Tournament

Title Description: give you \ (n \) numbers \ (a_i \), let you find two integers \ (x, y \; (x < y) \), and divide \ (a_i \) into three parts, less than \ (x \), greater than or equal to \ (Y \) and within \ ([x, y) \). In order to make the number of elements in the three parts meet the power of two, you need to add some numbers to find the minimum number of added numbers.

Data range: \ (1 \ Leq t \ Leq 10 ^ 4, 1 \ Leq n \ Leq 2 \ times 10 ^ 5, 1 \ Leq a_i \ Leq n, \ sum n \ Leq 2 \ times 10 ^ 5 \)

Idea: considering \ (a_i \leq n \), we can make a prefix and optimize the number of numbers in the calculation interval. We enumerate the positions of \ (x \), and then enumerate the power of two, that is \ (x + (1 < < J) \; (0 \ Leq J \ Leq 20) \) as \ (y - 1 \), that is, the second part of the target contains 1 < < J elements. By bisecting the position \ (pos \) of \ (y - 1 \) in the prefix and array, you can find out how many elements each of the three parts contains. Use the corresponding power to subtract what each part contains, which is what needs to be added. Take min for all cases.

Time complexity: \ (O(nlog^2n) \)

Reference code:

const int N = 2e5 + 5;
vector<int> dis(N, 0);
void init() {
	int cur = 0;
	dis[0] = 1;
	for (int i = 1; i < N; ++i) {
		if (i > (1 << cur)) ++cur;
		dis[i] = 1 << cur;
	}
	return;
}
void solve() {
	int n(0), a(0);
	cin >> n;
	vector<int>pre(n + 1, 0);
	for (int i = 1; i <= n; ++i) cin >> a, pre[a]++;
	for (int i = 1; i <= n; ++i) pre[i] += pre[i - 1];
	int res = INT_MAX;
	for (int i = 0; i <= n; ++i) {
		if (i < n && pre[i] == pre[i + 1]) continue;
		int ans = dis[pre[i]] - pre[i];
		for (int j = 0; j <= 20; ++j) {
			int pos = upper_bound(pre.begin(), pre.end(), pre[i] + (1 << j)) - pre.begin() - 1;
			res = min(res, ans + (1 << j) + dis[pre[n] - pre[pos]] - (pre[n] - pre[i]));
			if (pos == n) break;
		}
	}
	cout << res << '\n';
	return;
}