题解：P10299 [CCC 2024 S5] Chocolate Bar Partition

dyc2022 · 2025-08-12 09:10:49 · 题解

更好的阅读体验

先将所有格子的权值都减去这些格子的平均数。为了方便，我们先将所有格子的权值乘以 2n 保证平均数是整数。问题转化成，将 2 \times n 的网格划分成尽可能多的连通块，使得每一块的权值和为 0。

我们可以先考虑一个朴素的 dp：设 f_{i, j, k} 表示只考虑前 i 行，上面的格子所在连通块和为 j，下面的格子所在连通块和为 k 的答案。然而状态数是 O(nV^2)，V 为值域，没有什么前途。

然而我们发现很多状态是无用的。具体地，我们只关心一个连通块的最后一个格子在哪里，即要从哪里划分连通块。所以由上面的状态设计，一个有用的状态，一定是上面的格子或下面的格子所在连通块的和为 0，即 jk = 0。更进一步地，由于目前状态下只有一个连通块的权值和不为 0，因此我们甚至不需要记录 j 和 k，而是直接通过上下两行的前缀和得出答案。

我们设 f_{0/1, i} 表示目前考虑前 i 行，上面或下面的格子所在连通块的权值和不为 0。设目前考虑 f_{j, i}，令 k = j \oplus 1，则转移分三种：

将上下的格子都划分到前一列不为 0 的格子所在连通块。则连通块数量不会增加，从 \max(f_{j, i-1}, f_{k, i-1}) 转移。
将第 k 行末尾的若干个格子形成一个和为 0 的连通块，从 f_{k, l} + 1 转移，其中 l 是一个合法转移点满足 \sum\limits_{x=l+1}^{i}a_{k, x} = 0。
将第 k 行末尾的若干个格子和前面不为 0 的格子形成一个和为 0 的连通块，从 f_{k, l} + 1 转移，其中 l 是一个合法转移点满足 \sum\limits_{x=l+1}^{x}a_{k, x} + \sum\limits_{x=1}^{l}a_{k, x} + \sum\limits_{x=1}^{l}a_{j, x} = 0。
该行上下格子所在的格子连通块和都为 0，这种条件需满足 \sum \limits_{x=1}^{i}a_{j, x}+\sum \limits_{x=1}^{i}a_{k, x} = 0，用 \max(f_{j, i}, f_{k, i}) + 1 转移，表示可以新开一个连通块。

第一和第四个转移直接做就好了。第二、三开一个桶存满足条件的最大 f_{k, l}。由于前缀和值域很大，需要离散化。

那么这道题就做完了，复杂度 O(n \log n)。

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
#define N 800006
using namespace std;
inline void chkmax(int &x,int y){x=x<y?y:x;}
int n,bn,sum,b[N],a[2][N],s[2][N],s_[2][N];
int f[2][N],g[4][N];
main()
{
    scanf("%lld",&n);
    for(int i=0;i<2;i++)
        for(int j=1;j<=n;j++)scanf("%lld",&a[i][j]),sum+=a[i][j];
    for(int i=0;i<2;i++)
        for(int j=1;j<=n;j++)a[i][j]=a[i][j]*2*n-sum+a[i][j-1];
    for(int i=0;i<2;i++)
        for(int j=0;j<=n;j++)b[++bn]=a[i][j],b[++bn]=-a[i][j];
    sort(b+1,b+1+bn),bn=unique(b+1,b+1+bn)-b-1;
    for(int i=0;i<2;i++)
        for(int j=0;j<=n;j++)s[i][j]=lower_bound(b+1,b+1+bn,a[i][j])-b;
    for(int i=0;i<2;i++)
        for(int j=0;j<=n;j++)s_[i][j]=lower_bound(b+1,b+1+bn,-a[i][j])-b;
    memset(g,-0x3f,sizeof(g));
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<2;j++)
            chkmax(g[j][s[j][i-1]],f[j^1][i-1]);
        for(int j=0;j<2;j++)
            chkmax(g[j|2][s[j^1][i-1]],f[j][i-1]);
        for(int j=0;j<2;j++)
            chkmax(f[j][i],max(f[0][i-1],f[1][i-1]));
        for(int j=0;j<2;j++)
            chkmax(f[j][i],max(g[j^1][s[j^1][i]],g[(j^1)|2][s_[j^1][i]])+1);
        if(a[0][i]+a[1][i]==0)f[0][i]=f[1][i]=max(f[0][i],f[1][i])+1;
    }
    printf("%lld\n",f[0][n]);
    return 0;
}