Subscribed unsubscribe Subscribe Subscribe

0w1

UVA 11506 - Angry Programmer ( Mincut, Flow )

UVa Online Judge題意: 有若干個節點跟雙向連接的網路線連接結點之間。你可以破壞節點或者破壞網路線,希望 1 號節點連不上 M 號節點。給你破壞每個物件的花費,問需要的最小總花費多少。制約: 2 ≤ 節點數( M ) ≤ 50, 0 ≤ 網路線數( W ) ≤ 1000 0 ≤ 容量 ≤…

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

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

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 ≤…

HR Nominating Group Leaders ( Mo's Algorithm, Sqrt Decomposition )

Programming Problems and Competitions :: HackerRank題意: N 個人排成一排,每個人對人投一個票。Q 筆詢問,問 [ L, R ] 中,是否有恰好得到 X 票的人,如果有,輸出其中編號最小的。制約: 1 ≤ T ≤ 5 1 ≤ N, Q ≤ 1e5 N 的總和和 Q 的總和不超過 3e5。解…

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…

Monthly Training Farm - May 2017 D. oeis1 ( Offline )

https://oj.icpc.tw/contest/5/problem/DProblem Description: Define f( x ) as sum of digits of x, g( x ) as product of digits greater than 0 of x. Let D[ 1 ] = 8. D[ i ] = sum( f( D[ j ] ) + g( D[ j ] ) + 10 for j in range( 1, i ) ). Print D…

Monthly Training Farm - May 2017 C. factor1 ( Math, Sqrt Decomposition )

ICPC Blog Online JudgeProblem Description: Given A, B, print number of positive factors of all values between integer in [ A, B ].Constraints: 1 ≤ A ≤ B ≤ 1e14Solution: Consider calculating result of [ 1, B ] - [ 1, A - 1 ]. It uses simila…

Monthly Training Farm - May 2017 B. operator1 ( Math )

https://oj.icpc.tw/contest/5/problem/BProblem Description: Define operator @ with following property: To calculate a @ b, first we transform them into base 3, then apply addition without carry. For example, 7 @ 8 = 21_3 @ 22_3 = 10_3 = 3. …

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>…

CTF HR Infinite Links ( Web Crawler )

https://www.hackerrank.com/contests/capture-the-flag/challenges/infinite-links簡単な Web Crawler を書くだけ。 import urllib.request from queue import Queue def retrieve_msg_links( link ): line = list( urllib.request.urlopen( link ).read().…

CTF HR Secret Key

https://www.hackerrank.com/contests/capture-the-flag/challenges/secret-key与えられたリンクに入る。 ソース読む。 secret.js を呼ぶ事に気づく。 それを読んで、key.json を dict としてパスコード承認の動作をしているとわかる。 url の末尾を key.jso…

HE XOR queries ( Persistent Segment Tree on BIT, XOR, Online, Kth )

XOR queries | Segment Trees & Data Structures Practice Problems | HackerEarth題意: 給一個數列 A。要求在線處理 Q 筆詢問: 第一種: __將 A[ i ] 改為 x 第二種: __問 A[ l, r ] 排序後,其中 [ i, j ] 間的 xor 值為何。制約: N, Q ≤ 5e4 1 ≤ A[ i…

HE Dexter's Random Generator ( LCA, Persistent, Trie, XOR or Mo's ( TLE ) )

Dexter's Random Generator | Trie (Keyword Tree) & Data Structures Practice Problems | HackerEarth題意: 給一棵節點帶權的樹。每次詢問一條路徑,問路徑其中一個端點和路徑中任意節點的最大 XOR 值是多少。制約: 1 ≤ N, Q ≤ 1e5 1 ≤ A[ i ] ≤ 1e9解法…

HE Numbers Summation ( OEIS, Math, Square Root Decomposition )

https://www.hackerearth.com/challenge/competitive/april-circuits-17/algorithm/numbers-summation/題意: 給 N,求 S 對 1e9 + 7 取模。制約: 1 ≤ N ≤ 1e15解法: 無恥怒查 OEIS。 如果想認真解起來,要領應該跟這個是一樣的。時間 / 空間複雜度: O( N…

HE Filler Game ( SG )

Filler Game | Dynamic Programming and Bit Masking & Algorithms Practice Problems | HackerEarth題意: 一個 N * M 的棋盤,一開始也許會有障礙物。輪流操作放置一個障礙物,一個格子可以放障礙物若且唯若它是空的,而且它有一個相鄰的格子是空的。問先…

HE Fredo and Maths ( Math, Totient function )

Fredo and Maths | Totient Function & Math Practice Problems | HackerEarth題意: T 筆詢問。問 x^x^x^x^x^x... % M,其中有 K 個 x,為多少。制約: 1 ≤ T ≤ 1e5 1 ≤ M ≤ 1e7 1 ≤ K ≤ 1e18 M 解法: 利用尤拉定理可以知道,x^phi( M ) % M == 1,利用這…

HE Help Fredo ( Math, Binary Search )

Help Fredo | Binary Search & Algorithms Practice Problems | HackerEarth題意: 給 N 個元素,問最小的 x ,使得 A[ 0 ] * A[ 1 ] * A[ 2 ] .. A[ N - 1 ] 制約: 1 ≤ N ≤ 1e5 1 ≤ A[ i ] ≤ 1e10解法: 經典題,開 log 比較,二分搜 x。時間 / 空間複雜度…

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…

ARC 073 F - Many Moves ( DP, Segment Tree )

F: Many Moves - AtCoder Regular Contest 073 | AtCoder題意: 在一個一維的棋盤上,你有兩顆棋,一顆在 A 位置,另一顆在 B 位置。有 Q 次操作,第 i 次操作後你必須移動棋子使得至少其中一個佔據 X[ i ]。棋子移動的花費是移動的距離。問 Q 次操作後,可…

ARC 073 E - Ball Coloring ( Greedy )

E: Ball Coloring - AtCoder Regular Contest 073 | AtCoder題意: 有 N 個箱子,裡面有兩個球,球有各自的重量。對於每個箱子,都需要將其中一顆球放到袋子 A,另一顆放到袋子 B。一個袋子的價值是其中最大的重量和最小的重量的差。求最小的價值乘積。制約…

ARC 073 D - Simple Knapsack ( DP )

D: Simple Knapsack - AtCoder Regular Contest 073 | AtCoder題意: 有 N 個物品要做 01 背包問題。背包容量 W,要求價值最大。注意有個特殊限制:所有物品的容量和第一個物品的容量的差不超過 3。制約: 1≦N≦100 1≦W≦1e9 1≦wi≦1e9 すべての i=2,3,…,N につ…

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 ] ) 算出…

Yuki 470 Inverse S+T Problem ( 2SAT, Dummy Constraints )

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

Yuki 230 Splarraay スプラレェーイ ( bitset )

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 塗色…

Yuki 162 8020運動 ( DP )

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

Yuki 361 門松ゲーム2 ( SG, Game Theory )

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

Yuki 421 しろくろチョコレート ( Greedy, Maximum Bipartite Matching )

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

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 ]: 以位置 …

Yuki 409 ダイエット ( Decision Monotonous, DP )

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

Yuki 377 背景パターン ( Burnside Lemma, Math )

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