题解：P11218 【MX-S4-T2】「yyOI R2」youyou 不喜欢夏天

· · 题解

CSP 赛前写题解加 rp（

赛时用了半小时左右想出来了，但是去打 CF 了，没调完。

下文中的 \{co_a,co_b\} 表示上面一个格子的颜色为 co_a，下面一个格子的颜色为 co_b 的一列。

对于这类博弈题，我们可以考虑，如果先手已经做出了决策，后手的决策时什么？对于这道题，即 如果 youyou 已经选好了一个连通块，yy 会怎么操作？分开考虑每一个格子对，对于所有的 \{1,1\} 和 \{0,0\} 对，没有任何操作的必要性，因为操作与否并不会真正改变整个网格。如果一个 \{0,1\} 或一个 \{1,0\} 对被连通块完全覆盖，则这一列也没有必要操作，因为操作不会影响黑格子的总数和白格子的总数。那么，对于一个格子对，只有它是一个 \{0,1\} 对或 \{1,0\} 对，且这个格子对中有且仅有一个被选择了，这个格子对才可能产生有效的交换操作。

既然 yy 希望最小化黑色格子减白色格子的数量，即最小化黑色格子的数量或最大化白色格子的数量，那么容易发现 yy 一定会把这 m 次操作用在 使一个选择的黑色格子变白 上。即对于所有的 \{0,1\} 或 \{1,0\} 对，如果 youyou 选择且仅选择了黑色格子，那么在次数够用的情况下这一对格子会被交换。

知道了 youyou 的策略，接下来我们可以开始考虑 yy 的策略了。

首先有一个很显然的结论，因为选择的是一个连通块，设连通块中最靠左的格子的横坐标为 l，最靠右的格子的横坐标为 r，那么 [l,r] 中的每一对格子都会有至少一个被选，否则与这个点集是连通块相矛盾。

于是我们可以考虑确定了选点的区间 [l,r] 后 youyou 的决策。这时，问题被转换为了对于每一列选 [1,2] 个格子。明显地，由于 youyou 希望最大化黑色格子减白色格子的数量，即使最终的黑色格子尽量多且白色格子尽量少，对于 \{1,1\} 和 \{0,0\} 的决策可以确定。即对于 \{1,1\} 两个格子全选；对于 \{0,0\} 选与上一列选的点格子的纵坐标相同的格子，如果上一列选了两个格子则任选一个。

如何处理 \{0,1\} 和 \{1,0\} 对呢？笔者认为这是整道题目中最难的部分。直接贪心，不论是什么策略，都显然是错误的。这时我们需要一个新思想：分类讨论。我们只需使劲地拍脑袋，就会发现策略只有两种，一种是在可能的情况下全部都选黑格子，第二种是全部都选上（这些对内，黑色格子数等于白色格子数，贡献为 0）。除了这两种策略之外的任何策略都是不优的，简证如下：

很明显任何对内只选白色格子是劣的。于是我们要么选黑色格子，要么黑白全选。

设尽可能选黑格子，可以选出 s 个黑格子，我们要证明不优的策略选了 x 个黑格子，满足 0<x<s。

证毕。

于是，我们只要算出两种情况的答案并取最大值即可。

现在，我们的问题已经变得很简单了，只需要选出一个区间使得按照上面的方式计算，两种策略的最大值尽量大。

不如把这个问题稍微改变一下，变为找到全选情况下的最大值和尽量选黑色格子情况下的最大值并取 \max。容易证明这两个问题等价。

对于全选情况下的最大值，只需将 \{0,0\} 赋权 -1，\{1,1\} 赋权 2，\{0,1\} 和 \{1,0\} 赋权 0 并跑一下最大子段和即可。

对于尽量选黑格子的情况，也可以用类似的方法赋权跑最大子段和，但是无后效性的证明比较麻烦，这里就不提了。具体的实现是维护一个 lst 表示上次选的黑点的纵坐标，如果当前的黑白点对中黑点的纵坐标与上次选的黑点的纵坐标不同，就得选上当前列中的两个格子，原因显然。每到一个两个元素都被选上了的点就清空标记。记得最后的答案要减去 2m。

但是笔者比较蠢，赛时没把无后效性证出来，用了另一种写法：枚举上面提到的区间的右端点并用一个区间加单点修改求 \max\{\sum_{j=i}^r a_j\}（r 为当前枚举的右端点）的线段树（如果你不会这个技巧你可以做一做 P10381）。但是实质其实是一样的。这大概是没调出来的原因吧（

upd on 10.23 关于最大子段和做法的正确性。

首先 \{0,0\} 和 \{1,1\} 的正确性显然，然后将 \{1,0\} 和 \{0,1\} 转换时的负贡献向前挪动到上一个 1 位置不同的 \{1,0\} 或 \{0,1\} 格子，可以发现这是等价的。挪动负贡献后，无后效性就显然了。

最大子段和写法：

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define pb push_back
#define fst first
#define scd second
#define rep(i,s,e) for(int i=s;i<=e;++i)
#define dep(i,s,e) for(int i=s;i>=e;--i)

using ll=long long;
using pii=pair<int,int>;
using pll=pair<ll,ll>;

const int N=2e6+10;

int num(pii a){
    if(a.fst==a.scd) return a.fst;
    return a.fst+2;
}
/*
0: 0 0
1: 1 1
2: 0 1
3: 1 0
*/
void solve(){
    int n,m;
    cin>>n>>m;
    string a1,b1;
    cin>>a1>>b1;
    vector<int> ve;
    rep(i,0,n-1)
        ve.pb(num({a1[i]-'0',b1[i]-'0'}));
    int cnt=0,ans1=0;
    for(int typ:ve){
        if(typ==0) --cnt;
        else if(typ==1) cnt+=2;
        ans1=max(ans1,cnt);
        cnt=max(cnt,0);
    }
    int ans2=0,lst=0;
    cnt=0;
    for(int typ:ve){
        if(typ==0) --cnt;
        else if(typ==1){
            cnt+=2;
            lst=0;
        }
        else{
            if(!lst||lst==typ) ++cnt,lst=typ;
            else lst=0;
        }
        ans2=max(ans2,cnt);
        if(cnt<=0) cnt=lst=0;
    }
    ans2-=m*2;
    cout<<max(ans2,ans1)<<endl;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int c,t=1;
    cin>>c>>t;
    while(t--) solve();
    return 0;
}

线段树写法：

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define pb push_back
#define fst first
#define scd second
#define rep(i,s,e) for(int i=s;i<=e;++i)
#define dep(i,s,e) for(int i=s;i>=e;--i)

using ll=long long;
using pii=pair<int,int>;
using pll=pair<ll,ll>;

const int N=2e6+10;

int num(pii a){
    if(a.fst==a.scd) return a.fst;
    return a.fst+2;
}
/*
0: 0 0
1: 1 1
2: 0 1
3: 1 0
*/
#define ls ((u)<<1)
#define rs ((u)<<1|1)
int mx[N<<2],tag[N<<2],n,m;
void upd(int p,int v,int l=1,int r=n,int u=1){
    if(l==r){
        mx[u]=v;
        return;
    }
    int mid=(l+r)>>1;
    if(p<=mid) upd(p,v,l,mid,ls);
    else upd(p,v,mid+1,r,rs);
    mx[u]=max(mx[ls],mx[rs]);
}
void pd(int u){
    mx[ls]+=tag[u];
    mx[rs]+=tag[u];
    tag[ls]+=tag[u];
    tag[rs]+=tag[u];
    tag[u]=0;
}
void add2(int s,int t,int v,int l=1,int r=n,int u=1){
    if(t<l||r<s) return;
    if(s<=l&&r<=t){
        mx[u]+=v;
        tag[u]+=v;
        return;
    }
    int mid=(l+r)>>1;
    pd(u);
    if(s<=mid) add2(s,t,v,l,mid,ls);
    if(t>mid) add2(s,t,v,mid+1,r,rs);
    mx[u]=max(mx[ls],mx[rs]);
}
int get(int s,int t,int l=1,int r=n,int u=1){
    if(t<l||r<s) return INT_MIN;
    if(s<=l&&r<=t) return mx[u];
    int mid=(l+r)>>1;
    pd(u);
    return max(get(s,t,l,mid,ls),get(s,t,mid+1,r,rs));
}
void solve(){
    cin>>n>>m;
    rep(i,1,n<<2) mx[i]=tag[i]=0;
    string a1,b1;
    cin>>a1>>b1;
    vector<int> ve;
    rep(i,0,n-1)
        ve.pb(num({a1[i]-'0',b1[i]-'0'}));
    int cnt=0,ans1=0;
    for(int typ:ve){
        if(typ==0) --cnt;
        else if(typ==1) cnt+=2;
        ans1=max(ans1,cnt);
        cnt=max(cnt,0);
    }
    int ans2=0,stp=0,lst=0;
    for(int typ:ve){
        ++stp;
        if(typ==0) add2(1,stp,-1);
        else if(typ==1){
            add2(1,stp,2);
            lst=0;
        }
        else{
            if(lst==0||lst==typ) add2(1,stp-1,1),lst=typ;
            else lst=0;
            upd(stp,1);
        }
        ans2=max(ans2,get(1,stp));
    }
    ans2-=m*2;
    cout<<max(ans2,ans1)<<endl;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int c,t=1;
    cin>>c>>t;
    while(t--) solve();
    return 0;
}