CF120D 题解

题意

给定一个 n \times m 的长方形矩阵，第 (i,j) 个方格上面有值 c_{i,j}。可以横或竖着把矩阵切成三部分，不能切开网格，使切出的三部分每个部分所包含的方格的值的总和分别为 A，B，C。求有多少种切法。

思路

首先 n,m \leq 50，可以直接暴力枚举每一种切法的值并与 A，B，C 比较。

计算值嘛，搞个前缀和就行了。要注意的是枚举 n 和 m，需要两个前缀和数组。

注意一下每次循环的下标就好了，按照题目要求开 freopen 文件输入输出。

细节都讲完了，具体看代码吧。

代码

（这份代码是从 @piggy123 巨佬的错误代码改正过来的）

#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 记录（洛谷）

AC 记录（CF）