[Codeforces] 1065 Three pieces

-
LINK：http://codeforces.com/contest/1065/problem/D

SOL：http://codeforces.com/contest/1065/submission/44892468

FST掉的一題。
我原本的寫法是DP，然後每次轉移的時候都BFS一次，然後寫到快瘋掉，賽中就鏘了一百多行，然後就FST了QAQ

之後好長一段時間因為這題感覺很麻煩所以就一直放著，直到後來看了別人的code後才發現原來只是我的寫法很複雜而已@@

事實上，可以將座標(x, y)、棋子編號為0, 1, 2，將所有狀態寫成( ( x*n + y )*3 + 棋子編號 )，然後就可以建出一張圖，處理只換一次棋子、只走一步的所有可能後，再用floyd warshall做全點對最短距離，接著再好好DP就OK了。

話說floyd warshall那裏應該可以更好的，因為我其實只要求從第 i 格走到第 i+1 格的不同棋子間的最短路徑就好了，所以其實是可以用dijkstra，又或者雖然沒研究過，不過好像可以用0-1DFS？

至今仍然不確定為何會FST QAQ

留言

張貼留言

這個網誌中的熱門文章

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