Problem - F - Codeforces 題意： 給 N, K，代表有多少學生，以及花費總和上限。接著給學生們的實力 A。現在把學生分組，一組的花費是最大實力和最小實力的差。求花費不超過 K，將所有學生分組的方案數，求其餘數。 解法： 先將學生按實力排序後，定義動態規…

Problem - B - Codeforces 題意： 給一個序列 A，要你求一個相同長度的 B 序列，使 B 序列中任意兩個數字皆互質，此前提下 SIGMA{ abs( A[ i ] - B[ i ] ) } 最小。輸出 B 的長相。 解法： A 最大只會有 30，可以證明 B 只需考慮 [ 1, 60 ] 內的數。因為如果…

Problem - 479E - Codeforces 題意： 給 N, A, B, K，代表有幾層樓，初始在哪層，哪層是禁止樓層，要轉移多少次。由 x 轉移到 y 是合法的若且唯若 | x - y | 解法： dp[ i ][ j ] : 已轉移 i 次，最後一次在第 j 層樓時的方案數。 如果樸素轉移，會變成 O( N…

Problem - D - Codeforces 題意： 公主和龍玩一個遊戲，背包裡初始有若干個白老鼠和若干個黑老鼠。公主先開始，輪流取一個老鼠出來，先取出白老鼠的贏。取出後不放回，但龍取老鼠之後，會有一隻還在背包裡的老鼠，平等隨機地逃走消失不再回來。當背包裡沒有…

Problem - 540D - Codeforces 題意： 在一座島上有三種人，只出剪刀，只出石頭，只出布的人。每一秒都有一對人會相見。每對人相見的機率都相同，如果相見的是同一種人，則什麼都不會發生，否則他們會決鬥，就跟一般猜拳規則一樣定勝負，輸的人會死掉。給三種…

Problem - 294B - Codeforces 題意： 給一堆相同高度的書，用厚度和寬度描述。放書的方法是相放一層豎的，再將剩下的橫放在那層上。橫放的那層寬度總和不得超過下面豎著放的那層厚度總和。求最小厚度總和。 解法： 由於書的厚度只有兩種，因此可以分開枚舉兩…

Problem - 455B - Codeforces 題意： 玩連續 K 輪遊戲。每輪遊戲規則都一樣，初始時為空字串，輪流向字串結尾添加一個新的字元，操作後必須是字典中某個字的前綴。若無法進行合法的操作，則判為失敗。敗者為下一輪遊戲的先手。兩人採取最優策略爭奪第 K 輪的…

Problem - 557C - Codeforces 題意： 一個桌子有若干個腳，每個腳用其高度和拔掉該腳所需花費描述。求最小總花費，使得最常的腳是絕對多數( 過所有腳數量一半 )。 解法： 利用各種預處理。枚舉最大長度後，透過各種前綴和快速得到更大長度的花費總和，接著枚…

Problem - 340D - Codeforces 題意： 給一個元素相異序列用以描述一個圖，所有逆序數對之間存在一條無向邊。求最大獨立集合( 集合中所有點接無邊連接 )的數量。 解法： 只要沒有逆序數對，就不會有邊。沒有逆序數對意味著是遞增序列。因此問題轉換成求 LIS。…