論文：許智磊--淺談補(bǔ)集轉(zhuǎn)化思想在統(tǒng)計(jì)問題中的應(yīng)用

可以發(fā)現(xiàn)這道題長度極小 總數(shù)極小 轉(zhuǎn)化為總數(shù)減去有相交

去重可以運(yùn)用有序化的思想?

如何排除這種重復(fù)計(jì)數(shù)呢？我們采用一種排除重復(fù)的常用方法：有序化。也就是設(shè)法對于新矩形的一種擺放方案，只在處理與它相交的編號最小的已有矩形時才允許計(jì)入總數(shù)T。例如圖七中，如果我們規(guī)定左邊的黑色矩形編號較小，則在處理右邊的黑色矩形時，與它相交的藍(lán)色擺放方案就不允許計(jì)入T，因?yàn)橛疫叺暮谏匦尾⒉皇桥c藍(lán)色方案相交的編號最小的已擺放矩形。容易證明，這樣計(jì)數(shù)不會出現(xiàn)重復(fù)。

#include<cstdio> #include<cstdlib> #include<algorithm> using namespace std;inline char nc(){static char buf[100000],*p1=buf,*p2=buf;if (p1==p2) { p2=(p1=buf)+fread(buf,1,100000,stdin); if (p1==p2) return EOF; }return *p1++; }inline void read(int &x){char c=nc(),b=1;for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1;for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); }inline void read(char &x){for (x=nc();x!='V' && x!='H';x=nc()); }const int N=35;struct Rect{int x1,y1,x2,y2;Rect() { }Rect(int x1,int y1,int x2,int y2):x1(x1),y1(y1),x2(x2),y2(y2) { }friend bool cross(Rect A,Rect B){return B.x1<=A.x2+1 && B.x2>=A.x1-1 && B.y1<=A.y2+1 && B.y2>=A.y1-1;} }R[N];int n,m,L;int main(){char type; int len; int dx,dy;freopen("t.in","r",stdin);freopen("t.out","w",stdout);read(n); read(m); read(L);for (int i=1;i<=L;i++){read(R[i].x1); read(R[i].y1); swap(R[i].x1,R[i].y1);read(len); R[i].x2=R[i].x1; R[i].y2=R[i].y1;read(type); if (type=='V') R[i].x2+=len-1; else R[i].y2+=len-1;}read(len); int Ans=0;if (len<=m){dx=1; dy=len;Ans+=(n-dx+1)*(m-dy+1);for (int i=1;i<=L;i++){for (int x=R[i].x1-dx;x<=R[i].x2+1;x++)for (int y=R[i].y1-dy;y<=R[i].y2+1;y++){if (x<=0 || x+dx-1>n || y<=0 || y+dy-1>m) continue;Rect tem=Rect(x,y,x+dx-1,y+dy-1);int flag=0;for (int j=i+1;j<=L && !flag;j++)if (cross(tem,R[j]))flag=1;if (!flag)Ans--;}}}if (len!=1 && len<=n){dx=len; dy=1;Ans+=(n-dx+1)*(m-dy+1);for (int i=1;i<=L;i++){for (int x=R[i].x1-dx;x<=R[i].x2+1;x++)for (int y=R[i].y1-dy;y<=R[i].y2+1;y++){if (x<=0 || x+dx-1>n || y<=0 || y+dy-1>m) continue;Rect tem=Rect(x,y,x+dx-1,y+dy-1);int flag=0;for (int j=i+1;j<=L && !flag;j++)if (cross(tem,R[j]))flag=1;if (!flag)Ans--;}}}printf("%d\n",Ans);return 0; }

總結(jié)

以上是生活随笔為你收集整理的[补集转化 有序化去重] Ural 1212 Battleship的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。