列表

详情


SG2. 矩阵元素相乘

描述

A[n,m]是一个n行m列的矩阵,a[i,j]表示A的第i行j列的元素,定义x[i,j]为A的第i行和第j列除了a[i,j]之外所有元素(共n+m-2个)的乘积,即x[i,j]=a[i,1]*a[i,2]*...*a[i,j-1]*...*a[i,m]*a[1,j]*a[2,j]...*a[i-1,j]*a[i+1,j]...*a[n,j],现输入非负整形的矩阵A[n,m],求MAX(x[i,j]),即所有的x[i,j]中的最大值。

输入描述

第一行两个整数n和m。之后n行输入矩阵,均为非负整数。

输出描述

一行输出答案。

示例1

输入:

3 5
5 1 8 5 2
1 3 10 3 3
7 8 5 5 16

输出:

358400

原站题解

C 解法, 执行用时: 2ms, 内存消耗: 312KB, 提交时间: 2021-09-23

#include <stdio.h>
#include <limits.h>

int main()
{
    int n,m;
    while(scanf("%d %d",&n,&m)!=EOF)
    {
        int arr[n][m];
        int max=INT_MIN;
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
                scanf("%d",&arr[i][j]);
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                int sum=1;
                for(int k=0;k<n;k++)
                    if(k!=i)
                        sum*=arr[k][j];
                for(int k=0;k<m;k++)
                    if(k!=j)
                        sum*=arr[i][k];
                if(sum>max)
                    max=sum;
            }
        }
        printf("%d\n",max);
    }
    return 0;
}

C++ 解法, 执行用时: 2ms, 内存消耗: 376KB, 提交时间: 2020-09-08

#include <iostream>
#include <vector>
using namespace std;

long shuzi(vector< vector<int> > v,int i,int j)
{
    int x,y;
    long sum = 1;
    for(x=0;x<v.size();x++)
    {
        if(x!=i)
        {
           sum *= v[x][j];
        }
    }
    for(y=0;y<v[0].size();y++)
    {
        if(y!=j)
        {
            sum *= v[i][y];
        }
    }
    return sum;
}

int main()
{
    int n,m;
    while(cin>>n>>m)
    {
    vector< vector<int> > v(n);
    int temp;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            cin>>temp;
            v[i].push_back(temp);
        }
    }
    long max = 0;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            if(max < shuzi(v,i,j))
            {
                max = shuzi(v,i,j);
            }
        }
    }
    cout<<max<<endl;
    }
}

C 解法, 执行用时: 2ms, 内存消耗: 376KB, 提交时间: 2020-05-15

#include<stdio.h>
int main(){
    int n,m,i,j,k;
    while(scanf("%d %d",&n,&m)==2){
    long long t,max=0;
    int a[n][m];
    for(i=0;i<n;i++)
        for(j=0;j<m;j++)
            scanf("%d",&a[i][j]);
    for(i=0;i<n;i++){
        for(j=0;j<m;j++){
            t=1;
            for(k=0;k<j;k++)
                t=t*a[i][k];
            for(k=j+1;k<m;k++)
                t=t*a[i][k];
            for(k=0;k<i;k++)
                t=t*a[k][j];
            for(k=i+1;k<n;k++)
                t=t*a[k][j];
            if(t>max)
                max=t;
        }
    }
    printf("%lld\n",max);}
    return 0;
}

C 解法, 执行用时: 2ms, 内存消耗: 376KB, 提交时间: 2018-09-11

#include <stdio.h>
int main() {
    int m,n,i,j,p,q;
    long A[10000][10000];
    long X[10000][10000];
    long max_x,temp1;
    while(scanf("%d %d",&m, &n) != EOF)
    {
        for (i=0;i<m;i++)
        {
            for(j=0;j<n-1;j++)
            {
                scanf("%d ",&A[i][j]);
            }
            scanf("%d\n",&A[i][j]);
        }
        
        max_x=0;
        for(i=0;i<m;i++)
        {
            for(j=0;j<n;j++)
            {
                temp1=1;
                for(p=0;p<j;p++)
                    temp1=temp1*A[i][p];
                for(p=j+1;p<n;p++)
                    temp1=temp1*A[i][p];
                
                for(p=0;p<i;p++)
                    temp1=temp1*A[p][j];
                for(p=i+1;p<m;p++)
                    temp1=temp1*A[p][j];
               // temp1=temp1/A[i][j]/A[i][j];
                X[i][j]=temp1;
                if(X[i][j]>max_x)
                    max_x=X[i][j];
                
                
                
            }
        }
        
        
        
        
        
        printf("%d\n",max_x);
    }
        
    return 0;
}

C++ 解法, 执行用时: 2ms, 内存消耗: 380KB, 提交时间: 2021-05-29

#include <iostream>
#include <vector>

using namespace std;

int main(){
    int n,m;
    while (cin >> n >> m){
        vector<vector<int>> A(n, vector<int>(m, 0));
        vector<int> row(n);
        vector<int> col(m);
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                cin >> A[i][j];
                A[i][j] = A[i][j] == 0 ? -1 : A[i][j];
                row[i] = j==0 ? A[i][j] : row[i] * A[i][j];
                col[j] = i==0 ? A[i][j] : col[j] * A[i][j];
            }
        }
        int res = 0;
        //cout << col[2] << endl;
        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
               res = max(res, row[i] * col[j] / A[i][j] / A[i][j]);
            }
        }
        cout << res << endl;
    }
    return 0;
}

上一题