第一次vp。
9.2 15:10 开始。
之前因为补作业没有打这个 154 场，但是就vp表现来看如果打了可能就要加 $-154$ 了 ( )。
遇到思路卡住的就直接看 jiangly 写的题解，最后开出 $4$ 题，rk1400左右，真实水平应该低于 rk5000。
T1
很简单。只要注意到 $17$ 和 $71$ 同为素数即可。
T2
第一次没想出来。
首先注意到当 $\exists i \ s.t.\ a_i = b_i = 0 \and a_{i+1} = b_{i+1} = 1$ 时，存在合法操作（只需将两串 $[1, i - 1]$ 全部变成 $0$，$[i + 1, n - 2]$ 全部变成 $1$ 即可。）因此猜测必要性也同样满足。
首先注意到如果两串能转换成相等，则这两个字符串可以调成 $00 \dots 01 \dots 11$ 的形式。因此，我们考虑一个字符串 $S$ 且 $S$ 不满足 $s_i = 0, s_{i + 1} = 1$。那么有两种情况：$s_i = s_{i+1}$ 或 $s_i = 1, s_{i + 1} = 0$。当 $s_i = s_{i + 1}$ 时，我们必须改变其中一个。但由于它们相邻且相同，任何有效的修改必然会同时修改它们两个。当 $s_i = 1, s_{i + 1} = 0$ 时，对其中一个的修改必然造成这两个字符的相同。故必要性成立。
代码很简单。
T3
个人认为 T3 比 T4 难。
首先，我们可以注意到当一个数组前面已经是无序时，它就不可能是有序的了。基于这一点，我们记 $f_i$
为 前 $i$ 个数是否有序。特殊地，$f_i = -1$ 表示 （目前）的有序性暂无确定。记录一下 $0$ 的数量，利用 vector 直接维护即可。
细节很多。注意一些特判。
void solve() {
string str;
cin >> str;
vector<int> f; // 前缀是否排序
int tot = 0; // 0的数量
for (char ch : str) {
if (ch == '+') {
f.push_back(-1); //暂未确定
}
else if (ch == '-') {
if (f.back() == 0) tot--;
int x = f.back();
f.pop_back();
if (x == 1 and not f.empty()) { // 如果 f_i 为1，那么f_i-1也为1（这是针对back为-1的修改）
f.back() = 1;
}
}
else if (ch == '1') {
if (tot > 0) { //前缀无序，矛盾
cout << "No\n";
return;
}
if (not f.empty()) { //同上
f.back() = 1;
}
}
else {
if (f.size() <= 1) { //特判（题中规定 数量 <= 1 时是有序的）
cout << "No\n";
return;
}
if (f.back() == 1) { //矛盾
cout << "No\n";
return;
}
if (f.back() == -1) {
tot++; // 增加0的数量
f.back() = 0; //将-1变为0
}
}
debug::print(tot);
}
cout << "Yes\n";
}
T4
将整个数组变成有序的等价于将连续逆序对的数量减至 $0$ 。记乘上的数为 $x$。我们分情况来看：
当 $x = 0$ 时只能单点乘，且等价于在后（前）乘上一个充分大（充分小）的数，可以不用考虑。
当 $x > 0$ 时，每次操作最多只能将连续的一对逆序对变成正序的。
当 $x < 0$ 时，最后答案一定是前面一段全负，后面一段全正。设操作下标为 $k$，则 原数组中 $[0, k]$ 为逆序，$[k + 1, n - 1]$ 为正序。维护一个前缀逆序与前缀正序的数量，这样即可做到 $\mathcal{O(n)}$。
代码如下：
void solve() {
int n;
cin >> n;
vector<int> a(n + 1);
vector<int> pre1(n + 1), pre2(n + 1); // pre1为逆序，pre2为正序、
//由于可以取等，pre1[i] + pre2[i] 可能不等于(大于) i
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
for (int i = 1; i < n; i++) {
pre1[i] = pre1[i - 1] + (a[i] >= a[i + 1]);
}
for (int i = 2; i <= n; i++) {
pre2[i] = pre2[i - 1] + (a[i - 1] <= a[i]);
}
int ans = pre1[n - 1];
for (int i = 2; i <= n; i++) {
int res1 = pre2[i], res2 = pre1[n - 1] - pre1[i];
ans = min(ans, res1 + res2 + 1); //加上乘上负数这一次操作
}
cout << ans << "\n";
}
jiangly 的（额外）空间 $\mathcal{O}(1)$ 的写法（核心思路在于我们只需用到 $[0, k]$ 中的逆序对数量和 $[k + 1, n - 1]$ 中的正序对这一段信息，因此可以直接边统计边维护 $[k + 1, n - 1]$ 中的正序对数：
void solve() {
int n;
std::cin >> n;
std::vector<int> a(n);
for (int i = 0; i < n; i++) {
std::cin >> a[i];
}
int ans = 0;
for (int i = 0; i < n - 1; i++) {
ans += (a[i] >= a[i + 1]);
} //总逆序对数
int res = ans;
for (int i = 1; i < n; i++) {
res -= (a[i - 1] >= a[i]); //减去逆序的(当i = 0 时即为最初ans)
ans = std::min(ans, res + 1);
res += (a[i - 1] <= a[i]); // 加上正序的
} // 当 i = n - 1 时，由于 (n - 2, n - 1]只有一个元素，所以最后一次更新res后无须更新ans，这一定不会更优
std::cout << ans << "\n";
}
后记：
第一次 vp，虽然成绩中规中矩，但思维能力和代码能力都有所改善，且 vp 时他人的实时排名所带来的真实感和紧迫感都不是零散的刷题所能带来的，而这 $1200+$ 的文字经历和对题目的深度思考与细节探究都是非常重要且深刻的。以后也要继续努力。
2023.9.3 0:37