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

Problem - C - Codeforces題意： 給字串 A, B，求最短的一個 B 的子字串，使得從 B 刪去這段子字串後的新字串 B' 為 A 的一個子序列。輸出 B'。資料規模： 字串長度不超過 1e5 TL: 2000 ms ML: 256 MB解法： 由左到右枚舉 A 的字串的切割點，並透過預處理這…

預備知識： 1. 在討論密碼學時，一般以柯克霍夫原則為前提：即使密碼系統的任何細節已為人悉知，只要密匙未洩漏，它也應是安全的。其他常見前提如下：( Image from Wiki ) 2. 完善保密性：若暗文有完善保密性，那麼攻擊者不可能解讀明文中的任何一個片段。 3…

kmjp さんの記事を参考にしました。 Problem - A - Codeforces題意： 給你 2 * N 個數字，要把 N 個數向下取整，另外 N 個數向上取整。問總和的最小變化量是多少。資料規模： The first line contains integer n (1 ≤ n ≤ 2000). The next line contains 2n …

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 - C - Codeforces題意： 給你一個數值矩陣。要你將數值塗改，使得最大的數字最小，但在：所有行，或所有列裡，原本數值的大小關係皆不改變。資料規模： The first line of the input contains two integers n and m (, the number of rows and the n…

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 - D - Codeforces題意： 給一個數列，以及一些厄運質數。一個數的價值等於，質因數分解後，非厄運質數數量 - 厄運質數數量。可以做任意次操作，每次操作選擇數列中一個下標，將該下標以前的所有數字都除以他們的共同最大因數。求最大總價值。資料規…

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 - 696C - Codeforces題意： 給你 K 個數 A[ i ]，代表 N = PI{ A[ i ], for all i }。 有三個杯子，一開始中間的杯子裡面有寶物，每回合平等隨機地選左邊的或右邊的杯子，和中間的杯子交換。求 N 回合後，寶物在中間的機率。以分數形式表示，並分別…

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 - E - Codeforces題意： 給你長度 N，以及長度 N 的兩個相異字串 S 和 T。求有多少可能的字串 W，使得從 W 刪去一個字符可以成為 S，也能成為 T。資料規模： The first line contains integer n (1 ≤ n ≤ 100 000) — the length of words S and T. T…

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 …