0w1

Ad hoc

ARC 039 C - 幼稚園児高橋君

Problem Description: You are on an infinitely large grid. Initially you are at coordinate (0, 0). You would move towards of the four directions (URDL) each unit of time, and stop at the first integer coordinate that had not yet been visite…

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 的最終樣貌資料規模…