0w1

Ad hoc

ARC 074 C - Chocolate Bar ( Ad hoc )

C: Chocolate Bar - AtCoder Regular Contest 074 | AtCoder題意: 把巧克力沿著線切,分成三個非空的塊。 問最大和最小的塊的面積差最小是多少。制約: 2 ≤ H, W ≤ 1e5解法: 只可能有兩種切法 | | | 或 | -。90 度旋轉再做一樣的事情。 第一刀切下去之後顯…

CFr 811 D. Vladik and Favorite Game ( Interactive, Ad hoc )

Problem - 811D - Codeforces題意: 給一張地圖,有些是炸彈,走上去馬上死。 起點在左上角,目標是 'F'。 你可以上下左右移動,但是上和下的控制可能是反的,左右也是。 互動走到 F。 操作數不可超過 2 * N * M。制約: 1 ≤ N, M ≤ 100 保證有至少一條路徑…

CFR 269 C. Flawed Flow ( Flow )

Problem - 269C - Codeforces izrak の提出見て回答。題意: 給你一張無向圖,邊有容量,要求定向,使得有最大流。源點 1,匯點 N。制約: 2 ≤ N ≤ 2e5 N - 1 ≤ M ≤ 2e5 C[ i ] ≤ 1e4解法: 初始時對所有邊的端點添上該邊的容量。 為了要滿足流量守恆,也就…

CFR 808 E. Selling Souvenirs ( Ad hoc, Monotonous )

Problem - 808E - Codeforces題意: 有 N 個物品,你的背包容量為 M。第 i 個物品容量為 W[ i ],價值為 C[ i ]。求可容的最大可能價值總和。制約: 1 ≤ N ≤ 1e5 1 ≤ M ≤ 3e5 1 ≤ W[ i ] ≤ 3 1 ≤ C[ i ] ≤ 1e9解法: 如果只有兩種重量,那有多簡單。 考慮討…

CFR 794 E. Choosing Carrot ( Game, Ad hoc )

Problem - 794E - Codeforces題意: 給長度 N 的數列 A[]。現在輪流玩遊戲,選擇一個端點的元素,讓它消失。當元素數量為 1 的時候遊戲立即結束。先手的目標是最大化最後一個元素,後手的目標是最小化最後一個元素。先手打算作弊,自己操作連續 K 輪後,當作…

CFR 794 D. Labelling Cities ( Ad hoc, Graph )

Problem - 794D - Codeforces題意: 有 N 個城市,M 條路。如果存在,輸出一個方案,為每個城市 u 分配一個數字 X[ u ],使得 abs( X[ u ] - X[ v ] ) ≤ 1 若且唯若 u, v 相鄰。制約: N, M ≤ 3e5解法: 首先考慮這樣的一對城市 ( u, v ):它們的鄰接陣列,…

Yuki 514 宝探し3 ( Ad hoc, Interactive )

No.514 宝探し3 - yukicoder題意: 在一個 1e9 * 1e9 的平面上,有個座標藏著寶藏。你每次可以問一個點和寶藏的曼哈頓距離是多少。請在兩次以內的詢問找到寶藏位置。解法: 問 ( 0, 0 ) 得距離 A,接著問 ( 0, A ) 得距離 B,那麼寶藏一定在 ( B / 2, A - B…

CFR 622 D. Optimal Number Permutation ( Ad hoc )

Problem - 622D - Codeforces題意: 要求排列兩個 [ 1, n ] 組成的長度為 2 * n 的陣列,使得以下 s 最小。 d[ i ] 為 i 處於的兩個位置形成的距離。制約: 1 ≤ N ≤ 5e5解法: 看解說,覺得非常神祕,遇到類似題應該還是不會。 主要想法是這樣,猜測可以直接…

CFR 803 B. Distances to Zero ( Ad hoc )

Problem - B - Codeforces題意: 給一個數列,其中至少有一個元素為 0。對每一個位置輸出離它最近的 0 的距離。制約: The first line contains integer n (1 ≤ n ≤ 2e5) — length of the array a. The second line contains integer elements of the array …

CFR 798 D. Mike and distribution ( Adhoc / Random )

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 )。制約…

CFR 795 K. Stepan and Vowels ( Ad hoc )

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

CFR 795 J. Stepan's Series ( Ad hoc )

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

CFR 795 H. Repairing Of String ( Ad hoc )

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…

CFR 795 D. Lie or Truth ( Ad hoc )

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…

Yuki 491 10^9+1と回文 ( Ad hoc, Palindrome )

No.491 10^9+1と回文 - yukicoder題意: 給 N,問有幾個數字不超過 N,是 1e9 + 1 的倍數,並且是迴文。制約: N ≤ 1e18解法: 怒猜超過 1e9 之後不會有迴文了。( 求證明 ) 所以要求的其實是 1e9 以下的迴文數。 因為是迴文,所以只要枚舉左半邊,也就是大約…

GCJ 2017 Qual B. Tidy Numbers ( Ad hoc )

Dashboard - Qualification Round 2017 - Google Code Jam題意: 問不超過 N 的最大的,以十進制表示時,由左到右檢視,數字呈非遞減的數為何。制約: 1 ≤ T ≤ 100. 1 ≤ N ≤ 1e18. 解法: 一開始寫數位統計 dp 寫到快哭出來。 仔細想想,只要倒著決定就可以…

ARC 071 E - TrBBnsformBBtion ( Ad hoc )

E: TrBBnsformBBtion - AtCoder Regular Contest 071 | AtCoder題意: 給字串 S, T。Q 筆詢問,指定 S 的某個子字串 S', T 的某個子字串 T',問是否能透過施行以下操作任意次由 S' 轉換為 T'。 1. 將 'A' 換成 "BB" 2. 將 'B' 換成 "AA" 3. 將 "AAA" 換成 "…

CFR 788 B. Weird journey ( Euler's Path, Ad hoc )

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

CFR 792 D. Paths in a Complete Binary Tree ( Ad hoc, Binary Search )

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

CFR 613 C. Necklace ( Ad hoc, Palindrome )

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

CFR 781 C. Underground Lab ( Ad hoc, Time Stamp, DFS )

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

POI 2 Stage 2 Triangles ( Ad hoc, Math, Fibonacci )

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…

IOICJ 92 Double path tree ( Ad hoc, Timestamp )

Problem Description: Given a tree, you want to do the least amount of operations to assert that for any two distinct nodes, there are at least two distinct simple paths that connect them.Constraints: 1≤T≤300 3≤n≤1e5 1≤xi,yi≤n A valid tree …

CFR Educational 17 C. Two strings ( Ad hoc )

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

CFR 351 A. Jeff and Rounding ( Ad hoc, Math )

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

CFR 533 E. Correcting Mistakes ( Ad hoc )

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…

Bangladesh OI 2016 National Round pF. Batman and Robin ( Ad hoc )

http://codeforces.com/gym/101212/attachments/download/5014/bangladesh-informatics-olympiad-2016-en.pdf Dashboard - Bangladesh Informatics Olympiad 2016 - Codeforces題意: 給你 L, A,代表字串的大小,以及可能字符集合大小。 接著給字串,以數字…

CFR 14 D. Two Paths ( Ad hoc, Tree, DP )

Problem - 14D - Codeforces題意: 給一棵樹,求兩個不相交的路徑,長度乘積最長可以是多少。資料規模: 節點數: 2 ≤ N ≤ 200 時間限制:1000 ms 空間限制:64 MB解法: 因為樹原本是連通的,而不能相交其實就是有一條路徑可以把他們連起來卻不准連起來,所…

Yuki 318 学学学学学 ( Ad hoc / Segment Tree )

No.318 学学学学学 - yukicoder題意: 給一個數列 A。現在要產生另一個數列 B。產生的步驟為: for each integer t in 1 to 1e9: __for each integer x in leftmostPositionInA( t ) to rightmostPositionInA( t ): ____B[ x ] = t 求 B 的最終樣貌資料規模…

ARC 065 D - 連結 ( Ad hoc )

D: 連結 / Connectivity - AtCoder Regular Contest 065 | AtCoder題意: 給相同節點數的兩個圖,對於每個點,求有多少點和它在兩個圖上都屬於相同的連通分量。資料規模: 節點數 2≦N≦2e5 兩個圖分別邊數 1≦K,L≦1e5 保證同一個圖不存在重邊 時限 2000 ms 記…