CF120D 题解
Jerrlee✅
2022-03-06 16:26:15
## 题意
给定一个 $n \times m$ 的长方形矩阵，第 $(i,j)$ 个方格上面有值 $c_{i,j}$。可以横或竖着把矩阵切成三部分，不能切开网格，使切出的三部分每个部分所包含的方格的值的总和分别为 $A$，$B$，$C$。求有多少种切法。
## 思路
首先 $n,m \leq 50$，可以直接暴力枚举每一种切法的值并与 $A$，$B$，$C$ 比较。
计算值嘛，搞个前缀和就行了。要注意的是枚举 $n$ 和 $m$，需要两个前缀和数组。
注意一下每次循环的下标就好了，按照题目要求开 `freopen` 文件输入输出。
细节都讲完了，具体看代码吧。
## 代码
（这份代码是从 @piggy123 巨佬的错误代码改正过来的）
```cpp
#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a[505][505],sml[505],smc[505],smll[505],smcc[505];
int main(){
freopen("input.txt","r",stdin);
freopen("output.txt","w",stdout);
ll n,m;
cin >> n >> m;
for (ll i=1;i<=n;i++){
for (ll j=1;j<=m;j++){
cin >> a[i][j];
smc[i]+=a[i][j];
sml[j]+=a[i][j];
}
}
for (ll i=1;i<=n;i++){
smcc[i]=smcc[i-1]+smc[i];
}
for (ll i=1;i<=m;i++){
smll[i]=smll[i-1]+sml[i];
}
ll x,y,z,ans=0;
cin >> x >> y >> z;
if (n>=3){// 特判建议加上，毕竟 n,m 可以有一个数小于三的
for (ll i=1;i<n;i++){
for (ll j=i+1;j<n;j++){
// 1 to i,i+1 to j, j+1 to n
ll a=smcc[i],b=smcc[j]-smcc[i],c=smcc[n]-smcc[j];
//cout << i << " "<< j << " "<< a << " "<< b << " "<< c << endl;
if(a==x&&b==y&&c==z)ans++;
else if(a==y&&b==x&&c==z)ans++;
else if(a==y&&b==z&&c==x)ans++;
else if(a==z&&b==x&&c==y)ans++;
else if(a==x&&b==z&&c==y)ans++;
else if(a==z&&b==y&&c==x)ans++;
}
}
}
if (m>=3){
for (ll i=1;i<m;i++){
for (ll j=i+1;j<m;j++){
// 1 to i,i+1 to j, j+1 to n
ll a=smll[i],b=smll[j]-smll[i],c=smll[m]-smll[j];
// cout << i << " "<< j << " "<< a << " "<< b << " "<< c << endl;
if(a==x&&b==y&&c==z)ans++;
else if(a==y&&b==x&&c==z)ans++;
else if(a==y&&b==z&&c==x)ans++;
else if(a==z&&b==x&&c==y)ans++;
else if(a==x&&b==z&&c==y)ans++;
else if(a==z&&b==y&&c==x)ans++;
}
}
}
cout << ans;// notice the value of i and j!
}
```
[AC 记录（洛谷）](https://www.luogu.com.cn/record/70747051)
[AC 记录（CF）](http://codeforces.com/contest/120/submission/148532354)