洛谷 CF508A Pasha and Pixels 题解

题目传送门 CF传送门

话说这道题咋这么多坑！

具体思路

把全部位置第一次染成黑色的轮次是第几轮，时间复杂度为 /(/varTheta(k)/) ，接着从点 /(1,1/) 一直到点 /(n-1,m-1/) 全部都判断一遍 ，时间复杂度为 /(/varTheta(nm)/) ，总时间复杂度为 /(/varTheta(nm+k)/) 又因为 /(n,m/le 10^3/) 且 /(k/le 10^5/) ，所以并不会超时。

做法讲解

1 存法

我用了一个 /(a_{i,j}/) 表示在位置 /(i,j/) 第一次被染色的时候是第几次。

但是由于题目要求取的是最小值，因此需要用一个 min 函数来辅助我们更新数值。

/(ans/) 表示答案，及最小的次数，使得出现 /(2/times 2/) 的黑色格子时，至少需要经过多少次。

2 判断与求解

接下来是判断部分，我们首先需要将每个地方都判断过一次，如果这个数与其右边，下边，右下边均不为初始化的值，那么我们可以对 /(ans/) 进行更新，代码如下：

			if(a[i][j]<114514&&a[i][j+1]<114514&&a[i+1][j]<114514&&a[i+1][j+1]<114514){
				ans=min(ans,max(a[i][j],max(a[i+1][j],max(a[i][j+1],a[i+1][j+1]))));
				//答案要取最小值（题目要求）
			}

由此，我们可以得出代码。

奉上代码

#include<bits/stdc++.h>
namespace my_std{
	using namespace std;
	#define ll long long
	#define ref(i,x,y) for(register int i=(x);i<=(y);i++)
	#define fer(i,x,y) for(register int i=(x);i>=(y);i--)
	#define il inline
	#define mpii map<int,int>
	#define mpib map<int,bool>
	#define mpplll map<pll,ll>
	#define mppccl map<pcc,ll>
	#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
	char buf[1<<21],*p1=buf,*p2=buf;
	inline ll read(){
	    char c=getchar();
	    ll x=0;
	    for(;!isdigit(c);c=getchar());
	    for(;isdigit(c);c=getchar()) x=(x<<1)+(x<<3)+(c^48);
	    return x;
	}
}
using namespace my_std;
int n,m,k,ans=114514;
int a[1010][1010];
int main(){
	cin.tie(0),cout.tie(0);
	ios::sync_with_stdio(false);
	//输入输出优化，正常来讲可以不写
	cin>>n>>m>>k;
	memset(a,114514,sizeof(a));
	/*
	初始化a[i][j]要为一个很大的数
	因为后面需要取较小的值
	*/
//	ref(i,1,n){
//		ref(j,1,m){
//			cin>>a[i][j];
//		}
//	}
	ref(i,1,k){
		int x,y;
		cin>>x>>y;
		a[x][y]=min(a[x][y],i);
		//a[i][j]尽量的小，因此需要用min函数
	}
	ref(i,1,n){
		ref(j,1,m){
			if(a[i][j]<114514&&a[i][j+1]<114514&&a[i+1][j]<114514&&a[i+1][j+1]<114514){
				ans=min(ans,max(a[i][j],max(a[i+1][j],max(a[i][j+1],a[i+1][j+1]))));
				//答案要取最小值（题目要求）
			}
		}
	}
	cout<<((ans==114514)?0:ans)<<endl;
}