2024-2025 CTU Open Contest
===
比賽鏈結
---
https://codeforces.com/gym/105442/

比賽影片
---
{%youtube FhDS6EqFr3c%}

記分板
---

題解
---
### A. Flag Bearer
---
#### 題目摘要
將旗語轉成英文字母後再位移，最後再轉成旗語

#### 想法
實作題，加油!!!

:::spoiler 實作

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define F first
#define S second

int moves[8][2]={{1, 0}, {1, -1}, {0, -1}, {-1, -1}, {-1, 0}, {-1, 1}, {0, 1}, {1, 1}};

int tot=0;
int read(){
    char c[10][10];
    for(int i=0;i<9;i++) for(int j=0;j<9;j++) cin >> c[i][j];
    pii dir={-1, -1};
    for(int i=0;i<8;i++){
        if (c[moves[i][0]+4][moves[i][1]+4]=='#'){
            if (dir.F==-1) dir.F=i;
            else dir.S=i;
        }
    }
    if (dir.F==4&&dir.S==6) return 'j'-'a';
    if (dir.F==4&&dir.S==7) return 'v'-'a';
    if (dir.F==3&&dir.S==6) return 'y'-'a';
    if (dir.F==6&&dir.S==7) return 'z'-'a';
    if (dir.F==0) return dir.S-1;
    if (dir.F==1&&dir.S-dir.F<=2) return 'h'-'a'+(dir.S-1)-1;
    if (dir.F==1) return 'k'-'a'+(dir.S-3)-1;
    if (dir.F==2) return 'o'-'a'+(dir.S-dir.F)-1;
    if (dir.F==3) return 't'-'a'+(dir.S-dir.F)-1;
    if (dir.F==5) return 'w'-'a'+(dir.S-dir.F)-1;
}

pii convert(int x){
    pii dir;
    if (x==9) return {4, 6};
    if (x==21) return {4, 7};
    if (x==24) return {3, 6};
    if (x==25) return {6, 7};
    if (0<=x&&x<=6) return {0, x+1};
    if (7<=x&&x<=8) return {1, x-5};
    if (10<=x&&x<=13) return {1, x-6};
    if (14<=x&&x<=18) return {2, x-11};
    if (19<=x&&x<=20) return {3, x-15};
    if (22<=x&&x<=23) return {5, x-16};
}

void output(pii x){
    char c[10][10];
    for(int i=0;i<9;i++) for(int j=0;j<9;j++) c[i][j]='.';
    c[4][4]='*';
    for(int i=0;i<8;i++){
        if (x.F==i||x.S==i){
            for(int k=1;k<4;k++){
                c[4+moves[i][0]*k][4+moves[i][1]*k]='#';
            }
        }
    }
    for(int i=0;i<9;i++){
        for(int j=0;j<9;j++) cout << c[i][j];
        cout << '\n';
    }
}

void solve(){
    int n, m;
    cin >> n >> m;
    for(int i=0;i<n;i++){
        int x=read();
        x+=m;
        x%=26;
        output(convert(x));
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int _t=1;
    // cin >> _t;
    while(_t--) solve();
}

:::

### B. Cowpproximation
---
#### 題目摘要

#### 想法

:::spoiler 實作

:::

### C. Reptile Eggs
---
#### 題目摘要

#### 想法

:::spoiler 實作

:::

### D. Fishception
---
#### 題目摘要
給你很多點，這些點原本都是各自長方形的四個角，保證任何一個長方形不會相交，並且比較大的長方形會包含所有比較小的長方形，並且除了最小的長方形，每個長方形會包住一個長方形，問你最小的長方形的面積。
#### 想法
發現根據限制最左、右、上、下的點一定是最外層那個長方形的點，對每個點的x和y sort過後，每次拔掉最外層的點，剩下四個點就是答案要的四個點了。
:::spoiler 實作

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define F first
#define S second
#define rep(a, b, c) for(int a = b; a < c; a++)
#define pb push_back
#define all(x) (x).begin(), (x).end()

const int IINF = 1e9 + 7;

void solve(){
    int n; cin >> n;
    vector<tuple<ll, ll, int>> X(n), Y(n);
    rep (i, 0, n) {
        auto &[x, y, id] = X[i];
        cin >> x >> y;
        id = i;
        auto &[y2, x2, idd] = Y[i];
        y2 = y, x2 = x, idd = id;
    }
    sort(all(X));
    sort(all(Y));
    deque<tuple<ll, ll, int>> XX, YY;
    for (auto a : X) XX.pb(a);
    for (auto a : Y) YY.pb(a);
    set<int> st;
    while (n - st.size() > 4) {
        while (st.count(get<2>(XX.front()))) XX.pop_front();
        while (st.count(get<2>(XX.back()))) XX.pop_back();
        // while (st.count(get<2>(YY.front()))) YY.pop_front();
        // while (st.count(get<2>(YY.back()))) YY.pop_back();
        st.insert(get<2>(XX.front()));
        // cout << get<0>(XX.front()) << ' ' << get<1>(XX.front()) << '\n';
        XX.pop_front();
        st.insert(get<2>(XX.back()));
        // cout << get<0>(XX.back()) << ' ' << get<1>(XX.back()) << '\n';
        XX.pop_back();
        // while (st.count(get<2>(XX.front()))) XX.pop_front();
        // while (st.count(get<2>(XX.back()))) XX.pop_back();
        while (st.count(get<2>(YY.front()))) YY.pop_front();
        while (st.count(get<2>(YY.back()))) YY.pop_back();
        st.insert(get<2>(YY.front()));
        // cout << get<1>(YY.front()) << ' ' << get<0>(YY.front()) << '\n';
        YY.pop_front();
        st.insert(get<2>(YY.back()));
        // cout << get<1>(YY.back()) << ' ' << get<0>(YY.back()) << '\n';
        YY.pop_back();
        assert(st.size() % 4 == 0);
    }
    // cerr << XX.size() << ' ' << YY.size() << '\n';
    while (st.count(get<2>(XX.front()))) XX.pop_front();
    while (st.count(get<2>(XX.back()))) XX.pop_back();
    while (st.count(get<2>(YY.front()))) YY.pop_front();
    while (st.count(get<2>(YY.back()))) YY.pop_back();
    // for (auto [x, y, i] : XX) cout << x << ' ' << y << ' ' << i << '\n';
    // for (auto [y, x, i] : YY) cout << x << ' ' << y << ' ' << i << '\n';
    st.insert(get<2>(YY.front()));
    st.insert(get<2>(YY.back()));
    while (st.count(get<2>(XX.front()))) XX.pop_front();
    while (st.count(get<2>(XX.back()))) XX.pop_back();
    auto [x, y, i] = XX[0];
    auto [y2, x2, ii] = YY.back();
    auto [y3, x3, iii] = YY[0];
    // cout << x << ' ' << y << ' ' << x2 << ' ' << y2 << ' ' << x3 << ' ' << y3 << '\n';
    cout << abs((x2 - x) * (y3 - y) - (x3 - x) * (y2 - y)) << '\n';
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int _t=1;
    // cin >> _t;
    while(_t--) solve();
}

:::

### E. Pigpartite Giraffe
---
#### 題目摘要

#### 想法

:::spoiler 實作

:::

### F. Hamster
---
#### 題目摘要
給$N \times M$的圖，點權$a_{ij}$，求從左上走到右下不經過走過的點的最大權重和。
#### 想法

發現N, M其中一個是奇數一定能全拿。

若是偶數的話，可以觀察到最好狀況一定只會不取一個點，而可以選的點的$i + j$要是奇數，找到最小值減掉就是答案了。

:::spoiler 實作

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define F first
#define S second
#define rep(a, b, c) for(int a = b; a < c; a++)

const int IINF = 1e9 + 7;

void solve(){
    int n, m; cin >> n >> m;
    vector g(n, vector<int>(m));
    ll ans = 0;
    rep (i, 0, n) rep (j, 0, m) {
        cin >> g[i][j];
        ans += g[i][j];
    }
    if ((n & 1) || (m & 1)) {
        cout << ans << '\n';
    } else {
        int mi = IINF;
        rep (i, 0, n) rep (j, 0, m) if ((i + j) & 1) mi = min(mi, g[i][j]);
        cout << ans - mi << '\n';
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int _t=1;
    // cin >> _t;
    while(_t--) solve();
}

:::

### G. Pray Mink
---
#### 題目摘要
給正整數$N$，每次可以刪掉其中一個位數，若出現前導0就把前導0全刪，求在第一次出現合數前能出現多少次質數。
#### 想法
位數只有10，開心dfs，刪掉一個位數就把深度加一，出現合數就剪枝，出現前導0就不要加深度，答案就是能走到的最大深度

判質數用根號，讚

:::spoiler 實作

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define F first
#define S second
#define rep(a, b, c) for(int a = b; a < c; a++)
#define pb push_back

const int IINF = 1e9 + 7;

void solve(){
    string s; cin >> s;
    int n = s.size();
    auto check = [&](int p) -> bool {
        if (p == 1) return false;
        for (int i = 2; i * i <= p; i++) {
            if (p % i == 0) return false;
        }
        return true;
    };
    if (check(stoi(s)) == 0) {
        cout << 0 << '\n';
        return;
    }
    int ans = 0;
    auto dfs = [&](auto self, int mask, int dep) -> void {
        ans = max(ans, dep);
        if (__builtin_popcount(mask) == 1) return;
        rep (i, 0, n) if (mask >> i & 1) {
            string tmp = "";
            rep (j, 0, n) if (i != j && (mask >> j & 1)) tmp.pb(s[j]);
            if (tmp[0] == '0') {
                self(self, mask ^ (1 << i), dep);
            } else if (check(stoi(tmp))) {
                self(self, mask ^ (1 << i), dep + 1);
            }
        }
    };
    dfs(dfs, (1 << n) - 1, 1);
    cout << ans << '\n';
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int _t=1;
    // cin >> _t;
    while(_t--) solve();
}

:::

### H. Ornithology
---
#### 題目摘要
兩個水管，被分成$n$個位置。一開始所有鳥都在第一個水管上，並且第$i$個位置有$p_i$隻鳥，每隻鳥會有到第二根水管的目標位置，求所有鳥從第一根水管到第二根的路徑有幾個交點(不會有鳥飛行路徑一模一樣)

#### 想法
裸逆序數對

:::spoiler 實作

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define F first
#define S second
#define rep(a, b, c) for(int a = b; a < c; a++)

const int IINF = 1e9 + 7;

const int N=2e5+10;
ll bit[N];

int n;
void update(int x, ll k){for(;x<=n;x+=x&-x) bit[x]+=k;}
ll query(int x){
    ll res=0;
    for(;x;x-=x&-x) res+=bit[x];
    return res;
}

void solve(){
    cin >> n;
    vector<int> v;
    for(int i=0;i<n;i++){
        int p;
        cin >> p;
        vector<int> tmp(p);
        for(auto &x:tmp) cin >> x;
        sort(tmp.begin(), tmp.end());
        for(auto x:tmp) v.push_back(x+1);
    }
    ll ans=0;
    for(auto x:v){
        ans+=query(n)-query(x);
        update(x, 1);
    }
    cout << ans << '\n';
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int _t=1;
    // cin >> _t;
    while(_t--) solve();
}

:::

### I. P||k Cutting
---
#### 題目摘要
求有多少區間元素or起來是$K$

#### 想法
對位元做事，找以位置作為左端的右端合法區間，最後再求一個位置的所有位元的右端合法區間的交集，拿區間長度更新答案就好

:::spoiler 實作

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define F first
#define S second
#define rep(a, b, c) for(int a = b; a < c; a++)

const int IINF = 1e9 + 7;


void solve(){
    int n, k;
    cin >> n >> k;
    vector<int> a(n+1);
    vector<vector<int>> L(n+1, vector<int>(31, 0)), R(n+1, vector<int>(31, 0));
    for(int i=1;i<=n;i++) cin >> a[i];
    for(int j=0;j<=30;j++){
        vector<int> val(n+1, 0);
        for(int i=1;i<=n;i++) val[i]=(a[i]>>j&1);
        int z=1;
        for(int i=1;i<=n;i++){
            if (z<i) z=i;
            while(z<=n&&val[z]==0) z++;
            if (k>>j&1){
                L[i][j]=z;
                R[i][j]=n+1;
            }else{
                L[i][j]=i;
                R[i][j]=z;
            }
        }
    }
    ll ans=0;
    for(int i=1;i<=n;i++){
        int l=L[i][0], r=R[i][0];
        for(int j=0;j<=30;j++){
            l=max(l, L[i][j]);
            r=min(r, R[i][j]);
        }
        ans+=max(0, r-l);
    }
    cout << ans << '\n';
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int _t=1;
    // cin >> _t;
    while(_t--) solve();
}

:::

### J. Rabid Rabbit
---
#### 題目摘要
一個長度為$N$的陣列及$Q$筆詢問，問$[L, R]$內有多少個不同的費氏數$F=a_i + a_j \ (L \leq i \leq j \leq R)$
#### 想法
觀察到$a_i$最大只有到$10^9$，根據我爆搜出來最多只需要維護45個費氏數，因此可以有個簡單的作法。

考慮詢問離線，讓左界從大到小，對每個費氏數維護他的一個左界以右的 $(\ell, \ r)$，代表$\,a_{\ell} + a_r = F$，可以取到這個費氏數的區間就是當詢問的右界$\ge r$。因此會很直覺地想要讓他的r越小越好，所以要做的就是在左界往左時好好維護每個費氏數的(l, r)，然後開一顆BIT維護答案就好。

複雜度$O(N \times 45 + Q \log N)$
:::spoiler 實作

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define F first
#define S second
#define rep(a, b, c) for(int a = b; a < c; a++)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define pii pair<int, int>
#define F first
#define S second


const int MAXN = 1e5 + 5;
const int IINF = 1e9 + 7;

int BIT[MAXN];

void mod(int x, int val) {
    while (x <= MAXN - 5) {
        BIT[x] += val;
        x += x & -x;
    }
}

int query(int x) {
    int res = 0;
    while (x) {
        res += BIT[x];
        x -= x & -x;
    }
    return res;
}

void solve(){
    int n, q; cin >> n >> q;
    vector<ll> a(n + 1), f;
    rep (i, 1, n + 1) cin >> a[i];
    f.pb(1);
    f.pb(2);
    while (f.end()[-2] + f.back() <= 2000000000) {
        f.pb(f.end()[-2] + f.back());
    }
    const int SZ = 45;
    vector<vector<pii>> que(n + 1);
    rep (i, 0, q) {
        int l, r; cin >> l >> r;
        l++, r++;
        que[l].pb({r, i});
    }
    vector<int> fid(SZ, n + 1);
    map<ll, int> mp;
    vector<int> ans(q, 0);
    for (int l = n; l > 0; --l) {
        rep (i, 0, SZ) {
            if (mp.find(f[i] - a[l]) == mp.end()) continue;
            if (mp[f[i] - a[l]] > fid[i]) continue; 
            if (fid[i] != n + 1) {
                mod(fid[i], -1);
            }
            fid[i] = mp[f[i] - a[l]];
            mod(fid[i], 1);
        }
        for (auto [r, id] : que[l]) {
            ans[id] = query(r);
        }
        mp[a[l]] = l;
    }
    rep (i, 0, q) cout << ans[i] << '\n';
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int _t=1;
    // cin >> _t;
    while(_t--) solve();
}

:::

### K. Fellow Sheep
---
#### 題目摘要
給你由很多個單位組成的一張圖，然後要你求最大流。

#### 想法
每個單位只有五條邊，然後每個單位的出點接在下一個單位的入點上，所以對每個單位個別算好以後取min就好。(好像其實是最小割但反正一樣)
:::spoiler 實作

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define F first
#define S second
#define rep(a, b, c) for(int a = b; a < c; a++)

const int IINF = 1e9 + 7;

void solve(){
    int n; cin >> n;
    int ans = IINF;
    rep (i, 0, n) {
        vector<int> a(5);
        rep (j, 0, 5) cin >> a[j];
        int g = min(a[0], a[1]);
        a[0] -= g;
        a[1] -= g;
        int sum = g;
        if (a[0]) a[3] += min(a[2], a[0]);
        else {
            a[0] += min(a[2], a[1]);
            sum += min(a[2], a[1]);
            a[3] -= min(a[2], a[1]);
        }
        sum += min(a[3], a[4]);
        ans = min(ans, sum);
    }
    cout << ans << '\n';
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int _t=1;
    // cin >> _t;
    while(_t--) solve();
}

:::

### L. Watchdogs
---
#### 題目摘要

#### 想法
用lca來算路徑長，將奇數長度路徑中間點先點好，如果是偶數，若其中一個已經有被點過的就跳過，否則將中間兩個點的邊存起來，最小值就會是這些邊重新建圖的最小點覆蓋。

觀察到樹上一條邊的兩個點深度可以分奇偶，因此可以用深度的奇偶性建張二分圖的流模型，跑個最大流加上原本點過的點就是答案。

複雜度應該是$O(N \sqrt N)$
:::spoiler 實作

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define F first
#define S second
#define rep(a, b, c) for(int a = b; a < c; a++)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define pii pair<int, int>
#define F first
#define S second

const int MAXN = 1e5 + 5;
const int IINF = 1e9 + 7;

struct Dinic {
    struct edge {
        int v, r; ll rc;
    };
    vector<vector<edge>> adj;
    vector<int> dis, it;
    Dinic(int n) : adj(n), dis(n), it(n) {}
    void add_edge(int u, int v, ll c) {
        adj[u].pb({v, adj[v].size(), c});
        adj[v].pb({u, adj[u].size() - 1, 0});
    }
    bool bfs(int s, int t) {
        fill(all(dis), IINF);
        queue<int> q;
        q.push(s);
        dis[s] = 0;
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (const auto &[v, r, rc] : adj[u]) {
                if (dis[v] < IINF || rc == 0) continue;
                dis[v] = dis[u] + 1;
                q.push(v);
            }
        }
        return dis[t] < IINF;
    }
    ll dfs(int u, int t, ll cap) {
        if (u == t || cap == 0) return cap;
        for (int &i = it[u]; i < (int)adj[u].size(); ++i) {
            auto &[v, r, rc] = adj[u][i];
            if (dis[v] != dis[u] + 1) continue;
            ll tmp = dfs(v, t, min(cap, rc));
            if (tmp > 0) {
                rc -= tmp;
                adj[v][r].rc += tmp;
                return tmp;
            }
        }
        return 0;
    }
    ll flow(int s, int t) {
        ll ans = 0, tmp;
        while (bfs(s, t)) {
            fill(all(it), 0);
            while ((tmp = dfs(s, t, IINF)) > 0) {
                ans += tmp;
            }
        }
        return ans;
    }
};

void solve(){
    int n, m; cin >> n >> m;
    vector<vector<int>> adj(n);
    rep (i, 0, n - 1) {
        int a, b; cin >> a >> b;
        adj[a].pb(b);
        adj[b].pb(a);
    }
    vector<int> dep(n);
    vector<vector<int>> pa(n, vector<int>(20));
    auto dfs = [&](auto self, int u, int p) -> void {
        for (int v : adj[u]) {
            if (v == p) continue;
            dep[v] = dep[u] + 1;
            pa[v][0] = u;
            self(self, v, u);
        }
    };
    dep[0] = 0;
    dfs(dfs, 0, -1);
    rep (j, 1, 20) rep (i, 0, n) pa[i][j] = pa[pa[i][j - 1]][j - 1];
    vector<int> ok(n, 0);
    vector<pii> mou;
    auto lca = [&](int a, int b) -> int {
        if (dep[a] < dep[b]) swap(a, b);
        int d = dep[a] - dep[b];
        rep (i, 0, 20) if (d >> i & 1) a = pa[a][i];
        if (a == b) return a;
        for (int i = 19; i >= 0; --i) {
            if (pa[a][i] != pa[b][i]) {
                a = pa[a][i];
                b = pa[b][i];
            }
        }
        return pa[a][0];
    };
    rep (i, 0, m) {
        int a, b; cin >> a >> b;
        int p = lca(a, b);
        int dis = dep[a] + dep[b] - dep[p] * 2;
        if (dep[a] < dep[b]) swap(a, b);
        if (dis & 1 ^ 1) {
            dis /= 2;
            rep (j, 0, 20) if (dis >> j & 1) {
                a = pa[a][j];
            }
            ok[a] = 1;
        } else {
            mou.pb({a, b});
        }
    }
    Dinic G(n + 2);
    int s = n, t = s + 1;
    rep (i, 0, n) {
        if (dep[i] & 1) G.add_edge(i, t, 1);
        else G.add_edge(s, i, 1);
    }
    for (auto [a, b] : mou) {
        int p = lca(a, b);
        int dis = dep[a] + dep[b] - dep[p] * 2;
        // cout << dis << ' ' << a << ' ' << b << ' ';
        dis /= 2;
        rep (i, 0, 20) if (dis >> i & 1) a = pa[a][i];
        // cout << a << '\n';
        if (ok[a] || ok[pa[a][0]]) continue;
        if (dep[a] & 1) G.add_edge(pa[a][0], a, 1);
        else G.add_edge(a, pa[a][0], 1);
    }
    int ans = 0;
    rep (i, 0, n) {
        // cout << ok[i] << ' ';
        ans += ok[i];
    }
    cout << ans + G.flow(s, t) << '\n';
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int _t=1;
    // cin >> _t;
    while(_t--) solve();
}

:::