Problem - D - Codeforces題意： 給長度 N 的數列 A。問最大的數，使得該數是數列中一半以上的數的因數為何。制約： N ≤ 1e6 A ≤ 1e12解法： 令答案為 g，那麼有一半以上的數字是 g 的倍數。 因此考慮隨機選取一個下標 r，把所有 gcd( A[ r ], A[ i ] ) 算出…

No.470 Inverse S+T Problem - yukicoder題意： 給定 N 個長度為三的字串，求一種分割，使得每個字串被分為兩個非空子字串，且不存在重複的字串。制約： N ≤ 1e5 sigma: { 'a'~'z', 'A'~'Z' }解法： 注意到當 N > | sigma | 時，一定無解，所以 N 可以視作 ≤…

No.230 Splarraay ｽﾌﾟﾗﾚｪｰｲ - yukicoder題意： 初始時有一個長度為 N 的陣列。現在 a, b 兩人玩遊戲，有 Q 個操作依序被進行，第 i 個操作可以用 ( x[ i ], l[ i ], r[ i ] ) 描述： x = 0 : 令 ca 為 arr[ l, r ] 中 a 塗色數，cb 為 arr[ l, r ] 中 b 塗色…

No.162 8020運動 - yukicoder題意： 你上下各有一排 14 個連續的牙齒。 你現在 A 歲，你想知道你在 80 歲時，期望會有多少顆牙齒剩下。 牙齒掉落的機率是 P[ 左邊的牙齒是否剩下 + 右邊的牙齒是否剩下 ]。解法： 考慮動態規劃： dp[ i ][ j ][ k ] : 經過 i …

No.361 門松ゲーム2 - yukicoder題意： 一開始有一個長度 L 單位的棒子。輪流操作，操作要選擇一個棒子，砍成三個不同長度的棒子，令這三個棒子的長度為 L1, L2, L3，則必須滿足： max( L1, L2, L3 ) - min( L1, L2, L3 ) ≤ D 先不能操作的人輸，問誰贏。制…

No.421 しろくろチョコレート - yukicoder題意： 有一個 N * M 的黑白交接的棋盤巧克力。有些已經被吃掉了，用 '.' 表示。你每吃一片 1 * 2 的巧克力會得到幸福值 100，每吃不相鄰的一塊黑色和一塊白色會得到幸福值 10，隨便吃一塊會得到幸福值 1，問最大幸…

Problem - E - Codeforces題意： 給一個數列，對每一個值輸出： 1 if 它不屬於任何一個 LIS 2 if 它屬於某個 LIS，但沒有它也存在相同長度的 LIS 3 if 拔掉它的話 LIS 長度會改變制約： N ≤ 1e5 A ≤ 1e5解法： 用 dp 跟 BIT 的要領求出 st_len[ i ]: 以位置 …

No.409 ダイエット - yukicoder題意： 有 N 天，第 i 天有重量 D[ i ] 單位的甜甜圈可以吃。你現在的重量是 W 單位，你想減肥，所以每天你可以選擇吃或不吃。如果吃了，你的體重就會增加吃掉的重量並歸零壓力值，否則你會減去 A 單位的重量但同時增加一個單…

No.377 背景パターン - yukicoder題意： H * W 格子的壁紙，每個格子有 K 種顏色中一種。這個壁紙由無窮左到無窮右不重疊貼滿，無窮下方至無窮下方也一樣。問牆壁的圖案有多少種，對 1e9 + 7 取模。兩個牆壁的圖案相同若且唯若同時存在相同一個 H * W 的圖案…

Programming Problems and Competitions :: HackerRank題意： 有 N 個線段，用長度描述。每一秒以均等機率有兩個線段合併 ( 長度變為總和 )。問期望上 K 秒後，每個線斷所成的圓面積總和為何。制約： 1 ≤ N ≤ 1e5 0 ≤ K ≤ N - 1 0 ≤ R[ i ] ≤ 1e4解法： 首先…

Programming Problems and Competitions :: HackerRank題意： N 個點 M 個邊，第 i 個邊用 a[ i ], b[ i ] 描述。求一個生成樹，使得 sum( a ) / sum( b ) 最大。制約： 2 ≤ N ≤ 1e5 N - 1≤ M ≤ 1e5 1 ≤ a[ i ], b[ i ] ≤ 100解法： 裸的最優比例生成樹。 聽…

F: Dam - AtCoder Regular Contest 072 | AtCoder題意： 有一個水壩，容量是 L。有 N 天，第 i 天早上會有溫度 T[ i ] 容量 V[ i ] 的水流進水壩，晚上你可以讓水壩流出任意適當多容量的水。分別對於 [ 1, N ] 的所有 i，問使得第 i 天恰有容量 L 的水在水壩…

E: Alice in linear land - AtCoder Regular Contest 072 | AtCoder題意： 有一個車子在數線上的原點。目標是 D。依序有 N 個操作，d[ i ] 代表第 i 次操作的參數。每次操作將會使車子向目標的方向前進 d[ i ]，但特別地，如果操作後不會接近，則該次操作無…

D: Alice&Brown - AtCoder Regular Contest 072 | AtCoder題意： 兩堆石頭，數量 X, Y。輪流操作，一次選一個正整數的偶數 v，從一個至少有 v 個石頭的堆裡除去，並在另一堆上添加 v / 2 顆石頭。先不能操作的人輸。問雙方最佳操作下誰贏。制約： 0 ≤ X, Y ≤…

C: Sequence - AtCoder Regular Contest 072 | AtCoder題意： 給 N 個數字的數列 A。一次操作選一個數字 +1 或 -1。問最少要幾次操作，才能使得前綴和的正負交替。制約： 2≦n≦1e5 |ai|≦1e9 ai は整数解法： 枚舉開頭是正或負。由左到右確定數字，只有在必要…

Dashboard - Round 1B 2017 - Google Code Jam題意： T 筆測資。有 N 個城市，用相鄰矩陣表示距離，不保證輸入距離滿足三角不等式。每個城市有一隻馬，用可行走距離 E 和最高速度 S 描述。Q 筆詢問，問 u 到 v 的最少時間。詢問之間不互相影響，而在一筆詢問…

Dashboard - Round 1B 2017 - Google Code Jam嗯..? 好像根本就不用二分搜題意： T 筆測資。你在數線上的原點，目的地是 D。除了你現在騎著的馬，一共有 N 隻馬，任兩隻不共享位置的處於某整數位置，並有一個最高速度的屬性描述。當後面的馬追上前面的馬時，…

Problem - D - Codeforces題意： 給長度 N 的兩個數列 A, B，求構造一個 C[]，使得 len( C ) ≤ N / 2 + 1，且所有元素相異，且任意 i 滿足 1 ≤ C[ i ] ≤ N，並有 sum( A[ k ] for k in C ) * 2 > sum( A ) 且 sum( B[ k ] for k in C ) * 2 > sum( B )。制約…

Problem - C - Codeforces題意： 給長度為 N 的數列 A。每次可以進行的操作為，選擇一個 i，並執行 A[ i ], A[ i + 1 ] = A[ i ] - A[ i + 1 ], A[ i ] + A[ i + 1 ]。問至少要進行幾次操作，才能使得 gcd( A ) > 1。制約： The first line contains a singl…

Problem - L - Codeforces題意： 有 N 天，你有 K 個巧克力棒。第一天和最後一天一定是空的，而且你一定要吃巧克力棒。其他天有些要工作，所以那些天不能吃巧克力棒。問最佳的安排下，你最少的最多不能吃巧克力棒的連續天數。制約： The first line contains…

Problem - K - Codeforces題意： 給一個長度為 N 的字串，要求進行壓縮，規則如下： 若 "aeiouy" 任意一個字符連續出現兩次以上，則壓縮為一個。 例外是若 'e' 或 'o' 連續出現恰兩次，則不能壓縮。制約： The first line contains the integer n (1 ≤ n ≤ 1…

Problem - J - Codeforces題意： 給一個長度為 N 的字串，由 "YN?" 組成。'?' 有可能為 'Y'，有可能為 'N'。給定一個 K，問是否有可能存在一個連續 'N' 子字串長度恰為 K。注意連續 'N' 子字串必須是最大的，也就是左界左邊和右界右邊的元素必須為 'Y'。制約…

Problem - I - Codeforces題意： 有 N 種字串。你的目標字串為 target。問至少要連接幾次字串，才能使得這個大字串的子序列有 target。制約： The first line contains the integer n (1 ≤ n ≤ 50) — the number of strings in Stepan's set. The next n lin…

Problem - H - Codeforces題意： 給 C[]，C[ i ] 代表長度為 i 的元素種類單一子字串的數量。求構造字串。制約： The first line contains the integer n (1 ≤ n ≤ 2000) — the length of the Stepan's favorite string. The second line contains the seque…

Problem - G - Codeforces題意： 給 A, H, W，代表有一個紙張 H * W 大小，圖片是一個邊長為 A 的正方形。現在要放任意個正方形，使得所有相鄰正方形之間，以及邊界和其相鄰的正方形的間距為任意實數 x。問 x 最小可以是多少，無解則輸出 -1。制約： The fir…

Problem - F - Codeforces題意：制約： The first line contains the integer n (1 ≤ n ≤ 50 000) — the number of pens Stepan has. The second line contains the sequence of integers a1, a2, ..., an (1 ≤ ai ≤ 1e9), where ai is equal to the number …

Problem - E - Codeforces題意： 給大數 N，以及一個數字 M。考慮 N 的所有循環 ( N[ x : ] + N[ : x ], for any N[ x ] != 0 )，問其中模 M 後最小的數字為何。制約： The first line contains the integer which Stepan has. The length of Stepan's integ…

Problem - D - Codeforces題意： 給長度 N 的 A, B 數列。問是否可以只任意排列 [ L, R ] 區間內的元素，使得 A = B。制約： The first line contains three integers n, l, r (1 ≤ n ≤ 1e5, 1 ≤ l ≤ r ≤ n) — the number of Vasya's cubes and the position…

Problem - C - Codeforces題意： 你有無限多個七段顯示器，問不超過 n 個段可以發光的前提下，可構成的最大數字是多少。制約： The first line contains the integer n (2 ≤ n ≤ 100 000) — the maximum number of sections which can be highlighted on the…

Problem - B - Codeforces題意： 你有 n 個 PhOI 獎牌，m 個 IOI 獎牌，各自用價值 c 和重量 w 描述。你有一個容器可以容下不超過 d 的總重量，問在兩種獎牌至少各一枚，且當一種獎牌中價值為 x 的獎牌被納入則所有價值超過 x 的同種獎牌也都必須納入的前提…