CSES PLAN I

因為我跟 peienwu 被揍爛了，於是我們決定寫CSES來增進自己的實力
peienwu CSES補完計畫

目錄

CSES PLAN I

• Introductory Problems
• Sorting and Searching
• Dynamic Programming
• Graph Algorithms

CSES PLAN II

• Range Queries
• Tree Algorithms
• Mathematics
• String Algorithms
• Geometry

CSES PLAN III

• Advanced Techniques

CSES PLAN IV

• Additional Problems

Introductory Problems

Weird Algorithm

暴力

#include <bits/stdc++.h>
#define int long long
using namespace std;

signed main(){
    int n;
    cin >> n;
    cout << n << " ";
    while(n != 1){
        if(n & 1) n = 3 * n + 1;
        else n /= 2;
        cout << n << " ";
    }
    return 0;
}

Missing Number

暴力

#include <bits/stdc++.h>
#define int long long
using namespace std;

signed main(){
    int n, x, sum = 0, tot;
    cin >> n;
    tot = n * (n + 1) / 2;
    while(--n){
        cin >> x;
        sum += x;
    }
    cout << tot - sum;
    return 0;
}

Repetitions

暴力

#include <bits/stdc++.h>
using namespace std;

signed main(){
    string S;
    int sum = 0, ans = 0;
    char lst = 'O';
    cin >> S;
    for(char s : S){
        if(s == lst) sum++;
        else{
            lst = s;
            sum = 1;
        }
        ans = max(ans, sum);
    }
    cout << ans;
    return 0;
}

Increasing Array

暴力

#include <bits/stdc++.h>
#define int long long
using namespace std;

signed main(){
    int n, x, lst = 0, ans = 0;
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> x;
        if(x < lst) ans += lst - x;
        else lst = x;
    }
    cout << ans;
    return 0;
}

Permutations

暴力

#include <bits/stdc++.h>
using namespace std;
array<bool, 1000004> vis;
signed main(){
    int n;
    cin >> n;
    if(n < 4 && n > 1){
        cout << "NO SOLUTION";
        return 0;
    }
    for(int i = n - !(n & 1); i >= 1; i -= 2){
        cout << i << " ";
    }
    for(int i = n - (n & 1); i >= 2; i -= 2){
        cout << i << " ";
    }
    return 0;
}

Number Spiral

數學

#include <bits/stdc++.h>
#define int long long
using namespace std;

signed main(){
    int t, x, y;
    cin >> t;
    while(t--){
        cin >> x >> y;
        if(x > y){
            if(x & 1){
                cout << (x - 1) * (x - 1) + y;
            }else{
                cout << (x - 1) * (x - 1) + (2 * x - y);
            }
        }else{
            if(y & 1){
                cout << (y - 1) * (y - 1) + (2 * y - x);
            }else{
                cout << (y - 1) * (y - 1) + x;
            }
        }
        cout << "\n";
    }
    return 0;
}

Two Knights

數學

#include <bits/stdc++.h>
#define int long long
using namespace std;

signed main(){
    int n;
    cin >> n;
    for(int k = 1; k <= n; k++){
        /*
        all : k^2(k^2 - 1) / 2
        no : 8(k - 2)(k - 1) / 2
         = 4(k - 2)(k - 1)
        */
        cout << k * k * (k * k - 1) / 2 - 4 * (k - 2) * (k - 1) << "\n";
    }
    return 0;
}

Two Sets

暴力

#include <bits/stdc++.h>
#define int long long
using namespace std;
array<bool, 1000004> vis;
void bag(int n){
    int tot = n * (n + 1) / 2, sum = 0, cnt = 0;
    if(tot & 1){
        cout << "NO";
        return;
    }
    cout << "YES\n";
    for(int i = n; i > 0; i--){
        if(sum < tot / 2){
            sum += i;
            vis[i] = 1;
            cnt++;
        }
        if(sum > tot / 2){
            sum -= i;
            vis[i] = 0;
            cnt--;
        }
    }
    cout << cnt << "\n";
    for(int i = 1; i <= n; i++){
        if(vis[i]) cout << i << " ";
    }
    cout << n - cnt << "\n";
    cout << "\n";
    for(int i = 1; i <= n; i++){
        if(!vis[i]) cout << i << " ";
    }
}
signed main(){
    int n;
    cin >> n;
    bag(n);
    return 0;
}

Bit Strings

暴力

#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
int go(int n){
    int k = 1;
    while(n--){
        k <<= 1;
        k %= mod;
    }
    return k;
}
signed main(){
    int n;
    cin >> n;
    cout << go(n);
    return 0;
}

Trailing Zeros

暴力

#include <bits/stdc++.h>
using namespace std;

signed main(){
    int n, f = 5, ans = 0;
    cin >> n;
    for(int i = 1; i < 13; i++){
        ans += n / f;
        f *= 5;
    }
    cout << ans;
    return 0;
}

Coin Piles

數學

#include <bits/stdc++.h>
using namespace std;

signed main(){
    int t, a, b;
    cin >> t;
    while(t--){
        cin >> a >> b;
        if((a + b) % 3 == 0 && a >= b / 2 + b % 2 && b >= a / 2 + a % 2) cout << "YES\n";
        else cout << "NO\n";
    }
    return 0;
}

Palindrome Reorder

暴力

#include <bits/stdc++.h>
using namespace std;
string S;
array<int, 26> C;
array<char, 1000004> ans;
void go(int n){
    int p = 0;
    for(int i = 0; i < n / 2; i++){
        while(C[p] < 2) p++;
        ans[i] = ans[n - 1 - i] = p + 'A';
        C[p] -= 2;
    }
    if(n & 1){
        for(int i = 0; i < 26; i++){
            if(C[i]) ans[n / 2] = i + 'A';
        }
    }
    for(int i = 0; i < n; i++){
        cout << ans[i];
    }
}
signed main(){
    cin >> S;
    int cnt = 0, n;
    n  = S.size();
    for(char s : S){
        C[s - 'A']++;
    }
    for(int c : C){
        cnt += c & 1;
    }
    if(cnt - (n & 1)) cout << "NO SOLUTION";
    else go(n);
    return 0;
}

Gray Code

暴力

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
vector<string> S;
signed main(){
    int n;
    cin >> n;
    S.pb("0");
    S.pb("1");
    for(int i = 2; i < (1 << n); i <<= 1){
        for(int j = i - 1; j >= 0; j--){
            S.pb(S[j]);
        }
        for(int j = 0; j < i; j++){
            S[j] = "0" + S[j];
        }
        for(int j = i; j < 2 * i; j++){
            S[j] = "1" + S[j];
        }
    }
    for(string s : S){
        cout << s << "\n";
    }
    return 0;
}

Tower of Hanoi

遞迴

#include <bits/stdc++.h>
using namespace std;
void go(int n, int s, int t){
    int mid = 6 - s - t;
    if(!n) return;
    go(n - 1, s, mid);
    cout << s << " " << t << "\n";
    go(n - 1, mid, t);
}
signed main(){
    int n;
    cin >> n;
    cout << (1 << n) - 1 << "\n";
    go(n, 1, 3);
    return 0;
}

Creating Strings

暴力

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
array<int, 26> C;
vector<string> SS;
signed main(){
    string S;
    cin >> S;
    for(char s : S){
        C[s - 'a']++;
    }
    S.clear();
    for(int i = 0; i < 26; i++){
        while(C[i]){
            S.pb(i + 'a');
            C[i]--;
        }
    }
    SS.pb(S);
    while(next_permutation(S.begin(), S.end())){
        SS.pb(S);
    }
    cout << SS.size() << "\n";
    for(string s : SS){
        cout << s << "\n";
    }
    return 0;
}

Apple Division

暴力

#include <bits/stdc++.h>
#define int long long
using namespace std;
array<int, 20> P;
int go(int n){
    int a, b, ans = 2e10;
    for(int i = 0; i < 1 << n; i++){
        a = b = 0;
        for(int j = 0; j < n; j++){
            if(i & (1 << j)) a += P[j];
            else b += P[j];
        }
        ans = min(ans, abs(a - b));
    }
    return ans;
}
signed main(){
    int n;
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> P[i];
    }
    cout << go(n);
    return 0;
}

Chessboard and Queens

暴力

#include <bits/stdc++.h>
using namespace std;
array<array<int, 12>, 12> C;
void update(int x, int y, int v){
    for(int i = 1; i <= 8; i++){
        C[x][i] += v;
        C[i][y] += v;
    }
    for(int i = 1; i < 8; i++){
        if(x + i > 8 || y + i > 8) break;
        C[x + i][y + i] += v;
    }
    for(int i = 1; i < 8; i++){
        if(x + i > 8 || y - i < 1) break;
        C[x + i][y - i] += v;
    }
    for(int i = 1; i < 8; i++){
        if(x - i < 1 || y + i > 8) break;
        C[x - i][y + i] += v;
    }
    for(int i = 1; i < 8; i++){
        if(x - i < 1 || y - i < 1) break;
        C[x - i][y - i] += v;
    }
}
int dfs(int n){
    int ans = 0;
    if(!n) return 1;
    for(int i = 1; i <= 8; i++){
        if(C[n][i]) continue;
        update(n, i, 1);
        ans += dfs(n - 1);
        update(n, i, -1);
    }
    return ans;
}
signed main(){
    char c;
    for(int i = 1; i <= 8; i++){
        for(int j = 1; j <= 8; j++){
            cin >> c;
            if(c == '*') C[i][j]++;
        }
    }
    cout << dfs(8);
    return 0;
}

Digit Queries

數學

#include <bits/stdc++.h>
#define int long long
using namespace std;
int pwr(int x, int k){
    int v = 1;
    for(int i = 1; i <= 18; i <<= 1){
        if(k & i) v *= x;
        x *= x;
    }
    return v;
}
int dig(int k){
    int n = 1, ans;
    while(k > 9 * n * pwr(10, n - 1)){
        k -= 9 * n * pwr(10, n - 1);
        n++;
    }
    ans = pwr(10, n - 1) + (k - 1) / n;
    k = (k - 1) % n;
    ans = (ans / pwr(10, n - k - 1)) % 10;
    return ans;
}
signed main(){
    int q, k;
    cin >> q;
    while(q--){
        cin >> k;
        cout << dig(k) << "\n";
    }
    return 0;
}

Grid Paths

暴力 DFS

#include <bits/stdc++.h>
using namespace std;
array<char, 48> S;
array<array<bool, 9>, 9> vis;
int ans = 0;
void dfs(int x, int y, int s){
    if(x < 1 || y < 1 || x > 7 || y > 7 || vis[x][y]) return;
    if(x == 1 && y == 7){
        if(s == 48) ans++;
        return;
    }
    if(!vis[x - 1][y] && !vis[x + 1][y] && vis[x][y - 1] && vis[x][y + 1]) return;
    if(vis[x - 1][y] && vis[x + 1][y] && !vis[x][y - 1] && !vis[x][y + 1]) return;
    vis[x][y] = 1;
    if(S[s] == '?' || S[s] == 'L') dfs(x - 1, y, s + 1);
    if(S[s] == '?' || S[s] == 'R') dfs(x + 1, y, s + 1);
    if(S[s] == '?' || S[s] == 'U') dfs(x, y - 1, s + 1);
    if(S[s] == '?' || S[s] == 'D') dfs(x, y + 1, s + 1);
    vis[x][y] = 0;
}
signed main(){
    for(int i = 0; i < 48; i++){
        cin >> S[i];
    }
    for(int i = 1; i <= 7; i++){
        vis[0][i] = 1;
        vis[i][0] = 1;
        vis[8][i] = 1;
        vis[i][8] = 1;
    }
    dfs(1, 1, 0);
    cout << ans;
    return 0;
}

Sorting and Searching

Distinct Numbers

排序

#include <bits/stdc++.h>
using namespace std;
array<int, 200004> X;
signed main(){
    int n, lst = 0, ans = 0;
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> X[i];
    }
    sort(X.begin(), X.begin() + n);
    for(int i = 0; i < n; i++){
        if(X[i] != lst) ans++;
        lst = X[i];
    }
    cout << ans;
    return 0;
}

Apartments

排序 雙指針

#include <bits/stdc++.h>
using namespace std;
array<int, 200004> A, B;
signed main(){
    int n, m, k, p = 0, ans = 0;
    cin >> n >> m >> k;
    for(int i = 0; i < n; i++){
        cin >> A[i];
    }
    for(int i = 0; i < m; i++){
        cin >> B[i];
    }
    sort(A.begin(), A.begin() + n);
    sort(B.begin(), B.begin() + m);
    for(int i = 0; i < n; i++){
        while(p < m && abs(B[p] - A[i]) > k && B[p] < A[i] + k) p++;
        if(p < m && abs(B[p] - A[i]) <= k){
            ans++;
            p++;
        }
    }
    cout << ans;
    return 0;
}

Ferris Wheel

排序 雙指針

#include <bits/stdc++.h>
using namespace std;
array<int, 200004> P;
signed main(){
    int n, x, p, ans = 0;
    cin >> n >> x;
    for(int i = 0; i < n; i++){
        cin >> P[i];
    }
    sort(P.begin(), P.begin() + n);
    p = n - 1;
    for(int i = 0; i <= p; i++){
        while(i < p && P[p] + P[i] > x){
            p--;
            ans++;
        }
        if(i >= p || (i < p && P[p] + P[i] <= x)){
            p--;
            ans++;
        }
    }
    cout << ans;
    return 0;
}

Concert Tickets

Set

#include <bits/stdc++.h>
using namespace std;
multiset<int> H;
signed main(){
    int n, m, h, t;
    cin >> n >> m;
    for(int i = 0; i < n; i++){
        cin >> h;
        H.insert(h);
    }
    for(int i = 0; i < m; i++){
        cin >> t;
        if(H.upper_bound(t) == H.begin()) cout << "-1\n";
        else{
            cout << *--H.upper_bound(t) << "\n";
            H.erase(--H.upper_bound(t));
        }
    }
    return 0;
}

Restaurant Customers

排序

#include <bits/stdc++.h>
#define pb push_back
#define pii pair<int, int>
#define ff first
#define ss second
using namespace std;
vector<pii> P;
signed main(){
    int n, l, r, now = 0, ans = 0;
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> l >> r;
        P.pb({l, 1});
        P.pb({r, -1});
    }
    sort(P.begin(), P.end());
    for(pii p : P){
        now += p.ss;
        ans = max(ans, now);
    }
    cout << ans;
    return 0;
}

Movie Festival

排序

#include <bits/stdc++.h>
#define pii pair<int, int>
#define ff first
#define ss second
using namespace std;
bool cmp(pii a, pii b){
    if(a.ss != b.ss) return a.ss < b.ss;
    return a.ff < b.ff;
}
array<pii, 200004> P;
signed main(){
    int n, l, r, ans = 0;
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> l >> r;
        P[i] = {l, r};
    }
    sort(P.begin(), P.begin() + n, cmp);
    l = 0;
    for(pii p : P){
        if(p.ff >= l){
            ans++;
            l = p.ss;
        }
    }
    cout << ans;
    return 0;
}

Sum of Two Values

Set Map

#include <bits/stdc++.h>
using namespace std;
set<int> A;
map<int, int> M;
signed main(){
    int n, x, a;
    bool ans = 0;
    cin >> n >> x;
    for(int i = 1; i <= n; i++){
        cin >> a;
        if(A.lower_bound(x - a) != A.end()){
            if(*A.lower_bound(x - a) == x - a){
                ans = 1;
                cout << i << " " << M[x - a];
                break;
            }
        }
        A.insert(a);
        M[a] = i;
    }
    if(!ans) cout << "IMPOSSIBLE";
    return 0;
}

Maximum Subarray Sum

Greedy

#include <bits/stdc++.h>
#define int long long
using namespace std;

signed main(){
    int n, ans = -1e18, sum = 0, x;
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> x;
        sum += x;
        ans = max(ans, sum);
        if(sum < 0) sum = 0;
    }
    cout << ans;
    return 0;
}

Stick Lengths

二分搜

#include <bits/stdc++.h>
#define int long long
using namespace std;
array<int, 200004> P;
int cost(int n, int k){
    int sum = 0;
    for(int i = 0; i < n; i++){
        sum += labs(k - P[i]);
    }
    return sum;
}
int BS(int n){
    int l = 1, r = 1e9, mid;
    while(l != r){
        mid = (l + r) / 2;
        if(cost(n, mid) < cost(n, mid + 1)) r = mid;
        else l = mid + 1;
    }
    return cost(n, l);
}
signed main(){
    int n;
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> P[i];
    }
    cout << BS(n);
    return 0;
}

Missing Coin Sum

排序

#include <bits/stdc++.h>
#define int long long
using namespace std;
array<int, 200004> X;
signed main(){
    int n, sum = 0;
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> X[i];
    }
    sort(X.begin(), X.begin() + n);
    for(int i = 0; i < n; i++){
        if(X[i] > sum + 1){
            cout << sum + 1;
            return 0;
        }
        sum += X[i];
    }
    cout << sum + 1;
    return 0;
}

Collecting Numbers

暴力

#include <bits/stdc++.h>
using namespace std;
array<int, 200004> X;
signed main(){
    int n, x, ans = 1;
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> x;
        X[x] = i;
    }
    for(int i = 1; i <= n; i++){
        ans += X[i] < X[i - 1];
    }
    cout << ans;
    return 0;
}

Collecting Numbers II

暴力

#include <bits/stdc++.h>
using namespace std;
array<int, 200004> X, P;
int check(int a, int b){
    int sum = 0;
    if(X[a - 1] > X[a]) sum++;
    if(X[a + 1] < X[a]) sum++;
    if(X[b - 1] > X[b]) sum++;
    if(X[b + 1] < X[b]) sum++;
    if(a - b == 1 && X[a] < X[b]) sum--;
    if(b - a == 1 && X[b] < X[a]) sum--;
    return sum;
}
signed main(){
    int n, m, a, b, x, ans = 1;
    cin >> n >> m;
    X[n + 1] = n + 1;
    for(int i = 1; i <= n; i++){
        cin >> x;
        P[i] = x;
        X[x] = i;
    }
    for(int i = 1; i <= n; i++){
        ans += X[i] < X[i - 1];
    }
    while(m--){
        cin >> a >> b;
        swap(P[a], P[b]);
        a = P[a], b = P[b];
		ans -= check(a, b);
		swap(X[a], X[b]);
		ans += check(a, b);
        cout << ans << "\n";
    }
    return 0;
}

Playlist

Set

#include <bits/stdc++.h>
using namespace std;
set<int> S;
array<int, 200004> K;
signed main(){
    int n, ans = 0, p = 0;
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> K[i];
        while(S.find(K[i]) != S.end()){
            S.erase(K[p++]);
        }
        S.insert(K[i]);
        ans = max(ans, i - p + 1);
    }
    cout << ans;
    return 0;
}

Towers

Set

#include <bits/stdc++.h>
using namespace std;
multiset<int> T;
signed main(){
    int n, k;
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> k;
        if(T.upper_bound(k) != T.end()){
            T.erase(T.upper_bound(k));
        }
        T.insert(k);
    }
    cout << T.size();
    return 0;
}

Traffic Lights

Set

#include <bits/stdc++.h>
using namespace std;
set<int> T;
multiset<int> dis;
signed main(){
    int x, n, p, l, r;
    cin >> x >> n;
    dis.insert(x);
    T.insert(0);
    T.insert(x);
    for(int i = 0; i < n; i++){
        cin >> p;
        l = 0, r = x;
        auto it = T.upper_bound(p);
        r = *it;
        l = *--it;
        dis.erase(dis.find(r - l));
        dis.insert(r - p);
        dis.insert(p - l);
        T.insert(p);
        cout << *--dis.end() << " ";
    }
    return 0;
}

Josephus Problem I

BIT

#include <bits/stdc++.h>
using namespace std;
array<int, 200004> BIT;
void update(int p, int x){
    for(; p < 200004; p += p & -p){
        BIT[p] += x;
    }
}
int query(int p){
    int sum = 0;
    for(; p > 0; p -= p & -p){
        sum += BIT[p];
    }
    return sum;
}
int find(int x){
    int p = 0, sum = 0;
    for(int i = (1 << 17); i > 0; i >>= 1){
        if(p + i < 200004 && sum + BIT[p + i] < x){
            p += i;
            sum += BIT[p];
        }
    }
    return p + 1;
}
signed main(){
    int n, now, p;
    cin >> n;
    p = n;
    now = 0;
    for(int i = 1; i <= n; i++){
        update(i, 1);
    }
    while(p > 1){
        now = find((query(now) + 1) % query(n) + 1);
        cout << now << " ";
        update(now, -1);
        p--;
    }
    cout << find(1);
    return 0;
}

Josephus Problem II

BIT

#include <bits/stdc++.h>
using namespace std;
array<int, 200004> BIT;
void update(int p, int x){
    for(; p < 200004; p += p & -p){
        BIT[p] += x;
    }
}
int query(int p){
    int sum = 0;
    for(; p > 0; p -= p & -p){
        sum += BIT[p];
    }
    return sum;
}
int find(int x){
    int p = 0, sum = 0;
    for(int i = (1 << 17); i > 0; i >>= 1){
        if(p + i < 200004 && sum + BIT[p + i] < x){
            p += i;
            sum += BIT[p];
        }
    }
    return p + 1;
}
signed main(){
    int n, now, p, k;
    cin >> n >> k;
    p = n;
    now = 0;
    for(int i = 1; i <= n; i++){
        update(i, 1);
    }
    while(p > 1){
        now = find((query(now) + k) % query(n) + 1);
        cout << now << " ";
        update(now, -1);
        p--;
    }
    cout << find(1);
    return 0;
}

Nested Ranges Check

排序 BIT

#include <bits/stdc++.h>
#define pb push_back
#define pii pair<int, int>
#define ff first
#define ss second
using namespace std;
struct rng{
    int l, r, t;
};
array<int, 200004> BIT, ans;
array<rng, 200004> R;
vector<pii> X, Y;
bool cmp(rng a, rng b){
    if(a.l != b.l) return a.l < b.l;
    return a.r > b.r;
}
void reset(){
    for(int &b : BIT) b = 0;
}
void update(int p){
    for(; p < 200004; p += p & -p){
        BIT[p]++;
    }
}
int query(int p){
    int sum = 0;
    for(; p > 0; p -= p & -p){
        sum += BIT[p];
    }
    return sum;
}
signed main(){
    int n, x, y, lst = 0, cnt = 0;
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> x >> y;
        X.pb({x, i});
        Y.pb({y, i});
        R[i].t = i;
    }
    sort(X.begin(), X.end());
    sort(Y.begin(), Y.end());
    for(pii p : X){
        if(p.ff != lst) cnt++;
        R[p.ss].l = cnt;
        lst = p.ff;
    }
    lst = cnt = 0;
    for(pii p : Y){
        if(p.ff != lst) cnt++;
        R[p.ss].r = cnt;
        lst = p.ff;
    }
    sort(R.begin(), R.begin() + n, cmp);
    for(int i = n - 1; i >= 0; i--){
        ans[R[i].t] = query(R[i].r);
        update(R[i].r);
    }
    for(int i = 0; i < n; i++){
        cout << !!ans[i] << " ";
        ans[i] = 0;
    }
    cout << "\n";
    reset();
    for(int i = 0; i < n; i++){
        ans[R[i].t] = query(200001) - query(R[i].r - 1);
        update(R[i].r);
    }
    for(int i = 0; i < n; i++){
        cout << !!ans[i] << " ";
    }
    return 0;
}

Nested Ranges Count

排序 BIT

#include <bits/stdc++.h>
#define pb push_back
#define pii pair<int, int>
#define ff first
#define ss second
using namespace std;
struct rng{
    int l, r, t;
};
array<int, 200004> BIT, ans;
array<rng, 200004> R;
vector<pii> X, Y;
bool cmp(rng a, rng b){
    if(a.l != b.l) return a.l < b.l;
    return a.r > b.r;
}
void reset(){
    for(int &b : BIT) b = 0;
}
void update(int p){
    for(; p < 200004; p += p & -p){
        BIT[p]++;
    }
}
int query(int p){
    int sum = 0;
    for(; p > 0; p -= p & -p){
        sum += BIT[p];
    }
    return sum;
}
signed main(){
    int n, x, y, lst = 0, cnt = 0;
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> x >> y;
        X.pb({x, i});
        Y.pb({y, i});
        R[i].t = i;
    }
    sort(X.begin(), X.end());
    sort(Y.begin(), Y.end());
    for(pii p : X){
        if(p.ff != lst) cnt++;
        R[p.ss].l = cnt;
        lst = p.ff;
    }
    lst = cnt = 0;
    for(pii p : Y){
        if(p.ff != lst) cnt++;
        R[p.ss].r = cnt;
        lst = p.ff;
    }
    sort(R.begin(), R.begin() + n, cmp);
    for(int i = n - 1; i >= 0; i--){
        ans[R[i].t] = query(R[i].r);
        update(R[i].r);
    }
    for(int i = 0; i < n; i++){
        cout << ans[i] << " ";
        ans[i] = 0;
    }
    cout << "\n";
    reset();
    for(int i = 0; i < n; i++){
        ans[R[i].t] = query(200001) - query(R[i].r - 1);
        update(R[i].r);
    }
    for(int i = 0; i < n; i++){
        cout << ans[i] << " ";
    }
    return 0;
}

Room Allocation

排序

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
struct day{
    int t, c, p;
};
priority_queue<int, vector<int>, greater<int>> Q;
array<int, 200004> R;
vector<day> C;
bool cmp(day a, day b){
    if(a.t != b.t) return a.t < b.t;
    return a.c > b.c;
}
signed main(){
    int n, l, r, now = 0, ans = 0;
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> l >> r;
        C.pb({l, 1, i});
        C.pb({r, -1, i});
        Q.push(i);
    }
    sort(C.begin(), C.end(), cmp);
    for(day d : C){
        if(d.c > 0){
            R[d.p] = Q.top();
            Q.pop();
        }else{
            Q.push(R[d.p]);
        }
        now += d.c;
        ans = max(ans, now);
    }
    cout << ans << "\n";
    for(int i = 1; i <= n; i++){
        cout << R[i] << " ";
    }
    return 0;
}

Factory Machines

二分搜

#include <bits/stdc++.h>
#define int long long
using namespace std;
array<int, 200004> T;
int run(int n, int t){
    int sum = 0;
    for(int i = 0; i < n; i++){
        sum += t / T[i];
    }
    return sum;
}
int BS(int n, int k){
    int l = 0, r = 1e18 / n, mid;
    r += r / n;
    while(l != r){
        mid = (l + r) / 2;
        if(run(n, mid) < k) l = mid + 1;
        else r = mid;
    }
    return l;
}
signed main(){
    int n, k;
    cin >> n >> k;
    for(int i = 0; i < n; i++){
        cin >> T[i];
    }
    cout << BS(n, k);
    return 0;
}

Tasks and Deadlines

Greedy

#include <bits/stdc++.h>
#define int long long
#define pii pair<int, int>
#define ff first
#define ss second
using namespace std;
array<pii, 200004> T;
signed main(){
    int n, a, d, now = 0, ans = 0;
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> a >> d;
        T[i] = {a, d};
    }
    sort(T.begin(), T.begin() + n);
    for(int i = 0; i < n; i++){
        now += T[i].ff;
        ans += T[i].ss - now;
    }
    cout << ans;
    return 0;
}

Reading Books

數學

#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
    int n, sum = 0, lng = 0, t;
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> t;
        sum += t;
        lng = max(lng, t);
    }
    if(lng * 2 < sum) cout << sum;
    else cout << 2 * lng;
    return 0;
}

Sum of Three Values

Map

#include <bits/stdc++.h>
using namespace std;
array<int, 5004> A;
map<int, int> M;
signed main(){
    int n, x;
    cin >> n >> x;
    for(int i = 1; i <= n; i++){
        cin >> A[i];
    }
    for(int i = 1; i <= n; i++){
        for(int j = i + 1; j <= n; j++){
            if(M.find(x - A[i] - A[j]) != M.end()){
                cout << M[x - A[i] - A[j]] << " " << i << " " << j;
                return 0;
            }
        }
        M[A[i]] = i;
    }
    cout << "IMPOSSIBLE";
    return 0;
}

Sum of Four Values

排序 雙指針

#include <bits/stdc++.h>
using namespace std;
struct s{
    int v, i, j;
};
array<int, 1004> A;
array<s, 1000004> S;
bool cmp(s a, s b){
    return a.v < b.v;
}
signed main(){
    int n, x, cnt = 0, p;
    cin >> n >> x;
    for(int i = 1; i <= n; i++){
        cin >> A[i];
    }
    for(int i = 1; i <= n; i++){
        for(int j = i + 1; j <= n; j++){
            S[cnt++] = {A[i] + A[j], i, j};
        }
    }
    sort(S.begin(), S.begin() + cnt, cmp);
    p = cnt - 1;
    for(int i = 0; i < p; i++){
        while(S[i].v + S[p].v > x) p--;
        while(S[i].v + S[p].v == x && (S[i].i == S[p].i || S[i].i == S[p].j || S[i].j == S[p].i || S[i].j == S[p].j)) p--;
        if(S[i].v + S[p].v == x){
            cout << S[i].i << " " << S[i].j << " " << S[p].i << " " << S[p].j;
            return 0;
        }
    }
    cout << "IMPOSSIBLE";
    return 0;
}

Nearest Smaller Values

Monoton Stack

#include <bits/stdc++.h>
#define pii pair<int, int>
#define ff first
#define ss second
using namespace std;

signed main(){
    int n, x;
    stack<pii> S;
    cin >> n;
    S.push({0, 0});
    for(int i = 1; i <= n; i++){
        cin >> x;
        while(x <= S.top().ff) S.pop();
        cout << S.top().ss << " ";
        S.push({x, i});
    }
    return 0;
}

Subarray Sums I

雙指針

#include <bits/stdc++.h>
using namespace std;
array<int, 200004> A;
signed main(){
    int n, x, p = 0, sum = 0, ans = 0;
    cin >> n >> x;
    for(int i = 0; i < n; i++){
        cin >> A[i];
        sum += A[i];
        while(sum > x){
            sum -= A[p++];
        }
        if(sum == x) ans++;
    }
    cout << ans;
    return 0;
}

Subarray Sums II

Map

#include <bits/stdc++.h>
#define int long long
using namespace std;
map<int, int> M;
signed main(){
    int n, x, a, sum = 0, ans = 0;
    cin >> n >> x;
    M[0]++;
    for(int i = 0; i < n; i++){
        cin >> a;
        sum += a;
        ans += M[sum - x];
        M[sum]++;
    }
    cout << ans;
    return 0;
}

Subarray Divisibility

暴力

#include <bits/stdc++.h>
#define int long long
using namespace std;
array<int, 200004> mod;
signed main(){
    int n, a, sum = 0, ans = 0;
    cin >> n;
    mod[0]++;
    for(int i = 0; i < n; i++){
        cin >> a;
        sum += a;
        mod[((sum % n) + n) % n]++;
    }
    for(int i = 0; i < n; i++){
        ans += (mod[i] * (mod[i] - 1)) / 2;
    }
    cout << ans;
    return 0;
}

Subarray Distinct Values

雙指針

#include <bits/stdc++.h>
#define int long long
using namespace std;
array<int, 200004> X;
map<int, int> M;
signed main(){
    int n, k, p = 0, now = 0, ans = 0;
    cin >> n >> k;
    for(int i = 0; i < n; i++){
        cin >> X[i];
        if(M[X[i]] == 0) now++;
        M[X[i]]++;
        while(now > k){
            M[X[p]]--;
            if(M[X[p]] == 0) now--;
            p++;
        }
        ans += i - p + 1;
    }
    cout << ans;
    return 0;
}

Array Division

二分搜

#include <bits/stdc++.h>
#define int long long
using namespace std;
array<int, 200004> X;
int cost(int n, int x){
    int k = 1, sum = 0;
    for(int i = 0; i < n; i++){
        if(X[i] > x) return 1e9;
        if(sum + X[i] > x){
            k++;
            sum = 0;
        }
        sum += X[i];
    }
    return k;
}
int BS(int n, int k){
    int l = 0, r = 2e14, mid;
    while(l != r){
        mid = (l + r) / 2;
        if(cost(n, mid) > k) l = mid + 1;
        else r = mid;
    }
    return l;
}
signed main(){
    int n, k;
    cin >> n >> k;
    for(int i = 0; i < n; i++){
        cin >> X[i];
    }
    cout << BS(n, k);
    return 0;
}

Sliding Median

排序 Map BIT 雙指針

#include <bits/stdc++.h>
using namespace std;
map<int, int> M;
array<int, 200004> X, L, BIT, m;
void update(int p, int x){
    for(; p < 200004; p += p & -p){
        BIT[p] += x;
    }
}
int find(int x){
    int sum = 0, p = 0;
    for(int i = (1 << 17); i > 0; i >>= 1){
        if(p + i < 200004 && sum + BIT[p + i] < x){
            p += i;
            sum += BIT[p];
        }
    }
    return p + 1;
}
signed main(){
    int n, k, cnt = 0, lst = 0;
    cin >> n >> k;
    for(int i = 0; i < n; i++){
        cin >> X[i];
        L[i] = X[i];
    }
    sort(L.begin(), L.begin() + n);
    for(int i = 0; i < n; i++){
        if(L[i] != lst) cnt++;
        M[L[i]] = cnt;
        m[cnt] = L[i];
        lst = L[i];
    }
    for(int i = 0; i < k; i++){
        update(M[X[i]], 1);
    }
    cout << m[find(k / 2 + (k % 2))] << " ";
    for(int i = k; i < n; i++){
        update(M[X[i]], 1);
        update(M[X[i - k]], -1);
        cout << m[find(k / 2 + (k % 2))] << " ";
    }
    return 0;
}

Sliding Cost

排序 Map BIT 雙指針

#include <bits/stdc++.h>
#define pii pair<int, int>
#define ff first
#define ss second
#define int long long
using namespace std;
map<int, int> M;
array<int, 200004> X;
array<pii, 200004> L;
array<int, 200004> B, C;
void update(int p, int x){
    for(; p < 200004; p += p & -p){
        B[p] += x / abs(x);
        C[p] += x;
    }
}
int query(int p){
    int sum = 0;
    for(; p > 0; p -= p & -p){
        sum += C[p];
    }
    return sum;
}
int find(int x){
    int sum = 0, p = 0;
    for(int i = (1 << 17); i > 0; i >>= 1){
        if(p + i < 200004 && sum + B[p + i] < x){
            p += i;
            sum += B[p];
        }
    }
    return p + 1;
}
signed main(){
    int n, k, cnt = 0, p;
    cin >> n >> k;
    for(int i = 0; i < n; i++){
        cin >> X[i];
        L[i] = {X[i], i};
    }
    sort(L.begin(), L.begin() + n);
    for(int i = 0; i < n; i++){
        cnt++;
        M[L[i].ss] = cnt;
    }
    for(int i = 0; i < k; i++){
        update(M[i], X[i]);
    }
    p = find(k / 2 + (k % 2));
    if(k & 1) cout << query(200001) - query(p) - query(p - 1) << " ";
    else cout << query(200001) - 2 * query(p) << " ";
    for(int i = k; i < n; i++){
        update(M[i], X[i]);
        update(M[i - k], -X[i - k]);
        p = find(k / 2 + (k % 2));
        if(k & 1) cout << query(200001) - query(p) - query(p - 1) << " ";
        else cout << query(200001) - 2 * query(p) << " ";
    }
    return 0;
}

Movie Festival II

Set 排序

#include <bits/stdc++.h>
#define pb push_back
#define pii pair<int, int>
#define ff first
#define ss second
using namespace std;
bool cmp(pii a, pii b){
    if(a.ss != b.ss) return a.ss < b.ss;
    return a.ff < b.ff;
}
vector<pii> M;
multiset<int> F;
signed main(){
    int n, k, ans = 0, l, r, siz = 0;
    cin >> n >> k;
    for(int i = 0; i < n; i++){
        cin >> l >> r;
        M.pb({l, r});
    }
    sort(M.begin(), M.end(), cmp);
    for(int i = 0; i < k; i++){
        F.insert(0);
    }
    for(pii m : M){
        auto it = F.upper_bound(m.ff);
        if(it == F.begin()) continue;
        F.erase(--it);
        F.insert(m.ss);
        ans++;
    }
    cout << ans;
    return 0;
}

Maximum Subarray Sum II

Monoton Deque

#include <bits/stdc++.h>
#define int long long
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define pii pair<int, int>
#define ff first
#define ss second
using namespace std;
deque<pii> Q;
array<int, 200004> S;
signed main(){
    int n, a, b, x, ans = -1e18;
    cin >> n >> a >> b;
    for(int i = 1; i <= n; i++){
        cin >> x;
        S[i] = x + S[i - 1];
        if(!Q.empty() && Q.front().ss < i - b) Q.ppf();
        while(i >= a && !Q.empty() && S[i - a] < Q.back().ff) Q.ppb();
        if(i >= a) Q.pb({S[i - a], i - a});
        if(!Q.empty()) ans = max(ans, S[i] - Q.front().ff);
    }
    cout << ans;
    return 0;
}

Dynamic Programming

Dice Combinations

DP

#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
array<int, 1000004> dp;
int DP(int n){
    dp[0] = 1;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= min(i, 6); j++){
            dp[i] += dp[i - j];
            dp[i] %= mod;
        }
    }
    return dp[n];
}
signed main(){
    int n;
    cin >> n;
    cout << DP(n);
    return 0;
}

Minimizing Coins

DP

#include <bits/stdc++.h>
using namespace std;
const int inf = 1e6 + 1;
array<int, 104> C;
array<int, 1000004> dp;
int DP(int x){
    for(int i = 1; i <= x; i++){
        dp[i] = inf;
        for(int c : C){
            if(c > i) continue;
            dp[i] = min(dp[i], dp[i - c] + 1);
        }
    }
    return dp[x] == inf? -1 : dp[x];
}
signed main(){
    int n, x;
    cin >> n >> x;
    for(int i = 0; i < n; i++){
        cin >> C[i];
    }
    cout << DP(x);
    return 0;
}

Coin Combinations I

DP

#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
array<int, 104> C;
array<int, 1000004> dp;
int DP(int x){
    dp[0] = 1;
    for(int i = 1; i <= x; i++){
        for(int c : C){
            if(c > i || !c) continue;
            dp[i] += dp[i - c];
            dp[i] %= mod;
        }
    }
    return dp[x];
}
signed main(){
    int n, x;
    cin >> n >> x;
    for(int i = 0; i < n; i++){
        cin >> C[i];
    }
    cout << DP(x);
    return 0;
}

Coin Combinations II

DP

#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
array<int, 104> C;
array<int, 1000004> dp;
int DP(int x){
    dp[0] = 1;
    for(int c : C){
        if(!c) break;
        for(int i = 1; i <= x; i++){
            if(i < c) continue;
            dp[i] += dp[i - c];
            dp[i] %= mod;
        }
    }
    return dp[x];
}
signed main(){
    int n, x;
    cin >> n >> x;
    for(int i = 0; i < n; i++){
        cin >> C[i];
    }
    cout << DP(x);
    return 0;
}

Removing Digits

DP

#include <bits/stdc++.h>
using namespace std;
const int inf = 1e6;
array<int, 1000004> dp;
int DP(int n){
    int t;
    for(int i = 1; i <= n; i++){
        dp[i] = inf;
        t = i;
        while(t > 0){
            dp[i] = min(dp[i], dp[i - t % 10] + 1);
            t /= 10;
        }
    }
    return dp[n];
}
signed main(){
    int n;
    cin >> n;
    cout << DP(n);
    return 0;
}

Grid Paths

DP

#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
array<array<char, 1004>, 1004> G;
array<array<int, 1004>, 1004> dp;
int DP(int i, int j){
    if(dp[i][j]) return dp[i][j];
    if(!i || !j || G[i][j] == '*') return 0;
    G[i][j] = '*';
    return dp[i][j] = (DP(i, j - 1) + DP(i - 1, j)) % mod;
}
signed main(){
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            cin >> G[i][j];
        }
    }
    dp[1][1] = G[1][1] == '*'? 0 : 1;
    cout << DP(n, n);
    return 0;
}

Book Shop

背包

#include <bits/stdc++.h>
using namespace std;
array<int, 1004> H, S;
array<int, 100004> dp;
int bag(int n, int x){
    int ans = 0;
    for(int j = 0; j < n; j++){
        for(int i = x; i >= H[j]; i--){
            dp[i] = max(dp[i], dp[i - H[j]] + S[j]);
            ans = max(ans, dp[i]);
        }
    }
    return ans;
}
signed main(){
    int n, x;
    cin >> n >> x;
    for(int i = 0; i < n; i++){
        cin >> H[i];
    }
    for(int i = 0; i < n; i++){
        cin >> S[i];
    }
    cout << bag(n, x);
    return 0;
}

Array Description

DP

#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
array<int, 100004> X;
array<array<int, 104>, 100004> dp;
int DP(int n, int m){
    int ans = 0;
    for(int i = 2; i <= n; i++){
        if(X[i]){
            for(int k = -1; k <= 1; k++){
                dp[i][X[i]] += dp[i - 1][X[i] + k];
                dp[i][X[i]] %= mod;
            }
        }else{
            for(int j = 1; j <= m; j++){
                for(int k = -1; k <= 1; k++){
                    dp[i][j] += dp[i - 1][j + k];
                    dp[i][j] %= mod;
                }
            }
        }
    }
    for(int i = 1; i <= m; i++){
        ans += dp[n][i];
        ans %= mod;
    }
    return ans;
}
signed main(){
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        cin >> X[i];
    }
    if(X[1]) dp[1][X[1]] = 1;
    else{
        for(int i = 1; i <= m; i++){
            dp[1][i] = 1;
        }
    }
    cout << DP(n, m);
    return 0;
}

Counting Towers

DP

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 1e9 + 7;
array<array<int, 8>, 1000004> dp;
void DP(){
    /*
    _|_ = 0, 2, 4
    */
    dp[0][7] = dp[0][5] = 1;
    for(int i = 1; i <= 1e6; i++){
        dp[i][0] = (dp[i - 1][0] + dp[i - 1][5]) % mod;
        dp[i][2] = (dp[i - 1][7] + dp[i - 1][3] + dp[i - 1][2] + dp[i - 1][6]) % mod;
        dp[i][3] = (dp[i - 1][7] + dp[i - 1][3] + dp[i - 1][2] + dp[i - 1][6]) % mod;
        dp[i][5] = (dp[i - 1][7] + dp[i - 1][3] + dp[i - 1][2] + dp[i - 1][6] + dp[i - 1][5] + dp[i - 1][0]) % mod;
        dp[i][6] = (dp[i - 1][7] + dp[i - 1][3] + dp[i - 1][2] + dp[i - 1][6]) % mod;
        dp[i][7] = (dp[i - 1][7] + dp[i - 1][3] + dp[i - 1][2] + dp[i - 1][6] + dp[i - 1][5] + dp[i - 1][0]) % mod;
    }
}
signed main(){
    int t, n;
    cin >> t;
    DP();
    while(t--){
        cin >> n;
        cout << dp[n][5] << "\n";
    }
    return 0;
}

Edit Distance

DP

#include <bits/stdc++.h>
using namespace std;
string A, B;
array<array<bool, 5004>, 5004> vis;
array<array<int, 5004>, 5004> dp;
int ED(int i, int j){
    if(!i || !j) return max(i, j);
    if(vis[i][j]) return dp[i][j];
    vis[i][j] = 1;
    if(A[i - 1] == B[j - 1]) return dp[i][j] = ED(i - 1, j - 1);
    return dp[i][j] = min({ED(i - 1, j - 1), ED(i - 1, j), ED(i, j - 1)}) + 1;
}
signed main(){
    cin >> A >> B;
    cout << ED(A.size(), B.size());
    return 0;
}

Rectangle Cutting

DP

#include <bits/stdc++.h>
using namespace std;
const int inf = 25e4;
array<array<int, 504>, 504> dp;
int DP(int a, int b){
    for(int i = 1; i <= a; i++){
        for(int j = 1; j <= b; j++){
            if(i == j) continue;
            dp[i][j] = inf;
            for(int k = 1; k < i; k++){
                dp[i][j] = min(dp[i][j], dp[k][j] + dp[i - k][j] + 1);
            }
            for(int k = 1; k < j; k++){
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[i][j - k] + 1);
            }
        }
    }
    return dp[a][b];
}
signed main(){
    int a, b;
    cin >> a >> b;
    cout << DP(a, b);
    return 0;
}

Money Sums

DP

#include <bits/stdc++.h>
using namespace std;
array<int, 104> X;
array<bool, 100004> dp;
void DP(int n){
    int cnt = 0;
    dp[0] = 1;
    for(int x : X){
        for(int i = n; i >= x; i--){
            dp[i] |= dp[i - x];
        }
    }
    for(int i = 1; i <= n; i++){
        cnt += dp[i];
    }
    cout << cnt << "\n";
    for(int i = 1; i <= n; i++){
        if(dp[i]) cout << i << " ";
    }
}
signed main(){
    int n, sum = 0;
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> X[i];
        sum += X[i];
    }
    DP(sum);
    return 0;
}

Removal Game

DP 賽局

#include <bits/stdc++.h>
#define int long long
using namespace std;
struct pii{
    int ff, ss;
    pii(){ff = ss = 0;};
    pii(int f, int s): ff(f), ss(s){}
    pii operator+(pii p){
        return pii(ff + p.ff, ss + p.ss);
    }
};
array<int, 5004> X;
array<array<pii, 5004>, 5004> dp;
pii maxf(pii a, pii b){
    if(a.ff > b.ff) return a;
    return b;
}
pii maxs(pii a, pii b){
    if(a.ss > b.ss) return a;
    return b;
}
pii play(int i, int j, int p){
    if(i > j) return {0, 0};
    if(dp[i][j].ff && dp[i][j].ss) return dp[i][j];
    if(!p){
        return dp[i][j] = maxf(play(i + 1, j, 1) + pii(X[i], 0), play(i, j - 1, 1) + pii(X[j], 0));
    }else{
        return dp[i][j] = maxs(play(i + 1, j, 0) + pii(0, X[i]), play(i, j - 1, 0) + pii(0, X[j]));
    }
}
signed main(){
    int n;
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> X[i];
    }
    cout << play(1, n, 0).ff;
    return 0;
}

Two Sets II

DP 模逆元

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int mod = 1e9 + 7;
array<int, 150004> dp;
int DP(int n, int x){
    dp[0] = 1;
    for(int j = 1; j <= n; j++){
        for(int i = x; i >= j; i--){
            dp[i] += dp[i - j];
            dp[i] %= mod;
        }
    }
    return (dp[x] * (int)(5e8 + 4)) % mod;
}
signed main(){
    int n, sum = 0;
    cin >> n;
    for(int i = 1; i <= n; i++){
        sum += i;
    }
    if(sum & 1) cout << 0;
    else cout << DP(n, sum / 2);
    return 0;
}

Increasing Subsequence

LIS

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
array<int, 200004> X;
int LIS(int n){
    vector<int> lis;
    for(int i = 0; i < n ;i++){
        auto it = lower_bound(lis.begin(), lis.end(), X[i]);
        if(it == lis.end()) lis.pb(X[i]);
        else *it = X[i];
    }
    return lis.size();
}
signed main(){
    int n;
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> X[i];
    }
    cout << LIS(n);
    return 0;
}

Projects

排序 DP

#include <bits/stdc++.h>
#define int long long
#define pb push_back
using namespace std;
struct w{
    int l, r, p;
};
bool cmpl(w a, w b){
    return a.l < b.l;
}
bool cmpr(w a, w b){
    return a.r < b.r;
}
array<int, 400004> dp;
array<w, 200004> W;
vector<w> L;
signed main(){
    int n, l, r, p, cnt = 0, lst = 0, ans = 0;
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> l >> r >> p;
        W[i].p = p;
        L.pb({l, i, 0});
        L.pb({r, i, 1});
    }
    sort(L.begin(), L.end(), cmpl);
    for(w ll : L){
        if(ll.l != lst) cnt++;
        if(ll.p) W[ll.r].r = cnt;
        else W[ll.r].l = cnt;
        lst = ll.l;
    }
    sort(W.begin(), W.begin() + n, cmpr);
    p = 0;
    for(int i = 1; i <= 2 * n; i++){
        dp[i] = dp[i - 1];
        while(p < n && W[p].r == i){
            dp[i] = max(dp[i], dp[W[p].l - 1] + W[p].p);
            p++;
        }
        ans = max(ans, dp[i]);
    }
    cout << ans;
    return 0;
}

Elevator Rides

狀壓DP

#include <bits/stdc++.h>
#define pii pair<int, int>
#define ff first
#define ss second
using namespace std;
array<int, 24> W;
array<pii, 1 << 20> dp;
int DP(int n, int x){
    int w, t;
    dp[0] = {1, 0};
    for(int i = 1; i < (1 << n); i++){
        dp[i] = {24, 0};
        for(int j = 0; j < n; j++){
            if(i & (1 << j)){
                t = dp[i ^ (1 << j)].ff;
                w = dp[i ^ (1 << j)].ss;
                if(w + W[j] > x){
                    t++;
                    w = min(W[j], w);
                }else w += W[j];
                dp[i] = min(dp[i], {t, w});
            }
        }
    }
    return dp[(1 << n) - 1].ff;
}
signed main(){
    int n, x;
    cin >> n >> x;
    for(int i = 0; i < n; i++){
        cin >> W[i];
    }
    cout << DP(n, x);
    return 0;
}

Counting Tilings

輪廓DP

#include <bits/stdc++.h>
using namespace std;
const int mod = 1e9 + 7;
array<array<int, 1 << 12>, 2> dp;
void cpy(int n){
    for(int i = 0; i < 1 << n; i++){
        dp[0][i] = dp[1][i];
        dp[1][i] = 0;
    }
}
int DP(int n, int m){
    dp[1][0] = 1;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            cpy(n);
            for (int s = 0; s < 1 << n; s++){
                if (dp[0][s]) {
                    if (j != n - 1 && !(s >> j & 3)){
                        dp[1][s ^ 1 << j + 1] += dp[0][s];
                        dp[1][s ^ 1 << j + 1] %= mod;
                    }
                    dp[1][s ^ 1 << j] += dp[0][s];
                    dp[1][s ^ 1 << j] %= mod;
                }
            }
        }
    }
    return dp[1][0];
}
signed main(){
    int n, m;
    cin >> n >> m;
    cout << DP(n, m);
    return 0;
}

Counting Numbers

數位DP

#include <bits/stdc++.h>
#define pb push_back
#define int long long
using namespace std;
vector<int> dig;
array<array<array<array<int, 2>, 2>, 10>, 20> dp;
int dfs(int d, int pre, bool t, bool z/*tight, zero*/){
    if(d < 0){
        return 1;
    }
    if(dp[d][pre][t][z]) return dp[d][pre][t][z];
    int sum = 0;
    if(t){
        if(z || pre) sum += dfs(d - 1, 0, !dig[d], z);
        for(int i = 1; i <= dig[d]; i++){
            if(i != pre) sum += dfs(d - 1, i, i == dig[d], 0);
        }
    }else if(z){
        sum += dfs(d - 1, 0, 0, 1);
        for(int i = 1; i <= 9; i++){
            sum += dfs(d - 1, i, 0, 0);
        }
    }else{
        for(int i = 0; i <= 9; i++){
            if(i != pre) sum += dfs(d - 1, i, 0, 0);
        }
    }
    return dp[d][pre][t][z] = sum;
}
int DP(int x){
    if(!x) return 1;
    for(int i = 0; i < 20; i++){
        for(int j = 0; j < 10; j++){
            for(int k = 0; k < 2; k++){
                for(int l = 0; l < 2; l++){
                    dp[i][j][k][l] = 0;
                }
            }
        }
    }
    dig.clear();
    while(x > 0){
        dig.pb(x % 10);
        x /= 10;
    }
    return dfs(dig.size() - 1, 0, 1, 1);
}
signed main(){
    int a, b;
    cin >> a >> b;
    cout << DP(b) - (a? DP(a - 1) : 0);
    return 0;
}

Graph Algorithms

Counting Rooms

DFS

#include <bits/stdc++.h>
using namespace std;
int n, m;
array<int, 4> dx = {0, -1, 0, 1}, dy = {1, 0, -1, 0};
array<array<char, 1004>, 1004> G;
void dfs(int i, int j){
    if(!i || !j || i > n || j > m || G[i][j] == '#') return;
    G[i][j] = '#';
    for(int k = 0; k < 4; k++){
        dfs(i + dx[k], j + dy[k]);
    }
}
signed main(){
    int ans = 0;
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cin >> G[i][j];
        }
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(G[i][j] == '.'){
                dfs(i, j);
                ans++;
            }
        }
    }
    cout << ans;
    return 0;
}

Labyrinth

BFS

#include <bits/stdc++.h>
using namespace std;
struct pos{
    int x, y, c;
};
int n, m;
array<int, 4> dx = {0, 1, 0, -1}, dy = {1, 0, -1, 0};
array<array<char, 1004>, 1004> G;
array<array<pos, 1004>, 1004> L;
pos bfs(pos s){
    pos u;
    queue<pos> Q;
    Q.push(s);
    while(!Q.empty()){
        u = Q.front();
        Q.pop();
        if(!u.x || !u.y || u.x > n || u.y > m || G[u.x][u.y] == '#') continue;
        if(G[u.x][u.y] == 'B') return u;
        G[u.x][u.y] = '#';
        L[u.x][u.y] = u;
        for(int i = 0; i < 4; i++){
            Q.push({u.x + dx[i], u.y + dy[i], i});
        }
    }
    return {0, 0, -1};
}
void print(pos now, int cnt){
    if(now.c == -1){
        if(now.x) cout << "YES\n" << cnt << "\n";
        else cout << "NO\n";
        return;
    }
    print(L[now.x - dx[now.c]][now.y - dy[now.c]], cnt + 1);
    if(now.c == 0) cout << "R";
    else if(now.c == 1) cout << "D";
    else if(now.c == 2) cout << "L";
    else cout << "U";
}
signed main(){
    pos s;
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cin >> G[i][j];
            if(G[i][j] == 'A'){
                s = {i, j, -1};
            }
        }
    }
    print(bfs(s), 0);
    return 0;
}

Building Roads

DSU

#include <bits/stdc++.h>
#define pb push_back
#define pii pair<int, int>
#define ff first
#define ss second
using namespace std;
array<int, 100004> DSU;
vector<pii> R;
int find(int x){
    if(DSU[x] == x) return x;
    return DSU[x] = find(DSU[x]);
}
void onion(int a, int b){
    int A = find(a), B = find(b);
    DSU[B] = A;
}
signed main(){
    int n, m, a, b, cnt = 0;
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        DSU[i] = i;
    }
    while(m--){
        cin >> a >> b;
        onion(a, b);
    }
    for(int i = 2; i <= n; i++){
        if(find(1) != find(i)){
            cnt++;
            R.pb({1, i});
            onion(1, i);
        }
    }
    cout << cnt << "\n";
    for(pii r : R){
        cout << r.ff << " " << r.ss << "\n";
    }
    return 0;
}

Message Route

BFS

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
array<int, 100004> L;
array<bool, 100004> vis;
array<vector<int>, 100004> G;
bool bfs(int s, int t){
    int u;
    queue<int> Q;
    Q.push(s);
    while(!Q.empty()){
        int u = Q.front();
        Q.pop();
        if(vis[u]) continue;
        vis[u] = 1;
        if(u == t) return 1;
        for(int v : G[u]){
            if(L[v]) continue;
            L[v] = u;
            Q.push(v);
        }
    }
    return 0;
}
void print(int u, int cnt){
    if(u == 1){
        cout << cnt << "\n1 ";
        return;
    }
    print(L[u], cnt + 1);
    cout << u << " ";
}
signed main(){
    int n, m, a, b;
    cin >> n >> m;
    while(m--){
        cin >> a >> b;
        G[a].pb(b);
        G[b].pb(a);
    }
    if(bfs(1, n)) print(n, 1);
    else cout << "IMPOSSIBLE";
    return 0;
}

Building Teams

DFS

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
array<vector<int>, 100004> G;
array<int, 100004> team;
bool dfs(int u, int t){
    team[u] = t;
    bool ok = 1;
    for(int v : G[u]){
        if(team[v]){
            if(team[v] == t) return 0;
            continue;
        }
        ok &= dfs(v, 3 - t);
    }
    return ok;
}
signed main(){
    int n, m, a, b;
    bool ans = 1;
    cin >> n >> m;
    while(m--){
        cin >> a >> b;
        G[a].pb(b);
        G[b].pb(a);
    }
    for(int i = 1; i <= n; i++){
        if(!team[i]) ans &= dfs(i, 1);
    }
    if(ans){
        for(int i = 1; i <= n; i++){
            cout << team[i] << " ";
        }
    }else cout << "IMPOSSIBLE";
    return 0;
}

Round Trip

DFS

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
array<vector<int>, 100004> G;
array<int, 100004> vis;
vector<int> ans;
int s;
bool dfs(int u, int p, int pre){
    vis[u] = p;
    for(int v : G[u]){
        if(v == pre) continue;
        if(vis[v]){
            if(vis[v] == p){
                s = v;
                ans.pb(v);
                ans.pb(u);
                return 1;
            }
            continue;
        }
        if(dfs(v, p, u)){
            ans.pb(u);
            if(s == u){
                cout << ans.size() << "\n";
                for(int a : ans){
                    cout << a << " ";
                }
                exit(0);
            }
            return 1;
        }
    }
    return 0;
}
signed main(){
    int n, m, a, b;
    cin >> n >> m;
    while(m--){
        cin >> a >> b;
        G[a].pb(b);
        G[b].pb(a);
    }
    for(int i = 1; i <= n; i++){
        if(!vis[i]){
            ans.clear();
            dfs(i, i, 0);
        }
    }
    cout << "IMPOSSIBLE";
    return 0;
}

Monsters

BFS

#include <bits/stdc++.h>
#define pb push_back
#define top front
#define pii pair<int, int>
#define x first
#define y second
using namespace std;
int n, m;
array<int, 4> dx = {0, 1, 0, -1}, dy = {1, 0, -1, 0};
array<array<char, 1004>, 1004> G;
array<array<int, 1004>, 1004> disa, dism, L;
vector<pii> M;
pii s;
void bfsa(){
    pii u;
    int nx, ny;
    queue<pii> Q;
    Q.push(s);
    disa[s.x][s.y] = 0;
    while(!Q.empty()){
        u = Q.top();
        Q.pop();
        if(!u.x || !u.y || u.x > n || u.y > m) continue;
        for(int i = 0; i < 4; i++){
            nx = u.x + dx[i];
            ny = u.y + dy[i];
            if(disa[nx][ny] >= 0 || G[nx][ny] == '#') continue;
            disa[nx][ny] = disa[u.x][u.y] + 1;
            L[nx][ny] = i;
            Q.push({nx, ny});
        }
    }
}
void bfsm(){
    pii u;
    int nx, ny;
    queue<pii> Q;
    for(pii p : M){
        dism[p.x][p.y] = 0;
        Q.push(p);
    }
    while(!Q.empty()){
        u = Q.top();
        Q.pop();
        if(!u.x || !u.y || u.x > n || u.y > m) continue;
        for(int i = 0; i < 4; i++){
            nx = u.x + dx[i];
            ny = u.y + dy[i];
            if(dism[nx][ny] >= 0 || G[nx][ny] == '#') continue;
            dism[nx][ny] = dism[u.x][u.y] + 1;
            Q.push({nx, ny});
        }
    }
}
void print(pii now){
    if(now == s) return;
    int l = L[now.x][now.y];
    print({now.x - dx[l], now.y - dy[l]});
    if(l == 0) cout << "R";
    else if(l == 1) cout << "D";
    else if(l == 2) cout << "L";
    else cout << "U";
}
signed main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cin >> G[i][j];
            if(G[i][j] == 'M') M.pb({i, j});
            if(G[i][j] == 'A') s = {i, j};
            disa[i][j] = dism[i][j] = -1;
        }
    }
    bfsa();
    bfsm();
    for(int i = 1; i <= m; i++){
        if(disa[1][i] >= 0 && (dism[1][i] < 0 || disa[1][i] < dism[1][i])){
            cout << "YES\n";
            cout << disa[1][i] << "\n";
            print({1, i});
            return 0;
        }
        if(disa[n][i] >= 0 && (dism[n][i] < 0 || disa[n][i] < dism[n][i])){
            cout << "YES\n";
            cout << disa[n][i] << "\n";
            print({n, i});
            return 0;
        }
    }
    for(int i = 1; i <= n; i++){
        if(disa[i][1] >= 0 && (dism[i][1] < 0 || disa[i][1] < dism[i][1])){
            cout << "YES\n";
            cout << disa[i][1] << "\n";
            print({i, 1});
            return 0;
        }
        if(disa[i][m] >= 0 && (dism[i][m] < 0 || disa[i][m] < dism[i][m])){
            cout << "YES\n";
            cout << disa[i][m] << "\n";
            print({i, m});
            return 0;
        }
    }
    cout << "NO";
    return 0;
}

Shortest Routes I

Dijkstra

#include <bits/stdc++.h>
#define pb push_back
#define int long long
using namespace std;
struct E{
    int v, w;
    E(){}
    E(int v, int w): w(w), v(v){}
    E operator+(E e){
        return E(v, w + e.w);
    }
};
struct cmp{
    bool operator()(E a, E b){
        return a.w > b.w;
    }
};
array<vector<E>, 100004> G;
array<int, 100004> dis;
void run(int s){
    E u;
    priority_queue<E, vector<E>, cmp> Q;
    Q.push(E(s, 1));
    while(!Q.empty()){
        u = Q.top();
        Q.pop();
        if(dis[u.v]) continue;
        dis[u.v] = u.w;
        for(E e : G[u.v]){
            Q.push(e + u);
        }
    }
}
signed main(){
    int n, m, a, b, c;
    cin >> n >> m;
    while(m--){
        cin >> a >> b >> c;
        G[a].pb(E(b, c));
    }
    run(1);
    for(int i = 1; i <= n; i++){
        cout << dis[i] - 1 << " ";
    }
    return 0;
}

Shortest Routes II

Floyd Warshall

#include <bits/stdc++.h>
#define int long long
using namespace std;
array<array<int, 504>, 504> dis;
int min(int a, int b){
    if(a < 0) return b;
    if(b < 0) return a;
    return a < b? a : b;
}
int add(int a, int b){
    if(a < 0 || b < 0) return -1;
    return a + b;
}
void run(int n){
    for(int k = 1; k <= n; k++){
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                if(i == j) continue;
                dis[i][j] = min(dis[i][j], add(dis[i][k], dis[k][j]));
            }
        }
    }
}
signed main(){
    int n, m, q, a, b, c;
    cin >> n >> m >> q;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            dis[i][j] = -1;
        }
        dis[i][i] = 0;
    }
    while(m--){
        cin >> a >> b >> c;
        dis[a][b] = dis[b][a] = min(dis[a][b], c);
    }
    run(n);
    while(q--){
        cin >> a >> b;
        cout << dis[a][b] << "\n";
    }
    return 0;
}

High Score

SPFA

#include <bits/stdc++.h>
#define pb push_back
#define int long long
using namespace std;
struct E{
    int v, w;
};
array<vector<E>, 2504> G, B;
array<bool, 2504> gis, bis;
array<int, 2504> dis, cnt;
void gfs(int u){
    gis[u] = 1;
    for(auto [v, w] : G[u]){
        if(!gis[v]) gfs(v);
    }
}
void bfs(int u){
    bis[u] = 1;
    for(auto [v, w] : B[u]){
        if(!bis[v]) bfs(v);
    }
}
int run(int s, int t){
    int u;
    queue<int> Q;
    Q.push(s);
    while(!Q.empty()){
        u = Q.front();
        Q.pop();
        for(auto [v, w] : G[u]){
            if(cnt[v] > t) continue;
            if(dis[u] + w > dis[v]){
                Q.push(v);
                dis[v] = dis[u] + w;
                cnt[v]++;
                if(cnt[v] > t && gis[v] && bis[v]) return -1;
            }
        }
    }
    return dis[t];
}
signed main(){
    int n, m, a, b, x;
    cin >> n >> m;
    for(int i = 2; i <= n; i++) dis[i] = -1e18;
    while(m--){
        cin >> a >> b >> x;
        G[a].pb({b, x});
        B[b].pb({a, x});
    }
    gfs(1);
    bfs(n);
    cout << run(1, n);
    return 0;
}

Flight Discount

Dijkstra

#include <bits/stdc++.h>
#define pb push_back
#define int long long
using namespace std;
struct E{
    int v, w, c;
};
struct cmp{
    bool operator()(E a, E b){
        return a.w > b.w;
    }
};
array<array<bool, 2>, 100004> vis;
array<vector<E>, 100004> G;
int run(int s, int t){
    E e;
    priority_queue<E, vector<E>, cmp> Q;
    Q.push({s, 0, 0});
    while(!Q.empty()){
        e = Q.top();
        Q.pop();
        if(vis[e.v][e.c]) continue;
        if(e.v == t) return e.w;
        vis[e.v][e.c] = 1;
        for(auto [v, w, c] : G[e.v]){
            if(!(e.c & c)) Q.push({v, e.w + w, c | e.c});
        }
    }
}
signed main(){
    int n, m, a, b, c;
    cin >> n >> m;
    while(m--){
        cin >> a >> b >> c;
        G[a].pb({b, c, 0});
        G[a].pb({b, c / 2, 1});
    }
    cout << run(1, n);
    return 0;
}

Cycle Finding

Bellman Ford

#include <bits/stdc++.h>
#define pb push_back
#define int long long
using namespace std;
struct E{
    int u, v, w;
};
vector<E> G;
array<int, 2504> dis, pre;
int run(int n){
    int c;
    for(int i = 0; i <= n; i++){
        c = 0;
        for(auto [u, v, w] : G){
            if(dis[v] > dis[u] + w){
                dis[v] = dis[u] + w;
                pre[v] = u;
                c = v;
            }
        }
    }
    return c;
}
void print(int v, int u){
    if(v == u){
        cout << u << " ";
        return;
    }
    print(pre[v], u);
    cout << v << " ";
}
signed main(){
    int n, m, a, b, c, u;
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        dis[i] = 1e18;
    }
    while(m--){
        cin >> a >> b >> c;
        G.pb({a, b, c});
    }
    if(u = run(n)){
        while(n--) u = pre[u];
        cout << "YES\n";
        print(pre[u], u);
        cout << u;
    }else cout << "NO";
    return 0;
}

Flight Routes

Dijkstra

#include <bits/stdc++.h>
#define pb push_back
#define int long long
using namespace std;
struct E{
    int v, w;
};
struct cmp{
    bool operator()(E a, E b){
        return a.w > b.w;
    }
};
array<vector<E>, 100004> G;
array<int, 100004> vis;
void run(int s, int t, int k){
    E e;
    priority_queue<E, vector<E>, cmp> Q;
    Q.push({s, 0});
    while(!Q.empty()){
        e = Q.top();
        Q.pop();
        if(vis[e.v] >= k) continue;
        if(e.v == t) cout << e.w << " ";
        vis[e.v]++;
        for(auto [v, w] : G[e.v]){
            Q.push({v, w + e.w});
        }
    }
}
signed main(){
    int n, m, k, a, b, c;
    cin >> n >> m >> k;
    while(m--){
        cin >> a >> b >> c;
        G[a].pb({b, c});
    }
    run(1, n, k);
    return 0;
}

Round Trip II

DFS

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
array<int, 100004> vis;
array<vector<int>, 100004> G;
stack<int> S;
vector<int> ans;
bool dfs(int u){
    if(vis[u]) return 0;
    vis[u] = 1;
    S.push(u);
    for(int v : G[u]){
        if(vis[v] == 1){
            while(S.top() != v){
                ans.pb(v);
                while(S.top() != v){
                    ans.pb(S.top());
                    S.pop();
                }
                ans.pb(v);
            }
            return 1;
        }
        if(dfs(v)) return 1;
    }
    S.pop();
    vis[u] = 2;
    return 0;
}
signed main(){
    int n, m, a, b;
    cin >> n >> m;
    while(m--){
        cin >> a >> b;
        G[a].pb(b);
    }
    for(int i = 1; i <= n; i++){
        if(dfs(i)){
            cout << ans.size() << "\n";
            reverse(ans.begin(), ans.end());
            for(int a : ans) cout << a << " ";
            return 0;
        }
    }
    cout << "IMPOSSIBLE";
    return 0;
}

Course Schedule

Topological Sort

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
array<int, 100004> in;
array<vector<int>, 100004> G;
vector<int> ord;
void topu(int n){
    int u;
    queue<int> Q;
    for(int i = 1; i <= n; i++){
        if(!in[i]) Q.push(i);
    }
    while(!Q.empty()){
        u = Q.front();
        Q.pop();
        ord.pb(u);
        for(int v : G[u]){
            in[v]--;
            if(!in[v]) Q.push(v);
        }
    }
}
signed main(){
    int n, m, a, b;
    cin >> n >> m;
    while(m--){
        cin >> a >> b;
        G[a].pb(b);
        in[b]++;
    }
    topu(n);
    if(ord.size() < n) cout << "IMPOSSIBLE";
    else{
        for(int o : ord) cout << o << " ";
    }
    return 0;
}

Longest Flight Route

Topological Sort DP

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
array<int, 100004> in, nxt, dp;
array<vector<int>, 100004> G;
stack<int> ord;
void topu(int n){
    int u;
    queue<int> Q;
    dp[n] = 1;
    for(int i = 1; i <= n; i++){
        in[0]++;
        if(!in[i]) Q.push(i);
    }
    while(!Q.empty()){
        u = Q.front();
        Q.pop();
        ord.push(u);
        for(int v : G[u]){
            in[v]--;
            if(!in[v]) Q.push(v);
        }
    }
    while(!ord.empty()){
        u = ord.top();
        ord.pop();
        for(int v : G[u]){
            if(!dp[v]) continue;
            if(dp[u] < dp[v] + 1){
                dp[u] = dp[v] + 1;
                nxt[u] = v;
            }
        }
    }
}
void print(int u){
    if(!u) return;
    if(u == 1){
        if(dp[1]) cout << dp[1] << "\n";
        else{
            cout << "IMPOSSIBLE";
            return;
        }
    }
    cout << u << " ";
    print(nxt[u]);
}
signed main(){
    int n, m, a, b;
    cin >> n >> m;
    while(m--){
        cin >> a >> b;
        in[b]++;
        G[a].pb(b);
    }
    topu(n);
    print(1);
    return 0;
}

Game Routes

Topological Sort DP

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int mod = 1e9 + 7;
array<int, 100004> in, dp;
array<vector<int>, 100004> G;
stack<int> ord;
int topu(int n){
    int u;
    queue<int> Q;
    dp[n] = 1;
    for(int i = 1; i <= n; i++){
        if(!in[i]) Q.push(i);
    }
    while(!Q.empty()){
        u = Q.front();
        Q.pop();
        ord.push(u);
        for(int v : G[u]){
            in[v]--;
            if(!in[v]) Q.push(v);
        }
    }
    while(!ord.empty()){
        u = ord.top();
        ord.pop();
        for(int v : G[u]){
            dp[u] += dp[v];
            dp[u] %= mod;
        }
    }
    return dp[1];
}
signed main(){
    int n, m, a, b;
    cin >> n >> m;
    while(m--){
        cin >> a >> b;
        in[b]++;
        G[a].pb(b);
    }
    cout << topu(n);
    return 0;
}

Investigation

Dijkstra DP

#include <bits/stdc++.h>
#define pb push_back
#define int long long
using namespace std;
const int mod = 1e9 + 7;
struct E{
    int v, w;
};
struct cmp{
    bool operator()(E a, E b){
        return a.w > b.w;
    }
};
array<int, 100004> dis, dp, minfly, maxfly;
array<vector<E>, 100004> G, B;
vector<int> ord;
void run(int s){
    E e;
    dp[s] = 1;
    minfly[s] = 1;
    maxfly[s] = 1;
    priority_queue<E, vector<E>, cmp> Q;
    Q.push({s, 1});
    dis[s] = 0;
    while(!Q.empty()){
        e = Q.top();
        Q.pop();
        if(dis[e.v]) continue;
        ord.pb(e.v);
        dis[e.v] = e.w;
        for(auto [v, w] : B[e.v]){
            Q.push({v, w + e.w});
        }
    }
    for(int u : ord){
        if(u != s) minfly[u] = 1e18;
        for(auto [v, w] : G[u]){
            if(dis[v] + w == dis[u]){
                dp[u] += dp[v];
                dp[u] %= mod;
                if(minfly[v]) minfly[u] = min(minfly[u], minfly[v] + 1);
                if(maxfly[v]) maxfly[u] = max(maxfly[u], maxfly[v] + 1);
            }
        }
    }
    cout << dis[1] - 1 << " " << dp[1] << " " << minfly[1] - 1 << " " << maxfly[1] - 1;
}
signed main(){
    int n, m, a, b, c;
    cin >> n >> m;
    while(m--){
        cin >> a >> b >> c;
        G[a].pb({b, c});
        B[b].pb({a, c});
    }
    run(n);
    return 0;
}

Planets Queries I

Doubling

#include <bits/stdc++.h>
using namespace std;
array<array<int, 30>, 200004> T;
void dabo(int n){
    for(int j = 1; j <= 29; j++){
        for(int i = 1; i <= n; i++){
            T[i][j] = T[T[i][j - 1]][j - 1];
        }
    }
}
int find(int x, int k){
    for(int i = 29; i >= 0; i--){
        if((1 << i) & k){
            x = T[x][i];
            k -= (1 << i);
        }
    }
    return x;
}
signed main(){
    cin.tie(0), cout.tie(0), ios::sync_with_stdio(0);
    int n, q, x, k;
    cin >> n >> q;
    for(int i = 1; i <= n; i++){
        cin >> T[i][0];
    }
    dabo(n);
    while(q--){
        cin >> x >> k;
        cout << find(x, k) << "\n";
    }
    return 0;
}

Planets Queries II

DFS Doubling Topological Sort

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
int cnt = 0;
array<int, 200004> in, out, cyc, com, cycnt, T;
array<vector<int>, 200004> B;
array<array<int, 20>, 200004> G;
stack<int> ord;
int cfs(int u, int c, int x = 0){
    if(com[u]) return x;
    com[u] = c;
    cyc[u] = ++x;
    return cycnt[u] = cfs(T[u], c, x);
}
void dfs(int u, int c){
    if(cyc[u]) in[u] = 0;
    else in[u] = ++cnt;
    com[u] = c;
    for(int v : B[u]){
        if(!in[v] && !cyc[v]) dfs(v, c);
    }
    if(cyc[u]) out[u] = 1e9;
    else out[u] = ++cnt;
}
void topu(int n){
    int u;
    queue<int> Q;
    for(int i = 1; i <= n; i++){
        cyc[i] = 1;
        if(!in[i]) Q.push(i);
    }
    while(!Q.empty()){
        u = Q.front();
        Q.pop();
        ord.push(u);
        cyc[u] = 0;
        in[T[u]]--;
        if(!in[T[u]]) Q.push(T[u]);
    }
    for(int i = 1; i <= n; i++){
        if(cyc[i]){
            cfs(i, i);
            dfs(i, com[i]? com[i] : i);
        }
    }
    while(!ord.empty()){
        u = ord.top();
        ord.pop();
        if(!com[u]) dfs(u, u);
    }
}
void dabo(int n){
    for(int j = 1; j < 20; j++){
        for(int i = 1; i <= n; i++){
            G[i][j] = G[G[i][j - 1]][j - 1];
        }
    }
}
int query(int a, int b){
    if(a == b) return 0;
    if(com[a] != com[b]) return -1;
    int ans = 0;
    for(int i = 19; i >= 0; i--){
        if(in[G[a][i]] > in[b] && out[G[a][i]] < out[b]){
            a = G[a][i];
            ans += 1 << i;
        }
    }
    a = G[a][0];
    ans++;
    if(a == b) return ans;
    if(cyc[a] && cyc[b]){
        ans += (cyc[b] - cyc[a] + cycnt[a]) % cycnt[b];
        return ans;
    }
    return -1;
}
signed main(){
    int n, q, a, b;
    cin >> n >> q;
    for(int i = 1; i <= n; i++){
        cin >> T[i];
        in[T[i]]++;
        if(i == T[i]) in[T[i]]--;
        G[i][0] = T[i];
        B[T[i]].pb(i);
    }
    topu(n);
    dabo(n);
    while(q--){
        cin >> a >> b;
        cout << query(a, b) << "\n";
    }
    return 0;
}

Planets Cycles

DFS Doubling Topological Sort

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
int cnt = 0;
array<int, 200004> in, out, cyc, com, cycnt, T;
array<vector<int>, 200004> B;
array<array<int, 20>, 200004> G;
stack<int> ord;
int cfs(int u, int c, int x = 0){
    if(com[u]) return x;
    com[u] = c;
    cyc[u] = ++x;
    return cycnt[u] = cfs(T[u], c, x);
}
void dfs(int u, int c){
    if(cyc[u]) in[u] = 0;
    else in[u] = ++cnt;
    com[u] = c;
    for(int v : B[u]){
        if(!in[v] && !cyc[v]) dfs(v, c);
    }
    if(cyc[u]) out[u] = 1e9;
    else out[u] = ++cnt;
}
void topu(int n){
    int u;
    queue<int> Q;
    for(int i = 1; i <= n; i++){
        cyc[i] = 1;
        if(!in[i]) Q.push(i);
    }
    while(!Q.empty()){
        u = Q.front();
        Q.pop();
        ord.push(u);
        cyc[u] = 0;
        in[T[u]]--;
        if(!in[T[u]]) Q.push(T[u]);
    }
    for(int i = 1; i <= n; i++){
        if(cyc[i]){
            cfs(i, i);
            dfs(i, com[i]? com[i] : i);
        }
    }
    while(!ord.empty()){
        u = ord.top();
        ord.pop();
        if(!com[u]) dfs(u, u);
    }
}
void dabo(int n){
    in[0] = 0, out[0] = 1e9;
    for(int j = 1; j < 20; j++){
        for(int i = 1; i <= n; i++){
            G[i][j] = G[G[i][j - 1]][j - 1];
        }
    }
}
int query(int x){
    int ans = 0;
    if(T[x] == x) return 1;
    if(cyc[x]) return cycnt[x];
    for(int i = 19; i >= 0; i--){
        if(in[G[x][i]] > in[0] && out[G[x][i]] < out[0]){
            x = G[x][i];
            ans += 1 << i;
        }
    }
    x = G[x][0];
    ans++;
    if(cyc[x]) return ans + cycnt[x];
    return -1;
}
signed main(){
    int n, q, a, b;
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> T[i];
        in[T[i]]++;
        G[i][0] = T[i];
        B[T[i]].pb(i);
    }
    topu(n);
    dabo(n);
    for(int i = 1; i <= n; i++){
        cout << query(i) << " ";
    }
    return 0;
}

Road Reparation

Kruskal

#include <bits/stdc++.h>
#define pb push_back
#define int long long
using namespace std;
struct E{
    int u, v, w;
};
array<int, 100004> DSU;
vector<E> G;
bool cmp(E a, E b){
    return a.w < b.w;
}
int find(int x){
    if(DSU[x] == x) return x;
    return DSU[x] = find(DSU[x]);
}
void onion(int a, int b){
    int A = find(a), B = find(b);
    DSU[B] = A;
}
void MST(int n){
    int ans = 0, cnt = n;
    for(auto [v, u, w] : G){
        if(find(v) == find(u)) continue;
        cnt--;
        onion(u, v);
        ans += w;
    }
    if(cnt == 1) cout << ans;
    else cout << "IMPOSSIBLE";
}
signed main(){
    int n, m, a, b, c;
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        DSU[i] = i;
    }
    while(m--){
        cin >> a >> b >> c;
        G.pb({a, b, c});
    }
    sort(G.begin(), G.end(), cmp);
    MST(n);
    return 0;
}

Road Construction

DSU

#include <bits/stdc++.h>
using namespace std;
array<int, 100004> DSU, S;
int find(int x){
    if(DSU[x] == x) return x;
    return DSU[x] = find(DSU[x]);
}
int onion(int a, int b){
    int A = find(a), B = find(b);
    if(S[A] < S[B]){
        DSU[A] = B;
        S[B] += S[A];
        return S[B];
    }else{
        DSU[B] = A;
        S[A] += S[B];
        return S[A];
    }
}
signed main(){
    int n, m, a, b, cnt, sz = 1;
    cin >> n >> m;
    cnt = n;
    for(int i = 1; i <= n; i++){
        DSU[i] = i;
        S[i] = 1;
    }
    while(m--){
        cin >> a >> b;
        if(find(a) != find(b)){
            cnt--;
            sz = max(sz, onion(a, b));
        }
        cout << cnt << " " << sz << "\n";
    }
    return 0;
}

Flight Routes Check

SCC

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
int cnt = 0;
array<bool, 100004> vis;
array<vector<int>, 100004> G, B, S;
array<int, 100004> scc, deg;
stack<int> out;
void bfs(int u){
    if(vis[u]) return;
    vis[u] = 1;
    for(int v : B[u]){
        bfs(v);
    }
    out.push(u);
}
void dfs(int u, int s){
    if(scc[u]) return;
    scc[u] = s;
    for(int v : G[u]){
        dfs(v, s);
    }
}
signed main(){
    int n, m, a, b, o;
    cin >> n >> m;
    while(m--){
        cin >> a >> b;
        G[a].pb(b);
        B[b].pb(a);
    }
    for(int i = 1; i <= n; i++){
        bfs(i);
    }
    while(!out.empty()){
        o = out.top();
        out.pop();
        if(!scc[o]) dfs(o, ++cnt);
    }
    for(int i = 1; i <= n; i++){
        S[scc[i]].pb(i);
        for(int v : G[i]){
            if(scc[v] == scc[i]) continue;
            deg[scc[i]]++;
        }
    }
    for(int i = 1; i <= cnt; i++){
        if(deg[i]) b = S[i][0];
        else a = S[i][0];
    }
    if(cnt == 1) cout << "YES";
    else{
        cout << "NO\n" << a << " " << b;
    }
    return 0;
}

Planets and Kingdoms

SCC

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
int k = 0;
array<vector<int>, 100004> G, B;
array<bool, 100004> vis;
array<int, 100004> scc;
stack<int> out;
void bfs(int u){
    if(vis[u]) return;
    vis[u] = 1;
    for(int v : B[u]){
        bfs(v);
    }
    out.push(u);
}
void dfs(int u){
    if(scc[u]) return;
    scc[u] = k;
    for(int v : G[u]){
        dfs(v);
    }
}
signed main(){
    int n, m, a, b, o;
    cin >> n >> m;
    while(m--){
        cin >> a >> b;
        G[a].pb(b);
        B[b].pb(a);
    }
    for(int i = 1; i <= n; i++){
        bfs(i);
    }
    while(!out.empty()){
        o = out.top();
        out.pop();
        if(!scc[o]) ++k, dfs(o);
    }
    cout << k << "\n";
    for(int i = 1; i <= n; i++){
        cout << scc[i] << " ";
    }
    return 0;
}

Giant Pizza

2-SAT Topological Sort

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
int k = 0;
array<vector<int>, 200004> G, B, C, S;
array<bool, 200004> vis;
array<int, 200004> scc, ans, in;
stack<int> out, ord;
void bfs(int u){
    if(vis[u]) return;
    vis[u] = 1;
    for(int v : B[u]) bfs(v);
    out.push(u);
}
void dfs(int u){
    if(scc[u]) return;
    scc[u] = k;
    for(int v : G[u]) dfs(v);
}
void topu(int n){
    int u;
    bool ok;
    queue<int> Q;
    for(int i = 1; i <= 2 * n + 1; i++){
        if(!in[i]) Q.push(i);
        ans[i] = -1;
    }
    while(!Q.empty()){
        u = Q.front();
        Q.pop();
        ord.push(u);
        for(int v : S[u]){
            in[v]--;
            if(!in[v]) Q.push(v);
        }
    }
    while(!ord.empty()){
        u = ord.top();
        ord.pop();
        ok = 1;
        for(int v : C[u]){
            if(ans[v / 2] >= 0) ok = 0;
        }
        if(!ok) continue;
        for(int v : C[u]){
            ans[v / 2] = v & 1;
        }
    }
}
signed main(){
    int n, m, a, b, o;
    char wa, wb;
    bool ok = 1;
    cin >> m >> n;
    while(m--){
        cin >> wa >> a >> wb >> b;
        a = 2 * a;
        b = 2 * b;
        if(wa == '+') a++;
        if(wb == '+') b++;
        G[a ^ 1].pb(b);
        B[b].pb(a ^ 1);
        G[b ^ 1].pb(a);
        B[a].pb(b ^ 1);
    }
    for(int i = 2; i <= 2 * n + 1; i++){
        bfs(i);
    }
    while(!out.empty()){
        o = out.top();
        out.pop();
        if(!scc[o]) k++, dfs(o);
    }
    for(int i = 1; i <= n; i++){
        //cout << scc[2 * i] << " " << scc[2 * i + 1] << "\n";
        if(scc[2 * i] == scc[2 * i + 1]) ok = 0;
    }
    if(!ok){
        cout << "IMPOSSIBLE";
        return 0;
    }
    for(int i = 2; i <= 2 * n + 1; i++){
        C[scc[i]].pb(i);
        for(int v : G[i]){
            if(scc[v] == scc[i]) continue;
            in[scc[v]]++;
            S[scc[i]].pb(scc[v]);
        }
    }
    topu(n);
    for(int i = 1; i <= n; i++){
        cout << (ans[i]? "+ " : "- ");
    }
    return 0;
}

Coin Collector

SCC Topological Sort DP

#include <bits/stdc++.h>
#define pb push_back
#define int long long
using namespace std;
int k = 0;
array<int, 100004> K, scc, dp, val, in;
array<bool, 100004> vis;
array<vector<int>, 100004> G, B, S;
stack<int> out, ord;
void bfs(int u){
    if(vis[u]) return;
    vis[u] = 1;
    for(int v : B[u]) bfs(v);
    out.push(u);
}
void dfs(int u){
    if(scc[u]) return;
    scc[u] = k;
    for(int v : G[u]) dfs(v);
}
int topu(int n){
    int u, ans = 0;
    queue<int> Q;
    for(int i = 1; i <= n; i++){
        if(!in[i]) Q.push(i);
    }
    while(!Q.empty()){
        u = Q.front();
        Q.pop();
        ord.push(u);
        for(int v : S[u]){
            in[v]--;
            if(!in[v]) Q.push(v);
        }
    }
    while(!ord.empty()){
        u = ord.top();
        ord.pop();
        dp[u] = val[u];
        for(int v : S[u]){
            dp[u] = max(dp[u], dp[v] + val[u]);
        }
        ans = max(ans, dp[u]);
    }
    return ans;
}
signed main(){
    int n, m, a, b, o;
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        cin >> K[i];
    }
    while(m--){
        cin >> a >> b;
        G[a].pb(b);
        B[b].pb(a);
    }
    for(int i = 1; i <= n; i++){
        bfs(i);
    }
    while(!out.empty()){
        o = out.top();
        out.pop();
        if(!scc[o]) k++, dfs(o);
    }
    for(int i = 1; i <= n; i++){
        val[scc[i]] += K[i];
        for(int v : G[i]){
            if(scc[v] == scc[i]) continue;
            in[scc[v]]++;
            S[scc[i]].pb(scc[v]);
        }
    }
    cout << topu(k);
    return 0;
}

Mail Delivery

Euler Tour

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
array<set<int>, 100004> G;
vector<int> ans;
void ola(int u){
    int v;
    while(G[u].size()){
        v = *G[u].begin();
        G[u].erase(v);
        G[v].erase(u);
        ola(v);
    }
    ans.pb(u);
}
signed main(){
    int n, m, a, b;
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        cin >> a >> b;
        G[a].insert(b);
        G[b].insert(a);
    }
    for(int i = 1; i <= n; i++){
        if(G[i].size() & 1){
            cout << "IMPOSSIBLE";
            return 0;
        }
    }
    ola(1);
    if(ans.size() < m + 1){
        cout << "IMPOSSIBLE";
        return 0;
    }
    reverse(ans.begin(), ans.end());
    for(int a : ans) cout << a << " ";
    return 0;
}

De Bruijn Sequence

DFS

#include <bits/stdc++.h>
#define pb push_back
#define ppb pop_back
using namespace std;
int n;
array<array<int, 2>, 1 << 15> G;
array<bool, 1 << 15> vis;
vector<int> ans;
int dfs(int u, int cnt){
    if(vis[u]) return u;
    int v = 0, tmp;
    vis[u] = 1;
    if(cnt == 1 << n){
        for(int i = 0; i < n; i++) cout << "0";
        for(int a : ans) cout << a;
        exit(0);
    }
    for(int i = 0; i < 2; i++){
        if(G[u][i] == -1) continue;
        ans.pb(i);
        tmp = dfs(G[u][i], cnt + 1);
        if(tmp && tmp != u) v = tmp, G[u][i] = -1;
        ans.ppb();
    }
    vis[u] = 0;
    return v;
}
signed main(){
    cin >> n;
    for(int i = 0; i < 1 << n; i++){
        G[i][0] = (i << 1) & ((1 << n) - 1);
        G[i][1] = ((i << 1) | 1) & ((1 << n) - 1);
    }
    dfs(0, 1);
    return 0;
}

Teleporters Path

Euler Tour

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
array<set<int>, 100004> G;
array<int, 100004> in;
stack<int> ans;
void ola(int u){
    int v;
    while(G[u].size()){
        v = *G[u].begin();
        G[u].erase(v);
        ola(v);
    }
    ans.push(u);
}
signed main(){
    int n, m, a, b;
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        cin >> a >> b;
        G[a].insert(b);
        in[b]++;
    }
    in[a]++;
    in[n]--;
    for(int i = 1; i <= n; i++){
        if(in[i] != G[i].size()){
            cout << "IMPOSSIBLE";
            return 0;
        }
    }
    ola(1);
    if(ans.size() == m + 1){
        while(!ans.empty()){
            cout << ans.top() << " ";
            ans.pop();
        }
    }else cout << "IMPOSSIBLE";
    return 0;
}

Hamiltonian Flights

Hamiltonian Cycle 狀壓DP

#include <bits/stdc++.h>
#define pb push_back
#define pii pair<int, int>
#define ff first
#define ss second
using namespace std;
const int mod = 1e9 + 7;
array<vector<int>, 24> G;
array<array<int, 20>, 1 << 20> dp;
array<array<bool, 20>, 1 << 20> vis;
int run(int n){
    int s, u;
    queue<pii> Q;
    dp[1][0] = 1;
    Q.push({1, 0});
    vis[1][0] = 1;
    while(!Q.empty()){
        s = Q.front().ff;
        u = Q.front().ss;
        Q.pop();
        if(u == n - 1) continue;
        for(int v : G[u]){
            if((1 << v) & s) continue;
            dp[s | (1 << v)][v] += dp[s][u];
            dp[s | (1 << v)][v] %= mod;
            if(vis[s | (1 << v)][v]) continue;
            Q.push({s | (1 << v), v});
            vis[s | (1 << v)][v] = 1;
        }
    }
    return dp[(1 << n) - 1][n - 1];
}
signed main(){
    int n, m, a, b;
    cin >> n >> m;
    while(m--){
        cin >> a >> b;
        a--, b--;
        G[a].pb(b);
    }
    cout << run(n);
    /*for(int i = 1; i < 1 << n; i++){
        for(int j = 0; j < n; j++){
            cout << dp[i][j] << " ";
        }
        cout << "\n";
    }*/
    return 0;
}

Knight's Tour

暴力 DFS

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
struct V{
    int d, x, y;
};
array<int, 8> dx = {-2, -1, 1, 2, 2, 1, -1, -2}, dy = {1, 2, 2, 1, -1, -2, -2, -1};
array<array<int, 12>, 12> C;
int deg(int x, int y){
    int d = 0, nx, ny;
    for(int i = 0; i < 8; i++){
        nx = x + dx[i], ny = y + dy[i];
        if(nx < 1 || ny < 1 || nx > 8 || ny > 8 || C[nx][ny]) continue;
        d++;
    }
    return d;
}
void dfs(int x, int y, int s){
    C[x][y] = s;
    if(s == 64){
        for(int i = 1; i <= 8; i++){
            for(int j = 1; j <= 8; j++){
                cout << C[i][j] << " ";
            }
            cout << "\n";
        }
        exit(0);
    }
    int nx, ny;
    vector<V> nxt;
    for(int i = 0; i < 8; i++){
        nx = x + dx[i], ny = y + dy[i];
        if(nx < 1 || ny < 1 || nx > 8 || ny > 8 || C[nx][ny]) continue;
        nxt.pb({deg(nx, ny), nx, ny});
    }
    sort(nxt.begin(), nxt.end(), [](V a, V b){return a.d < b.d;});
    for(V v : nxt){
        dfs(v.x, v.y, s + 1);
    }
    C[x][y] = 0;
}
signed main(){
    int x, y;
    cin >> x >> y;
    dfs(y, x, 1);
    return 0;
}

Download Speed

Dinic

#include <bits/stdc++.h>
#define pb push_back
#define int long long
using namespace std;
struct pipe{
    int u, v, f;
};
const int inf = 4e12;
int t;
array<int, 504> lvl, P;
array<vector<int>, 504> G;
vector<pipe> E;
int bfs(int s){
    int u, v;
    queue<int> Q;
    Q.push(s);
    lvl[s] = 1;
    while(!Q.empty()){
        u = Q.front();
        Q.pop();
        for(int i : G[u]){
            v = E[i].v;
            if(lvl[v] || !E[i].f) continue;
            lvl[v] = lvl[u] + 1;
            Q.push(v);
        }
    }
    return lvl[t];
}
int dfs(int u, int f){
    if(u == t || !f) return f;
    int wut, ans = 0;
    for(int &i = P[u]; i < G[u].size(); i++){
        pipe &e = E[G[u][i]], &b = E[G[u][i] ^ 1];
        if(lvl[e.v] == lvl[u] + 1){
            wut = dfs(e.v, min(e.f, f));
            e.f -= wut;
            b.f += wut;
            f -= wut;
            ans += wut;
        }
    }
    return ans;
}
int dinic(int s){
    int ans = 0, tmp;
    while(1){
        for(int &l : lvl) l = 0;
        if(!bfs(s)) break;
        while(1){
            for(int &p : P) p = 0;
            if(tmp = dfs(s, inf)) ans += tmp;
            else break;
        }
    }
    return ans;
}
signed main(){
    int n, m, a, b, c, cnt = 0;
    cin >> n >> m;
    while(m--){
        cin >> a >> b >> c;
        G[a].pb(cnt++);
        G[b].pb(cnt++);
        E.pb({a, b, c});
        E.pb({b, a, 0});
    }
    t = n;
    cout << dinic(1);
    return 0;
}

Police Chase

Dinic

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
struct pipe{
    int u, v, f;
};
const int inf = 1e3;
int t;
array<int, 504> lvl, P, vis;
array<vector<int>, 504> G;
vector<pipe> E;
int bfs(int s){
    int u, v;
    queue<int> Q;
    Q.push(s);
    lvl[s] = 1;
    while(!Q.empty()){
        u = Q.front();
        Q.pop();
        for(int i : G[u]){
            v = E[i].v;
            if(lvl[v] || !E[i].f) continue;
            lvl[v] = lvl[u] + 1;
            Q.push(v);
        }
    }
    return lvl[t];
}
int dfs(int u, int f){
    if(u == t || !f) return f;
    int wut, ans = 0;
    for(int &i = P[u]; i < G[u].size(); i++){
        pipe &e = E[G[u][i]], &b = E[G[u][i] ^ 1];
        if(lvl[e.v] == lvl[u] + 1){
            wut = dfs(e.v, min(e.f, f));
            e.f -= wut;
            b.f += wut;
            f -= wut;
            ans += wut;
        }
    }
    return ans;
}
int dinic(int s){
    int ans = 0, tmp;
    while(1){
        for(int &l : lvl) l = 0;
        if(!bfs(s)) break;
        while(1){
            for(int &p : P) p = 0;
            if(tmp = dfs(s, inf)) ans += tmp;
            else break;
        }
    }
    return ans;
}
void go(int u, int c){
    if(vis[u]) return;
    vis[u] = c;
    for(int i : G[u]){
        if(!E[i].f) continue;
        go(E[i].v, c);
    }
}
signed main(){
    int n, m, a, b, cnt = 0;
    cin >> n >> m;
    while(m--){
        cin >> a >> b;
        G[a].pb(cnt++);
        G[b].pb(cnt++);
        E.pb({a, b, 1});
        E.pb({b, a, 1});
    }
    t = n;
    cout << dinic(1) << "\n";
    go(1, 1);
    go(t, 2);
    for(pipe e : E){
        if(e.f) continue;
        if(vis[e.u] && vis[e.v] && vis[e.u] != vis[e.v]){
            cout << e.u << " " << e.v << "\n";
        }
    }
    return 0;
}

School Dance

二分圖匹配

#include <bits/stdc++.h>
#define pb push_back
using namespace std;
array<bool, 504> vis;
array<int, 504> mate;
array<vector<int>, 504> G;
int rob(int u){
    for(int v : G[u]){
        if(vis[v]) continue;
        vis[v] = 1;
        if(!mate[v] || rob(mate[v])){
            mate[v] = u;
            return 1;
        }
    }
    return 0;
}
signed main(){
    int n, m, k, a, b, cnt = 0;
    cin >> n >> m >> k;
    while(k--){
        cin >> a >> b;
        G[a].pb(b);
    }
    for(int i = 1; i <= n; i++){
        for(bool &v : vis) v = 0;
        cnt += rob(i);
    }
    cout << cnt << "\n";
    for(int i = 1; i <= m; i++){
        if(mate[i]){
            cout << mate[i] << " " << i << "\n";
        }
    }
    return 0;
}

Distinct Routes

Dinic

#include <bits/stdc++.h>
#define pb push_back
#define ppb pop_back
using namespace std;
struct pipe{
    int u, v, f;
};
const int inf = 1e3;
int t;
array<bool, 504> vis;
array<int, 504> lvl, P;
array<vector<int>, 504> G;
vector<int> ans;
vector<pipe> E;
int bfs(int s){
    int u, v;
    queue<int> Q;
    Q.push(s);
    lvl[s] = 1;
    while(!Q.empty()){
        u = Q.front();
        Q.pop();
        for(int i : G[u]){
            v = E[i].v;
            if(lvl[v] || !E[i].f) continue;
            lvl[v] = lvl[u] + 1;
            Q.push(v);
        }
    }
    return lvl[t];
}
int dfs(int u, int f){
    if(u == t || !f) return f;
    int wut, ans = 0;
    for(int &i = P[u]; i < G[u].size(); i++){
        pipe &e = E[G[u][i]], &b = E[G[u][i] ^ 1];
        if(lvl[e.v] == lvl[u] + 1){
            wut = dfs(e.v, min(e.f, f));
            e.f -= wut;
            b.f += wut;
            f -= wut;
            ans += wut;
        }
    }
    return ans;
}
int dinic(int s){
    int ans = 0, tmp;
    while(1){
        for(int &l : lvl) l = 0;
        if(!bfs(s)) break;
        while(1){
            for(int &p : P) p = 0;
            if(tmp = dfs(s, inf)) ans += tmp;
            else break;
        }
    }
    return ans;
}
bool run(int u){
    if(vis[u]) return 0;
    ans.pb(u);
    if(u == t){
        cout << ans.size() << "\n";
        for(int a : ans) cout << a << " ";
        cout << "\n";
        return 1;
    }
    vis[u] = 1;
    for(int i : G[u]){
        if(i & 1 || E[i].f) continue;
        if(run(E[i].v)){
            E[i].f++;
            vis[u] = 0;
            return 1;
        }
    }
    ans.ppb();
    vis[u] = 0;
    return 0;
}
signed main(){
    int n, m, a, b, cnt = 0;
    cin >> n >> m;
    while(m--){
        cin >> a >> b;
        G[a].pb(cnt++);
        G[b].pb(cnt++);
        E.pb({a, b, 1});
        E.pb({b, a, 0});
    }
    t = n;
    cout << (cnt = dinic(1)) << "\n";
    while(cnt--){
        ans.clear();
        run(1);
    }
    return 0;
}