题解 P3717 【[AHOI2017初中组]cover】

· · 题解

更好的阅读体验请点这里

（这不是暴力就可以了吗）

当然正解就是暴力，所以假设n,m,r\leqslant 1000，再看看这道题

这道题就是典型的区间修改（将可以覆盖的地方+1）与单次查询（最后问>0的有几个）

于是以行为单位差分，每一次修改相当于对每一行的元素做区间修改

但是每一行被修改的位置和长度互不相同，具体取决于半径r和行号i到圆心所在行号y的距离（|i-y|）

假设存在e_{0..r}数组，e_i表示斜边为r，对边为i的直角三角形的邻边长度的整数部分，即e_i=\lfloor\sqrt{r^2-i^2}\rfloor

那么对于第i行，如果圆心是(x,y)，半径为r，覆盖的区间就是[max(1,x-e_{|i-y|}),min(n,x+e_{|i-y|})]（可别忘了处理边界）

最后是如何计算e数组

（当然可以直接使用sqrt()）

但是注意到e数组具有不上升单调性，可以使用一种类似递推的方法做，保证计算O(n)（虽然说其实完全没有必要啦）

具体做法就请大家自己想啦（其实是本蒟蒻太懒了），上代码

//This program is written by Brian Peng.
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include<bits/stdc++.h>
using namespace std;
#define Rd(a) (a=read())
#define Gc(a) (a=getchar())
#define Pc(a) putchar(a)
inline int read(){
    register int x;register char c(getchar());register bool k;
    while(!isdigit(c)&&c^'-')if(Gc(c)==EOF)exit(0);
    if(c^'-')k=1,x=c&15;else k=x=0;
    while(isdigit(Gc(c)))x=(x<<1)+(x<<3)+(c&15);
    return k?x:-x;
}
void wr(register int a){
    if(a<0)Pc('-'),a=-a;
    if(a<=9)Pc(a|'0');
    else wr(a/10),Pc((a%10)|'0');
}
signed const INF(0x3f3f3f3f),NINF(0xc3c3c3c3);
long long const LINF(0x3f3f3f3f3f3f3f3fLL),LNINF(0xc3c3c3c3c3c3c3c3LL);
#define Ps Pc(' ')
#define Pe Pc('\n')
#define Frn0(i,a,b) for(register int i(a);i<(b);++i)
#define Frn1(i,a,b) for(register int i(a);i<=(b);++i)
#define Frn_(i,a,b) for(register int i(a);i>=(b);--i)
#define Mst(a,b) memset(a,b,sizeof(a))
#define File(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout)
#define N (110)
int n,m,r,a[N][N],e[N],x,y,ans;
signed main(){
    Rd(n),Rd(m),*e=Rd(r);
    Frn1(i,1,r){e[i]=e[i-1];while(e[i]*e[i]+i*i>r*r)--e[i];}
    while(m--){
        Rd(x),Rd(y);
        Frn1(i,max(1,y-r),min(n,y+r)){
            ++a[max(1,x-e[abs(i-y)])][i];
            --a[min(n,x+e[abs(i-y)])+1][i];
        }
    }
    Frn1(i,1,n)Frn1(j,1,n)if(a[i][j]+=a[i-1][j])++ans;
    wr(ans),exit(0);
}

（个人认为如果n,m,r\leqslant 1000，这道题至少上绿）