Problem - C - Codeforces題意： 給一個長度為 N 的數列，要做 K 次操作。每次將數列排序後，奇數項 ( 1 based ) 和 X 做 xor，偶數項不變。問所有操作結束後，數列的長相。資料規模： First line consists of three integers n, k, x (1 ≤ n ≤ 1e5, 0 ≤ k ≤…

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

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

http://main.edu.pl/en/archive/oi/2/mud題意： 首都在 ( 0, 0 ) 的位置，有 M 個人在首都裡。接著有 L 條線，每條線有若干個城市，依序用線上和前一個 ( 第一個城市和首都 ) 的距離以及人數描述。要求選一個點使得所有人到該點的總花費最小，一個人行走一單…

http://main.edu.pl/en/archive/oi/2/kpk題意： 給一張圖，有若干障礙物，給始點和終點，問是否可以不左轉不倒回從始點走到終點，可以的話輸出最短路徑的方案。資料規模： In the first line of the standard input there are two integers separated by a s…

http://main.edu.pl/en/archive/oi/2/pal題意： 給一個字串，問最多和最少可以拆分成幾個偶數長度迴文，存在的話輸出方案。資料規模： The standard input contains one word consisting of at least 1 and at most 200 small letters of English alphabet. …

UVa Online Judge題意： 給一個 R * C 的圖，保證周圍都是牆( # )，也不能拜訪 ( X )，起點在 ( S )，問在拜訪最多 ( * ) 的前提下，最短迴路的最小字典序序列序列是什麼。資料規模： The input file contains no more than 20 test cases. The details of e…

Problem - 19B - Codeforces題意： 有 N 種商品各一個，若購買第 i 種商品，需要花費 C[ i ] 單位的錢，但是可以得到 T[ i ] 單位的店員不注意的時間，而店員不注意的時間每單位可以供你偷一件尚未購買的商品。問你最少要付多少錢才能獲得所有商品。資料規模…

Problem - C - Codeforces題意： 給一個長度為 N 的大寫英文字母組成的字串，一次操作可以將任一兩相鄰字符交換，問最少要多少次交換才能使得 "VK" 不以子字串形式出現。資料規模： The first line of the input contains an integer n (1 ≤ n ≤ 75) — the l…

Problem - 13C - Codeforces完全就是同一個題 只是這題要滾動才不會 MLE，然後詢問的是非遞減，所以不需要用到減下標的技巧。題意： 給一個陣列 A，可以任意讓值 +1 或 -1 任意多次，問最少要幾次才能將 A 變成非遞減數列。資料規模： MAXA ≤ 1e9 N ≤ 5000 T…

Problem - 11D - Codeforces題意： 給一個無向圖。問有多少個簡單環 ( 無重複經過的點的環 )。資料規模： N ≤ 19 TL: 2000 ms解法： 考慮一個環，選定一個點 ( 這裡用編號最小的點 ) 切開之後變成一條鍊，假設原本是 abcd 這樣的環，那其實可以用點的集合和…

Problem - 8C - Codeforces題意： 給原點 ( sx, sy )，以及 N 個座標 X, Y。每次至多選兩個座標，依序拜訪完後，回到原點。問最好的路徑，使得路徑長最小。兩個座標的路徑長為歐幾里德距離的平方。資料規模： The first line of the input file contains the…

http://ioinformatics.org/locations/ioi16/contest/day2/paint/paint-TWN.pdf 1959 - [IOI 2016] Paint | TIOJ INFOR Online Judge題意： 給一個序列含 '.', 'X', '_'，分別代表該位置的字符為未知、必為黑色、必為白色。再給 K 個數字 C[]，代表由左到右看…

Problem - E - Codeforces題意： 給一個矩陣，表示每對人之間的憎恨值。現在要把人划分為 K 群，每群必須都是連續編號的人。一個群的憎恨值貢獻是所有編號的有序對的憎恨值總和。求最少憎恨值總和。資料規模： The first line contains two integers n and k…

Problem - E - Codeforces題意： 有 N 個價值的物品，每個都有無限多個。輸出拿恰好 K 個物品可以產生出的所有值。資料規模： The first line contains two integers n and k (1 ≤ n, k ≤ 1000) — the number of kinds of products and the number of produc…

No.243 出席番号(2) - yukicoder題意： 有 N 位可分別的學生，現在你要分配 0 ~ N - 1 的座位給他們。每個學生都有一個不喜歡的座位編號。求每個人都不作到不喜歡的座位編號的方案數，對 1e9 + 7 取模。資料規模： 生徒の数Nが最初の行で与えられる。1≤N≤500…

Problem - D - Codeforces題意： 問 N 個節點組成的二叉樹，深度不少於 H 的方案有幾種。資料規模： H ≤ N ≤ 35解法： dp[ i ][ j ] : N 個節點的二叉樹，深度等於 H 的方案數 兩種轉移，首先當前的根是一定要的，一種是左空或又空，另一種是兩個都非空。時…

Problem - 314C - Codeforces題意： 給一個 N 個數組成的數列 A。現在有人把 A 的所有相異的非遞減子序列都生出來了。輸出，對這些子序列分別求，不比該子序列的字典序大的所有子序列的方案數，的總和，對 1e9 + 7 取模。資料規模： The first line contains…

Problem - D - Codeforces題意： 給一個 N 個正整數組成的 A 數列。可以選一個連續區間，並決定每個數值分別的正負號，但其總和必須為 0 才合法。問有幾種合法的選取方式，選取方式相異若左界或右界不同，或任意一個元素分配到的正負號不同。輸出方案數對 1e…

Problem - 404D - Codeforces題意： 給一個字符串，裡面只有 0, 1, 2, *, ? 五種符號。如果是數字，表示左右的 * 個數加起來一定有那麼多。如果是 ? 代表未確定。求有幾種 ? 的代入方式使得序列合法，對 1e9 + 7 取模。資料規模： The first line contains s…

Problem - 431D - Codeforces題意： 給 M, K。求一個 N，滿足 1 ≤ N ≤ 1e18 且在二進制下，[ N + 1, 2 * N ] 中恰有 M 個數恰有 K 個 1。資料規模： The first line contains two space-separated integers, m and k (0 ≤ m ≤ 1e18; 1 ≤ k ≤ 64).解法： 直覺…

Problem - 156C - Codeforces題意： T 筆測資。每次給一個字串。有一種操作可以進行：選取兩個不同位置的字符，一個變成字典序小一的字符，另一個變成字典序大一的字符。特別的，a 沒有字典序小一的字符，z 沒有字典序大一的字符，而沒有相應的字符就不能進…

Problem - 768E - Codeforces題意： N 堆石頭，輪流取，不能取的輸。對於某一堆石頭，不能拿走同個數量的石頭兩次。求後手勝敗。資料規模： First line consists of a single integer n (1 ≤ n ≤ 1e6) — the number of piles. Each of next n lines contains…

Problem - D - Codeforces題意： 求長度為 N 且沒有領導 0 的正整數中，有多少數字存在一個非 0 的後綴 y，使得 k 整除 y。輸出方案術對 m 取模。資料規模： Input consists of three integers n, k, m (1 ≤ n ≤ 1000, 1 ≤ k ≤ 100, 1 ≤ m ≤ 1e9).解法： dp[…

3866 -- Exclusive Access 2題意： 給一個 N 個無向邊的圖。求一種方案使所有邊定向，並有最短的最長路徑 ( 即不存在環 )。無法到達的點對之間的路徑長不須考慮。資料規模： N ≤ 100 節點為 [ L, Z ] 間的大寫英文字母，數量不超過 15。 TL: 5000 ms ML: 655…

2127 -- Greatest Common Increasing Subsequence題意： 給兩個數列 A, B，長度分別為 N, M，求最長公共遞增子序列。資料規模： 元素大小在 int32 範圍 N, M ≤ 500 TL: 2000 ms解法： 顯然可以定義 O( N^3 ) 的 dp，但這裡考慮 O( N^2 )。 dp[ i ][ j ] : B[…

Problem Description: There is a tower with N floors, each floor having M rooms in order. One receives score S[ i ][ j ] when being at the j'th room of the i'th floor. You start at the X'th room at the first floor. Your objective is to trav…