0w1

Entries from 2016-11-15 to 1 day

CFR 367 E. Sereja and Intervals ( Segment Trick DP + Pigeon Hole Principle )

Problem - E - Codeforces題意: 在 [ 1, M ] 中,要算有多少種方法,可以有 N 個有序區間( ex: { [ 1, 2 ], [ 3, 4 ] } != { [ 3, 4 ], [ 1, 2 ] } ),不存在任一個區間包含另一個區間,且有至少一個區間的左界為 X,求其餘數。數據範圍: 需要區間數,值域…

CFR 637 D. Running with Obstacles ( DP, Reverse Thinking )

Problem - D - Codeforces題意: 初始時在 x = 0,要到 x = M,一路上會有若干個地雷。有兩種移動方式,跑步可以一次跑無窮遠,但不能越過地雷,跳躍可以越過地雷,但必須先跑連續至少 S 格,才能進行一次至多 D 格移動的跳躍。所有移動都只能向右。求是否存…

CFR 637 C. Promocodes with Mistakes ( Ad hoc, Bruteforce )

Problem - C - Codeforces題意: 給若干個條碼,由六個 0 ~ 9 之間的數字組成。求一個最大 K,保證就算打錯 K 個數字,依然可以確定是哪個條碼。數據範圍: 條碼的數量 1 ≤ N ≤ 1000解法: 首先顯然如果 N = 1,那一定是 K = 6,全部打錯都行。否則顯然 K = …

CFR 637 B. Chat Order ( Ad hoc, Set )

Problem - B - Codeforces題意: 給通知的順序,若是新的人的通知則會到訊息版最上面,否則會將舊的人提到訊息版的最上面。求最終樣貌。數據範圍: 通知數 1 ≤ N ≤ 2e5 通知的人名 1 ≤ | name | ≤ 10解法: 在動態過程中,每個人名一定只會對應到一個位置,…

Default Code ( 2016 / 11 / 15 )

#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector< int > vi; typedef vector< vi > vvi; typedef vector< vvi > vvvi; typedef vector< vvvi > vvvvi; typedef vector< vvvvi > vvvvvi; typedef vector< ll > vl; typedef vector< vl </bits/stdc++.h>…

CFR 255 C. Almost Arithmetical Progression ( Binary Search + DP )

Problem - 255C - Codeforces題意: 給一個序列。求一個最長子序列的長度,子序列滿足相鄰的數字的差是正負交替。ex: 10, 20, 10, 20數據範圍: 序列長度 1 ≤ N ≤ 4000 元素大小 1 ≤ B[ i ] ≤ 1e6解法: 對每個元素預處理出現在哪些位置。接著考慮動態規劃 d…