Subscribed unsubscribe Subscribe Subscribe

0w1

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

ARC 072 E - Alice in linear land ( DP )

E: Alice in linear land - AtCoder Regular Contest 072 | AtCoder題意: 有一個車子在數線上的原點。目標是 D。依序有 N 個操作,d[ i ] 代表第 i 次操作的參數。每次操作將會使車子向目標的方向前進 d[ i ],但特別地,如果操作後不會接近,則該次操作無…

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…

Yuki 497 入れ子の箱 ( DP )

No.497 入れ子の箱 - yukicoder題意: 給 N 個箱子,用三維各自的長度描述。一個箱子 i 容得下另一個箱子 j 若且唯若 X[ i ] > X[ j ] and Y[ i ] > Y[ j ] and Z[ i ] > Z[ j ]。問最多可以形成多少幾層的箱子。制約: 1≤N≤1000 1≤Xi,Yi,Zi解法: 依最小的…

Yuki 496 ワープクリスタル (給料日前編) ( DP )

No.496 ワープクリスタル (給料日前編) - yukicoder題意: 你有 N 顆一次性的魔法石頭,第 i 顆可以幫你在 X 軸上 + X[ i ],Y 軸上 + Y[ i ],但花費魔力 C[ i ]。你現在在 ( 0, 0 ),你的目的地是 ( Gx, Gy )。另外一種移動方式是向上或向右一格,花費 F。…

ARC 071 F - Infinite Sequence ( DP )

F: Infinite Sequence - AtCoder Regular Contest 071 | AtCoder題意: 問有多少無窮長度數列 A[] 滿足: 1. i 的下一個元素開始連續 A[ i ] 個皆相同 2. 對所有的 N ≤ i, j,A[ i ] = A[ j ] 輸出答案對 1e9 + 7 取模。制約: 1≤n≤1e6 n は整数解法: 首先…

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 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 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 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 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 C. Divide by Three ( DP )

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

CFR 786 A. Berzerk ( DP, Game )

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

POI 2 Stage 2 Mudstock Bis ( Tree, DP )

http://main.edu.pl/en/archive/oi/2/mud題意: 首都在 ( 0, 0 ) 的位置,有 M 個人在首都裡。接著有 L 條線,每條線有若干個城市,依序用線上和前一個 ( 第一個城市和首都 ) 的距離以及人數描述。要求選一個點使得所有人到該點的總花費最小,一個人行走一單…

POI 2 Stage 2 The Right-Turn Drivers' Club ( DP, BFS )

http://main.edu.pl/en/archive/oi/2/kpk題意: 給一張圖,有若干障礙物,給始點和終點,問是否可以不左轉不倒回從始點走到終點,可以的話輸出最短路徑的方案。資料規模: In the first line of the standard input there are two integers separated by a s…

POI 2 Stage 1 Palindromes ( DP, Hash )

http://main.edu.pl/en/archive/oi/2/pal題意: 給一個字串,問最多和最少可以拆分成幾個偶數長度迴文,存在的話輸出方案。資料規模: The standard input contains one word consisting of at least 1 and at most 200 small letters of English alphabet. …

UVA 10818 - Dora Trip ( DP, bitmask )

UVa Online Judge題意: 給一個 R * C 的圖,保證周圍都是牆( # ),也不能拜訪 ( X ),起點在 ( S ),問在拜訪最多 ( * ) 的前提下,最短迴路的最小字典序序列序列是什麼。資料規模: The input file contains no more than 20 test cases. The details of e…

CFR 19 B. Checkout Assistant ( DP )

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

CFR 790 C. Bear and Company ( DP )

Problem - C - Codeforces題意: 給一個長度為 N 的大寫英文字母組成的字串,一次操作可以將任一兩相鄰字符交換,問最少要多少次交換才能使得 "VK" 不以子字串形式出現。資料規模: The first line of the input contains an integer n (1 ≤ n ≤ 75) — the l…

CFR 13 C. Sequence ( DP )

Problem - 13C - Codeforces完全就是同一個題 只是這題要滾動才不會 MLE,然後詢問的是非遞減,所以不需要用到減下標的技巧。題意: 給一個陣列 A,可以任意讓值 +1 或 -1 任意多次,問最少要幾次才能將 A 變成非遞減數列。資料規模: MAXA ≤ 1e9 N ≤ 5000 T…

CFR 11 D. A Simple Task ( DP, Bitmask, Hamiltonian Walk )

Problem - 11D - Codeforces題意: 給一個無向圖。問有多少個簡單環 ( 無重複經過的點的環 )。資料規模: N ≤ 19 TL: 2000 ms解法: 考慮一個環,選定一個點 ( 這裡用編號最小的點 ) 切開之後變成一條鍊,假設原本是 abcd 這樣的環,那其實可以用點的集合和…

CFR 8 C. Looking for Order ( Bitmask, DP )

Problem - 8C - Codeforces題意: 給原點 ( sx, sy ),以及 N 個座標 X, Y。每次至多選兩個座標,依序拜訪完後,回到原點。問最好的路徑,使得路徑長最小。兩個座標的路徑長為歐幾里德距離的平方。資料規模: The first line of the input file contains the…

IOI 2016 Paint ( DP )

http://ioinformatics.org/locations/ioi16/contest/day2/paint/paint-TWN.pdf 1959 - [IOI 2016] Paint | TIOJ INFOR Online Judge題意: 給一個序列含 '.', 'X', '_',分別代表該位置的字符為未知、必為黑色、必為白色。再給 K 個數字 C[],代表由左到右看…

CFR 321 E. Ciel and Gondolas ( DP, Monotonic, Divide and Conquer )

Problem - E - Codeforces題意: 給一個矩陣,表示每對人之間的憎恨值。現在要把人划分為 K 群,每群必須都是連續編號的人。一個群的憎恨值貢獻是所有編號的有序對的憎恨值總和。求最少憎恨值總和。資料規模: The first line contains two integers n and k…

CFR 632 E. Thief in a Shop ( DP )

Problem - E - Codeforces題意: 有 N 個價值的物品,每個都有無限多個。輸出拿恰好 K 個物品可以產生出的所有值。資料規模: The first line contains two integers n and k (1 ≤ n, k ≤ 1000) — the number of kinds of products and the number of produc…

Yuki 243 出席番号(2) ( DP, Inclusion Exclusion )

No.243 出席番号(2) - yukicoder題意: 有 N 位可分別的學生,現在你要分配 0 ~ N - 1 的座位給他們。每個學生都有一個不喜歡的座位編號。求每個人都不作到不喜歡的座位編號的方案數,對 1e9 + 7 取模。資料規模: 生徒の数Nが最初の行で与えられる。1≤N≤500…

CFR 9 D. How many trees? ( DP )

Problem - D - Codeforces題意: 問 N 個節點組成的二叉樹,深度不少於 H 的方案有幾種。資料規模: H ≤ N ≤ 35解法: dp[ i ][ j ] : N 個節點的二叉樹,深度等於 H 的方案數 兩種轉移,首先當前的根是一定要的,一種是左空或又空,另一種是兩個都非空。時…

CFR 314 C. Sereja and Subsequences ( DP, BIT )

Problem - 314C - Codeforces題意: 給一個 N 個數組成的數列 A。現在有人把 A 的所有相異的非遞減子序列都生出來了。輸出,對這些子序列分別求,不比該子序列的字典序大的所有子序列的方案數,的總和,對 1e9 + 7 取模。資料規模: The first line contains…

CFR 383 D. Antimatter ( DP )

Problem - D - Codeforces題意: 給一個 N 個正整數組成的 A 數列。可以選一個連續區間,並決定每個數值分別的正負號,但其總和必須為 0 才合法。問有幾種合法的選取方式,選取方式相異若左界或右界不同,或任意一個元素分配到的正負號不同。輸出方案數對 1e…

CFR 404 D. Minesweeper 1D ( DP )

Problem - 404D - Codeforces題意: 給一個字符串,裡面只有 0, 1, 2, *, ? 五種符號。如果是數字,表示左右的 * 個數加起來一定有那麼多。如果是 ? 代表未確定。求有幾種 ? 的代入方式使得序列合法,對 1e9 + 7 取模。資料規模: The first line contains s…

CFR 431 D. Random Task ( Binary Search, Digit DP )

Problem - 431D - Codeforces題意: 給 M, K。求一個 N,滿足 1 ≤ N ≤ 1e18 且在二進制下,[ N + 1, 2 * N ] 中恰有 M 個數恰有 K 個 1。資料規模: The first line contains two space-separated integers, m and k (0 ≤ m ≤ 1e18; 1 ≤ k ≤ 64).解法: 直覺…

CFR 156 C. Cipher ( DP )

Problem - 156C - Codeforces題意: T 筆測資。每次給一個字串。有一種操作可以進行:選取兩個不同位置的字符,一個變成字典序小一的字符,另一個變成字典序大一的字符。特別的,a 沒有字典序小一的字符,z 沒有字典序大一的字符,而沒有相應的字符就不能進…

CFR 768 E. Game of Stones ( SG Value, DP )

Problem - 768E - Codeforces題意: N 堆石頭,輪流取,不能取的輸。對於某一堆石頭,不能拿走同個數量的石頭兩次。求後手勝敗。資料規模: First line consists of a single integer n (1 ≤ n ≤ 1e6) — the number of piles. Each of next n lines contains…

CFR 507 D. The Maths Lecture ( DP )

Problem - D - Codeforces題意: 求長度為 N 且沒有領導 0 的正整數中,有多少數字存在一個非 0 的後綴 y,使得 k 整除 y。輸出方案術對 m 取模。資料規模: Input consists of three integers n, k, m (1 ≤ n ≤ 1000, 1 ≤ k ≤ 100, 1 ≤ m ≤ 1e9).解法: dp[…

POJ 3866 Exclusive Access 2 ( Dilworth Theorem, DP, bitmask )

3866 -- Exclusive Access 2題意: 給一個 N 個無向邊的圖。求一種方案使所有邊定向,並有最短的最長路徑 ( 即不存在環 )。無法到達的點對之間的路徑長不須考慮。資料規模: N ≤ 100 節點為 [ L, Z ] 間的大寫英文字母,數量不超過 15。 TL: 5000 ms ML: 655…

POJ 2127 Greatest Common Increasing Subsequence ( DP )

2127 -- Greatest Common Increasing Subsequence題意: 給兩個數列 A, B,長度分別為 N, M,求最長公共遞增子序列。資料規模: 元素大小在 int32 範圍 N, M ≤ 500 TL: 2000 ms解法: 顯然可以定義 O( N^3 ) 的 dp,但這裡考慮 O( N^2 )。 dp[ i ][ j ] : B[…

IOICJ 109 Big Tower ( DP, Deque )

Problem Description: There is a tower with N floors, each floor having M rooms in order. One receives score S[ i ][ j ] when being at the j'th room of the i'th floor. You start at the X'th room at the first floor. Your objective is to trav…

IOICJ 91 Printer ( DP, 1D / 1D Convex Optimization )

Problem Description: You have a book with N pages in total. Page i requires cost A[ i ] to be printed. You have a weird printer, the cost of printing a continuous segment [ L, R ) is ( Sigma{ A[ i ], L ≤ i Constraints: 1≤T≤100 1≤N≤1e5 1≤K≤…

IOICJ 82 Minions ( DP )

Problem Description: Currently you have n minions in a row on the war field, where each minion at the i'th position shows an attack value of a[ i ]. You have another m aces yet to be summoned. You can set aces at both ends or between any t…

IOICJ 80 Buying Potions ( DP, Multiple Knapsack, Monotonous )

Problem Description: There are N shops that sell potions, and each of them only sells one kind of potion. The i'th shop sells potions for P[ i ] per glass, where each glass could heal B[ i ] units of health, but has only C[ i ] glasses in …

IOICJ 89 Tool Man ( DP )

Problem Description: You are given an array A consisting of N elements. You know that they are K different people's orders, where some consecutive elements are what they have ordered. You also know that every order was ordered by some one,…

POJ 1180 Batch Scheduling ( Slope Optimization DP )

1180 -- Batch Scheduling題意: 有 N 個工作,用 T[ i ], F[ i ] 描述第 i 個工作需要花費的時間,以及單位時間的價值。第 i + 1 個工作不能在第 i 個工作完成之前被完成。每次可以選擇 k 個,未完成的工作中編號最小的工作,花費其 T 的總和,令之 P,的時…

CFR Educational 17 D. Maximum path ( DP )

Problem - D - Codeforces題意: 有一個 3 * N 的矩陣,每個格子裡面有一個整數值。由左上角走到右下角,兩個格子可以互通若且唯若有公共邊,求路徑沒有重複格子的前提下,經過的格子值最大總和。資料規模: 1 ≤ N ≤ 1e5 TL: 2000 ms ML: 256 MB解法: dp[ i…

CFR 235 B. Let's Play Osu! ( DP, Math )

Problem - B - Codeforces題意: 假設有個 OX 序列,每個連續段 'O' 長度若為 x,則該段貢獻為 x^2。已知序列長度,以及分別每個字符為 O 的機率,求期望貢獻和。資料規模: The first line contains an integer n (1 ≤ n ≤ 1e5) — the number of clicks. Th…

TIOJ 1908 大根蘿蔔 ( DP, bitmask )

1908 - 大根蘿蔔 | TIOJ INFOR Online JudgeProblem Description: You are given a matrix of N * N, each cell with a positive value. You can take values away from each cell at most once, in any order, but after taking a value from a particular …

CFR 158 E. Phone Talks ( DP )

Problem - E - Codeforces題意: 有 N 通電話,用 T[ i ], D[ i ],分別為來電時間和通電時間長度描述。保證來電時間嚴格遞增。當有個電話來電時,可以選擇是否無視,如果不無視,就要接起來,佔用 D[ i ] 單位的時間,除非目前是正在打電話的狀態,那麼將這…

CFR 360 B. Levko and Array ( DP, Binary Search )

Problem - B - Codeforces題意: 給一個數列,可以更改至多 K 個數,使成為任意數,求更改後最小的相鄰值絕對差。資料規模: The first line contains two integers n and k (1 ≤ k ≤ n ≤ 2000). The second line contains space-separated integers a1, a2,…

CFR 509 C. Sums of Digits ( DP )

Problem - C - Codeforces題意: 給 N 個數字, B[ i ] 代表第 i 個數字各位數總和為 B[ i ]。求可能對應的數列的最後一個值的最小可能,且須滿足數列嚴格遞增。資料規模: The first line contains a single integer number n (1 ≤ n ≤ 300). Next n lines …

CFR 533 B. Work Group ( DP )

Problem - B - Codeforces題意: 給一棵以 1 為根的樹,以及點的權重。求一個集合,使得集合內每個點,以自身為子樹的根時,子樹內所有自身以外的點在集合中出現偶數次。問最大可能權重總和。資料規模: The first line contains integer n (1 ≤ n ≤ 2e5) — …

CFR 372 B. Counting Rectangles is Fun ( DP, Inclusion Exclusion )

Problem - B - Codeforces題意: 給一個 0 / 1 矩陣,Q 筆詢問,求以 ( A, B ) 為左上角,( C, D ) 為右下角的矩陣中,有多少不同的矩形元素全為 0。資料規模: There are three integers in the first line: n, m and q (1 ≤ n, m ≤ 40, 1 ≤ q ≤ 3e5). Each…