題目大意就是給你一個R*C的棋盤，上面有超級兵，這種超級兵會攻擊 同一行、同一列、同一主對角線的所有元素，現在給你N個超級兵的坐標，需要你求出有多少方塊是不能被攻擊到的(R,C,N<50000)

遇到這種計數問題就要聯想到容斥（組合數學太重要了），由容斥原理：

被攻擊的方塊數=行被攻擊的方塊數+列被攻擊的方塊數+主對角線被攻擊的方塊數-同時被行、列攻擊的方塊數-同時被行、對角線攻擊的方塊數-同時被列、對角線攻擊的方塊數+同時被行、列、對角線攻擊的方塊數

因為行列都不會很大，所以我們用三個數組分別記錄行、列、對角線上含有超級兵的情況（從1開始）。對于對角線，我們不妨從右上角開始編起，從1-R+C-1,那么對于任意一塊<x,y>，它所屬的對角線為x-y+C。

開始計數：

行被攻擊的方塊數和列被攻擊的方塊數，這個很簡單，就是掃一遍數組，然后如果有超級兵就加上

主對角線被攻擊的方塊數：我們需要知道對于任何一條主對角線，在R*C的棋盤里，它的主對角線有多長，根據推導，我們發現當對角線編號為1~C的時候，對角線都是從第一行開始的，它的長度按道理來講應該是隨著編號的增加遞增的，但是當長度達到一定的時候就會收到行數的限制，因此長度為min(i,R)。可以理解為，i就是因為收到列數的限制的最大的長度，但是同時還需要收到行數的限制。當編號為C+1~R+C-1的時候，此時長度總體來講會遞減，主要收到行數的限制，但是同樣也會收到列數的限制，因此長度為min(R+C-i,C)。得到長度以后我們就可以遍歷一遍得到主對角線被攻擊的方塊數

同時被行、列攻擊的方塊數：這個很簡單，就是總共被攻擊的行數*被攻擊的列數

同時被行、對角線攻擊的方塊數：我們只要知道對角線在行上的范圍，然后再統計在這個范圍內有多少行被攻擊就可以了。為了快速得到一個范圍內有多少行被攻擊，我們可以用一個前綴數組，來計算某一個行區間內有多少被攻擊。現在重點在于如何求對角線所占行的范圍。同樣的我們需要進行分類討論：當序號為1~C的時候，每一個對角線都是從第1行開始的，我們只需要加上上面求得的長度就能夠得到最后一行應該為min(i,C)。當序號為C+1~R+C-1的時候，每一行是從i-C+1開始的，到i-C+1+min(R+C-i,C)結束。

同時被列、對角線攻擊的方塊數：分析同上，我們這里只討論每一條對角線列的范圍額：當序號為1~C的時候，是C-i+1到C-i+1+min(i,C)，當序號為C+1~R+C-1的時候，是1到min(R+C-1,C)

同時被行、列、對角線攻擊的方塊數：這個可能就沒有很簡單了，我們需要求出所有既被行、列攻擊，又被對角線攻擊的塊數。設X行Y列，則如果要同時被攻擊，應該還存在一個對角線X-Y+C，觀察這個式子，我們有什么方法迅速得到嗎？好多個數相加、好多個數相減，我們還需要得到所有的結果，而且還不能遍歷（會超時），我們就應該聯想到FFT，加減運算轉化為多項式乘法運算后，使用FFT就能nlogn解決問題。那么這兩個多項式應該怎么構造呢？行多項式我們不妨就設為r[i]*xⁱ,那么列多項式應該為c[i]*x^C-i，這樣運算以后的結果就是x^i-j+C，得到的對角線的系數就是這條對角線同時被行列攻擊的塊數（因為i,j是不同的，所以是這個對角線上的不同的塊）。如果i-j+C處恰好有一條對角線，接說明這些塊需要加上。

可以看一哈我寫的代碼，應該還是比較清晰的。

AC代碼：

#include<iostream> #include<cstring> #include<cstdio> #include<climits> #include<algorithm> #include<ctime> #include<cstdlib> #include<queue> #include<set> #include<map> #include<cmath>using namespace std; const int MAXN=1<<17; const double PI=acos(-1.0); typedef long long ll;int read() {int x=0,sign=1; char c=getchar();while(c<'0' || c>'0') {if(c=='-') sign=-1; c=getchar();}while(c>='0' && c<='9'){x=x*10+c-'0'; c=getchar();}return x*sign; }struct complex {double r,i;complex(double _r=0,double _i=0):r(_r),i(_i){}complex operator +(const complex &b) {return complex(r+b.r,i+b.i);}complex operator -(const complex &b) {return complex(r-b.r,i-b.i);}complex operator *(const complex &b) {return complex(r*b.r-i*b.i,r*b.i+i*b.r);} }A[MAXN],B[MAXN];void change(complex y[],int len) {int i,j,k;for(i = 1, j = len/2;i < len-1;i++){if(i < j)swap(y[i],y[j]);k = len/2;while( j >= k){j -= k;k /= 2;}if(j < k)j += k;} }void fft(complex y[],int len,int on) {change(y,len);for(int h = 2;h <= len;h <<= 1){complex wn(cos(-on*2*PI/h),sin(-on*2*PI/h));for(int j = 0;j < len;j += h){complex w(1,0);for(int k = j;k < j+h/2;k++){complex u = y[k];complex t = w*y[k+h/2];y[k] = u+t;y[k+h/2] = u-t;w = w*wn;}}}if(on == -1)for(int i = 0;i < len;i++)y[i].r /= len; }void FFT(int a[],int la,int b[],int lb)//la,lb分別是a,b數組的最高位+1 {int len=1; while(len<la+lb) len<<=1;for(int i=0;i<la;++i) A[i]=complex(a[i],0);for(int i=la;i<len;++i) A[i]=complex(0,0);for(int i=0;i<lb;++i) B[i]=complex(b[i],0);for(int i=lb;i<len;++i) B[i]=complex(0,0);fft(A,len,1); fft(B,len,1);for(int i=0;i<len;++i) A[i]=A[i]*B[i];fft(A,len,-1); }int R,C,D,N; int r[MAXN],c[MAXN],d[MAXN]; int sumr[MAXN],sumc[MAXN];//行列前綴和 ll ans;int main() {//freopen("data.txt","w",stdout);int T;//T=read();scanf("%d",&T);for(int Case=1;Case<=T;++Case){//initans=0; sumr[0]=sumc[0]=0;for(int i=0;i<=R;i++) r[i]=0;for(int i=0;i<=C;i++) c[i]=0;for(int i=0;i<=D;i++) d[i]=0;//read //R=read(); C=read(); N=read();scanf("%d%d%d",&R,&C,&N);int u,v;while(N--){//u=read(); v=read();scanf("%d%d",&u,&v);r[u]=1; c[v]=1; d[u-v+C]=1;}//統計行列被攻擊的塊數,得到前綴和 for(int i=1;i<=R;++i){if(r[i]) ans+=C; sumr[i]=sumr[i-1]+r[i];}for(int i=1;i<=C;++i){if(c[i]) ans+=R; sumc[i]=sumc[i-1]+c[i];}//test//減去行列同時被攻擊的塊數ans-=sumr[R]*sumc[C]; //統計主對角線被攻擊的塊數//減去同時被行和對角線、列和對角線攻擊的塊數 //1~R-1+C X-Y+CD=R-1+C;for(int i=1;i<=D;++i){if(d[i]){if(i<=C)//對角線塊數遞增，行數限制 {int dr1=0,dr2=min(i,R); //行數始末 int dc1=C-i,dc2=dc1+dr2;//列數始末 ans+=dr2;ans-=sumr[dr2]-sumr[dr1];ans-=sumc[dc2]-sumc[dc1];}else//對角線塊數遞減，列數限制 {int dc1=0,dc2=min(R+C-i,C);//列數始末 int dr1=i-C,dr2=dr1+dc2; //行數始末ans+=min(R+C-i,C);ans-=sumr[dr2]-sumr[dr1];ans-=sumc[dc2]-sumc[dc1];}}}//加上同時被行列對角線攻擊的方塊reverse(c,c+C+1);FFT(r,R+1,c,C+1);for(int i=1;i<=D;++i){if(d[i]){ans+=(ll)(A[i].r+0.5); }}printf("Case %d: %lld\n",Case,(ll)R*C-ans);//if(Case!=T) printf("\n");}return 0; }

總結

以上是生活随笔為你收集整理的UVa12633-Super Rooks on Chessboard-容斥+FFT的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。