蒟蒻的小窝

蒟蒻的小窝

题解 P5542 【[USACO19FEB]Painting The Barn S】

posted on 2020-08-18 19:56:36 | under 题解 |

笨蛋的方法就是模拟呗,每次都涂上,最后扫一趟就好了,但是这效率最慢是 $n*1000000$,明显是超时滴。 但我们看,每次是涂一个方块,整个方块内颜色都会 $+1$,那就果断造前缀和然后二维容斥啊,对与 $x1,y1,x2,y2$,我们把造前缀和的二维数组 $F[x1][y1]+1,F[x2][y1]-1,F[x1][y2]-1,F[x2][y2]+1;$ 咦?为什么是x2,y2而不是x2+1,y2+1呢?因为题目给的是点而不是边,x个点中间只有 $x-1$ 条边,所以x2其实就是x2-1+1。 最后造前缀和 $F[i][j]+=F[i-1][j]+F[i][j-1]-F[i-1][j-1];$ 只要 $F[i][j]==k$ ,那 $ans$ 就 $++$,最后输出结果就完了。 但是,数据给的范围是 $0-1000$,也就是说当 $x=0$ 或 $y=0$ 的时候, $i,j$ 也是从 $0$ 开始跑的,那么 $i-1,j-1$ 就小于 $0$ 了,F数组就会越界,那么该怎么处理呢? 在读数据的时候把给的坐标都+1就完了,最后造前缀和刷答案的时候从 $1-1001$ 就ok了。

Code:

#include<bits/stdc++.h>
#define maxh 1005
using namespace std;
int N,K,Ans,F[maxh][maxh];
int read(){
    int ret=0,f=1;char ch=getchar();
    while (!isdigit(ch)){if (ch=='-')f=-f;ch=getchar();}
    while (isdigit(ch)) ret=(ret<<3)+(ret<<1)+ch-'0',ch=getchar();
    return ret*f;
}
int main(){
    N=read(),K=read();
    while (N--){
        int a=read()+1,b=read()+1,c=read()+1,d=read()+1;
        F[a][b]++,F[a][d]--,F[c][b]--,F[c][d]++;
    }
    for (int i=1;i<=1001;i++)
    for (int j=1;j<=1001;j++){
        F[i][j]+=F[i-1][j]+F[i][j-1]-F[i-1][j-1];
        Ans+=F[i][j]==K;
    }
    printf("%d\n",Ans);
    return 0;
}