0w1

Amortized Complexity

CFR 566 F. Clique in the Divisibility Graph ( DP, Math, Complexity Analysis )

Problem - 566F - Codeforces題意: 給一個嚴格遞增序列。求子序列最長長度,子序列滿足所有相鄰元素對,後一個元素可以被前一個整除。資料規模: 序列長度 1 ≤ N ≤ 1e6 元素大小 1 ≤ A[ i ] ≤ 1e6 時限 1000 ms 記憶體 256 MB解法: 注意到 [ 1, N ] 的數的…

CFR Educational 10 C. Foe Pairs ( Amortized Complexity )

Problem - C - Codeforces 每次即時刪除無用的編號( 因為所有編號相異 ),似乎就能夠均攤解決。 #include <bits/stdc++.h> using namespace std; const int MAXN = 3e5 + 5; const int MAXM = 3e5 + 5; typedef long long ll; int n, m; int p[ MAXN ]; set< int > foe[ MAX</bits/stdc++.h>…

CFR 526 C. Om Nom and Candies ( Enumeration )

Problem - C - Codeforces If we can have more than LCM( wr, wb ) candies, not losing generality assuming hr / wr > hb / wb, the optimal solution will take at least many red candies. After processing those, we will have c % lcm( wr, wb ) can…