题意：$n*m$棋盘放置k个皇后，问几个格子不被攻击 1≤n,m≤20000,1≤k≤500
开set判重暴力$O(n*k)$然而，setMLE了QAQ
正解确实是$O(n*k)$的
以hang[i]记录此行是否被占用
用c[i]动态维护没被占用的行有几个安全的，（枚举皇后打标记）
#include<cstdio> #include<iostream> #include<cstring> #include<cctype> #include<algorithm> #include<set> using namespace std; #define olinr return #define _ 0 #define love_nmr 0 #define DB double int x[20505]; int y[20505]; bool hang[20505]; bool c[20505]; inline int read() { int x=0,f=1; char ch=getchar(); while(!isdigit(ch)) { if(ch=='-') f=-f; ch=getchar(); } while(isdigit(ch)) { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } inline void put(int x) { if(x<0) { x=-x; putchar('-'); } if(x>9) put(x/10); putchar(x%10+'0'); } int n; int m; int k; int ans; int main() { n=read(); m=read(); k=read(); for(int i=1;i<=k;i++) { x[i]=read(); y[i]=read(); hang[x[i]]=true; } for(int i=1;i<=n;i++) { if(!hang[i]) { memset(c,0,sizeof c); int sum=m; for(int j=1;j<=k;j++) { if(!c[y[j]]) //枚举所占列，sum-- { c[y[j]]=true; sum--; } if(y[j]+x[j]-i>=1&&y[j]+x[j]-i<=m&&!c[y[j]+x[j]-i]) //自己推一下，神奇的事情发生了！ 这居然是皇后左下到右上对角线与当前行交点的y！！！！！！！ { c[y[j]+x[j]-i]=true; sum--; } if(y[j]-x[j]+i>=1&&y[j]-x[j]+i<=m&&!c[y[j]-x[j]+i]) //这里是从右下到左上的交点 { c[y[j]-x[j]+i]=true; sum--; } } ans+=sum; //统计安全~~~~~的 } } put(ans); olinr ~~(0^_^0)+love_nmr; }