Problem - D - Codeforces題意： f( s ) = k, if f( s[ 0, s.len / 2 ) ) = f( s[ ( len + 1 ) / 2, s.len ) ) = k - 1, _______= 0, otherwise 給字串 seq，求 Sigma{ f( s ), for all s is prefix substring of seq }資料規模： 字串長度 ≤ 5e6 TL: 500 ms…

Problem - D - Codeforces題意： 給一個 01 字串，字符間或者左界右界放隔板。求至少放兩個隔板時，以二進位讀進所有被夾在隔板間的數字，令該數字集合中最大數為 x，則集合中所有數為正整數且含 [ 1, x ] 間所有數的方案數，對 1e9 + 7 取模。資料規模： 字…

Problem - C - Codeforces題意： 有 N 個道館，裡面都有若干隻怪獸。怪獸用一個整數描述，表示品種。現在要定義一個一對一 ( 雙向 ) 函數，把 { 1, 2, .. M } 映射到任意一個 [ 1, M ] 的排列。求有多少種這樣的一對一函數，滿足分別將每個道館的怪獸經過函…

Problem - B - Codeforces題意： 求最大團大小，滿足團裡所有 S[ i ] 的最大公因數不為 1。資料規模： 1 ≤ N ≤ 1e5 1 ≤ S[ i ] ≤ 1e5 TL: 2000 ms ML: 512 MB解法： 如果某個最大公因數 x 的倍數數量是最大可能的，那麼顯然對 x 的所有非 1 因數，倍數數量也…

Problem - C - Codeforces題意： 給你一個數列，有 N 個元素，再給你一個整數 K。你可以分別將數列中每個元素 a[ i ] 變為 [ max( 1, a[ i ] - K ), a[ i ] ] 中任意一個整數。求變換過的數列的最大可能最大公因數。資料規模： 1 ≤ n ≤ 3e5 1 ≤ k ≤ 1e6 1 ≤ …

http://codeforces.com/gym/101212/attachments/download/5014/bangladesh-informatics-olympiad-2016-en.pdf Dashboard - Bangladesh Informatics Olympiad 2016 - Codeforces題意： 給你 L, A，代表字串的大小，以及可能字符集合大小。 接著給字串，以數字…

http://codeforces.com/gym/101212/attachments/download/5014/bangladesh-informatics-olympiad-2016-en.pdf Dashboard - Bangladesh Informatics Olympiad 2016 - Codeforces題意： 有 N 個房子，一開始裡面都有一個小屁孩，用屁孩值描述。每個房子的出度…

http://codeforces.com/gym/101212/attachments/download/5014/bangladesh-informatics-olympiad-2016-en.pdf Dashboard - Bangladesh Informatics Olympiad 2016 - Codeforces題意： 有 N 個怪獸，用 ( X[ i ], V[ i ] )，一維座標及強度描述。有一種操作，…

http://codeforces.com/gym/101212/attachments/download/5014/bangladesh-informatics-olympiad-2016-en.pdf Dashboard - Bangladesh Informatics Olympiad 2016 - Codeforces題意： 求有多少 [ 1, N ] 的排列，有至少 K 個逆序數對。資料規模： For easy v…

http://codeforces.com/gym/101212/attachments/download/5014/bangladesh-informatics-olympiad-2016-en.pdf Dashboard - Bangladesh Informatics Olympiad 2016 - Codeforces題意： 給 N, K，求 N! 整除 K ^ x 的最大 x 是多少。資料規模： For easy versi…

http://codeforces.com/gym/101212/attachments/download/5014/bangladesh-informatics-olympiad-2016-en.pdf Dashboard - Bangladesh Informatics Olympiad 2016 - Codeforces題意： 實現一個雙向佇列，可以回答以下三種詢問： 1. ‘1 x y’ ID 為 y 的人從前…

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 ]…