Educational Codeforces Round 121 (Rated for Div. 2)題解

目前補到D

A. Equidistant Letters

題目描述：給你一個字元串\(s\)，該字元串隻含有小寫字母，且每個字母出現次數不超過\(2\)次，讓你将\(s\)重排，使得每對出現次數為兩次的字元的下标差相同。

思路：将\(s\)排序，使得每對出現次數為兩次的字元的下标差都為\(1\)即可。

時間複雜度：\(O(Tnlogn)\)，\(n\)為字元串長度。

參考代碼：

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

B. Minor Reduction

題目描述：給你一個十進制數，長度為\(n\)，用字元串表示，你需要選擇一個下标\(i , 1 \leq i < n\),然後将\(s_i , s_{i + 1}\)的位置替換成\(s_i + s_{i + 1}\)，問這樣操作後能取得的最大值。

資料範圍：\(1 \leq T \leq 10^4 , 2 \leq n \leq 10^{200000} , \sum n \leq 2 \times 10^ 5\)

思路：先倒着掃一遍，若存在\(s_i + s_{i + 1} \geq 10\)就将該位置變成二者的和，否則将\(s_1 , s_2\)合并。

時間複雜度：\(O(n)\)

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

題目描述：有\(n\)隻怪物，出現在\(k_i\)時刻擁有血條\(h_i\)，假設不釋放能量是釋放了\(0\)的能量，那麼每次你可以釋放比前一次多一的能量，或者釋放\(1\)點能量，隻有當釋放的能量不小于\(h_i\)時才能殺死怪物，問将所有怪物殺死的最小能量釋放數。

資料範圍：\(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\)

思路：考慮倒着貪心，對于每一個出現在\(k_i\)結點的怪物，他至少需要在\(k_i - h_i + 1\)時刻開始從\(1\)開始遞增。故倒着周遊，每次對于目前的\(i\)，找到一個\(j\;(j < i)\)使得\(k_j < \mathop{min}\limits_{p = j + 1}^{i} \{k_p-h_p + 1\}\)。記\(need\)表示殺死第\(i\)個怪物最小的開始時間，在上述找尋的過程中需要更新\(need\)，其中\(need = \mathop{min}\limits_{p = j + 1}^{i} \{k_p-h_p + 1\}\)

時間複雜度：\(O(\sum n)\)

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

題目描述：給你\(n\)個數字\(a_i\),讓你求出兩個整數\(x , y\;(x < y)\)，将\(a_i\)分成三部分，小于\(x\)，大于等于\(y\)和在\([x , y)\)内的。為了讓三部分中元素個數滿足是二的幂次，你需要添加一些數字，求最少的添加數字的數量。

資料範圍：\(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\)

思路：考慮到\(a_i \leq n\)，可以做一個字首和優化計算區間内的數字個數，我們枚舉\(x\)的位置，然後枚舉二的幂次也即\(x + (1 << j)\;(0 \leq j \leq 20)\)作為\(y - 1\)，也即第二部分目标含有

1 << j

個元素，二分求\(y - 1\)在字首和數組中的位置\(pos\)就可以求出三部分各含有多少元素。使用相應的幂次減去各部分含有的就是需要添加的，對所有情況取

min

即可。

時間複雜度：\(O(nlog^2n)\)

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;
}