Subscribed unsubscribe Subscribe Subscribe

0w1

Codeforces

CFR 776 C. Molly's Chemicals ( Math )

Problem - 776C - Codeforces題意: 給你一個長度 N 的序列,以及 K。問有多少個區間的總和是 K 的非負整數次方。制約: The first line of input contains two integers, n and k, the number of chemicals and the number, such that the total affection …

CFR 799 E. Aquarium decoration ( Binary Search )

Problem - E - Codeforces題意: 有 N 個商品,用價格描述。你一共要選擇 M 樣物品,使得 Masha 喜歡其中至少 K 件,Arkady 也喜歡其中至少 K 件。問最小花費,無解輸出 -1。制約: The first line contains three integers n, m and k (1 ≤ n ≤ 200000, 1 ≤…

CFR 799 D. Field expansion ( Dummy Constraints, Greedy )

Problem - D - Codeforces題意: 你有一個 H * W 的棋盤。你的目標是要在這之棋盤上能容下 A * B 的棋盤,但是容的時候邊之間必須平行或垂直。你有 N 個放大燈,選長或寬照上去之後那個邊會變 X[ i ] 倍。你可以以任意順序使用放大燈,問至少要用幾個放大燈…

CFR 799 C. Fountains ( Segment Tree )

Problem - C - Codeforces題意: 有 N 樣物品,用價格和價值描述。一樣物品可能是要用 C 類貨幣購買,也有可能是要用 D 類貨幣購買。選兩個相異的物品購買,使得價值總和最大。輸出價值總和。制約: The first line contains three integers n, c and d (2 ≤…

CFR 662 A. Gambling Nim ( Linear Basis, Math, Probability )

Problem - A - Codeforces題意: 有 N 張卡牌,正面和反面各有一個非負整數。現在兩個人玩遊戲,每場開局每張牌會均勻隨機呈正面向上或背面向上。把 N 個呈現在上的數字當做 N 堆的石頭,進行 Nim 的遊戲。雙方絕頂聰明的前提下,先手贏的機率為何。制約: T…

CFR 797 F. Mice and Holes ( DP, Monotonous, Divide and Conquer Optimization, or Deque Optimization )

Problem - F - Codeforces題意: 有 N 隻老鼠,用座標描述。有 M 個洞,用座標和容量描述。一隻位於座標 x 的老鼠進到位於座標 y 的洞裡要花費 abs( x - y )。問最小花費總和為何,才能使所有老鼠進洞。制約: 1 ≤ N, M ≤ 5000 abs( X[ i ] ), abs( P[ i ] )…

CFR 51 D. Beautiful numbers ( Digit DP )

Problem - D - Codeforces題意: 問 [ L, R ] 之間有多少整數,是可以被自身的所有非零數位整除。制約: T ≤ 10 1 ≤ L, R ≤ 9e18解法: 考慮 [ 1, x ] 的動態規劃: 一個顯然的狀態可以這樣定義: dp[ i ][ j ][ k ][ l ]: 考慮前 i 位,模 lcm( 1, 2, .. 9 …

CFR 806 E. Blog Post Rating ( Segment Tree, Fenwick Tree )

Problem - E - Codeforces りんごさんの提出見て回答。題意: 有 N 個人,編號 1 到 N 要投票。投票可以使得當前的票數 +1 / +0 / -1 其中一個。每個人心目中都有一個期望票數,輪到他的時候他會依據當前的票數,操作使得接近他的期望票數。求對於所有 x,編…

CFR 806 D. Perishable Roads ( Shortest Path, Graph )

Problem - D - Codeforces題意: 有 N 個城市,每對城市之間存在一個雙向路徑,每一條邊有一個死亡值 P。 一個路徑的死亡值是整條路徑上的邊的死亡值中的最小值。 對於每個城市 x,問一種方法,使得每個點對外都只留下一個有向邊,使得所有城市都會到達城市 …

CFR 806 C. Prairie Partition ( Binary Search, Greedy )

Problem - C - Codeforces題意: 考慮一種整數的拆分方式,將一個數 x 拆分為 x = 1 + 2 + 4 + .. + 2^( k - 1 ) + r, 1 ≤ k and 0 ≤ r ≤ 2^k。原本有若干個數,進行這樣的拆分後,排序好,現在給你。問所有可能的原序列長度。制約: The first line contain…

CFR 806 B. Dynamic Problem Scoring ( Dummy Constraints, Greedy )

Problem - B - Codeforces題意: 有 N 個人參加比賽,有五題,每個人的參數是五題的答對時間,沒有答對則以 -1 表示。一個人在一個題目的得分是這樣計算的: 考慮一個題,令 p 為答對人數,q 為參賽人數,則 p / q 對應到表格中的該題的最大分數。 對於一個…

CFR 806 A. Success Rate ( Math, Extended GCD )

Problem - A - Codeforces題意: 你現在寫了 y 個題目,答對了 x 個。你想知道你最少要再寫幾題才能有答對比率 p / q。若無解輸出 -1。制約: The first line contains a single integer t (1 ≤ t ≤ 1000) — the number of test cases. Each of the next t l…

CFR 622 F. The Sum of the k-th Powers ( Lagrange's Interpolation, Math )

Problem - 622F - Codeforces題意: 令 f( k, x ) = sum( pow( i, k ) for i in range( 1, x + 1 ) ) % ( 1e9 + 7 )。 問 f( K, N ) 是多少。制約: 1 ≤ N ≤ 1e9 0 ≤ K ≤ 1e6解法: 很神奇,還沒看到這題的時候我就有想過手算一樣的問題了,還蠻顯然是用拉格…

CFR 622 D. Optimal Number Permutation ( Ad hoc )

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

CFR 609 F. Frogs and mosquitoes ( Discretization, Segment Tree, Binary Search )

Problem - 609F - Codeforces題意: 有 N 隻青蛙在一維數線上,用位置和舌頭長度描述。現在依序有 M 隻蚊子出現,用位置和營養值描述。一個在位置 x,舌頭長度 t 的青蛙可以吃位於位置 y 的蚊子若且唯若 x ≤ y ≤ x + t,而且這隻青蛙是所有能吃到這隻蚊子的…

CFR 609 E. Minimum spanning tree for each edge ( LCA, Union Find, Kruskal )

Problem - 609E - Codeforces題意: 給一張圖,分別問每一條邊必須被選擇時的最小生成樹花費是多少。制約: N, M ≤ 2e5解法: 找出原圖的最小生成樹後,做倍增 LCA,同時紀錄向上的瓶頸( 最大 )權值。指定的邊若在原本的生成樹,直接輸出當前最小花費,否則…

CFR 598 C. Nearest vectors ( atan2 )

Problem - 598C - Codeforces題意: 給 N 個非零向量,求任意一對夾角最小的向量對。資料規模: N ≤ 1e5解法: 極角排序。 atan2( y, x ) 回傳的範圍在 [ -pi, pi ] 之間,只有 atan2( 0, 0 ) 是未定義的。時間 / 空間複雜度: O( N lg N ) #include <bits/stdc++.h> using </bits/stdc++.h>…

CFR 803 F. Coprime Subsequences ( Inclusion Exclusion, Math, Sieve )

Problem - F - Codeforces題意: 給 N 個元素的數列 A。問有幾種不同的非空子序列,其最大公因數不為 1。輸出方案數對 1e9 + 7 取模。制約: The first line contains one integer number n (1 ≤ n ≤ 100000). The second line contains n integer numbers a…

CFR 803 G. Periodic RMQ Problem ( Discretization, Segment Tree )

Problem - G - Codeforces題意: 給一個長度為 n 的 B 數列。現在將 B 數列黏貼 k 次變成一個新的數列。有 Q 筆詢問: op = 1: __將 [ l, r ] 中的元素全部更改為 x op = 2: __詢問 [ l, r ] 中的最小值制約: The first line contains two integers n and k…

CFR 803 E. Roma and Poker ( DP )

Problem - E - Codeforces題意: 你在玩遊戲,一場有三種結果,勝/平/敗。你知道當你的勝利的場數和敗北的場數的絕對差在 K 以上時,會立刻退出遊戲。現在你有一個序列描述 N 場遊戲,而你知道你打完這 N 場後退出。有些紀錄被塗成 '?',要你復原出一個合理…

CFR 803 D. Magazine Ad ( Binary Search )

Problem - D - Codeforces題意: 要求在 K 行以內,用最小的寬度排版文字。輸出最小合理的寬度。一行的末尾必須是空白或是 '-' 符號。保證字不會由 '-' 開頭,也不會有連續的 '-' 或是連續的空白。制約: The first line contains number k (1 ≤ k ≤ 1e5). T…

CFR 803 C. Maximal GCD ( Greedy )

Problem - C - Codeforces題意: 給 n, k,要求構造一個數列,數列長度必須是 k,元素總和必須是 n,而且要是嚴格遞增的。在此前提下,數列的 gcd 要最大。若不存在解則輸出 -1。制約: The first line consists of two numbers n and k (1 ≤ n, k ≤ 1e10).…

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 803 A. Maximal Binary Matrix ( Greedy )

Problem - A - Codeforces題意: 構造一個字典序最大的 N * N 的 01 矩陣,其中洽有 k 個 1,而且對於主對角線是對稱的。若不存在則輸出 -1。制約: The first line consists of two numbers n and k (1 ≤ n ≤ 100, 0 ≤ k ≤ 1e6).解法: 首先若 K > N * N 顯…

CFR 364 D. Ghd ( Random, Math )

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

CFR 486 E. LIS of Sequence ( DP, Fenwick Tree )

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

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…