专栏文章

题解：P13420 [COCI 2012/2013 #6] SUME

CChenxuhang_play
P13420题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mioqdr32
此快照首次捕获于
2025/12/02 23:26
3 个月前
此快照最后确认于
2025/12/02 23:26
3 个月前
查看原文

前言

记 aa 为输入的矩阵，ai,ja_{i,j} 表示数组中第 ii 行，第 jj 列的值，AA 表示题目中最终需要输出的数，AiA_i 表示这些数中的第 ii 个。
注意：在这篇题解中下标从 00 开始到 n−1n-1。

思路

可以发现在整个数组中有两个行、列可以作为突破口。
它们是第 00 行（即对于所有的 a0,ia_{0,i}，其中 i∈[0,n−1]i\in[0,n-1]）和第 n−1n-1 列（即对于左右的 ai,n−1a_{i,n-1}，其中 i∈[0,n−1]i\in[0,n-1]）。
根据题意，可以得到如下信息（其中 i∈[0,n−1]i\in[0,n-1]）。
a0,i=A0+Aiai,n−1=Ai+An−1a_{0,i}=A_0+A_i\\ a_{i,n-1}=A_i+A_{n-1}
如果我们把 a0,ia_{0,i} 与 ai,n−1a_{i,n-1} 相减就可以得到一个惊人的事实（其中 i∈[0,n−1]i\in[0,n-1]）。
ai,n−1−a0,i=(Ai+An−1)−(A0+Ai)=An−1−A0a_{i,n-1}-a_{0,i}=(A_i+A_{n-1})-(A_0+A_i)=A_{n-1}-A_0
ai,n−1a_{i,n-1} 和 a0,ia_{0,i} 是已知的，由上面的式子能够求出 An−1−A0A_{n-1}-A_0（可以证明，这里无论 ii 取多少，An−1−A0A_{n-1}-A_0 的值总是固定的）。根据题意，a0,n−1=A0+An−1a_{0,n-1}=A_0+A_{n-1}。我们都知道，对于两个实数 x,yx,y 能够知道 x+yx+y 和 x−yx-y，就能分别求出 xx 和 yy，公式是 x=(x+y)+(x−y)2x=\frac{(x+y)+(x-y)}{2}。这里我们求出了 An−1−A0A_{n-1}-A_0 和 A0+An−1A_0+A_{n-1}。所以可以求出 A0A_0。
求出 A0A_0 之后，只需要将所有的 a0,ia_{0,i} 减去 A0A_0 即可求出所有的 Ai+1A_{i+1}（其中 i∈[1,n−1]i\in[1,n-1]）。

代码

代码如下。
CPP
#include<bits/stdc++.h>
using namespace std;
int main()
{
	long long n;
	cin>>n;
	long long a[n][n],a1[n],a2[n];
	if(n==2)
	{
		cout<<"1 1";
		return 0;
	}
	for(long long i=0;i<n;i++)
	{
		for(long long j=0;j<n;j++)
		{
			cin>>a[i][j];
		}
	}
	for(long long i=0;i<n;i++)
	{
		a1[i]=a[0][i];
	}
	a1[0]=(a[0][n-1]-(a[1][n-1]-a[0][1]))/2;
	for(long long i=1;i<n;i++)
	{
		a1[i]=a1[i]-a1[0];
	}
	for(long long i=0;i<n;i++)
	{
		cout<<a1[i]<<" ";
	}
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...