0w1

Dummy Constraints

CFR 815 C. Karen and Supermarket

Problem Description: There are N items, the i'th item costs C[i], and we have a coupon that can reduce its price by D[i]. However, for every coupon i to be effective, coupon X[i] must be used, i.e., i'th item bought. You have B units of mo…

CFR 444 C. DZY Loves Colors ( Segment Tree, Dummy Constraints )

Problem - 444C - Codeforces題意: 給長度 N 的數列 A[]。初始時 A[ i ] = i, for all 1 ≤ i ≤ N。 M 筆詢問,兩種形式: 1 l r x:將 [ l, r ] 都塗色為 x 2 l r:輸出 [ l, r ] 的貢獻總和 初始時所有元素的貢獻為 0。 當一個元素由 u 變為 v 時,增加貢…

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

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

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

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

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 34 砂漠の行商人 ( Dummy Constraints )

No.34 砂漠の行商人 - yukicoder最悪の場合は通る砂漠のレベルが全部最高である 9のとき。この場合は遠回りはいらないのでマンハッタン距離を考えて、体力は精々 N * 2 * 9 で十分だと分くる。 int N, V, Sx, Sy, Gx, Gy; vvi LV; void init(){ cin >> N >> …