题面

原题

题目描述

众所周知，灭霸希望借助宇宙魔方的力量完成他不可告人的计划。

为了能够释放出宇宙魔方的力量，灭霸制造了一个魔方模型进行练习。

魔方模型是一个 N 层，每层 N 行 N 列的立方体。魔方的每一格会储存一定的能量，一开始每格的能量都是0。

灭霸每次可以给魔方的任意一层的 N*N 个格子同时加上 X 点能量（ X 为任意整数），或者整体转动魔方（仅仅是把魔方的底面换成另一面）。若干次操作之后，魔方的一个格子意外损坏了。灭霸希望你计算出损坏的格子原本储存了多少能量。

输入格式

第一行输入一个整数 N 代表魔方的边长。

接下来有 N 块数据，第 i 块代表魔方的第 i 层。

每一块数据有 N 行，每行 N 个整数，第 x 行第 y 个整数代表这一层的第 x 行第 y 列的格子中储存了多少能量。如果某一个数是-1，代表这一格魔方损坏了。数据保证 N^3 个数中有且仅有一个 -1。

输出格式

输出一个整数代表损坏的魔方原本储存了多少能量。

样例数据

见 xoj 。

数据范围

20% 的数据1 ≤ N ≤ 5；

另外有20% 的数据，魔方的底面一直没有换过；

另外有20% 的数据，魔方的底面可能换过，但灭霸只给魔方增加过一次能量；

100% 的数据1 ≤ N ≤ 100，每格的能量数 ≤ 1000。

题意概括

一个边长为 $N$ 的立方体，分成 $N^3$ 个小立方体，每个立方体都对应一个初始为 $0$ 的权值。现可以进行 $2$ 种操作：

$1.$ 将任意一层的小方块的权值加上 $X$ $(X\in Z)$

$2.$ 整体转动这个立方体

先给出进行若干步操作后小立方体的权值，但缺失了一个（标记为 $-1$ ）。请根据其他已知的权值推出这个未知的权值。

题解

Part1：乱搞做法（有漏洞，但是能AC）

思路

很显然，无论怎么操作，最后的权值之和必须是 $N^2$ 的倍数。 而我们只缺了一个权值，设它为 $x$。设其他权值累加和为 $ans$，那么显然有：

$n^2\mid ans+x$ ，其中的竖线为整除符号。

那么有：$x=k{n}^2-ans,k\in N^{\ast }$

显然，上式中能让 $x$ 取到最小正值的 $k=\lfloor ans/n^2\rfloor +1$

那么有：

$x=(\lfloor ans/n^2\rfloor +1)n^2-ans$

若 $x=0$，那么输出 $n^2$。

代码

乱搞代码如下，非常短：

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int ans=1,n,f;//因为会加到一个-1，所以累加从1开始
	scanf("%d",&n);
	for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) for(int k=1;k<=n;k++) scanf("%d",&f),ans+=f;
	printf("%d",(ans/(n*n)+1)*(n*n)-ans+((ans/(n*n)+1)*(n*n)-ans==0)*(n*n));
}

漏洞

虽然代码简短，思路简洁，写出来的难度很低，并且可以拿到满分，但是它的漏洞也是很明显的。

为什么 $k$ 一定要让 $x$ 取到最小正值？谁规定的？显然没有任何规定。

事实上，根据上面思路，我们根本得不出 $k$ 的值，只能知道 $k_{min}=\lfloor ans/n^2\rfloor +1$

但为什么，这个错误的思路，打出来的错误的代码，可以得到 $100pts$ ?

其实可以证明，在本题数据中，对于任何 $n>31$，上述表达式是恒正确的。

部分正确性证明

由上面的推导，得：

$x\le (\lfloor ans/n^2\rfloor +1)n^2-ans$，则$x\le \lfloor ans/n^2\rfloor n^2+n^2-ans$，

则$x=(\lfloor ans/n^2\rfloor n^2+n^2-ans)+c{n}^2,c\in N$，

而显然，$\lfloor ans/n^2\rfloor n^2+n^2-ans>=0$，结合题目中所说的数据范围，$x\le 1000$，

得 $c{n}^2\le 1000,c\in N$。

若 $n>31$，则 $n^2>1000$，为使 $c{n}^2\le 1000,c\in N$ ，那么 $c$ 只能取 $0$。

此时 $x=(\lfloor ans/n^2\rfloor +1)n^2-ans$ 就是正确的了。

hack数据

虽然对于任何 $n>31$，上述表达式是恒正确的，但是对于 $n\le 31$，表达式就不一定对了。（真是废话）

在此情况下，只要 $x>n^2$ 就会出错。非常简单的一组 $hack$ 数据为：

输入
2
0 0
0 0
9 9
9 -1
正确输出     程序输出
9           1

但显然，出题者没有考虑到，会有一个代码在 $n$ 大时恒正确，但在 $n$ 小时出现错误。

补救

很简单，如果担心会被卡掉，只需要把 $n\le 31$ 的数据判掉就行了。而 $n\le 31$ 时完全可以暴力，两相结合，一个对于任何 $n$ 都正确的代码就完成了。

Part2：正解

我们假设第 $x$ 层，$y$ 行 $z$ 列的格子坐标为 $(x,y,z)$，那么我们将这个格子染成颜色 $(x+y+z)mod(n)$，考虑记录每种颜色的格子的总能量。可以发现每一次充能操作中每种颜色的格子增加的能量数都是一样的，因此最后每种颜色的格子的总能量也是一样的。

因此只需要计算出缺失格子的颜色，然后这种颜色的总能量和其余颜色的总能量的差就是答案。

正解代码：

#include<bits/stdc++.h>
using namespace std;
const int N=105;
int a[N][N][N],n,yu,ans1,ans2;
int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			for(int k=1;k<=n;k++)
			{
				scanf("%d",&a[i][j][k]);
				if(a[i][j][k]==-1) yu=(i+j+k)%n,a[i][j][k]=0;
			}
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			for(int k=1;k<=n;k++)
			{
				if((i+j+k)%n==(yu==1?0:0)) ans1+=a[i][j][k];
				if((i+j+k)%n==yu) ans2+=a[i][j][k];
			}
		}
	}
	printf("%d",ans1-ans2);
}

正解空间复杂度和代码长度都没有乱搞做法优呀，那谁用正解