本文共 1803 字，大约阅读时间需要 6 分钟。
如果只有行和列的覆盖,那么可以直接做,但现在有左上到右下的覆盖.
考虑对行和列的覆盖情况做一个卷积,然后就有了x+y的非覆盖格子数.
然后用骑士的左上到右下的覆盖特判掉那些x+y的格子就可以了.
注意题意,Row是从上到下来的,被坑得好惨.
#include #include #include #include #include #include #include #include #include #include using namespace std;#define LL long long#define FILE "dealing"#define up(i,j,n) for(LL i=j;i<=n;++i)#define db double#define ull unsigned long long#define eps 1e-10#define pii pair LL read(){ LL x=0,f=1,ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();} return f*x;}const LL maxn=402000,maxm=20000,mod=(LL)(1e9+7+0.1),limit=(LL)(1e6+1),inf=(LL)(1e9);bool cmax(LL& a,LL b){return a b?a=b,true:false;}namespace FFT{ db pi=acos(-1.0); struct cp{ db x,y; cp(db x=0,db y=0):x(x),y(y){} cp operator+(const cp& b){return cp(x+b.x,y+b.y);} cp operator-(const cp& b){return cp(x-b.x,y-b.y);} cp operator*(const cp& b){return cp(x*b.x-y*b.y,x*b.y+y*b.x);} }w[maxn],a[maxn],b[maxn]; LL R[maxn],H,L; void FFT(cp* a,LL f){ up(i,0,L-1)if(i >1; cp wn(cos(pi/l),f*sin(pi/l)); up(i,1,l-1)w[i]=w[i-1]*wn; for(LL st=0;st >1]>>1)|((i&1)<<(H-1)); w[0].x=1; FFT(a,1);FFT(b,1); up(i,0,L-1)a[i]=a[i]*b[i]; FFT(a,-1); up(i,1,n+m-1)ch[i]=(LL)(a[i].x+0.5); }};LL n,m,K;LL a[maxn],b[maxn],c[maxn],d[maxn];int main(){ freopen(FILE".in","r",stdin); freopen(FILE".out","w",stdout); LL T=read(); up(j,1,T){ n=read(),m=read(),K=read(); up(i,1,n)a[i]=1; up(i,1,m)b[i]=1; up(i,1,n+m)d[i]=0; up(i,1,K){ LL x=n-read()+1,y=read(); a[x]=0,b[y]=0; d[x+y]=1; } FFT::solve(a,b,n,m,c); LL ans=0; up(i,1,n+m)if(c[i]&&!d[i])ans+=c[i]; printf("Case %lld: %lld\n",j,ans); } return 0;}
转载于:https://www.cnblogs.com/chadinblog/p/6524253.html