Subscribed unsubscribe Subscribe Subscribe

0w1

Hi everyone, please feel free to have discussions with me!

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 798 C. Mike and gcd problem ( Math )

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…

CFR 795 L. Bars ( Binary Search )

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

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 I. Composing Of String ( DP )

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…

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 G. Perfectionist Arkadiy ( Math )

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

CFR 795 F. Pens And Days Of Week ( Periodic )

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 …

CFR 795 E. Big Number and Remainder ( Math )

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…

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…

CFR 795 C. Maximum Number ( Greedy )

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…

CFR 795 B. Significant Cups ( Monotonicity )

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

CFR 795 A. Amusement Park ( Greedy, Ternary Search )

Problem - A - Codeforces題意: 有 N 個人,用一個 01 序列描述,0 代表小孩,1 代表大人。給定 C1, C2,你要將這些人分群,使得每個群至少有一個大人,而且最小化 sum( C1 + C2 * ( X[ i ] - 1 )^2 ),其中 X[ i ] 代表第 i 個群的人數。制約: The first …

CFR 616 E. Sum of Remainders ( Math, Sqrt Decomposition )

Problem - E - Codeforces題意: 給 N, M,求: 資料規模: The only line contains two integers n, m (1 ≤ n, m ≤ 1e13) — the parameters of the sum.解法: 首先觀察到 因此所求可以寫成 考慮比較簡單的這個問題: 這個的求法是基於平方分割,細節和這篇…

CFR 327 C. Magic Five ( Math )

Problem - 327C - Codeforces題意: 給一個大數 A,將其複製 K 次連接成一個新的大數 S。問有多少種方法任意刪除 S 中的數字,使得留下來的數字被 5 整除。允許領導 0,但不允許空字串。兩個方法相同若且唯若兩個方法刪除的數字的位置都是一樣的。資料規模:…

CFR 244 B. Undoubtedly Lucky Numbers ( Digit DP, Python deepcopy() )

Problem - B - Codeforces題意: 給正整數 N,問有多少正整數不超過 N,在十進制下可以用不超過兩種數字表示。資料規模: N ≤ 1e9解法: dp[ i ][ j ][ k ][ l ]: 已處理 N 的長度為 i 的前綴,已使用的數字是 ( j, k ),滿足 j 用 python 的編程瓶頸在於宣…

CFR 120 B. Quiz League ( Python read / write file )

Problem - B - Codeforces題意: 很水,不太重要,這裡記錄 python 的讀 / 寫檔。 前三行有,就等價 C++ 開了 freopen() import sys sys.stdin = open( 'input.txt', 'r' ) sys.stdout = open( 'output.txt', 'w' ) N, K = map( int, input().split() ) K -=…

CFR 86 D. Powerful array ( Mo's Algorithm, Math )

Problem - D - Codeforces題意: 給一個長度為 N 的數列 A[]。T 筆詢問,問對 [ L, R ] 中存在的所有相異數值 s,SUM( K[ s ] * K[ s ] * s ) 是多少。K[ s ] 代表 [ L, R ] 區間中,s 出現的次數。資料規模: First line contains two integers n and t (1 …

CFR 301 A. Yaroslav and Sequence ( Greedy )

Problem - 301A - Codeforces題意: 給一個長度為 2 * N - 1 的數列 A。你可以進行任意次以下的操作: 選擇任意 N 個相異的元素,讓他們的符號反轉 ( 乘上 -1 )。 問操作後,可以得到的最大數列和為何。資料規模: The first line contains an integer n (2 …

CFR 656 E. Out of Controls ( Python )

Problem - E - Codeforces題意: 給一個 N * N 的鄰接矩陣表示 ( i, j ) 間的邊的距離。問最遠點對的距離為何。 但是,規定不能用類如 for, while, repeat 等關鍵詞 ( 詳見題目本身 )。資料規模: The first line of the input contains a single integer N …

CFR 656 B. Scrambled ( Math, Periodic, Python )

Problem - B - Codeforces題意: 這是愚人節題,瓶頸貌似是在要花點時間把這稍微被打亂的文章看完。 總之題意就是給 M, R,問 [ 0, ∞ ] 這些整數中,有多少百分比的 d 對任意一個 0 ≤ i 資料規模: N, MAXM, MAXR ≤ 16解法: 顯然會以 LCM 為單位形成週期。…

CFR 525 E. Anya and Cubes ( Search )

Problem - E - Codeforces題意: 給 N 個數字的數列 A[]。你可以選至多 K 個數字,將它們變成自己的階乘,這個操作對同一個元素只能使用一次。問有幾種方法可以得到一個子集合,其總和恰為 S。兩種方法相同若且唯若集合相同且施加的操作相同。資料規模: The…

CFR 44 E. Anfisa the Monkey ( Greedy )

Problem - 44E - Codeforces題意: 給 K, A, B,以及一個字串 S。要求輸出方案,使得將 S 分為 K 個子字串,滿足所有子字串長度在 [ A, B ] 之間。資料規模: The first line contains three integers k, a and b (1 ≤ k ≤ 200, 1 ≤ a ≤ b ≤ 200). The secon…

CFR 768 D. Jon and Orbs ( DP, Probability )

Problem - D - Codeforces題意: 有 K 種卡片,每天都可以抽一張,抽到的種類機率分佈是隨機均勻。Q 筆詢問,問第幾天開始可以確定,對於任意一種卡片,有 P / 2000 的機率有至少一張。資料規模: First line consists of two space separated integers k, q…

CFR 552 E. Vanya and Brackets ( Greedy, Expression Parsing, Python )

Problem - E - Codeforces題意: 給一個由 '+', '*', '0' ~ '9' 組成的合法數式,要求在任意合法的位置插入一對括弧,求最大可能結果。資料規模: The first line contains expression s (1 ≤ |s| ≤ 5001, |s| is odd), its odd positions only contain digi…

CFR 768 C. Jon Snow and his Favourite Number ( DP )

Problem - C - Codeforces題意: 給一個長度為 N 的數列,要做 K 次操作。每次將數列排序後,奇數項 ( 1 based ) 和 X 做 xor,偶數項不變。問所有操作結束後,數列的長相。資料規模: First line consists of three integers n, k, x (1 ≤ n ≤ 1e5, 0 ≤ k ≤…

CFR 780 B. The Meeting Place Cannot Be Changed ( Binary Search )

題意: 有些整數點上有朋友,每個朋友有個最高速率。問所有朋友集結到任意實數點需要的最短時間。資料規模: The first line contains single integer n (2 ≤ n ≤ 60 000) — the number of friends. The second line contains n integers x1, x2, ..., xn (1…

CFR 777 C. Alyona and Spreadsheet ( Python Output Optimization )

Problem - C - Codeforces題意: 給一個 N * M 的矩陣。K 筆詢問,每次問 [ L, R ] 範圍的行是否存在一個列,使得在 [ L, R ] 之間為非遞減。資料規模: The first line of the input contains two positive integers n and m (1 ≤ n·m ≤ 100 000) — the num…

CFR 767 D. Cartons of milk ( Binary Search, Counting Sort )

Problem - D - Codeforces題意: 你有 N 個牛奶,第 i 瓶會在 A[ i ] 天後壞掉。商店有 M 個牛奶,第 i 瓶會在 B[ i ] 天後壞掉。你一天喝至多 K 瓶牛奶,問最多可以買多少牛奶,使得你不必喝任何壞掉的牛奶。資料規模: N, M ≤ 1e6 過期天數 ≤ 1e7 TL: 2000…

CFR 767 C. Garland ( Tree DP )

Problem - C - Codeforces題意: 給一棵節點帶權的樹。問是否存在一種分割方法,使得可以分成三個非空子樹,使得權重總和相同。輸出方案。資料規模: The first line contains single integer n (3 ≤ n ≤ 1e6) — the number of lamps in the garland. Then n…

CFR 788 C. The Great Mixing ( Math, bitset, DP )

Problem - C - Codeforces題意: 你的目標濃度是 N / 1000。你有 K 種液體,濃度分別為 a[ i ] / 1000。每一種液體可以用任意非負整數單位容量,求最小正整數,代表使用的總容量成功調配出目標濃度。資料規模: The first line contains two integers n, k (…

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 788 A. Functions again ( DP )

Problem - A - Codeforces題意: 給一個長度為 N 的數列 A[]。求最大的 f( l, r ),滿足 1 ≤ l 資料規模: The first line contains single integer n (2 ≤ n ≤ 1e5) — the size of the array a. The second line contains n integers a1, a2, ..., an (-1e9…

CFR 792 E. Colored Balls ( Math, Sqrt Decomposition )

Problem - E - Codeforces題意: 給 N 種球的個數 A[]。要求按照下列規則將其分箱: 1. 同一個箱子不能存在兩種球 2. 最多球的箱子的球數和最少球的箱子的球數之差不得超過 1 3. 所有球都必須存在於一個箱子裡 4. 不得有空箱 問最佳的分箱方式下,可以用最少…

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

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

CFR 792 C. Divide by Three ( DP )

Problem - C - Codeforces題意: 給一個大數。問最少要刪除幾個數字才能使得剩下的數字為 3 的倍數。刪除後不得有前導 0。輸出方案。資料規模: 長度 ≤ 1e5解法: 刪除最少等價於保留最多。 dp[ i ][ j ] : 已考慮前 i 個數字,現在除以 3 餘 j,此時最大保…

CFR 613 C. Necklace ( Ad hoc, Palindrome )

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

CFR 613 B. Skills ( Binary Search )

Problem - B - Codeforces題意: 有 N 個技能,所有技能都用一個數值描述,上限皆為 A,你有 M 單位的金子,一個單位的金子可以提升一個技能的數值一個單位。你要最大化:數值為 A 的技能數量 * Cf + 最低的技能數值 * Cm。求最大化的值以及方案。資料規模:…

CFR 613 A. Peter and Snow Blower ( Geometry )

Problem - A - Codeforces題意: 給一個代表自轉中心的座標,以及順時針給的座標描述一個凸多邊形。問旋轉 360 度後,被覆蓋過的面積有多少。資料規模: N ≤ 1e5解法: 顯然要找離圓心的最遠點,以及最近點... 但仔細想想會發現不是最近點,其實是和任意線段…

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

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

CFR 781 B. Innokenty and a Football League ( 2SAT )

Problem - B - Codeforces題意: 給 N 個姓名,現在要為每個姓名做縮寫,但希望滿足以下規則: 1. 姓名是 A 的前三個字元,或 A 的前兩個字元接上 B 的第一個字元。 2. 任何縮寫不重複 3. 若對於第 i 個人採取第一種縮寫和第 j 個人採取第一種縮寫會是一樣的…

CFR 781 A. Andryusha and Colored Balloons ( Greedy, DFS )

Problem - A - Codeforces題意: 給一棵 N 個節點的樹,要求給每個節點著色,滿足所有長度為 2 的路徑裡的三個節點都異色。問最少顏色數量。資料規模: N ≤ 2e5解法: 隨便找一個節點當作根,轉為有根樹上的問題。遞迴拜訪一個節點之前先為該節點著色。在當…

CFR 786 C. Till I Collapse ( Math, Sqrt Dcmp, Divide and Conquer )

Problem - C - Codeforces題意: 給一個長度為 N 的陣列,用顏色描述。要求對於所有 K 資料規模: N ≤ 1e5解法: 據說這可以用資料結構 ( 樹狀數組 ) 直接做掉,但我看不懂。 首先答案一定是非嚴格遞減的。 這題的重點在於看透一個結論:「答案的種類大約在 …

CFR 786 B. Legacy ( Dijkstra, Segment Tree )

Problem - B - Codeforces題意: 給一張圖,N 個點,Q 個邊,起點 S。 邊有三種,各自用 u, v / L, R, w 描述: 1. u -> v : 代價 w 2. u -> [ L, R ] : 代價 w 3. [ L, R ] -> u : 代價 w 問所有終點的單源最短路徑,不存在則輸出 -1。資料規模: N, Q ≤ 1e…

CFR 786 A. Berzerk ( DP, Game )

Problem - A - Codeforces題意: 有 n 個星球,從 0 開始編號,順時針排成一圈。0 號星球是黑洞。兩人有各自的操作集合,遊戲採取輪流操作,每次操作時選擇自己的集合裡的一個數字,將怪獸順時針推移該數字那麼遠。第一位把怪獸推移至 0 號星球的人獲得勝利…

CFR 128 B. String ( Hash, PFS )

Problem - B - Codeforces題意: 給一個字串,你要把所有子字串 ( 只要下標不同即不同 ) 生出來後輸出字典序第 K 個的字串。資料規模: N, K ≤ 1e5 TL: 1000 ms ML: 256 MB解法: 因為 K 很小,所以按字典序小的出隊,接上自己後一個字符再丟回一個優先隊列…

CFR 228 E. The Road to Berland is Paved With Good Intentions ( 2SAT )

Problem - 228E - Codeforces題意: 給 N 個點 M 條邊,邊有邊權 0 或 1。每次操作選取一個點,將和此點連接的所有邊的權值反轉。問存不存在一種反轉方式可以讓所有邊的邊權變為 1,若有則輸出方案。資料規模: N ≤ 100 解法: 考慮每個邊,其實只能被兩端點…

CFR 285 D. Permutation Sum ( Meet in the Middle, Search )

Problem - D - Codeforces題意: 問有多少 A, B, C 數列的組合,使得 ( A[ i ] + B[ i ] ) % N = C[ i ],且 A, B, C 都是 [ 0, N ) 的排列。資料規模: The single line contains integer n (1 ≤ n ≤ 16). TL: 1500 ms ML: 256 MB解法: 有用到這題的結論,…

CFR 19 B. Checkout Assistant ( DP )

Problem - 19B - Codeforces題意: 有 N 種商品各一個,若購買第 i 種商品,需要花費 C[ i ] 單位的錢,但是可以得到 T[ i ] 單位的店員不注意的時間,而店員不注意的時間每單位可以供你偷一件尚未購買的商品。問你最少要付多少錢才能獲得所有商品。資料規模…