gym 103260 L. Extreme Wealth

不妨設(shè)兩個數(shù)分別是a,b,n=a+b
首先答案是\(2^{n}/(C_n^a)\)
這個結(jié)論可以通過DP后打表找出來
當(dāng)然也可以證明：
結(jié)論1：可以壓兩邊達(dá)到相同的效果
不妨設(shè)左右各壓了c，c+d,原本有X=2c+d
那么兩種情況分別會剩下2c,2c+2d
這和我對右邊壓d會達(dá)到同樣的效果，因?yàn)樽詈笠彩堑玫?c,2c+2d
結(jié)論二，錢一定可以壓完
不妨設(shè)我剩下x塊錢沒有壓出去
那么我左邊壓x/2，右邊壓x/2，也是同樣的效果
所以我們現(xiàn)在知道了，每一輪，我們都會把錢全部花光在兩邊
即我們現(xiàn)在有一顆決策二叉樹，到達(dá)每個葉子的概率是相同的，我們把錢全部壓倒葉子里，然后最后答案就是最小的葉子*\(2^n\)
這里顯然采取均分的方法，所以答案就是\(2^{n}/(C_n^a)\)

第二個問題來了，怎么計(jì)算答案
考慮當(dāng)n較小的時(shí)候用python暴力算，當(dāng)n較大的時(shí)候套用斯特林公式
\(n!=\sqrt{2\pi n}(\frac{n}{e})^n\)
整一個過程可以取ln算
就可以在誤差范圍內(nèi)通過此題了

1656 H. Equal LCM Subsets

先考慮一個check兩個集合lcm是否相等的樣子
對于A集合中的每個元素a，去計(jì)算
\(d=gcd(a/gcd(a,b_i))\)
考慮\(a/gcd(a,b_i)\)的意義，其實(shí)就是\(a\)和\(b_i\)中指數(shù)\(a\)比較大的部分
如果\(d>1\)，那么可以確定兩個lcm一定不相等
因?yàn)?span id="w0obha2h00" class="math inline">\(a\)已經(jīng)存在某一個因子的次方比\(b\)里面所有都大
若\(d=1\)，則可以推出\(a|lcm(B)\)
對\(B\)同理，假設(shè)此時(shí)所有\(d\)都為\(1\)，那么可以得到兩個集合的\(lcm\)相等

至此，做法已經(jīng)出來了，如果存在一個\(d>1\)，就把這個元素刪掉
然后不斷重復(fù)這個過程就可以了
至于如何快速詢問\(d\)，可以用\(n\)棵線段樹來維護(hù)

gym102538 300iq Contest 3 C.Cells Blocking

跑出一條盡可能往左的路和一條盡可能往右的路，分別即為\(A\)，\(B\)

考慮如果只能堵一個點(diǎn)怎么做

兩條路徑的交集就是答案了

同理，如果我們堵了一個交集，那么我們選任何一個其他點(diǎn)都是答案

否則，我們?nèi)ッ杜e\(A\)上的每一個點(diǎn)，堵上這個點(diǎn)，然后搜索另外的一條路徑盡可能往左的路徑C，此時(shí)CB的交集就是答案了

一開始我們預(yù)處理出每個點(diǎn)是否可以從起點(diǎn)到達(dá)且能到達(dá)終點(diǎn)

就可以\(O(路徑長度)\)搜出來一條路徑

故復(fù)雜度是\(O(n^2)\)

性質(zhì)有只往下或右走有一個性質(zhì)，就是第\(i\)步的位置一定在\(x+y=i\)的點(diǎn)上

然后這種圖的支配點(diǎn)是可以爆搜一下跑出來的

gym102538 300iq Contest 3 E Easy Win

答案等價(jià)于詢問\((a_{1}modx) ⊕{a_2modx}⊕....⊕ {a_nmodx}\)

對于異或問題，常常考慮拆位來做

對于取模問題，常常考慮枚舉倍數(shù)

對于一個\(x\)，去枚舉其倍數(shù)，不妨設(shè)其倍數(shù)為\(y\)

那么對于在\([y,y+x)\)中的所有數(shù)\(z\)，其余數(shù)都是\(z-y\)

換句話說，我們要快速求出\(z-y\)的異或和

帶減法依然是不好做的，考慮一位一位考慮，現(xiàn)在處理\(2^i\)

定義一個輔助數(shù)組\(f_{j,i}\)表示有多少個數(shù)\(x\)滿足\(x\ge j\)且\((x-j)\)在\(i\)這一位為\(1\)

有一個性質(zhì)就是假如\(x\)在第\(i\)位為1，那么\(x-2^{i+1}\)在第\(i\)位也同樣為1

可以遞推的\(f_{j,i}=f_{j+2^{i+1}}+cnt[j+2^ij+2^{i+1}-1]\)

\(cnt[l,r]\)的定義為，這個區(qū)間里有多少個數(shù)

這個\(f\)滿足一個性質(zhì)，就是雖然減的數(shù)不同，但是假如兩個數(shù)的差值是\(2^{i+1}\)，那么依然是可以差分的

這時(shí)候再去考慮我們的詢問\([y,y+x)\)

找到一個最大的位置\(k\in[y,y+x)\)，讓他與\(y\)關(guān)于\(2^{i+1}\)同余

差分得出\([y,k]\)的答案，然后對于\([k,y+x)\)，因?yàn)閰^(qū)間的長度不超過\(2^{i+1}\)，所以變化點(diǎn)只有一個，直接去詢問\(cnt[k+2^{i},min(k+2^{i+1}-1,y+x)]\)即可

復(fù)雜度\(O(nlog^2n)\)

1615 H

最優(yōu)化問題常見方法，構(gòu)造一個下界，嘗試構(gòu)造一個方案達(dá)到下界

構(gòu)造下界

我們定義\((u,v)\)為所有\(u\)可以到\(v\)的點(diǎn)對，直接相鄰或者間接相鄰都可以

假設(shè)存在有一個點(diǎn)對\((u,v)\)，那么答案至少為\(a_u-a_v\)

更一般的，如果對于k個點(diǎn)對\((u_i,v_i)\)，滿足一個數(shù)字在集合\((U∪V)\)中只出現(xiàn)了一次

那么答案至少為\(\sum a_{u_i}-a_{v_i}\)

找到這個最大的和即為下界

這個過程很簡單，對于原圖的\((u,v)\)，建立\((inf,a_u-a_v)\)的邊

然后對于每一個點(diǎn)\(u\),\(S\)與\(u\)和\(u\)與\(T\)建立\((1,0)\)的邊，跑最大費(fèi)用流即可

最后，如果\(u\)同時(shí)與S和T的邊都滿流了，把他設(shè)定為不滿流，顯然這樣不會影響費(fèi)用

這樣處理之后，每一個點(diǎn)要么和\(S\)滿流，要么和\(T\)滿流，即至多出現(xiàn)一次

構(gòu)造方案

在殘留網(wǎng)絡(luò)中，即如果還有流量就保留，包括反向邊，對S跑出到所有節(jié)點(diǎn)的最長路\(d_u\)

我們令\(b_u=a_u+d_u\)為答案

對于原來的一個限制點(diǎn)對\((u,v)\)，因?yàn)樵镜倪吜髁繛閕nf，故必存在與殘留網(wǎng)絡(luò)中，即有\(d_u+(a_u-a_v)\le d_v\)，即\(b_u=d_u+a_u\le d_v+a_v=b_v\)，符合條件

但同時(shí)，對于我們選中的點(diǎn)對\((u,v)\)，反向邊有流量，同理可得\(b_v\le b_u\)。

同時(shí)，因?yàn)?span id="w0obha2h00" class="math inline">\(u\)在殘留網(wǎng)絡(luò)中與\(t\)連通，故必不可能有\(d_u>0\)，否則找到一條增廣路

同理有\(d_v\)不可能小于\(0\)

故得到\(a_v\le b_v=b_u\le a_u\)

不難發(fā)現(xiàn)，對于一個選中的點(diǎn)對，調(diào)整力度恰好就是\(a_u-a_v\)

對于一個沒有選中的點(diǎn)，有\(d_u=0\)，證明同上

故恰好與所需的下界相同

1622 F

不妨令\(f(x)\)為消完因子之后的答案，即消完平方因子之后的數(shù)

顯然有\(f(xy)=f(f(x)f(y))\)

\(f(n!(n+1)!)=f(n+1)\)

對于偶數(shù)\(2k\)，\(f(1!2!3!...(2k)!)=f(2*4*8*...*2k)=f(2^k*k!)\)

若\(k\)為偶數(shù)，則只去掉\(k\)就可以是一個合法方案

若k為奇數(shù)，去掉\(k\)和\(2\)就是一個合法的方案

故對于偶數(shù)，只需要刪掉不超過2個數(shù)

奇數(shù)因?yàn)橥ㄟ^刪掉\(n\)就可以變?yōu)榕紨?shù)，故答案不超過\(3\)

故對于所有的數(shù)刪掉的數(shù)不超過\(3\)個

• 判斷平方數(shù)的一個小trick

對于所有質(zhì)數(shù)隨機(jī)一個大數(shù)\(p(x)\)，然后\(p(xy)=p(x) \ xor\ p(y)\)

一個數(shù)為平方數(shù)，顯然有\(p(x)=0\)

故得到做法，先判一下全選，然后嘗試刪掉一個，然后嘗試刪掉兩個，最后嘗試三個，一定能找到一組解