Jerrlee's blog

Jerrlee's blog

(2Y /-\|< |0|!

CF120D 题解

posted on 2022-03-06 16:26:15 | under 题解 |

题意

给定一个 $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)