[CF] Clique Problem

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

MySol：https://codeforces.com/contest/527/submission/51564334

我根本是個智障

看到題目後第一個想法是找一些規律，然後我還真的找到了

如果(i, j)滿足且(j, k)滿足並且 i < j < k，那麼(i, k)也滿足條件，這件事情是顯然

所以我就開始朝這邊開始想，我要怎麼快速找到一個連續序列，使的這序列相鄰兩兩都滿足呢？

我就開始亂想一通

假設xi < xj，把那個不等式拆開，變成：xj - xi >= wi + wj，移項得到：xj - wj >= xi + wi，所以 i 這個點往後連到的點 j 可以用一些資料結構亂維護，所以我就可以好好dfs了

歡樂大結局...才怪，邊數多到銀河的星星數不完，可悲

最後看解之後才發現我根本是個智障

觀察一下那個不等式，根本就是兩個點之間距離不能超過兩個點所具有的某個長度嘛
這不就是最多有多少區間互相之間無overlap啊@@

可悲，經典greedy題可是根本看不出來，人生失敗

留言

張貼留言

這個網誌中的熱門文章

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