[CF] B. XOR-pyramid

-
題目：https://codeforces.com/contest/983/problem/B

MySol：https://codeforces.com/contest/983/submission/51883938

我是智障的一千種理由

其中之一是我根本無法多看題目一眼然後看出性質

看完這題後很明顯可以感覺到如果我能夠O(1)弄出[l, r]的答案的話，那麼隨便弄弄就可以求出所有答案了。

理由是按照長度做DP，就可以維護在[l, r]內的最佳答案了。

然後我的思路就跑到了要如何O(1)呢？我馬上就想到了巴斯卡三角形

每格被算到的次數剛好是巴斯卡三角耶，成功把算出區間的複雜度弄到O(N)了，因為可以O(N^2)預處理楊輝三角形

然後就不會了QQ

看解之後馬上就察覺到了，[l, r]的答案 = [l, r - 1]^[l + 1, r]的答案，我根本智障

上面那個式子看起來很顯然，對吧？

嗯...，我也是這麼覺得的，那麼，一開始沒看出來的我是智障這件事就沒有爭議了，對吧？

留言

張貼留言

這個網誌中的熱門文章

Shellshock.io從入門到上手（針對單狙）（沒有圖片、影片版本）

-
簡單介紹 作為一款網頁版FPS遊戲，Shellshock.io提供了相對簡單易懂的遊戲機制。 首先，遊戲中總共只有六種主要武器，雖然在商城會販賣不同的skin，但不同的skin並不影響武器的強度。這六種分別為AK、散彈、SMG、連狙、RPG、單狙。 同時每位玩家會持有一把小槍作為輔助武器。 子彈會在地圖中隨機生成，同時手榴彈也是要在地上撿，最大上限是持有三顆手榴彈。重生時會將玩家的子彈補滿、手榴彈數量為max(now_num, 1)。 每位玩家都是一顆蛋，而且蛋的尺寸還挺大的。 SS是一種運動系FPS。主要原因有：移動速度快、受到傷害後會自動回血、每發子彈傷害並不高（depend on 槍種）……等等。 反正玩過就知道了>_<。 如何成為不錯的玩家（大部分針對crackshot） SS作為線上FPS遊戲，遊戲機制十分寬鬆，但說難聽一點，就是高手與新手全部攪在一起的大雜燴，所以常常會在某場中遇到數十殺以上的強者，每次與其對槍都輸，因而造成自己遊戲體驗不佳；又或者每次streak都無法超過3，這種情況著實令人沮喪。 那要怎麼才能成為強一點的玩家呢？ 由於本人專精於單狙，所以只對單狙加以說明，但部分道理其實是通用的。 其實要脫離一般人的程度其實很簡單，只要掌握「跑跑跳跳 -> 停下來射擊　-> 跑跑跳跳」這樣的循環就可以了。 相較於一般FPS，SS的子彈速度簡直就像是高鐵對上腳踏車一樣，非常慢，況且如果擦邊的話傷害也不高，另外還會自動回血，那麼很重要的一個要點就是，一直跑跑跳跳。 絕對不要停下來，停下來超過三秒的話早就被狙掉了。 在SS中，一個好的狙擊手從發現敵人到消滅對方根本花不到一秒。 其他近戰武器如果距離適當的話也不需要一秒。 換言之，站在原地超過一秒就NG了。 所以切記，一直跑跑跳跳，把WASD通通用上，最好是能用不規則的步伐移動，並且有事沒事就跳一下，這樣敵人也難以瞄準，何樂而不為呢？ 同理，如果為了瞄準一個敵人而停在原地也是不值得的事情，停下來，將準心瞄準敵人，等準心縮小，射擊，別管到底能不能射中，這種事情丟給上天決定就好了，絕對不要為了多調整一點點而多待任何一瞬間，射擊完後立刻跑，因為槍聲會使敵人注意到你。 只要記住以上要訣並且切實實踐的話，你就會發現自己的KDR漸漸上升了；可能會覺得槍
閱讀完整內容

[TIOJ] 1007燈泡問題

-
題目連結： http://tioj.ck.tp.edu.tw/problems/1007 我不會DP QAQ 　　這題我很久以前就寫過了，因為想起來OTOTOT說過的必須要複習學過的東西，所以最近想要將TIOJ裡的我寫過的題目都再刷過一次。 　　　由第 i 個燈泡開始亮0~n個後再接一個暗的，容易可以推出DP式：dp[ i ] = dp[ i-1 ]+dp[ i-2 ]+...+dp[ i-n-1 ] ，複雜度是O(NM)，雖然夠了但其實可以化簡，可以發現dp[ i ]-dp[ i-1 ]=dp[ i-1 ]-dp[ i-n-2 ]，也就是說dp[ i ] = 2*dp[ i-1 ]-dp[ i-n-2 ]，複雜度降到了O(M)。 　　不過在i <n+2時要注意（我數學不好@@，這裡一直搞混），i<=n時可以隨意開關所以是2^n，而 i=n+1 時根據原本的DP式可以知道式所有前面的項相加其實也就是2*(n+1)-1，而後面的直接DP即可 #include<bits/stdc++.h> # define int long long using namespace std ; int n,m; int dp[ 100 ]; main () { cin >> n >> m; dp[0] = 1; for(int i = 1; i <= n; i++) dp[i] = dp[i-1]<<1; dp[n+1] = (dp[n]<<1)-1; for(int i = n+2; i <= m; i++) dp[i] = (dp[i-1]<<1)-dp[i-n-2]; cout << dp[m] << endl; }
閱讀完整內容