[CF] D - Bookshelves

-
題目：https://codeforces.com/contest/981/problem/D

MySol：https://codeforces.com/contest/981/submission/51882872

我是智障

OK，這樣上面那句就可以在還沒點進去就看到了

這題有個大性質，那就是AND，這可跟甚麼XOR、OR不同，可是AND喔><

雖然有點違和感，但我一開始就當作一般的東東隨便去DP看看，結果卻連範測都過不了

問題在哪呢？

亂做的話它的子問題不能推到大問題，當然，如果你已經AC的話就另當別論了

那要怎樣才能有子問題的最優甚麼的性質呢？你應該要想到AND，像我就沒想到就去看解了

如果你有一塊的加起來的長相是mask，那你最終答案肯定小於mask

如果你有一次得到的結果是(1 << 60)，你就算是(1 << 59) - 1這麼多的1你也不care。

所以就會想到要從高位開始往下做DP

應該說看到是位元運算的題目就要想到對位元做事了，但我腦袋只閃過了一下下，就拋之腦後了QQ

留言

張貼留言

這個網誌中的熱門文章

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; }
閱讀完整內容