這裡留一些比較偏經典的題單，主要是還不會寫的東西，之後一併解決：Flow: D: 浮気予防 - AtCoder Beginner Contest 010 | AtCoderMath: D: LCM Rush - AtCoder Beginner Contest 020 | AtCoder D: 多重ループ - AtCoder Beginner Contest 021 | AtCoder

Problem - D - Codeforces題意： 你有 N 個牛奶，第 i 瓶會在 A[ i ] 天後壞掉。商店有 M 個牛奶，第 i 瓶會在 B[ i ] 天後壞掉。你一天喝至多 K 瓶牛奶，問最多可以買多少牛奶，使得你不必喝任何壞掉的牛奶。資料規模： N, M ≤ 1e6 過期天數 ≤ 1e7 TL: 2000…

Problem - C - Codeforces題意： 給一棵節點帶權的樹。問是否存在一種分割方法，使得可以分成三個非空子樹，使得權重總和相同。輸出方案。資料規模： The first line contains single integer n (3 ≤ n ≤ 1e6) — the number of lamps in the garland. Then n…

Problem - C - Codeforces題意： 你的目標濃度是 N / 1000。你有 K 種液體，濃度分別為 a[ i ] / 1000。每一種液體可以用任意非負整數單位容量，求最小正整數，代表使用的總容量成功調配出目標濃度。資料規模： The first line contains two integers n, k (…

Problem - B - Codeforces題意： 給一個 N 點 M 邊的無向圖，問有幾種方法，可以經過 M - 2 個邊洽兩次，剩下 2 個邊洽一次。沒有重邊，但可能有自環。兩個方法不同，若且唯若拜訪洽一次的任意一邊不同。資料規模： The first line contains two integers n,…

Problem - A - Codeforces題意： 給一個長度為 N 的數列 A[]。求最大的 f( l, r )，滿足 1 ≤ l 資料規模： The first line contains single integer n (2 ≤ n ≤ 1e5) — the size of the array a. The second line contains n integers a1, a2, ..., an (-1e9…

Problem - E - Codeforces題意： 給 N 種球的個數 A[]。要求按照下列規則將其分箱： 1. 同一個箱子不能存在兩種球 2. 最多球的箱子的球數和最少球的箱子的球數之差不得超過 1 3. 所有球都必須存在於一個箱子裡 4. 不得有空箱 問最佳的分箱方式下，可以用最少…

Problem - D - Codeforces題意： 給一個完滿二元樹，用最大編號描述。二元樹上的編號是遞迴配置的，如圖： 給 Q 筆詢問，每筆詢問給起點編號，以及操作字串，字串由 { 'U', 'L', 'R' } 組成，對於不可執行的操作無視之。問終點編號為何。資料規模： The firs…

Problem - C - Codeforces題意： 給一個大數。問最少要刪除幾個數字才能使得剩下的數字為 3 的倍數。刪除後不得有前導 0。輸出方案。資料規模： 長度 ≤ 1e5解法： 刪除最少等價於保留最多。 dp[ i ][ j ] : 已考慮前 i 個數字，現在除以 3 餘 j，此時最大保…

Problem - C - Codeforces題意： 給 'a' ~ 'a' + N - 1 各個字母的出現頻度。要求構造一個環狀的字串，使得最多處切下去會是迴文。資料規模： N ≤ 26 出現頻度總數不超過 1e5解法： 因為至少要有一個迴文就必須有不超過一個奇數的頻度，所以接下來可以分開討…

Problem - B - Codeforces題意： 有 N 個技能，所有技能都用一個數值描述，上限皆為 A，你有 M 單位的金子，一個單位的金子可以提升一個技能的數值一個單位。你要最大化：數值為 A 的技能數量 * Cf + 最低的技能數值 * Cm。求最大化的值以及方案。資料規模：…

Problem - A - Codeforces題意： 給一個代表自轉中心的座標，以及順時針給的座標描述一個凸多邊形。問旋轉 360 度後，被覆蓋過的面積有多少。資料規模： N ≤ 1e5解法： 顯然要找離圓心的最遠點，以及最近點... 但仔細想想會發現不是最近點，其實是和任意線段…

Problem - C - Codeforces題意： 給一個圖，要求放 K 個機器人並給出每個機器人的路徑，路徑長至多為 ceil( 2 * N / K )，使得所有節點都被至少一個機器人拜訪過。資料規模： N, M ≤ 2e5解法： 首先把圖轉換成任意一個生成樹。接著進行類似時間戳記的 DFS，…

Problem - B - Codeforces題意： 給 N 個姓名，現在要為每個姓名做縮寫，但希望滿足以下規則： 1. 姓名是 A 的前三個字元，或 A 的前兩個字元接上 B 的第一個字元。 2. 任何縮寫不重複 3. 若對於第 i 個人採取第一種縮寫和第 j 個人採取第一種縮寫會是一樣的…

Problem - A - Codeforces題意： 給一棵 N 個節點的樹，要求給每個節點著色，滿足所有長度為 2 的路徑裡的三個節點都異色。問最少顏色數量。資料規模： N ≤ 2e5解法： 隨便找一個節點當作根，轉為有根樹上的問題。遞迴拜訪一個節點之前先為該節點著色。在當…

Problem - C - Codeforces題意： 給一個長度為 N 的陣列，用顏色描述。要求對於所有 K 資料規模： N ≤ 1e5解法： 據說這可以用資料結構 ( 樹狀數組 ) 直接做掉，但我看不懂。 首先答案一定是非嚴格遞減的。 這題的重點在於看透一個結論：「答案的種類大約在 …

Problem - B - Codeforces題意： 給一張圖，N 個點，Q 個邊，起點 S。 邊有三種，各自用 u, v / L, R, w 描述： 1. u -> v : 代價 w 2. u -> [ L, R ] : 代價 w 3. [ L, R ] -> u : 代價 w 問所有終點的單源最短路徑，不存在則輸出 -1。資料規模： N, Q ≤ 1e…

Problem - A - Codeforces題意： 有 n 個星球，從 0 開始編號，順時針排成一圈。0 號星球是黑洞。兩人有各自的操作集合，遊戲採取輪流操作，每次操作時選擇自己的集合裡的一個數字，將怪獸順時針推移該數字那麼遠。第一位把怪獸推移至 0 號星球的人獲得勝利…

1952 - 小向的試煉 3-3：鑰匙(Key) | TIOJ INFOR Online Judge題意： 給一個長度為 N 的字串，接著 M 筆詢問。詢問 L, R, K 代表 [ L, R ] 的字母要按照字典序大到小( K = 0 ) 或小到大( K = 1 )排序。求所有操作後的字串長相。資料規模： 第一行有兩個正整…

PEG Judge - IOI '12 - Crayfish Scrivener題意： 要求支持三種詢問至多 1e6 筆： T L: 在當前字串尾添上字符 L U a: 取消前 a 個操作 P x: 輸出當前第 x 位的字符解法： Rope 水過，詳見代碼。 時間 / 空間複雜度： 有人說內部是持久化平衡樹，有人說是分塊…

http://main.edu.pl/en/archive/oi/18/met題意： 有 M 個環狀的地，每個地屬於一個人。有 K 次隕石事件，每次會在某一連續區間 [ L[ i ], R[ i ] ] 每個地分別降下有 W[ i ] 單位的隕石。有 N 個人，每個人有最少需要收集的隕石量 P[ i ]。要求分別輸出每個…

1343 - [IOI 2007, Day 1] Sails | TIOJ INFOR Online Judge題意： 有 N 個桿子，第 i 個桿子的高度為 H[ i ]，待放的旗子數量為 K[ i ]。 對於一個高度，若有 x 個旗子，那麼該高度的貢獻為 x * ( x - 1 ) / 2。 求最小總貢獻。資料規模： 輸入的第一行有一…

Problem - 1542題意： 給很多矩形的左下角和右上角座標，問聯集面積為何。資料規模： 座標為有理數 N ≤ 100解法： 離散化座標後，由下到上推移掃描線。時間 / 空間複雜度： O( N lg^2 N ) / O( N lg N ) #include <bits/stdc++.h> using namespace std; const int MAXN = 10</bits/stdc++.h>…

PEG Judge - IOI '98 - Picture題意： 給很多矩形的左下角和右上角座標，問總周長為何。被包含的線段不算在周長裡。資料規模： The first line of the input contains the number of rectangles (0 ≤ number of rectangles 解法： 掃描線，考慮對 X, Y 方向…

http://main.edu.pl/en/archive/oi/21/kur題意： 給一個長度 N 的數列，接著 M 筆詢問 [ L, R ] 中是否有個數字是絕對多數，有的話輸出該數字。資料規模： N, M ≤ 5e5 1 ≤ P ≤ N TL: 12000 ms ML: 128 MB解法： 一個持久化裸題，但記憶體卡得比較緊，要用離…

http://main.edu.pl/en/archive/oi/2/sze題意： 有 N 個工作，假設當前時間已經過 T 單位，那麼工作 i 需要花費的時間為 A[ i ] * T + B[ i ]。一次只能做一個工作，問最短時間完成的工作序列。資料規模： In the first line of the standard input there is…

http://main.edu.pl/en/archive/oi/2/obc題意： 給一棵樹，求一個序列，可以不重複拜訪所有節點，而且相鄰節點距離不超過 3。資料規模： In the first line of the standard input there is a positive integer n, not greater than 5000 - it is the number…

http://main.edu.pl/en/archive/oi/2/kod題意： 給一個序列 B，問是否有一個 [ 1, | B | ] 的排列 A，使得 B[ i ] 等於 A[ 0, i ) 中比 A[ i ] 大的數字的數量。輸出方案。資料規模： In the first line of the standard input there is a positive integer …

http://main.edu.pl/en/archive/oi/2/sza題意： 給一個 N * N 的棋盤，X, Y, Z 三塊為不用覆蓋的，求是否可以用 2 * 1 ( 可旋轉 ) 的東西覆蓋滿棋盤，可以的話輸出方案。資料規模： In the only line of the standard input there are written four numbers …

http://main.edu.pl/en/archive/oi/2/tro題意： 給很多邊的長度，問是否可以構成三角形，可以的話輸出方案。資料規模： In the standard input there is a finite sequence of at least three positive integers not greater then 1e9, terminated by the nu…