傳送門
https://codeforces.com/contest/1558
Table of Contents
久違的 Tourist round…
因為 B 題沒做出來，直接又跌成藍名。。。
Problem B. Up the Strip
給定下面的遞推公式：
$f(x) = \sum \limits_{y=1}^{x-1} f(x-y) + \sum \limits_{z=2}^{x} f(\lfloor \frac{x}{z} \rfloor)$
f(1) = 1，求 f(n)。
const int N = int(4e6) + 9;
Int f[N], s[N];
int n;
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
//freopen("/Users/minakokojima/Documents/GitHub/ACM-Training/Workspace/out.txt", "w", stdout);
#endif
RD(n, MOD); f[n] = s[n] = 1;
DWN(i, n, 1) {
f[i] = s[i+1];
//FOR_1(j, 2, i) f[i/j] += f[i];
for (int j=2;i*j<=n;++j) {
int l = i*j, r = min(n+1, l+j);
f[i] += s[l]-s[r];
}
s[i] = s[i+1] + f[i];
}
cout << f[1] << endl;
}
非常 nice 的題。。個人非常喜歡。。。naive 的我只會類似數論分塊的 sqrt 搞法。
但這個方法只能過 div2 的弱化版，比賽時華麗的 TLE 了。
正確的做法是考察相鄰狀態求和過程中的 diff，然後整塊整塊的處理。。
Problem C. Bottom-Tier Reversals
給定一個排列，每次你可以選一個前綴翻轉，問是否能在 5n/2 步數內排序這個排列。
遞歸構造，分情況倒著討論即可，發現恰好至多 5 步可以將規模減小 2，滿足條件。
Problem D. Top-Notch Insertions
計數。問有多少長度為 n 的排列 ai，滿足 ai 的值域為 [1,n] 且，對它執行插入排序時，插入的時刻和位置恰好時給定的 m 個操作。
假設不提供任何插入信息，那麼任意構造一個長度為 n，值域為 [1, n] 的非嚴格單調遞增序列都滿足條件，方案數是經典的 C(2n+1,n)。
（證明，後面的每個數都多一個等號成立的影子狀態，相當於給後面每個位置都累加 1，以保證每個數不相等，構造出從 2n+1 個數里選 n 個數的一一映射。）
那麼如果出現了插入信息，會讓一些位置的等號關係不成立，從而上面的影子狀態變少，假設有 m 個等號不成立，答案就是 C(2n+1-m,n)。
但是提供的插入信息不一定一定會讓 m+=1，有些信息是會重複的。
問題變為使用數據結構維護出等號不成立的位置即可。
標準做法是 Treap 或者 Splay 這種，可以支持在 kth 位置插入一個數的平衡樹結構，注意需要動態離散化。複雜度 O(nlogn)。
Splay + 動態離散化（608ms）
當然也可以使用 rope 卡過去，複雜度 O(nsqrt(n))，使用 rope 的代碼非常之短，就幾行，而且似乎因為是奇妙的可持久化塊狀鏈表結構，甚至不需要動態離散化，
雖然 使用 rope 有可能會帶來不幸，但是哪怕是用來對拍也比暴力要好寫的多。。。
Rush {
r = r0; RD(n); int m = 0; Rush {
int x, y; RD(x, y);
if (r[y] == 0) {
++m;
r.insert(y+1, 1);
} else {
r.insert(y, 0);
}
//REP(i, 10) cout << r[i]; cout <<endl;
}
cout << Binom(n+n-1-m, n) << endl;
}
貌似還有一種做法是倒著做，此時每次插入的位置就是最終的位置，於是可以 樹狀數組 記錄 Offset + 二分答案求 kth，複雜度 O(nlog2n)，實際跑得比平衡樹要快。
樹狀數組(374ms)
Problem E. Down Below
圖論題。給定一個 n 個點 m 條邊的無向圖。（無重邊、無自環、聯通）
你從 1 出發，每個其他點都有一個怪物，怪物有數值 ai 和 bi，當你到達 i 點時，你英雄的 power 必須要 > ai，怪物被消滅，然後 power += bi。
你不可以重複使用一條邊。（訪問後立刻返回）
問要消滅所有的怪物，英雄出發時所需的最少 power 時多少。
n <= 1000, m <= 2000
開始以為是雙連通分量 + 樹 dp。。。但是其實可以直接二分答案，然後迭代，每次用 bfs() 找環即可。
每找到一個環就把環上的點全加到可訪問集合里。我們甚至不需要維護訪問到每個點時的最大 power，因為如果需要 relax… 說明已經出現環了。
邏輯上這個可訪問的集合實際上可以看作是被並查集合併在一起形成的一個 super node，實現上要討論一下找到的環是在外部，還是首位都是這個 super node，雖然邏輯很簡單，但比較容易寫疵。
