0w1

bitmask

CFR 62 E. World Evil ( Flow, Mincut, DP, bitmask )

Problem - 62E - Codeforces題意: 給一個多角形柱體形成的網路,問最大流是多少。 起點是上面的面的所有點,匯點是下面的面的所有點。制約: 2 ≤ N ≤ 5 2 ≤ M ≤ 1e5 解法: 顯然不能暴力跑網路流算法。 考慮用 dp 求解。 最大流不好求,求最小割。 考慮水平…

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

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

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

ZOJ 3280 Choose The Best ( Bitmask )

ZOJ :: Problems :: Show Problem題意: 給 N 個 M 維的向量,並給關於每個維度的權值 W。求兩個不同的向量,使得兩個向量在每個維度的差的絕對值乘上對應的權值,總和起來最大。輸出最大總和。資料規模: There are no more than 15 cases. Process to the …

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 401 D. Roman and Numbers ( DP, Digit, Bitmask )

Problem - D - Codeforces題意: 給你一個數 N,和 M。求 N 有幾種排列 N',使得 N' 整除 M 且沒有領導零。資料規模: n (1 ≤ n TL: 4000 ms ML: 512 MB解法: 感覺就不太妙。考慮 dp,先有 M 這一維,然後 18 這數字感覺就很數位統計的 fu,在這裡又發現,…

CFR 757 D. Felicity's Big Secret Revealed ( DP )

Problem - D - Codeforces題意: 給一個 01 字串,字符間或者左界右界放隔板。求至少放兩個隔板時,以二進位讀進所有被夾在隔板間的數字,令該數字集合中最大數為 x,則集合中所有數為正整數且含 [ 1, x ] 間所有數的方案數,對 1e9 + 7 取模。資料規模: 字…