Problem Description: You have a book with N pages in total. Page i requires cost A[ i ] to be printed. You have a weird printer, the cost of printing a continuous segment [ L, R ) is ( Sigma{ A[ i ], L ≤ i Constraints: 1≤T≤100 1≤N≤1e5 1≤K≤…

Problem Description: Currently you have n minions in a row on the war field, where each minion at the i'th position shows an attack value of a[ i ]. You have another m aces yet to be summoned. You can set aces at both ends or between any t…

Problem Description: There are N shops that sell potions, and each of them only sells one kind of potion. The i'th shop sells potions for P[ i ] per glass, where each glass could heal B[ i ] units of health, but has only C[ i ] glasses in …

Problem Description: You are given an array A consisting of N elements. You know that they are K different people's orders, where some consecutive elements are what they have ordered. You also know that every order was ordered by some one,…

1180 -- Batch Scheduling題意： 有 N 個工作，用 T[ i ], F[ i ] 描述第 i 個工作需要花費的時間，以及單位時間的價值。第 i + 1 個工作不能在第 i 個工作完成之前被完成。每次可以選擇 k 個，未完成的工作中編號最小的工作，花費其 T 的總和，令之 P，的時…

Problem - D - Codeforces題意： 有一個 3 * N 的矩陣，每個格子裡面有一個整數值。由左上角走到右下角，兩個格子可以互通若且唯若有公共邊，求路徑沒有重複格子的前提下，經過的格子值最大總和。資料規模： 1 ≤ N ≤ 1e5 TL: 2000 ms ML: 256 MB解法： dp[ i…

Problem - B - Codeforces題意： 假設有個 OX 序列，每個連續段 'O' 長度若為 x，則該段貢獻為 x^2。已知序列長度，以及分別每個字符為 O 的機率，求期望貢獻和。資料規模： The first line contains an integer n (1 ≤ n ≤ 1e5) — the number of clicks. Th…

1908 - 大根蘿蔔 | TIOJ INFOR Online JudgeProblem Description: You are given a matrix of N * N, each cell with a positive value. You can take values away from each cell at most once, in any order, but after taking a value from a particular …

Problem - E - Codeforces題意： 有 N 通電話，用 T[ i ], D[ i ]，分別為來電時間和通電時間長度描述。保證來電時間嚴格遞增。當有個電話來電時，可以選擇是否無視，如果不無視，就要接起來，佔用 D[ i ] 單位的時間，除非目前是正在打電話的狀態，那麼將這…

Problem - B - Codeforces題意： 給一個數列，可以更改至多 K 個數，使成為任意數，求更改後最小的相鄰值絕對差。資料規模： The first line contains two integers n and k (1 ≤ k ≤ n ≤ 2000). The second line contains space-separated integers a1, a2,…

Problem - C - Codeforces題意： 給 N 個數字， B[ i ] 代表第 i 個數字各位數總和為 B[ i ]。求可能對應的數列的最後一個值的最小可能，且須滿足數列嚴格遞增。資料規模： The first line contains a single integer number n (1 ≤ n ≤ 300). Next n lines …

Problem - B - Codeforces題意： 給一棵以 1 為根的樹，以及點的權重。求一個集合，使得集合內每個點，以自身為子樹的根時，子樹內所有自身以外的點在集合中出現偶數次。問最大可能權重總和。資料規模： The first line contains integer n (1 ≤ n ≤ 2e5) — …

Problem - B - Codeforces題意： 給一個 0 / 1 矩陣，Q 筆詢問，求以 ( A, B ) 為左上角，( C, D ) 為右下角的矩陣中，有多少不同的矩形元素全為 0。資料規模： There are three integers in the first line: n, m and q (1 ≤ n, m ≤ 40, 1 ≤ q ≤ 3e5). Each…

Problem - C - Codeforces題意： 有 N 棵樹，用長度 A[ i ] 和魔力 B[ i ] 描述。保證 A 嚴格遞減，B 嚴格遞增，且 A[ 0 ] = 1, B[ N - 1 ] = 0。一次操作選擇一顆長度不為 0 的樹，使之長度少一。每操作完後，必須選擇一棵長度已為 0 的樹的魔力，加到總花…

Problem - 316B2 - Codeforces題意： 有 N 個人在排隊，不知道他們的順序，但知道某些人知道前面的人是誰，有些人不知道 ( 用 0 表示 )。求編號 X 的人有可能出現的所有位子。資料規模： The first line contains two integers n (1 ≤ n ≤ 1e3) and x (1 ≤ x…

Problem - E - Codeforces題意： 有 N 個雙向佇列，可以從左端或右端拿東西，東西用價值描述。求總共拿 M 個東西時，最大可能價值。資料規模： The first line of input data contains two integers n (1 ≤ n ≤ 100) and m (1 ≤ m ≤ 10000). The next n line…

Problem - C - Codeforces題意： 有 N 個球排一排，用價值 V[ i ] 和顏色 C[ i ] 描述。接著 Q 筆詢問，給你 A, B，要求一個序列的最大歡樂值。序列必須是升序的下標，歡樂值得計算方法為：若序列中某個下標 i 不為序列最小值，且前面一個下標 i - 1 的顏色 …

Problem - A - Codeforces WA 好多次... 題意： 有 N 個數字，給你兩兩之間的大小關係，左大，左小，或相等。求總和最小的合法數列長相。資料規模： The first line of input contains the number of students n (2 ≤ n ≤ 1000). The second line gives (n -…

Problem - C - Codeforces題意： 給一個操作序列，若字符為 'T' 則轉向，原地不動，若為 'F' 則向原方向前方走一格。求更改恰好 N 次字符後，最遠可以走多遠。一個字符可以修改多次。資料規模： The first line of input contains a string commands — the o…

Problem - C - Codeforces題意： 給一個只由 "DIMA" 中的字符組成的 N * M 的矩陣。有個人要重複以下過程： 1. 先選一個 'D' 的格子，在滿足條件而可以移動的前提下進行： 2. 移動到上下左右的其中一格 'I' 3. 移動到上下左右的其中一格 'M' 4. 移動到上下左…

Problem - 351B - Codeforces題意： 給你一個 1 ~ N 的排列。現在兩個人輪流操作，第一個人會選擇兩個數字，且一定選左數比右數大的兩個數字，並進行交換。第二個人會以 0.5 的機率選左數比右數大的兩個數字。求達到第一次排好期望需要幾次操作。資料規模： …

Problem - B - Codeforces題意： 玩遊戲王卡，對方有 N 張卡，成正面攻擊或守備狀態，如果是攻擊狀態，以攻擊力描述，守備狀態則以守備力描述。你有 M 張卡，全部都是攻擊狀態，用攻擊力描述，現在希望可以極大化對對手造成的生命值傷害總和。攻擊過的怪獸不…

Problem - B - Codeforces題意： 給兩個字串 S 和 T，求有多少種相異的 S 的不重疊子字串集合 ( 集合中任一個子字串有不同的左右界即屬於相異 )，滿足集合裡所有子字串含 T 為子字串，模上 1e9 + 7。資料規模： 1 ≤ |s|, |t| ≤ 1e5 TL: 2000 ms ML: 256 MB解…

Problem - D - Codeforces題意： 給你一個數 N，和 M。求 N 有幾種排列 N'，使得 N' 整除 M 且沒有領導零。資料規模： n (1 ≤ n TL: 4000 ms ML: 512 MB解法： 感覺就不太妙。考慮 dp，先有 M 這一維，然後 18 這數字感覺就很數位統計的 fu，在這裡又發現，…

Problem - D - Codeforces題意： 有一棵 n 個節點的樹，各自有一個值 a[ i ]。給你一個 d，求有多少邊和點構成的連通塊集合，滿足最大值和最小值的差不超過 d，模上 1e9 + 7。資料規模： 0 ≤ d ≤ 2000 1 ≤ n ≤ 2000 1 ≤ ai ≤ 2000 TL: 1000 ms ML: 256 MB解…

Problem - A - Codeforces題意： 給字串 S 和 T，要求有多少組 ( a, b, c, d )，使得 S[ a, b ) 和 T[ c, d ) 非空且 LCS 為 S[ a, b )。資料規模： 字串長度不超過 5000 TL: 1000 ms ML: 256 MB解法： dp[ i ][ j ]：滿足 LCS( S[ x, i ), T[ y, j ) ) == S…

Problem - B - Codeforces題意： 給一個 n 個整數組成的數列，和一個數字 k。 任意排列數字，使得以上式子最小。資料規模： 2 ≤ n ≤ 3e5, 1 ≤ k ≤ min(5000, n - 1) - 1e9 ≤ A[i] ≤ 1e9 TL: 2000 ms ML: 256 MB解法： 注意到下標對 K 取模的數字們是一群的，…

Problem - B - Codeforces題意： 給你 n 個數組成的數列 a，和總和上限 s，長度下限 l。求將數列 a 分割成最少數量的連續片段，滿足每個片段總和不超過 s，長度不小於 l。求最少可能片段數量。資料規模： 1 ≤ n ≤ 1e5, 0 ≤ s ≤ 1e9, 1 ≤ l ≤ 1e5,- 1e9 ≤ ai …

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 取模。資料規模： 字…