vp CF_edu154(div2)

rhineofts / 2023-09-03 / 原文

第一次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";
}