Codeforces Round 1085 (Div. 1 + Div. 2)——CF-2207-赛后总结-A，C 题总结（一定要关注数据范围限制）（01 串操作，抽水）

基本情况

https://codeforces.com/contest/2207

两道题目，排 2705 还可以，还不赖，感觉。

当然还是有进步的这个空间的。

心得感悟

就是这个 B，哎，感觉基本上是想到了，但是没关注到一个关键的这个数据范围限制。

一定要关注数据范围限制。

你看到这个，基本就知道简单的贪心和这个二分答案是解决不了的。

题目 A. 1-1

题目描述
给定一个长度为 $n$ 的 01 字符串 $s$。
在一次操作中，如果存在某个位置 $i$（$2 \le i \le n-1$）满足其左右相邻的字符均为 1（即 $s_{i-1} = s_{i+1} = 1$），则可以随意将 $s_i$ 修改为 0 或 1。
该操作可以执行任意次（包括零次）。你需要求出经过操作后，最终字符串中 1 的数量的最小值和最大值。

输入格式
第一行包含一个整数 $t$（$1 \le t \le 500$），表示测试数据的组数。
每组数据包含两行：
第一行为一个整数 $n$（$3 \le n \le 100$），表示字符串的长度。
第二行为一个长度为 $n$ 的 01 字符串 $s$。

输出格式
对于每组数据，输出两个整数，分别表示最终字符串中包含 1 的数量的最小值和最大值。

样例输入

4
3
111
6
011011
7
1011101
9
100101101

样例输出

2 3
3 5
4 7
5 7

样例解释
在第一组样例中：

• 最小数量为 $2$。操作过程：111 $\rightarrow$ 101。

• 最大数量为 $3$。不进行任何操作即可。

在第二组样例中：

• 最小数量为 $3$。操作过程：011011 $\rightarrow$ 011111 $\rightarrow$ 010111 $\rightarrow$ 010101。

• 最大数量为 $5$。操作过程：011011 $\rightarrow$ 011111。

---

https://codeforces.com/contest/2207/problem/A

就是贪心，不难发现，就是能操作的就操作（变为 1），那么得到就是最多的答案。

接着在能操作的就操作（变为 1），变好的这个串的前提下，然后能操作的就操作（变为 0），得到的就是最少的答案。

想到这样的方法，一个是 leetcode 好像做过类似思想的题目（和父亲讨论过，没做），还有就是我发现这个进行这个 1 操作后，继续进行 0 操作，得到的答案总归不是不优的，至少是比直接进行 0 操作一样，或者更好。

https://codeforces.com/contest/2207/submission/365935923

源代码

/**
 * Problem: A. 1-1
 * Contest: Codeforces Round 1085 (Div. 1 + Div. 2)
 * Judge: Codeforces
 * URL: https://codeforces.com/contest/2207/problem/A
 * Created: 2026-03-08 22:36:37
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT,testcase;

/*
 *
 */

void Solve() {
    ll N;
    cin >> N;
    string s;
    cin>>s;
    s.insert(s.begin(),'#');
    for (int i=2;i<=N-1;++i) {
        // string sub=s.substr(i,3);
        if (s[i-1]=='1' && s[i+1]=='1') {
            s[i]='1';
        }
    }
    ll mx_ans=count(all(s),'1');
    for (int i=2;i<=N-1;++i) {
        if (s[i-1]=='1' && s[i+1]=='1') {
            s[i]='0';
        }
    }
    ll mn_ans=count(all(s),'1');
    cout<<mn_ans<<" "<<mx_ans<<"\n";
    // ll mn_ans=count(all(s),'1');
    // for (int i=1;i<=N-4;++i) {
    //     string sub=s.substr(i,5);
    //     if (sub=="11011" || sub=="10111" || sub=="11101") {
    //         i+=4;
    //         mn_ans--;
    //     }
    // }
    // cout<<mn_ans<<"\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf);   // 无缓冲流，方便我们调试
#endif

    cin >> lT;
    for (testcase=1;testcase<=lT;++testcase)
        Solve();
    return 0;
}

/*
1
7
1011101

AC

*/

题目 C. Where’s My Water?

题目描述
给定一个高度为 $h$、列数为 $n$ 的网格。在第 $i$ 列中，最底部的 $a_i$ 个格子是泥土，其上方的格子全是水。
你可以在任意一个水格子上放置排水口，最多可以放置两个。
每个排水口可以排走所有能够通过仅向下、向左或向右移动（且不穿过任何泥土格子）到达该排水口的水格子。被两个排水口共同覆盖的水格子只会被计算一次。
求在最多放置两个排水口的情况下，能够排走的最大水格子总数。

输入格式
第一行包含一个整数 $t$（$1 \le t \le 10^3$），表示测试数据组数。
每组数据第一行包含两个整数 $n$ 和 $h$（$1 \le n \le 2000$，$1 \le h \le 10^9$），分别表示网格的列数和高度。
第二行包含 $n$ 个整数 $a_i$（$1 \le a_i \le h$），表示第 $i$ 列泥土格子的高度。
保证所有测试数据中 $n$ 的和不超过 $2000$。

输出格式
对于每组数据，输出一个单行整数，表示最多能排走的水格子数量。

样例

Input
6
7 4
1 3 1 2 3 1 1
8 10
7 5 1 3 2 5 6 8
1 1
1
10 20
5 2 1 2 1 3 6 7 1 1
5 1000000000
1 420420420 1 420420420 1
1 1000000000
1

Output
14
43
0
170
3738738738
999999999

样例解释
在第一组样例中，网格列数为 $7$，高度为 $4$。通过在合适的位置放置两个排水口，最多可以排走 $14$ 个水格子。
在第二组样例中，网格列数为 $8$，高度为 $10$。通过合理放置两个排水口，可以排走网格中全部的 $43$ 个水格子。
在第三组样例中，网格大小为 $1 \times 1$，且唯一的格子是泥土，没有水格子，无法放置排水口，因此输出 $0$。

---

https://codeforces.com/contest/2207/problem/C

不难发现，这道题目，应该是直接枚举两个的这个抽水的位置，然后 $O(1)$ 计算其所抽的水。

当然，为了实现这个常数级别的计算，前面需要进行一个 $O(n^2)$ 的预处理。

不难发现，就是抽水棒两边的这个计算（也就是图中绿色部分的计算）是非常容易的。但是中间蓝色问号部分的计算，是这道题目的难点。

如果说随意的，错误的进行计算，那么 9 格子就被漏掉了。

通过模拟，我们发现，如果两点之间是一个这个山，那么应该以山峰为界，互不干扰。

那么山峰是什么东西？就是最大值嘛，这两点之间的最大值的这个坐标就是山峰所在位置。

for (int i=1;i<=N;++i) {
    for (int j=i;j<=N;++j) {
        ll lans=0;
        // 最大值位置
        ll pos=dp[i][j];
        lans=pre_area[i][1]+suf_area[i][pos]+pre_area[j][pos]+suf_area[j][N];
        lans-=M-H[i]+M-H[pos]+M-H[j];
        ans=max(ans,lans);
    }
}

https://codeforces.com/contest/2207/submission/365935937

源代码

/**
 * Problem: C. Where's My Water?
 * Contest: Codeforces Round 1085 (Div. 1 + Div. 2)
 * Judge: Codeforces
 * URL: https://codeforces.com/contest/2207/problem/C
 * Created: 2026-03-08 23:05:02
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll)1e6+10, INF = (1ll<<61)-1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT,testcase;

/*
 *
 */

void Solve() {
    ll N,M;
    cin >> N >> M;
    vector<ll> H(N+2);
    for (int i=1;i<=N;++i) {
        cin>>H[i];
    }
    // vector<pair<ll,ll>> lr(N+2);
    // for (int i=1;i<=N;++i) {
    //     for (int r=i+1;r<=N;++r) {
    //         if (H[r]>=H[i]) {
    //             lr[i].second=i;
    //             break;
    //         }
    //     }
    //     for (int l=i-1;l>=1;--l) {
    //         if (H[l]>=H[i]) {
    //             lr[i].first=i;
    //             break;
    //         }
    //     }
    //     if (lr[i].first==0) {
    //         lr[i].first=i;
    //     }
    //     if (lr[i].second==0) {
    //         lr[i].second=i;
    //     }
    // }
    vector<vector<ll>> suf_area(N+2,vector<ll>(N+2)),pre_area(N+2,vector<ll>(N+2));
    for (int i=1;i<=N;++i) {
        ll mx=H[i];
        ll res=0;
        for (int j=i;j<=N;++j) {
            mx=max(H[j],mx);
            ll add=M-mx;
            res+=add;
            suf_area[i][j]=res;
        }
    }
    for (int i=1;i<=N;++i) {
        ll mx=H[i];
        ll res=0;
        for (int j=i;j>=1;--j) {
            mx=max(H[j],mx);
            ll add=M-mx;
            res+=add;
            pre_area[i][j]=res;
        }
    }
    ll ans=0;
    vector<vector<ll>> dp(N+2,vector<ll>(N+2));
    for (int l=1;l<=N;++l) {
        for (int r=l;r<=N;++r) {
            if (l==r) {
                dp[l][r]=l;
                continue;
            }
            dp[l][r]=dp[l][r-1];
            if (H[r]>H[dp[l][r-1]]) {
                dp[l][r]=r;
            }
        }
    }
    for (int i=1;i<=N;++i) {
        for (int j=i;j<=N;++j) {
            ll lans=0;
            ll pos=dp[i][j];
            lans=pre_area[i][1]+suf_area[i][pos]+pre_area[j][pos]+suf_area[j][N];
            lans-=M-H[i]+M-H[pos]+M-H[j];
            ans=max(ans,lans);
            // if (H[i]>=H[j]) {
            //
            //     ans=max(ans,lans);
            // }else {
            //     lans=pre_area[i][1]+suf_area[i][j-1]+suf_area[j][N]-(M-H[i]);
            //     ans=max(ans,lans);
            // }
        }
    }
    cout<<ans<<"\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf);   // 无缓冲流，方便我们调试
#endif

    cin >> lT;
    for (testcase=1;testcase<=lT;++testcase)
        Solve();
    return 0;
}

/*
1
7 4
1 3 1 2 3 1 1



void Solve() {
    ll N,M;
    cin >> N >> M;
    vector<ll> H(N+2);
    for (int i=1;i<=N;++i) {
        cin>>H[i];
    }
    // vector<pair<ll,ll>> lr(N+2);
    // for (int i=1;i<=N;++i) {
    //     for (int r=i+1;r<=N;++r) {
    //         if (H[r]>=H[i]) {
    //             lr[i].second=i;
    //             break;
    //         }
    //     }
    //     for (int l=i-1;l>=1;--l) {
    //         if (H[l]>=H[i]) {
    //             lr[i].first=i;
    //             break;
    //         }
    //     }
    //     if (lr[i].first==0) {
    //         lr[i].first=i;
    //     }
    //     if (lr[i].second==0) {
    //         lr[i].second=i;
    //     }
    // }
    vector<vector<ll>> suf_area(N+2,vector<ll>(N+2)),pre_area(N+2,vector<ll>(N+2));
    for (int i=1;i<=N;++i) {
        ll mx=H[i];
        ll res=0;
        for (int j=i;j<=N;++j) {
            mx=max(H[j],mx);
            ll add=M-mx;
            res+=add;
            suf_area[i][j]=res;
        }
    }
    for (int i=1;i<=N;++i) {
        ll mx=H[i];
        ll res=0;
        for (int j=i;j>=1;--j) {
            mx=max(H[j],mx);
            ll add=M-mx;
            res+=add;
            pre_area[i][j]=res;
        }
    }
    // vector<ll> pre_sum(N+2);
    // partial_sum(all(H),pre_sum.begin());
    ll ans=0;
    // auto get_area=[&](ll l1,ll r1) {
    //     ll lans=(r1-1>=l1 ? M*(r1-1-l1)-(pre_sum[r1-1]-pre_sum[l1]) : 0);
    //     lans+=suf_area[r1][N];
    //     lans+=pre_area[l1][1];
    //     if (l1==r1) {
    //         lans-=(M-H[l1]);
    //     }
    //     return lans;
    // };
    // auto get_area=[&](ll l1,ll r1) {
    //     ll lans=(r1-1>=l1 ? M*(r1-1-l1)-(pre_sum[r1-1]-pre_sum[l1]) : 0);
    //     lans+=suf_area[r1][N];
    //     lans+=pre_area[l1][1];
    //     if (l1==r1) {
    //         lans-=(M-H[l1]);
    //     }
    //     return lans;
    // };
    for (int i=1;i<=N;++i) {
        for (int j=i+1;j<=N;++j) {

            // auto [l1,r1]=lr[i];
            // auto [l2,r2]=lr[j];
            // if (l1==l2 && r1==r2) {
            //     ll lans=get_area(l1,r1);
            //     ans=max(ans,lans);
            // }else{
            //     ll lans=get_area(l1,r1)+get_area(l2,r2);
            // }

        }
    }
}
*/