题目传送门
DP、状态设计优化。
题意
将一个 \(2 \times N(N \le 2\times 10^5)\) 的矩阵分为尽可能多的联通块，使得每个联通块中的数的平均值都相等，求最多可以将矩阵分为多少个联通块。
题解
显然是 DP，并且复杂度要在 \(O(N \log N)\) 或者 \(O(N)\)。
平均值相等很难维护，看看有什么性质，可以转化一下。
首先我们有加权平均数公式：$$\bar x=\sum_{i=1}^{m} \frac{y_i}{y}\times \bar{x_i}$$
其中，\(y=\sum_{i=1}^{m} y_i,\bar{x_i}=\frac{1}{y_i}\sum a_j\)，表示用每组的平均数，可以求出整体的平均数。
题目中，我们将每个联通块视为一组，由于每组之间的平均值相同，所以有
所以每组的平均数和整个矩阵的平均数是相同的，于是我们可以将矩阵中每个数减去整个矩阵的平均数，为了不产生小数，我们先将矩阵中每个数乘上 \(2*N\)。
到此我们完成了第一步转化：将矩阵分为若干个联通块，要求联通块中所有数之和为 \(0\)。
接下来设计 dp 状态，设 \(f_{i,j,k}\) 表示转移到第 \(i\) 列，当前第 \(0\) 行正在处理的联通块的权值和为 \(j\)，当前第 \(1\) 行正在处理的联通块的权值和为 \(k\)，并且保证前面的联通块全部已经处理好了，即权值和为 \(0\)。
这样定义有什么好处呢？我们每次只要考虑多引入的一列中的两个数如何拼接到前面的块上去就好了。
然而。。。好像想不出转移式，而且三维的 dp 状态根本就做不到 \(O(N\log N)\)，怎么办？也许我们可以再优化一下我们的 dp 状态？
我们发现同时处理两个权值和不为 \(0\) 的联通块还是太难了，而且我们在上面的定义中其实根本不知道这两个联通块到底是不是一个，有没有拼在一起。所以我们看看能不能只处理一个权值和不为 \(0\) 的联通块。
仔细一想，发现上下两个联通块都不为 \(0\) 的状态是没有必要的，我们每次转移肯定都是用当前拼出一个权值和 为 \(0\) 的联通块去接上之前的 \(f\) 的某个状态，那么每次转移后肯定有一行的联通块权值为 \(0\) 了，而且转移时也用不到上下都不为 \(0\) 的状态。
所以我们重新定义 \(f_{i,j=0/1}\) 表示当前转移到第 \(i\) 行，不保证第 \(j\) 行的联通块的权值和为 \(0\)。
此时对于一个 \(f\) 状态，至多只有一个联通块的权值和不为 \(0\)，所以我们可以很方便的求出这个值。
具体的，记录 \(s_{i,j}=\sum_{k=1}^{i} a_{k,j}\)，对于 \(f_{i,j}\)，这个不为 \(0\) 的联通块的权值和为 \(s_{i,0}+s_{i,1}\)。
根据这个性质，我们进行 dp 转移，记 \(k=j\oplus 1\) 即另一行，那么对于 \(f_{i,j}\)：
首先我们要保证第 \(k\) 行即 \(a_{i,k}\) 所在的联通块的权值和为 \(0\)。
- 让 \(a_{i,j}\) 和 \(a_{i,k}\) 一起接上前面一个不为 \(0\) 的联通块，有 \(f_{i,j}\leftarrow \max(f_{i-1,0},f_{i-1,1})\)；
- 让另一行 \(k\) 连续一段数字 \((t,i]\) 单独成为一个联通块，有 \(f_{i,j}\leftarrow f_{t,j}+1\)，其中\(t\) 满足 \(s_{i,k}-s_{t,k}=0\)；
- 让另一行 \(k\) 连续一段数字 \((t,i]\) 和前面不为 \(0\) 的联通块拼在一起成为一个和为 \(0\) 的联通块，有 \(f_{i,j}\leftarrow f_{t,k}+1\)，其中 \(t\) 满足 \(s_{i,k}+s_{t,j}=0\)；
- 如果当前 \(s_{i,0}+s_{i,1}=0\) 说明当前不保证为 \(0\) 的联通块会等于 \(0\)，因此可以将其算上，有 \(f_{i,j}\leftarrow \max(f_{i,0},f_{i,1})+1\)。
中间两个转移可以用 std::map 维护，时间复杂度为 \(O(N \log N)\)，当然用哈希也是可以的，时间复杂度 \(O(N)\)，由于好写所以使用了前者。（用 map<key,val> mp[0/1] 表示当前行相同或相反的，值都为 key 的转移。）
代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5;
int n;
int a[N][2],s[N][2],avg,f[N][2];
struct val{int v; val(){v=-1e18;}};
map<int,val> g[4];
inline void gmx(val& a,int b){a.v=(a.v>b?a.v:b);}
signed main(){cin.tie(nullptr)->sync_with_stdio(false);cin>>n;for(int i=1;i<=n;i++) cin>>a[i][0],avg+=a[i][0],a[i][0]*=2*n;for(int i=1;i<=n;i++) cin>>a[i][1],avg+=a[i][1],a[i][1]*=2*n;for(int i=1;i<=n;i++) a[i][0]-=avg,s[i][0]=s[i-1][0]+a[i][0];for(int i=1;i<=n;i++) a[i][1]-=avg,s[i][1]=s[i-1][1]+a[i][1];for(int i=1;i<=n;i++){for(int j=0;j<=1;j++) gmx(g[j^1][s[i-1][j^1]],f[i-1][j]+1),gmx(g[j|2][s[i-1][j]],f[i-1][j^1]+1);for(int j=0;j<=1;j++) f[i][j]=max({f[i-1][0],f[i-1][1],g[j^1][s[i][j^1]].v,g[j|2][-s[i][j^1]].v});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];return 0;
}