做网站交互demo工具/品牌整合推广

题意：给你一个初始全为0的n*m矩阵，给你q次操作，每次操作在第ti秒将第(xi,yi)位置上的0变成1，问你最早什么时候回出现一个全为1的k*k的矩阵。

题解：我们可以二分时间，然后利用类似滑动窗口来找是否满足题意即可。

#include<stdio.h>
#include<algorithm>
using namespace std;
#define ll long long
int n,m,k,q,a[505][505],ans=-1;
int x[505*505],y[505*505],t[505*505];
int main(void)
{scanf("%d%d%d%d",&n,&m,&k,&q);for(int i=1;i<=q;i++)scanf("%d%d%d",&x[i],&y[i],&t[i]);int l=0,r=1000000001,mid;while(l<=r){mid=(l+r)/2;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)a[i][j]=0;for(int i=1;i<=q;i++)if(t[i]<=mid)a[x[i]][y[i]]=1;for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];int flag=0;for(int i=k;i<=n;i++)for(int j=k;j<=m;j++)flag|=(a[i][j]-a[i-k][j]-a[i][j-k]+a[i-k][j-k]==k*k);if(flag) ans=mid,r=mid-1;else l=mid+1;}printf("%d\n",ans);return 0;
}