【题解】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$ 和第 $2$ 行的元素都放进同一个块中，有 $f_{i,j}\leftarrow\max(f_{0,j-1},f_{1,j-1})$ 。
只在第 $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$ 。
在第 $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$ 。
特殊情况，当有 $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)

，可以通过此题。

代码

CPP

#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;
}

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

文章操作

题意

解法

实现

代码

相关推荐

评论

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