UVa12633-Super Rooks on Chessboard-容斥+FFT

題目大意就是給你一個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]*xi,那么列多項式應該為c[i]*xC-i，這樣運算以后的結果就是xi-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;
}

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/383760.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/383760.shtml
英文地址，請注明出處：http://en.pswp.cn/news/383760.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！

相關文章

Linux網絡編程---I/O復用模型之poll

Linux網絡編程---I/O復用模型之poll

https://blog.csdn.net/men_wen/article/details/53456474Linux網絡編程—I/O復用模型之poll 1.函數poll poll系統調用和select類似&#xff0c;也是在指定時間內輪詢一定數量的文件描述符&#xff0c;以測試其中是否有就緒者。 #include <poll.h>int poll(struct pollfd…
閱讀更多...
FFT模板

FFT模板

整理了一下&#xff0c;自己寫了一下模板 const double PIacos(-1.0); struct complex {double r,i;complex(double _r0,double _i0):r(_r),i(_i){}complex operator (const complex &b) {return complex(rb.r,ib.i);}complex operator -(const complex &b) {return c…
閱讀更多...
Linux網絡編程---I/O復用模型之epoll

Linux網絡編程---I/O復用模型之epoll

https://blog.csdn.net/men_wen/article/details/53456474 Linux網絡編程—I/O復用模型之epoll 1. epoll模型簡介 epoll是Linux多路服用IO接口select/poll的加強版&#xff0c;e對應的英文單詞就是enhancement&#xff0c;中文翻譯為增強&#xff0c;加強&#xff0c;提高&…
閱讀更多...
POJ 1741tree-點分治入門

POJ 1741tree-點分治入門

學習了一下點分治&#xff0c;如果理解有誤還請不吝賜教。 為了快速求得樹上任意兩點之間距離滿足某種關系的點對數&#xff0c;我們需要用到這種算法。 點分治是樹上的一種分治算法&#xff0c;依靠樹和子樹之間的關系進行分治從而降低復雜度。 和其他樹上的算法有一些區別…
閱讀更多...
基于單鏈表的生產者消費者問題

基于單鏈表的生產者消費者問題

『生產者與消費者問題分析』「原理」生產者生產產品&#xff0c;消費者消費產品。產品如果被消費者消費完了&#xff0c;同時生產者又沒有生產出產品&#xff0c;消費者 就必須等待。同樣的&#xff0c;如果生產者生產了產品&#xff0c;而消費者沒有去消費&#x…
閱讀更多...
C++智能指針（一）智能指針的簡單介紹

C++智能指針（一）智能指針的簡單介紹

https://blog.csdn.net/nou_camp/article/details/70176949C智能指針 在正式了解智能指針前先看一下下面的一段代碼 #include<iostream> using namespace std; class A { public:A():_ptr(NULL), _a(0){}~A(){} public:int* _ptr;int _a; };void test() {A a;int *p1 ne…
閱讀更多...
聰聰可可-點分治

聰聰可可-點分治

聰聰和可可是兄弟倆&#xff0c;他們倆經常為了一些瑣事打起來&#xff0c;例如家中只剩下最后一根冰棍而兩人都想吃、兩個人都想玩兒電腦&#xff08;可是他們家只有一臺電腦&#xff09;……遇到這種問題&#xff0c;一般情況下石頭剪刀布就好了&#xff0c;可是他們已經玩兒…
閱讀更多...
C++智能指針（二）模擬實現三種智能指針

C++智能指針（二）模擬實現三種智能指針

https://blog.csdn.net/nou_camp/article/details/70186721在上一篇博客中提到了Auto_ptr(C智能指針&#xff08;一&#xff09;)&#xff0c;下面進行模擬實現Auto_ptr 采用類模板實現 #include<iostream> using namespace std; template<class T> class Autoptr …
閱讀更多...
Prime Distance On Tree-樹分治+FFT

Prime Distance On Tree-樹分治+FFT

題目描述 Problem description. You are given a tree. If we select 2 distinct nodes uniformly at random, what’s the probability that the distance between these 2 nodes is a prime number? Input The first line contains a number N: the number of nodes in this…
閱讀更多...
C++智能指針（三）總結

C++智能指針（三）總結

https://blog.csdn.net/nou_camp/article/details/70195795 在上一篇博客中&#xff08;C智能指針&#xff08;二&#xff09;&#xff09;模擬實現了三種智能指針。 其中最好的就是shared_ptr,但是這并不代表它就是最完美的&#xff0c;它也有問題&#xff0c;這個問題就是循環…
閱讀更多...
POJ2114-Boatherds-樹分治

POJ2114-Boatherds-樹分治

題目描述 Boatherds Inc. is a sailing company operating in the country of Trabantustan and offering boat trips on Trabantian rivers. All the rivers originate somewhere in the mountains and on their way down to the lowlands they gradually join and finally th…
閱讀更多...
c++11 你需要知道這些就夠了

c++11 你需要知道這些就夠了

https://blog.csdn.net/tangliguantou/article/details/50549751c11新特性舉著火把尋找電燈今天我就權當拋磚引玉&#xff0c;如有不解大家一起探討。有部分內容是引用自互聯網上的內容&#xff0c;如有問題請聯系我。T&& 右值引用 std::move 右值引用出現之前我們只能…
閱讀更多...
HDU5977-Garden of Eden-樹分治+FWT

HDU5977-Garden of Eden-樹分治+FWT

題目描述 When God made the first man, he put him on a beautiful garden, the Garden of Eden. Here Adam lived with all animals. God gave Adam eternal life. But Adam was lonely in the garden, so God made Eve. When Adam was asleep one night, God took a rib fro…
閱讀更多...
C++11新特性學習

C++11新特性學習

https://blog.csdn.net/tennysonsky/article/details/778170481、什么是C11C11標準為C編程語言的第三個官方標準&#xff0c;正式名叫ISO/IEC 14882:2011 - Information technology -- Programming languages -- C。在正式標準發布前&#xff0c;原名C0x。它將取代C標準第二版I…
閱讀更多...
C++ override 關鍵字用法

C++ override 關鍵字用法

override關鍵字作用&#xff1a; 如果派生類在虛函數聲明時使用了override描述符&#xff0c;那么該函數必須重載其基類中的同名函數&#xff0c;否則代碼將無法通過編譯。舉例子說明struct Base {virtual void Turing() 0;virtual void Dijkstra() 0;virtual void VNeumann…
閱讀更多...
Gym - 101981I-MagicPotion-最大流

Gym - 101981I-MagicPotion-最大流

題目描述 There are n heroes and m monsters living in an island. The monsters became very vicious these days, so the heroes decided to diminish the monsters in the island. However, the i-th hero can only kill one monster belonging to the set Mi. Joe, the st…
閱讀更多...
c++仿函數 functor

c++仿函數 functor

https://www.cnblogs.com/decade-dnbc66/p/5347088.html內容整理自國外C教材先考慮一個簡單的例子&#xff1a;假設有一個vector<string>&#xff0c;你的任務是統計長度小于5的string的個數&#xff0c;如果使用count_if函數的話&#xff0c;你的代碼可能長成這樣&#…
閱讀更多...
HDU4812-D Tree-樹分治

HDU4812-D Tree-樹分治

題目描述 There is a skyscraping tree standing on the playground of Nanjing University of Science and Technology. On each branch of the tree is an integer (The tree can be treated as a connected graph with N vertices, while each branch can be treated as a v…
閱讀更多...
成為C++高手之實戰項目

成為C++高手之實戰項目

https://blog.csdn.net/niu_gao/article/details/51458721 在內存中模擬出一副牌&#xff0c;然后模擬洗牌&#xff0c;發牌等動作。 流程是這樣的&#xff1a;構建一副牌保存到一個數組中—洗牌—創建玩家—向玩家發牌–輸出每個玩家的牌。 #include <stdio.h> #include…
閱讀更多...
C++中String類的實現

C++中String類的實現

https://www.cnblogs.com/zhizhan/p/4876093.html原文&#xff1a;http://noalgo.info/382.html String是C中的重要類型&#xff0c;程序員在C面試中經常會遇到關于String的細節問題&#xff0c;甚至要求當場實現這個類。只是由于時間關系&#xff0c;可能只要求實現構造函數、…
閱讀更多...
最新文章

Copyright @ 2022~2023