【题解】P10299 [CCC 2024 S5] Chocolate Bar Partition

· · 题解

题意

给定一个 2\times N 的矩阵 a，将其分成若干联通块，每块的平均数均相等，求最多分成几块。

解法

平均数不方便直接处理，考虑先将其转化。注意到每一块的平均数均等于整个矩阵的平均数，于是可以将每个元素减去整个矩阵的平均数，考虑到精度原因，将其再乘上 2N，此时问题转化为每块的元素和为 0。设 \displaystyle sum_{i,j}=\sum_{k=1}^ja_{i,k}。

考虑用动态规划来解决问题，设 f_{i,j,k,0/1} 为第 i 列，其中第 1 列的块的和为 j，第 2 列为 k，这两列是否在同一块中，转移方程略，但是时间复杂度爆炸。

考虑优化，发现有两个块且两个块的和均不等于 0 的状态是没必要的，因为我们可以等到有一个块和为 0 时再来更新。故设 f_{i,j} 为枚举到第 j 列，此时第 i 行的块和为 0，另一行的块和不确定，最多分成的块数。

考虑转移，进行分类讨论：

  1. 将第 1 和第 2 行的元素都放进同一个块中，有 f_{i,j}\leftarrow\max(f_{0,j-1},f_{1,j-1})。
  2. 只在第 i 行中找到一个和为 0 的块，当块 (k,j] 满足和为 0 时有 sum_{i,j}=sum_{i,k}，由情况 1 的式子可知 f_{i} 单调不降，所以设 pos=\displaystyle\max_{k=0}^{j-1}k[sum_{i,j}=sum_{i,k}]，有 f_{i,j}\leftarrow f_{i,pos}+1。
  3. 在第 i 行（第 j 列及以前）和另一行（第 j 列之前）找一个横跨两行且和为 0 的块，由于选了这个块以后以前的所有元素均已固定，所以假设这个块包含了前面的所有元素，设 k 为满足条件的块在另一行最右侧的位置的左边，则有 sum_{i,j}+sum_{i\oplus1,k}=0，同上知 f_{i\oplus1} 单调不降，所以设 pos=\displaystyle\max_{k=0}^{j-1}k[sum_{i,j}=-sum_{i\oplus1,k}]，有 f_{i,j}\leftarrow f_{i\oplus1,pos}+1。
  4. 特殊情况，当有 sum_{0,j}+sum_{1,j}=0 时，另一行那个不确定和是否为 0 的块的和为 0，此时有 f_{0,j},f_{1,j}\gets\max(f_{0,j},f_{1,j})+1。

最终答案为 \displaystyle\max_{i\in\{0,1\}}\max_{j=1}^Nf_{i,j}。

实现

设 pre1_{j} 为情况 2 中 j 的 pos，设 pre2_{j} 为情况 3 中 j 的 pos，用 unordered_map 维护即可。

时间复杂度 O(N)，可以通过此题。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5;
int a[2][N],sum[2][N],pre1[2][N],pre2[2][N],f[2][N],g[N];
unordered_map<int,int>flg;
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int n,s=0;
    cin>>n;
    for(int i:{0,1})
    for(int j=1;j<=n;j++)
        cin>>a[i][j],s+=a[i][j],a[i][j]*=n<<1;
    for(int i:{0,1})
    for(int j=1;j<=n;j++)
        sum[i][j]=sum[i][j-1]+a[i][j]-s;
    for(int i:{0,1})
    {
        flg[0]=1;
        for(int j=1;j<=n;j++)
        {
            pre1[i][j]=flg[sum[i][j]]-1;
            flg[sum[i][j]]=j+1;
        }
        flg.clear();
    }
    for(int i:{0,1})
    {
        flg[0]=1;
        for(int j=1;j<=n;j++)
        {
            pre2[i][j]=flg[-sum[i][j]]-1;
            flg[sum[i^1][j]]=j+1;
        }
        flg.clear();
    }
    int ans=0;
    for(int j=1;j<=n;j++)
    {
        for(int i:{0,1})
        {
            f[i][j]=max(f[0][j-1],f[1][j-1]);
            if(pre1[i][j]!=-1)f[i][j]=max(f[i][j],f[i][pre1[i][j]]+1);
            if(pre2[i][j]!=-1)f[i][j]=max(f[i][j],f[i^1][pre2[i][j]]+1);
        }
        if(sum[0][j]+sum[1][j]==0)f[0][j]=f[1][j]=max(f[0][j],f[1][j])+1;
        ans=max(f[0][j],f[1][j]);
    }
    cout<<ans;
    return 0;
}