Educational Codeforces Round 128 (Rated for Div. 2)

A. Minimums and Maximums

题目大意

一个beautiful数组需要同时具备一下两个条件：

• 在这个数组中至少有$l_1$且至多有$r_1$个元素的值等于数组中的最小值。
• 在这个数组中至少有$l_2$且至多有$r_2$个元素的值等于数组中的最大值。

给定$l_1, r_1, l_2, r_2$，你的任务是计算数组中最少的的元素个数。

题目解析

如果$ [l_1, r_1] $ 和 $ [l_2, r_2] $ 的交集为空，那我们至少需要两种不同的元素来构造这个数组，那么最小的元素个数是 $l_1 + l_2$。
如果$ [l_1, r_1] $ 和 $ [l_2, r_2] $ 的交集不为空，我们设定他们的交集是 $ [l, r] $ ，可以看出 $ l = \max(l_1, l_2), r = \min(r_1, r_2)$ 。这时可以用一种元素来构造这个数组，即最大值等于最小值，那么最小的元素个数就是$\max(l_1, l_2)$。

参考代码

int main() {
    int t;
    cin >> t;
    while(t--){
        int l1, r1, l2, r2;
        cin >> l1 >> r1 >> l2 >> r2;
        int l = l1, r = r1;
        l = max(l, l2), r = min(r, r2);
        if(l <= r){ // 交集不为空
            cout << l << endl;
        }else {     // 交集为空
            cout << l1 + l2 << endl;
        }
    }
    return 0;
}

B. Robots

题目大意

现在有一个 $n$ 行 $m$ 列区域，区域内有些格子是空闲的（用E来表示），有些格子是包含机器人（用R来表示）。

现在可以同时将所有的机器人进行上下左右移动，不能将机器人移出区域。

问能不能移动之后，使得一个机器人移动左上角。

题目解析

首先把机器人所在的最小矩形框出来，如下图黄色区域所示。

当黄色矩形在区域内移动时，边界不能移出区域。又因为所有的机器人都在区域内，所以判断能不能移动机器人到左上角等于黄色区域的左上角是不是机器人。

参考代码

int main() {
    fastIO();
    int t;
    cin >> t;
    while(t--){
        int n, m;
        cin >> n >> m;
        // [mx, my] 黄色区域的左上角的位置
        int mx = inf, my = inf; 
        vector<int> arr(n, 0), brr(m, 0);
        vector<string> vecs(n);
        for(int i = 0; i < n; ++i){
            cin >> vecs[i];
            for(int j = 0; j < m; ++j){
                if(vecs[i][j] == 'R'){
                    mx = min(mx, i);
                    my = min(my, j);
                }
            }
        }
        if(vecs[mx][my] == 'R') cout << "YES\n";
        else cout << "NO\n";
    }
    return 0;
}

C. Binary String

题目大意

给你一个只包含0和1的字符串。
你可以从字符串的头部或者删除一些字符（删除字符之后，字符串可能为空）。这个操作的花费是以下两个指标的最大值：

• 操作完成之后，字符串中剩余的0的数目。
• 操作完成之后，字符串中移除的1的数目。

问最小的花费。

题目解析

二分枚举一下结果 $ans$ 。
然后对于每个枚举值，使用双指针遍历一遍字符串，要求双指针的区间内的0的数目不超过 $ans$ ，且区间长度越长越好 。然后判断双指针区间之外的部分的1的数目是否也满足不超过 $ans$ 。

参考代码

int main() {
    fastIO();
    int t;
    cin >> t;
    while(t--){
        string s;
        cin >> s;
        int n = s.length();
        //前缀的1的数目
        vector<int> sum1(n + 1, 0); 
        //前缀的0的数目
        vector<int> sum0(n + 1, 0);
        for(int i = 0; i < n; ++i){
            sum1[i + 1] = sum1[i] + s[i] - '0';
            sum0[i + 1] = sum0[i] + ((s[i] - '0') ^ 1);
        }
        
        // 检查当前的 ans 是否满足条件
        auto&& check = [&](int cur) -> bool{
            for(int l = 0, r = 1; r <= n; ++r){
                // 调整左边的指针，使得区间内0的数目不超过cur
                while(l < r and sum0[r] - sum0[l] > cur) l++;
                // 判断双指针外1的数目是否满足
                if(sum1[n] - sum1[r] + sum1[l] - sum1[0] <= cur) return true;
            }
            return false;
        };
        /** 二分 ans **/
        int ans = n;
        for(int i = (1 << 20); i; i >>= 1){
            if(ans - i >= 0 and check(ans - i)){
                ans -= i;
            }
        }
        cout << ans << endl;
    }
    return 0;
}

D. Dog Walking

题目大意

你在左右方向长廊上遛🐶，刚开始你站在位置为 $0$ 的地方。

你想给🐶一些自由，所以你会解开绳子，让狗自己活动一下。
狗能活动的时间是 $n$ 分钟，对于第 $i$ 分钟，狗的行为由 $a_i$ 来表示。

• $a_i < 0$ 代表🐶往左走了 $|a_i|$ 米。
• $a_i = 0$ 不确定🐶怎么走。(Unknown)
• $a_i > 0$ 代表🐶往右走了 $|a_i|$ 米。

$n$ 分钟之后，🐶会回到你身边，就是位置为 $0$ 的地方。

对于 Unknown 的时刻，你可以设定了 $a_i \in [-k, k]$（如果将 $a_i$ 设定为 $0$，那么它认为是原地不动）。

问通过设定Unknown的时刻的🐶的行为，🐶最大的活动范围是多大？最大的活动范围指的是狗能到达的最左边和最右边之内的所有点。

题目解析

枚举中两个不同时刻，假定在这两个时刻 $i, j$ 他们分别是🐶能到达最左边和最右边。

如果在 $i, j$ 时刻内，没有Unknown的时刻。那么狗能活动的最大范围就是 $i$ 时刻所处位置到 $j$ 时刻所处位置的距离的绝对值，和 $i, j$ 时刻中间的所处位置无关。

如果在 $i, j$ 时刻内，有Unknown的时刻。那么可以通过调整 $i, j$ 时刻内的Unknown时刻的狗子的行为，来调整狗子 $i$ 时刻所处位置到 $j$ 时刻所处位置的距离的绝对值的最大值。首先假定Unknown时刻狗子原地不动，如果 $i$ 时刻的狗子所在的位置在 $j$ 时刻的位置的左边，那么Unknown设定为满足条件的最大值的时候，那么狗子的移动范围就最大了。反之亦然。

参考代码

int main() {
    int n;
    ll k;
    cin >> n >> k;
    vector<ll> arr(n + 1, 0);
    for(int i = 1; i <= n; ++i) cin >> arr[i];
    ll sum = accumulate(itr(arr), 0ll); //统计Unknown都设定为0的情况下，狗子的最终位置。
    vector<int> zeros(n + 1, 0); // 统计前缀中0的数目
    for(int i = 1; i <= n; ++i){
        if(!arr[i]){
            zeros[i] = zeros[i - 1] + 1;
        }else{
            zeros[i] = zeros[i - 1];
        }
    }
    vector<ll> pref(n + 1, 0); // 统计Unknown都设定为0的情况下，狗子的前缀移动位置。
    for(int i = 1; i <= n; ++i) pref[i] = pref[i - 1] + arr[i];
    if(zeros[n] * k < abs(sum)){  // 设定了所有Unknown的时刻，狗子都不能返回初始点
        cout << -1 << endl;
        return 0;
    }
    vector<ll> vals(zeros[n], 0); // 设定狗子的Unknown时刻的情况集合，要求所有元素的绝对值之和尽量大，并且所有元素之和等于-sum
    ll tmp = abs(sum);
    for(int i = 0; i < zeros[n]; ++i){
        vals[i] = min(tmp, k);
        tmp -= vals[i];
    }
    for(int i = (int)zeros[n]- 1; i > 0 and !vals[i]; i -= 2){
        vals[i] += k;
        vals[i - 1] -= k;
    }
    int m = zeros[n];
    if(sum > 0){
        for(auto& it: vals) it = -it;
    }
    sort(itr(vals));
    vector<ll> prefv(m + 1, 0); 
    for(int i = 0; i < m; ++i){
        prefv[i + 1] = prefv[i] + vals[i];
    }
    ll ans = 1;
    for(int i = 1; i <= n; ++i){
        for(int j = 0; j < i; ++j){
            int tmpz = zeros[i] - zeros[j];
            ll tv = pref[i] - pref[j];
            ll sv1 = prefv[tmpz], sv2 = prefv[m] - prefv[m - tmpz];
            ans = max(ans, max(abs(tv + sv1), abs(tv + sv2)) + 1);
        }
    }
    cout << ans << endl;
    return 0;
}

E. Moving Chips

题目大意

给你一个 $2 \times n$ 的棋盘，棋盘上面的棋子可以往相邻的格子上面移动。每次可以将一枚棋子移动到相邻的格子上，如果格子上面存在棋子，那么移动的这枚棋子将会消失。

问最少的操作次数，使得棋盘上面只存在 $1$ 枚棋子。

题目解析

对于第 $i, j$ 个位置，分别考虑将包含当前列的左边的所有棋子移动到当前位置所需要的最小操作次数dpl[i][j]。
对于第 $i, j$ 个位置，分别考虑将包含当前列的右边的所有棋子移动到当前位置所需要的最小操作次数dpr[i][j]。

对于dpl[i][j]，它的转移方式是两种：

• 从dpl[i][j - 1] 将包含 $j - 1$ 列的所有左边的棋子转移到当前位置。
  dpl[i][j] = dp[i][j - 1] + 1
  如果 $i \oplus 1, j$ 位置存在一枚棋子，那么也需要转移过来。dpl[i][j]++
• 从dpl[i^1][j - 1] 将包含 $j - 1$ 列的所有左边的棋子转移到当前位置。
  dpl[i][j] = dp[i^1][j - 1] + 2
  如果 $j - 1$ 列及左边没有棋子，这种情况包含在上面一种情况当中了，就不再考虑。

最后考虑左右合并位置是$i, j$，那么左右的花费就是dpl[i][j - 1] + dpr[i][j]，如果左边和右边都有棋子，那么还需要加上他们合并的花费 1 。

参考代码

PS: 代码中的 dpl[i][j], dpr[i][j]的两维和上述分析中不同。

int main() {
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        vector<string> s(2);
        for(auto& it: s) cin >> it;
        vector<vector<int>> dpl(n, vector<int>(2, 0)), dpr(n, vector<int>(2, 0));
        for(int i = 0; i < n; ++i){ // 统计 dpl
            if(i == 0){
                if(s[1][i] == '*') dpl[i][0] = 1;
                if(s[0][i] == '*') dpl[i][1] = 1;
            }else{
                if(dpl[i - 1][0] > 0 or s[0][i - 1] == '*') dpl[i][0] = dpl[i - 1][0] + 1;
                if(dpl[i - 1][1] > 0 or s[1][i - 1] == '*') dpl[i][1] = dpl[i - 1][1] + 1;
                if(s[1][i] == '*') dpl[i][0]++;
                if(s[0][i] == '*') dpl[i][1]++;
                if(dpl[i - 1][1] or s[1][i - 1] == '*') dpl[i][0] = min(dpl[i - 1][1] + 2, dpl[i][0]);
                if(dpl[i - 1][0] or s[0][i - 1] == '*') dpl[i][1] = min(dpl[i - 1][0] + 2, dpl[i][1]);
            }
        }
        for(int i = n - 1; i >= 0; --i){// 统计 dpr
            if(i == n - 1){
                if(s[1][i] == '*') dpr[i][0] = 1;
                if(s[0][i] == '*') dpr[i][1] = 1;
            }else{
                if(dpr[i + 1][0] > 0 or s[0][i + 1] == '*') dpr[i][0] = dpr[i + 1][0] + 1;
                if(dpr[i + 1][1] > 0 or s[1][i + 1] == '*') dpr[i][1] = dpr[i + 1][1] + 1;
                if(s[1][i] == '*') dpr[i][0]++;
                if(s[0][i] == '*') dpr[i][1]++;
                if(dpr[i + 1][1] or s[1][i + 1] == '*') dpr[i][0] = min(dpr[i + 1][1] + 2, dpr[i][0]);
                if(dpr[i + 1][0] or s[0][i + 1] == '*') dpr[i][1] = min(dpr[i + 1][0] + 2, dpr[i][1]);
            }
        }
        int ans = min(min(dpl[n - 1][0], dpl[n - 1][1]), min(dpr[0][0], dpr[0][1]));  //处理两端的情况
        for(int i = 1; i < n; ++i){ // 处理合并的情况
            for(int j = 0; j < 2; ++j){
                int tmp = dpl[i - 1][j] + dpr[i][j];
                if((dpl[i - 1][j] or s[j][i - 1] == '*') and (dpr[i][j] or s[j][i] == '*')) ++tmp;
                ans = min(ans, tmp);
            }
        }
        cout << ans << endl;
    }
    return 0;
}