526互联

Educational Codeforces Round 150 (Rated for Div. 2) B. Keep it Beautiful

发布时间 2023-10-18 21:44:27作者: zsxuan

数组 \(a = [a_1, a_2, \cdots, a_n]\) 被称为是美丽的，如果可以将 \([1, x]\) 段移到 \([x + 1, n]\) 段后面，\(x \geq 0\) ，数组可以构成非降序。

现在有一个数组 \(a\) （一开始为空）和 \(q\) 个询问，第 \(i\) 个询问给一个正整数 \(x_i\) 。需要逐步执行以下操作。

  • 若 \(x_i\) 拼接到 \(a\) 末尾，可以使得 \(a\) 为美丽的，则拼接。并输出 \(1\) 。
  • 否则输出 \(0\) 。

显然是个涉及到细节的分类讨论题，两种思路。

思路一。不难观察到 \(a\) 要么是一段非降序。要么是两端非降序，假设断点在 \(x(a_x < a_{x - 1})\) 。需要满足 \(\forall i \in [2, x - 1], a_i \geq a_{i - 1}\) ， \(\forall i \in [x + 1, n]， a_i \geq a_{i - 1}, max_{i = x}^{n} a_i \leq a_1\) 。

于是有如下的模拟算法：

设输入数组 \(b\) ，指针 \(i\) 从 \(1\) 到 \(n\) ，维护 \(a\) 的末尾值 \(last\) ，且显然 \(b_1 = a_1\) 。

  • 断点未出现：
    若 \(i = 1\) 或者 \(b_i \geq last\) ，则 \(last = b_i\) ，输出 \(1\) 。否则，定义断点出现，若 \(b_i \leq b_1\) ，\(last = b_i\) 。输出 \(0\) 。
  • 断点出现：
    若 \(b_i \geq last\) 并且 \(b_i \leq b_1\) ，\(last = b_i\) ，输出 \(1\) 。否则，输出 \(0\) 。
view 
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
void solve(){
	int n; std::cin >> n;
	std::vector<int> a(n+1);
	for (int i = 1; i <= n; i++) std::cin >> a[i];
	int brk_p = 0, last = 0;
	for (int i = 1; i <= n; i++) {
		if (brk_p == 0) {
			if (i == 1 || a[i] >= last) {
				last = a[i];
				std::cout << 1;
			}
			else if (a[i] <= a[1]) {
				last = a[i];
				std::cout << 1;
				brk_p = i;
			}
			else {
				std::cout << 0;
			}
		}
		else if (brk_p != 0) {
			if (a[i] >= last && a[i] <= a[1]) {
				last = a[i];
				std::cout << 1;
			}
			else {
				std::cout << 0;
			}
		}
	}
	std::cout << '\n';
}
		                
int main() {
	int _ = 1; std::cin >> _;
	while (_--) solve();
	return 0;
}

第二种思路。不妨真的维护一个数组 \(a\) 。且可以把他视为一个循环移位的数组，即 \(1, n\) 相邻。

  • 若 \(a\) 满足 \(\forall i \in [2, n], a_i \geq a_{i - 1}\) 。则显然 \(a\) 是美丽的。
  • 若 \(a\) 中存在一个 \(j\) 使 \(a_j > a_{j + 1}\) 。让循环数组 \(a\) 选择在 \(j + 1\) 断开，于是只需 \(a_{1} \geq a_{j + 1}\) 即可。
  • 若 \(a\) 中存在两个或以上 \(j\) 使 \(a_j > a_{j + 1}\) ，无论选择哪个位置断开 \(a\) ，总会存在至少一个 \(a_x > a_{x + 1}\) 的位置。
view 
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
void solve(){
	int n; std::cin >> n;
	std::vector<int> a;
	int bad = 0;
	for (int i = 1; i <= n; i++) {
		int x; std::cin >> x;
		if (a.empty()) {
			a.push_back(x);
			std::cout << 1;
		}
		else {
			int nxt_bad = bad + (x < a.back());
			if (nxt_bad == 0 || (nxt_bad == 1 && x <= a[0])) {
				a.push_back(x);
				bad = nxt_bad;
				std::cout << 1;
			}
			else {
				std::cout << 0;
			}
		}
	}
	std::cout << '\n';
}
		                
int main() {
	int _ = 1; std::cin >> _;
	while (_--) solve();
	return 0;
}