MX-S4-T2 youyou 不喜欢夏天 题解
刘梓轩2010
·
·
题解
MX-S4-T2 youyou 不喜欢夏天 题解
题意
给你一个 2 \times n 的网格，每个格子是黑色的或是白色的，先手选出一个四联通的连通块，后手可以将 m 个列上下调换，先手要使得黑色块的数量减去白色块的数量尽量大，后手要使它尽量小，问你最终在选出的连通块里黑色块的数量减白色块的数量最大是多少。
$m \le n$，$\sum n \le 2\times 10^6$，$1 \le T \le 5$。
## 思路
首先，对于上下是全黑，一黑一白，全白，有不同的策略。
- 对于全黑，肯定是都选更优，这样无论怎么换，都不会减少贡献。
- 对于全白，我们肯定最多选一个，因为选两个一定不优，选一个就能维护连通性，或者直接不选。
- 对于一黑一白，我们又有两种选法。我们可以都选上，这样的贡献是 $0$，无论他怎么换都不会影响贡献；我们也可以只选那一个黑的，但是可能被调换，造成 $-2$ 的贡献，由于他最多换 $m$ 个，所以要减去 $2 \times m$ 的贡献。
需要注意的是，对于一黑一白只选一个黑的的位置的情况，如果选的不足 $2 \times m$ 个，设选了 $k$ 个，那么在造成 $-2 \times k$ 的贡献后，一定不如把这些位置的黑白块都选上更优，所以即使算出来的贡献不是这种选法真正的贡献，但是不会影响答案。
对于每种情况，我们可以通过 dp 解决。
设 $f_{i,j},j \in \{0,1,2,3\}$ 表示到了第 $i$ 个位置，最后一个不选/选了上面那个/选了下面那个/都选了的最大贡献（其实就是状压）。那么转移的时候，一个状态能转移到另一个状态，当且仅当两个状态选的列有交集，或者直接只选这一列。
设 $add_{i,j}$ 表示第 $i$ 列不选/选了上面那个/选了下面那个/都选了的贡献。
$f_{i,j}$ 的初值即为 $add_{i,j}$。
令 $\operatorname{and}$ 表示按位与。
转移方程即为：
$$f_{i,j}=\max_{k \in \{0,1,2,3\},j \operatorname{and} k \neq 0} f_{i-1,k}+add_k,f_{i,j}$$
复杂度 $O(n)$。
不理解结合代码。
## Code
```cpp
#include <bits/stdc++.h>
#define endl '\n'
#define int long long
#define fi first
#define se second
using namespace std;
const int N=2e6+10;
const int inf=0x3f3f3f3f3f3f3f3f;
int n,m;
string s[2];
int f[N][4];
int c;
int t;
int ans=-inf;
/*
对于上下全黑,肯定都选
对于全白,肯定最多选一个
对于一黑一白,有两种情况
1.一部分只选黑的,但有可能被调换
2.都选成上下都选,贡献为0
对于连通性,可以用状压维护
*/
signed main()
{
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(false);
cin>>c>>t;
while(t--)
{
ans=-inf;
cin>>n>>m;
cin>>s[0]>>s[1];
for(int i=0;i<=3;i++) f[0][i]=-inf;
for(int i=1;i<=n;i++) //第一种选法,所有的黑白都选,有0的贡献
{
int add[4]; //分别4种选法的贡献
add[0]=0;
if(s[0][i-1]=='1') add[1]=1;
else add[1]=-1;
if(s[1][i-1]=='1') add[2]=1;
else add[2]=-1;
add[3]=add[1]+add[2];
if(add[1]!=add[2]||(add[1]==add[2]&&add[1]==1)) add[1]=add[2]=-inf;
for(int j=0;j<4;j++) f[i][j]=add[j];
for(int j=0;j<4;j++)
{
for(int k=0;k<4;k++)
{
if(j&k) f[i][k]=max(f[i][k],f[i-1][j]+add[k]);
}
}
for(int j=0;j<4;j++) ans=max(f[i][j],ans);
}
for(int i=1;i<=n;i++) //第二种,有部分的黑白选的是黑的,对于这种选法,最多减去2*m的贡献
//需要注意的是,如果选的不足m个,那么一定没有上面的选法优,所以虽然说选出的答案不是正确的贡献,但一定不如上面的优
{
int add[4]; //分别4种选法的贡献
add[0]=0;
if(s[0][i-1]=='1') add[1]=1;
else add[1]=-1;
if(s[1][i-1]=='1') add[2]=1;
else add[2]=-1;
add[3]=add[1]+add[2];
for(int j=0;j<4;j++) f[i][j]=add[j];
if(add[1]==add[2]&&add[1]==1) add[1]=add[2]=-inf;
for(int j=0;j<4;j++)
{
for(int k=0;k<4;k++)
{
if(j&k) f[i][k]=max(f[i][k],f[i-1][j]+add[k]);
}
}
for(int j=0;j<4;j++) ans=max(f[i][j]-2*m,ans);
}
cout<<ans<<endl;
}
return 0;
}
```