[数学][思维] 2018camp day1 Board

http://newoj.acmclub.cn/problems/2054

题目给了一个方块板子,每次要么给同一列所有数字加上同一个数,要么给同一行加上全一个数,然后现在给出经过若干次这种操作之后的一个局面但是把其中一个点换成了-1,要求出来这个点的值应该是多少。

一开始没什么思路,后来写了写表达式似乎发现了可以直接解出来。设ri是第i行加的总数字,ci是第i列加的总数字,row是现在的-1所在的一行的和,col是-1所在的一列的和,若-1坐标为x,y,则可以设要求的数字为t=rx+cy,这时候可以列出来两个方程:

① row+col+2t+21==nt+Σri+Σci

② n*(Σri+Σci)==t+1+Σboard[i][j]

其中第一个方程是要求的那一点的行和列的和的两种表达式,第二个方程式整个board上的所有的点的和的两种表达形式。如果把(Σri+Σci)看作一个整体消掉,可以直接求出来t的表达式t=(n*(row+col)+2*n-Σboard[i][j]-1)/(n-1)^2

#include

using namespace std;

typedef long long LL;
const int maxn=1e3+5;
const int mod=1e9+7;

LL col[maxn],row[maxn],board[maxn][maxn],all;

int main()
{
    int n,x,y;
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            scanf("%lld",&board[i][j]);
            if(board[i][j]==-1)
                x=i,y=j;
        }
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
            row[i]+=board[i][j],col[i]+=board[j][i],all+=board[i][j];
    cout<<(n*(row[x]+col[y])+2*n-all-1)/(n-1)/(n-1)<
	

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据