#C241116A. 棋盘游戏
标签（Label）
- 观察+分析
网址（Website）
题目（Problem）
样例
输入数据 1
2
3
1 1 1
1 1 1
1 1 1
5
8 5 2 8 3
5 6 9 7 3
7 8 9 1 4
8 9 4 5 5
2 8 6 9 3输出数据 1
1
5
题解（Solution）
看到这道题的 $\sum n^2 $ 足足有 $5\times 10^5$ ，就开始想一堆带 $\log$ 的做法 ，总觉得有一些性质，但是又没有提取出来。
我们设 $mid=\frac{n}{2}+1$ 。不考虑复杂度，找一下这个题的规律。
矩阵往往是四个角最特殊。发现每次覆盖至少覆盖 $\frac{1}{4}$ 的范围，我们想要覆盖整个范围，就需要把四个角都给覆盖，发现对于 $(1,1)$ 位置，能覆盖到这个位置的矩阵的中心 $(x,y)$ 一定满足 $x\in[1,mid]\land y\in[1,mid]$ ，其他的角同理。容易发现当 $(1,1)$ 这个位置被覆盖之后，矩阵的 $(x,y)\vert x\in[1,mid]\land y\in[1,mid]$ 的点一定也会被覆盖，对于 $(x,y)\vert x\in[1,mid-1]\land y\in[1,mid-1]$ ，这些点只能覆盖 $(1,1)$ 这个点，对于 $(x,mid)$ 或 $(mid,y)$ ，它们至少可以覆盖两个角，特别的，对于 $(mid,mid)$ ，它可以直接覆盖所有位置。
观察到这些性质之后，我们就是要在四个角里面分别找到最小值来覆盖对应的角，对于在中轴上的点，它可以完成自己能覆盖的两个角的操作，因此就对这对应的两个角取 $\min$ ，最后拼接出来能覆盖四个角的方案，然后与 $(mid,mid)$ 一个点操作的方案取 $\min$ 就好了。
时间复杂度 $O(n^2)$ 。
出题者题解
代码（Code）
#include<bits/stdc++.h>
#include<vector>
#include<queue>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int>
#define int long long
#define x first
#define y second
inline int rd(){
char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}const int inf = 0x3f3f3f3f3f3f3f3f;
const int N = 505;
const int S = 501234;
bool ST;
priority_queue<pair<P,P>> q;
int n,half,ans,a[N][N];
int c[4][4],s[6],md;
void Solve(){
memset(c, 0x3f, sizeof c);
memset(s, 0x3f, sizeof s);
md = ans = inf;
n=rd(),half=n/2+1;
For(i,1,n) For(j,1,n){
int x=rd();
if(i^half && j^half) c[i/half][j/half] = min(c[i/half][j/half], x);else
if(i==half && j^half){
if(j<half) s[1] = min(s[1], x), c[0][0] = min(c[0][0], x), c[1][0] = min(c[1][0], x);
else s[3] = min(s[3], x), c[0][1] = min(c[0][1], x), c[1][1] = min(c[1][1], x);
}else
if(i^half && j==half){
if(i<half) s[4] = min(s[4], x), c[0][0] = min(c[0][0], x), c[0][1] = min(c[0][1], x);
else s[2] = min(s[2], x), c[1][0] = min(c[1][0], x), c[1][1] = min(c[1][1], x);
}else{
assert(i==half && j==half);
md = min(md, x);
}
}
s[1] = min(s[1], c[0][0]+c[1][0]);
s[2] = min(s[2], c[1][0]+c[1][1]);
s[3] = min(s[3], c[0][1]+c[1][1]);
s[4] = min(s[4], c[0][0]+c[0][1]);
ans = min({md, s[1]+s[3], s[2]+s[4]});
printf("%lld\n", ans);
}
bool ED;
signed main(){
cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
freopen("distorted.in","r",stdin);
freopen("distorted.out","w",stdout);
int Tt=rd();double Tim=clock();
while(Tt--) Solve();
return cerr<<"TIME:"<<(clock()-Tim)/CLOCKS_PER_SEC,0;
}
