Entries from 2017-05-01 to 1 month
Problem - 808E - Codeforces題意: 有 N 個物品,你的背包容量為 M。第 i 個物品容量為 W[ i ],價值為 C[ i ]。求可容的最大可能價值總和。制約: 1 ≤ N ≤ 1e5 1 ≤ M ≤ 3e5 1 ≤ W[ i ] ≤ 3 1 ≤ C[ i ] ≤ 1e9解法: 如果只有兩種重量,那有多簡單。 考慮討…
Problem - 788E - Codeforces題意: 給長度 N 的數列 A[]。 這個數列代表士兵們,他們的強度。初始時所有士兵都是活著的。一個隊伍是合法的,如果他有 5 個人,令下標為 a 有 M 筆詢問,分為兩種: 1 x:反轉 x 號士兵的狀態 ( 保證活 -> 死 ) 2 x:反轉 x …
Problem - 794E - Codeforces題意: 給長度 N 的數列 A[]。現在輪流玩遊戲,選擇一個端點的元素,讓它消失。當元素數量為 1 的時候遊戲立即結束。先手的目標是最大化最後一個元素,後手的目標是最小化最後一個元素。先手打算作弊,自己操作連續 K 輪後,當作…
Problem - 794D - Codeforces題意: 有 N 個城市,M 條路。如果存在,輸出一個方案,為每個城市 u 分配一個數字 X[ u ],使得 abs( X[ u ] - X[ v ] ) ≤ 1 若且唯若 u, v 相鄰。制約: N, M ≤ 3e5解法: 首先考慮這樣的一對城市 ( u, v ):它們的鄰接陣列,…
標ㄐㄧProblem - 794F - Codeforces題意: 給長度 N 的數列 A。有 Q 筆詢問,分兩種: 1 l r x y:代表要將 A[ l .. r ] 中所有 x 的數位變換成 y 2 l r:代表要輸出 A[ l .. r ] 的總和制約: N, Q ≤ 1e5 1 ≤ A[ i ] ≤ 1e9 For query type 1: y != 0解法: …
UVa Online Judge題意: 有若干個節點跟雙向連接的網路線連接結點之間。你可以破壞節點或者破壞網路線,希望 1 號節點連不上 M 號節點。給你破壞每個物件的花費,問需要的最小總花費多少。制約: 2 ≤ 節點數( M ) ≤ 50, 0 ≤ 網路線數( W ) ≤ 1000 0 ≤ 容量 ≤…
No.514 宝探し3 - yukicoder題意: 在一個 1e9 * 1e9 的平面上,有個座標藏著寶藏。你每次可以問一個點和寶藏的曼哈頓距離是多少。請在兩次以內的詢問找到寶藏位置。解法: 問 ( 0, 0 ) 得距離 A,接著問 ( 0, A ) 得距離 B,那麼寶藏一定在 ( B / 2, A - B…
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 …
Problem - E - Codeforces題意: 有 N 個商品,用價格描述。你一共要選擇 M 樣物品,使得 Masha 喜歡其中至少 K 件,Arkady 也喜歡其中至少 K 件。問最小花費,無解輸出 -1。制約: The first line contains three integers n, m and k (1 ≤ n ≤ 200000, 1 ≤…
Problem - D - Codeforces題意: 你有一個 H * W 的棋盤。你的目標是要在這之棋盤上能容下 A * B 的棋盤,但是容的時候邊之間必須平行或垂直。你有 N 個放大燈,選長或寬照上去之後那個邊會變 X[ i ] 倍。你可以以任意順序使用放大燈,問至少要用幾個放大燈…
Problem - C - Codeforces題意: 有 N 樣物品,用價格和價值描述。一樣物品可能是要用 C 類貨幣購買,也有可能是要用 D 類貨幣購買。選兩個相異的物品購買,使得價值總和最大。輸出價值總和。制約: The first line contains three integers n, c and d (2 ≤…
Programming Problems and Competitions :: HackerRank題意: N 個人排成一排,每個人對人投一個票。Q 筆詢問,問 [ L, R ] 中,是否有恰好得到 X 票的人,如果有,輸出其中編號最小的。制約: 1 ≤ T ≤ 5 1 ≤ N, Q ≤ 1e5 N 的總和和 Q 的總和不超過 3e5。解…
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 ] )…
Problem - D - Codeforces題意: 問 [ L, R ] 之間有多少整數,是可以被自身的所有非零數位整除。制約: T ≤ 10 1 ≤ L, R ≤ 9e18解法: 考慮 [ 1, x ] 的動態規劃: 一個顯然的狀態可以這樣定義: dp[ i ][ j ][ k ][ l ]: 考慮前 i 位,模 lcm( 1, 2, .. 9 …
Problem - E - Codeforces りんごさんの提出見て回答。題意: 有 N 個人,編號 1 到 N 要投票。投票可以使得當前的票數 +1 / +0 / -1 其中一個。每個人心目中都有一個期望票數,輪到他的時候他會依據當前的票數,操作使得接近他的期望票數。求對於所有 x,編…
Problem - D - Codeforces題意: 有 N 個城市,每對城市之間存在一個雙向路徑,每一條邊有一個死亡值 P。 一個路徑的死亡值是整條路徑上的邊的死亡值中的最小值。 對於每個城市 x,問一種方法,使得每個點對外都只留下一個有向邊,使得所有城市都會到達城市 …
Problem - C - Codeforces題意: 考慮一種整數的拆分方式,將一個數 x 拆分為 x = 1 + 2 + 4 + .. + 2^( k - 1 ) + r, 1 ≤ k and 0 ≤ r ≤ 2^k。原本有若干個數,進行這樣的拆分後,排序好,現在給你。問所有可能的原序列長度。制約: The first line contain…
Problem - B - Codeforces題意: 有 N 個人參加比賽,有五題,每個人的參數是五題的答對時間,沒有答對則以 -1 表示。一個人在一個題目的得分是這樣計算的: 考慮一個題,令 p 為答對人數,q 為參賽人數,則 p / q 對應到表格中的該題的最大分數。 對於一個…
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…
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…
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…
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. …
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解法: 很神奇,還沒看到這題的時候我就有想過手算一樣的問題了,還蠻顯然是用拉格…
Problem - 622D - Codeforces題意: 要求排列兩個 [ 1, n ] 組成的長度為 2 * n 的陣列,使得以下 s 最小。 d[ i ] 為 i 處於的兩個位置形成的距離。制約: 1 ≤ N ≤ 5e5解法: 看解說,覺得非常神祕,遇到類似題應該還是不會。 主要想法是這樣,猜測可以直接…
Problem - 609F - Codeforces題意: 有 N 隻青蛙在一維數線上,用位置和舌頭長度描述。現在依序有 M 隻蚊子出現,用位置和營養值描述。一個在位置 x,舌頭長度 t 的青蛙可以吃位於位置 y 的蚊子若且唯若 x ≤ y ≤ x + t,而且這隻青蛙是所有能吃到這隻蚊子的…
Problem - 609E - Codeforces題意: 給一張圖,分別問每一條邊必須被選擇時的最小生成樹花費是多少。制約: N, M ≤ 2e5解法: 找出原圖的最小生成樹後,做倍增 LCA,同時紀錄向上的瓶頸( 最大 )權值。指定的邊若在原本的生成樹,直接輸出當前最小花費,否則…
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>…
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().…
https://www.hackerrank.com/contests/capture-the-flag/challenges/secret-key与えられたリンクに入る。 ソース読む。 secret.js を呼ぶ事に気づく。 それを読んで、key.json を dict としてパスコード承認の動作をしているとわかる。 url の末尾を key.jso…