P10299 [CCC 2024 S5] Chocolate Bar Partition 做题记录

题目描述

给定一个 $2\times n$ 的网格图，每个格子都有一个权值，你需要将这些格子划分为尽可能多的连通块，使得每一个连通块的格子权值的平均值均相等。这里的联通指的是四联通。

分析

首先先将所有格子减去平均值，这样转化为将格子划分为尽可能多的连通块，使得每一块所有格子的和为 $0$。

一个直观的想法是在状态中记录上一列两个格子所在连通块的大小进行 DP，但这是不可接受和不必要的。

如果上一列两个格子所在的连通块不同且两个连通块的权值和都不为 $0$ 的状态是毫无必要的，因为我们完全可以等到至少有一个连通块的权值和为 $0$ 的时候再考虑这种转移。

此时保证在已经考虑完的格子中，至多有一个连通块的权值不为 $0$。此时这个连通块的权值也是不必要记录的，因为其它的连通块的和均为 $0$，则已经考虑完的所有格子的和就是这个连通块的权值。

现在我们把状态精简到 $f_{i,0/1}$，表示已经考虑完了前 $i$ 列的格子，第 $0/1$ 行的格子所在的连通块的和不保证为 $0$。不妨记录 $s_{i,0/1}$ 为第 $0/1$ 行前 $i$ 个格子的和。

当前讨论的是 $f_{i,k}$ 的转移，记 $l=1-k$，即另外一行的编号。

• 让一列两个格子全部划入和不一定为 $0$ 的连通块内，用 $\max\{f_{i-1,0},f_{i-1,1}\}$ 来更新。
• 让在另外一行内末尾若干个格子单独成为一个和为 $0$ 的连通块，用 $\displaystyle\max_{j<i,s_{j,l}=s_{i,l}}\{f_{j,k}+1\}$ 来更新。
• 在另外一行内末尾若干个格子和先前和不一定为 $0$ 的连通块拼起来形成一个和为 $0$ 的连通块，此时会在当前这一行产生一个和不一定为 $0$ 的连通块，用 $\displaystyle\max_{j<i,s_{i,l}+s_{j,k}=0}\{f_{j,l}+1\}$ 来更新。

特殊地，如果 $s_{i,0}+s_{i,1}=0$，则说明此时不保证为 $0$ 的连通块的和为 $0$，需要将 $f_{i,0}$ 和 $f_{i,1}$ 均更新为 $\max\{f_{i,0},f_{i,1}\}+1$。

使用哈希表或者 std::map 等维护第二种和第三种转移即可做到 $O(n)$ 或 $O(n\log n)$。

Code

constexpr int N=2e5+5;using ll=unsigned long long;constexpr int inf=1e9;
ll a[N][2],s[N][2];int f[N][2];struct dat{int v;inline dat(){v=-inf;}};
map<ll,dat>mp[4];inline void gmx(dat&x,int y){if(x.v<y) x.v=y;}
inline void work()
{
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    int n;ll sum=0;cin>>n;
    for(int i=0;i<=1;i++) for(int j=1;j<=n;j++) cin>>a[j][i],sum+=a[j][i],a[j][i]*=2*n;
    for(int i=0;i<=1;i++) for(int j=1;j<=n;j++) a[j][i]-=sum;
    for(int i=0;i<=1;i++) for(int j=1;j<=n;j++) s[j][i]=s[j-1][i]+a[j][i];
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=1;j++) gmx(mp[j][s[i-1][j]],f[i-1][j^1]),gmx(mp[j|2][s[i-1][j^1]],f[i-1][j]);
        for(int j=0;j<=1;j++) f[i][j]=max({f[i-1][0],f[i-1][1],mp[j^1][s[i][j^1]].v+1,mp[(j^1)|2][-s[i][j^1]].v+1});
        if(s[i][0]+s[i][1]==0) f[i][0]=f[i][1]=max(f[i][0],f[i][1])+1;
    }
    cout<<f[n][0]<<"\n";
}