Problem - 645D - Codeforces題意： 有 N 個機器人打鬥，機器人之間勝負是依戰鬥力的大小關係定的，而所有機器人的戰鬥力相異。依順序給機器人編號 u[ i ], v[ i ]，表示編號 u[ i ] 的機器人戰鬥力比 v[ i ] 的機器人高。求第幾個資訊開始能確定所有機器人…

Problem - 14D - Codeforces題意： 給一棵樹，求兩個不相交的路徑，長度乘積最長可以是多少。資料規模： 節點數： 2 ≤ N ≤ 200 時間限制：1000 ms 空間限制：64 MB解法： 因為樹原本是連通的，而不能相交其實就是有一條路徑可以把他們連起來卻不准連起來，所…

Problem - 615C - Codeforces題意： 給 A 字串和 B 字串，可以將 A 字串中的子字串剪下來，選擇要不要翻轉後，接到當前的字串後面。問最少操作數能否接成 B，要輸出方案。解法： 首先顯然從左到右掃過 B 字串，每次貪心選取最長且合法的子字串接上。 考慮最…

Problem - 245H - Codeforces題意： 給一個字串。接著 Q 筆詢問給左界右界，求對應的子字串中有多少回文子字串。資料規模： 字串長度 1 ≤ | S | ≤ 5000 1 ≤ Q ≤ 1e6 時間限制：2500 ms 空間限制：256 MB解法： 先用 O( N ^ 2 ) 預處理 is_pal[ l ][ r ]，表…

Problem - B - Codeforces題意： 有一棵樹，每個節點都有一個值。每次操作可以選一個含節點 1 的樹 ( 邊和節點連通的集合 )，將所有值加一或減一。求至少要多少次操作才能將所有值歸零。資料規模： 節點數： 1 ≤ N ≤ 1e5 值域：abs( V[ i ] ) ≤ 1e9 時間限制…

Problem - 432D - Codeforces題意： 給一個字串，分別對所有前綴和後綴相等的子字串算出該子字串出現幾次，並按長度由小至大輸出。資料規模： 1 ≤ |S| ≤ 1e5解法： 無法 hash，因為這種題目需要利用前綴後綴那種字串本身的特性。所以來用 Z 算法吧！ 先知道 …

Problem - D - Codeforces題意： 放煙火，煙火有 N 個階段，在第 i 個階段會往前噴 T[ i ] 個單位長度後，向 +45度 和 -45度分岔繼續噴，並同時變成下個階段。求噴完會經過多少格子。資料規模： 1 ≤ N ≤ 30 1 ≤ T[ i ] ≤ 5 時間限制：2500 ms 空間限制：256 …

http://codeforces.com/contest/7/problem/C題意： 給一個方程式 Ax + By + C = 0，找一組整數 ( x, y ) 在該直線上。或者判斷不存在。解法： 先用 ext_gcd 判斷 Ax + By = gcd( A, B ) 時的 x, y 分別是多少。 ext_gcd 要背！不懂還是要硬背！( 我總是想不…

Problem - B - Codeforces題意： 有 N 張照片，成環形，第一張的左邊是第 N 張。一開始在第一張照片，如果照片是 'w' 就必須花 B 秒將它變成 'h' 才能觀賞，觀賞要 1 秒，向左或向右滑都要 A 秒。但如果當前的照片還沒有觀賞過，不能滑動。求最佳方案下 T 秒…

Problem - D - Codeforces題意： 給一個序列，有 '(', ')', '?' 三種符號，每個 '?' 有相應的代價可以轉換成左括弧或右括弧，求最小總代價，使得變成合法的括弧序列，或者判斷不存在合法的方案。資料規模： 序列長度 1 ≤ N ≤ 5e4 轉換代價 1 ≤ A[ i ], B[ i …

Problem - E - Codeforces題意： Q 筆詢問： 有 N 顆糖果要分給 F 個人，每個人至少拿到一顆，但希望每個人的糖果個數的最大公因數為 1。求方法數模上 1e9 + 7。資料規模： 1 ≤ Q ≤ 1e5 1 ≤ F ≤ N ≤ 1e5 時間限制： 5000 ms 空間限制： 256 MB解法： 考慮 N …

Problem - D - Codeforces題意： 給兩個陣列，每次操作可以選一個陣列中的一個數字對其加一或減一。求至少要多少次操作，才能使得第一個陣列中最小的數字不小於第二個陣列中最大的數字。資料規模： 數列大小： 1 ≤ N, M ≤ 1e5 數字大小： 1 ≤ A[ i ], B[ i ]…