Subscribed unsubscribe Subscribe Subscribe

0w1

CFR 128 B. String ( Hash, PFS )

Problem - B - Codeforces題意: 給一個字串,你要把所有子字串 ( 只要下標不同即不同 ) 生出來後輸出字典序第 K 個的字串。資料規模: N, K ≤ 1e5 TL: 1000 ms ML: 256 MB解法: 因為 K 很小,所以按字典序小的出隊,接上自己後一個字符再丟回一個優先隊列…

CFR 198 1B. Jumping on Walls ( PFS )

Problem - B - Codeforces Dijkstraみたいな感じでやればいいね。 #include <bits/stdc++.h> using namespace std; const int MAXN = 1e5 + 5; const int MAXK = 1e5 + 5; int n, k; char w[ 2 ][ MAXN ]; struct State{ int t, x, lv; State( int _t = -1, int _x = -1, in</bits/stdc++.h>…

CFR 129 D. String ( Priority Queue )

Problem - D - Codeforces 因為關鍵的只有最小的10萬個,所以可以用priority queue模擬。不過現在這個方法過不了,因為judge time 變成兩倍。抓了別人的code來測試果真如此。雖然說有另一種解法是用後綴陣列,我這禮拜要趕緊學起來。 #include <bits/stdc++.h> using namesp</bits/stdc++.h>…

UVA 10603 Fill ( PFS )

UVa Online Judge 題目要求用最少的水來往達到 d或接近 d,又注意到水不會減少亦不會增加,故狀態只有二維 ( 知道其中兩個分別裝了多少就能知道剩下的那個 ),這是一種隱式圖走訪的問題,可以用 PFS解決。 #include <bits/stdc++.h> using namespace std; const int MAXN = </bits/stdc++.h>…

UVA 10537 Toll! Revisited ( PFS )

UVa Online Judge 從終點逆推回去更新最小值。具體來說用 Priority First Search,尋找目前還沒用過的擁有最小值的節點來更新它所有可能的前驅點。打印路徑的時候只要反方向( 其實也就是順向 ) 檢查哪些點是可通行的,取其字典序最小慢慢遞進就行了。複雜度…