acm哪些腦洞令人嘆為觀止？

打acm也有一段時間了 經常被一些神奇的腦洞（黑魔法）或者是神奇的數據結構 震驚的不要不要的 求匯總～

P.S.猴子排序什麼的就算了

---

2015年 world final

j題，求區間最大值，標準做法是快速傅里葉變換。

有一個隊的做法是 暴力算每個值，每40個數的區間存一個最大值，存了一張一萬多的表。對於所有詢問，只要到表裡找，然後再算80個就行了。

下面是官方題解(注意那個 all but one)

我就是這麼寫的。

這就很尷尬了。

---

昨天學習杜教代碼的時候看到了一個黑科技（先上代碼讓大家感受一下）

VI gao(int n) {
VI ret(p+1,0);
if (n==0) {
ret[0]=1;
} else if (n%2==0) {
VI c=gao(n/2);
rep(i,0,p+1) rep(j,0,p+1) if (i+j&<=p) ret[i+j]+=c[i]*c[j]; } else { VI c=gao(n-1); rep(i,0,p+1) rep(j,0,2) if (i+j&<=p) ret[i+j]+=c[i]; } return ret; }

這段代碼返回一個vector，其第i項是

我們知道求有一個經典的遞推的方法：

這種方法因為有除法，在要模的數是一個合數的時候就不適用了

此時，通常的做法就是根據上述公式每次暴力求i和前面那些項的gcd，然後除掉，我也一直是這樣寫的，

直到昨天看到杜教的代碼……

---

位運算模擬一個球滾滾滾滾滾然後掉進洞里

來源：2015 ICPCCamp Day 2 Problem C

---

貌似是14年北京站熱身賽第一題，輸入三段合法的C艹代碼，問每一段是否會死循環。

---

高二的時候看過一道題，當時確實覺得嘆為觀止。

1．星器之中有N×M個區域，可看作分成N行和M列的格子，每個區域之中有若干單位的稱為「星」的對象，這個對象的最小單位已經被確定，所以，這個數量總是整數。

2．魔法使可以驅動星器中位於同一行或同一列的不相鄰（有公共邊的區域稱為相鄰的）兩個區域中各1單位的「星」，使得它們分別向中心移動1格。

3．每一次使用2中的方法驅動「星」，將會產生魔力，魔法使會得到這一部分魔力。魔力的量等於這個兩個區域之間所間隔的區域數。

然後給出星器的初態與末態，輸出至多產生的魔力值

題解是：

?答案與移動方法無關

?行列獨立

?「一個星星的勢能定義為他到左上角格子的距離的平方（即，行號的平方和列號的平方的和），可知，使用一次魔法釋放出的魔力就是兩個星星的勢能和的改變數/2。這樣，計算初、末狀態的所有星星的勢能和，相減/2即可。」

最後竟然腦洞到了勢能守恆....

不過ACM不是好多腦洞題嗎...什麼猜個結論之類的...

---

某次codeforces D題我不記得是div1還是div2了 計算自行車會不會掉進湖裡面的 一大堆人各種情況模擬 一種解答是直接找270度角就完了。找到再更新。侵刪

---

不是ACM題，是某道oi題。

bzoj3308

---

推薦閱讀：