P3271 JLOI2016 方 容斥 數學

2022-09-22 22:15:14 字數 2364 閱讀 5171

給定一個\(n*m\)的矩陣,從中刪去\(k\)個頂點,求最後能形成多少個正方形

範圍&性質:\(1\le n,m\le 10^6,1\le k\le 2000\),正方形可以是斜著的(邊不一定與網格圖上的邊重合)

暴力做法:

列舉,複雜度\(o(nmk)\),直接去世

正解:通過容斥簡化運算,記\(f(i)\)表示至少包含\(i\)個被刪除的點的正方形數目,最終的答案就是\(f(0)-f(1)+f(2)-f(3)+f(4)\),那麼問題轉化成了如何求\(f(i)\)

首先我們考慮對於一個被刪除的點,它能形成的正方形有多少種,情況如下圖所示

我們很容易觀察出正方形可以分為兩類,斜著的和正著的,但是斜著的正方形可以在大的正方形裡被統計,rt

我們按照橫縱座標的差值,對斜著的正方形進行定義,如下圖的正方形我們可以稱其為\((a,b)\)正方形

那麼對於一個被刪除的點,它的屬性可以用四個值表示分別為\((u,d,l,r)\)

我們先考慮\((0,x)\)正方形,也就是橫平豎直的正方形,分象限考慮,這樣的正方形的數目是\(min(l,d)+min(d,r)+min(u,r)+min(u,l)\)

接下來考慮斜著的正方形,我們依舊分象限考慮,先考慮\((l,r,d)\)所在象限,正方形\((a,b)\)

我們列出此時對\(a\)的限制$a\le r,a\le a+b-1,1\le a,a+b-l\le a $改為列舉a+b,轉化成**就是

for(int c=2;c<=d&&c<=l+r;c++)

但是,單次\(o(n^2)\)的複雜度不優秀,其實\(c\)影響答案的值只在\([l+1,r+1]\)範圍內,因為小於\(l+1\)時\(min\)會取1,大於$ r+1\(時\)min$會取r,在取值範圍內是一次函式,所以可以對列舉進行優化,只列舉分界點

int lim=min(l+r,h),res=0;

int pos[3]=;

sort(pos,pos+3);

int cl=1,cr,vl,vr;

for(int i=0;i<3;i++)

return res;

對於含兩個以上的情況,列舉兩個點,利用向量或者座標等數學知識推出其他點的座標

tip:對於含至少三個點的情況會重複計算\(c_3^2\)次,對於至少四個點的情況會重複計算\(c_4^2\)次,統計答案的時候直接除掉就可以

#include#define mk(x,y) make_pair(x,y)

using namespace std;

namespace zzc

int calc(int l,int r,int h)

; sort(pos,pos+3);

int cl=1,cr,vl,vr;

for(int i=0;i<3;i++)

return res; }

int calc0()

return res; }

int calc1()

return res; }

int calc2()

}return res; }

int calc3()

if(check(x1-y1+y2,y1+x1-x2)&&check(x2+y2-y1,y2-x2+x1))

if(((y1+y2+x1+x2)&1)==0)}}

}return res/3;

}int calc4()

if(check(x1-y1+y2,y1+x1-x2)&&check(x2+y2-y1,y2-x2+x1))

if(((y1+y2+x1+x2)&1)==0)}}

} return res/6;

} void work()

printf("%d\n",(calc0()-calc1()+calc2()-calc3()+calc4()+mod)%mod); }}

signed main()

JLOI2016 成績比較 容斥 拉格朗日插值

洛谷p3270 jloi2016 成績比較 要求的是三部分 1 只考慮從所有人中選出k個人被碾壓的方案數 2 只考慮所有人每門成績高低關係 高於b神或低於b神 的方案數 3 只考慮所有人的具體成績方案數 答案顯然是三數相乘 下文中下標均從1開始 比如 文中u i表示題中u 顯然是 c k 每門都要有...