The 2024 ICPC Asia Kunming Regional Contest

2024/12/9 ICPC Competition

---

qoj補題鏈接

有了上次南京打鐵的慘痛經歷這次也是成功拿銅了。雖然差130罰時銀有點可惜，但也算是自己短暫的oi生涯的一個總結吧。

---

M. Matrix Construction

M. 題意

構造一個$n\times m$的排列矩陣使得任意兩個相鄰位置的和是唯一的。
n, m ~ 1e3

你説它簡單吧，大部分人都卡了一個小時。你説它難吧，想到用斜綫就很顯然，挺微妙的簽到題。

複雜度 $O(nm)$。

M. 代碼

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

#define ll long long

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
  
    int t; cin >> t;
    while (t --) {
        int n, m; cin >> n >> m;
        vector<vector<int>> a(n, vector<int>(m));
        for (int i = 0, k = 0; i < n+m-1; ++ i) {
            int x = min(i, n-1);
            int y = max(0, i-(n-1));
            while (x >= 0 && y >= 0 && x < n && y < m) {
                a[x][y] = ++ k, -- x, ++ y;
            }
        }
        cout << "Yes\n";
        for (int i = 0; i < n; ++ i) {
            for (int j = 0; j < m; ++ j) {
                cout << a[i][j] << ' ';
            }
            cout << '\n';
        }
    }
} 

---

H. Horizon Scanning

H. 題意

找出最小的扇形的角度使得其任意旋轉角度都能覆蓋$k$個點。
k, n ~ 2e5

極端的情況就是覆蓋了$k-1$個點然後再往順時和逆時方向擴一個點，極角排序枚舉一下起始位置取最大值即可。

複雜度是 $O(nlogn)$ 。

H. 代碼

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

#define ld long double
#define ll long long

struct Point {
    ld x, y, ang;
    Point() {};
    Point(ld x, ld y): x(x), y(y), ang(atan2(y, x)) {};
    bool operator<(Point p) {
        return ang < p.ang;
    }
};

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cout << setprecision(18);
  
    ld PI = M_PI;
  
    int t; cin >> t;
    while (t --) {
        int n, k; cin >> n >> k;
        vector<Point> pts;
        for (int i = 0; i < n; ++ i) {
            int x, y; cin >> x >> y;
            pts.emplace_back(Point(x, y));

        }
        sort(pts.begin(), pts.end());
        for (int i = 1; i <= 2; ++ i) {
            for (int j = 0; j < n; ++ j) {
                Point p = pts[j];
                p.ang += i * 2 * PI;
                pts.emplace_back(p);
            }
        }
        ld res = 0;
        for (int i = 0; i < n; ++ i) res = max(res, pts[i+k].ang - pts[i].ang);
        cout << res << '\n';
    }
} 

---

J. Just another Sorting Problem

J. 題意

有一個排列，Alice能交換任意位置，Bob能交換相鄰位置，在有限回合内排列有序則Alice贏，判斷最優策略下誰贏。
n ~ 1e5

對於大的$n$顯然只有當第一次輪到Bob時排列是有序Alice才贏。有一個萬惡的edge case是$n=3$（WA了三發），此時若所有位置不是有序的，Bob的任意操作都會使一個位置有序。

複雜度是 $O(n)$。

J. 代碼

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

#define ll long long

string solve(int n, int cnt, string s) {
    if (n == 1) return "Alice";
    if (n == 2) return "Alice";
    if (n == 3) {
        if (cnt == 1 && s == "Alice") return "Alice";
        if (cnt == 0 && s == "Bob") return "Alice";
        if (cnt == 3 && s == "Bob") return "Alice";
        return "Bob";
    }
    if (cnt == n-2 && s == "Alice") return "Alice";
    if (cnt == n && s == "Bob") return "Alice";
    return "Bob";
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
  
    int t; cin >> t;
    while (t --) {
        int n; cin >> n;
        string s; cin >> s;
        vector<int> a(n);
        for (int i = 0; i < n; ++ i) cin >> a[i];
        int cnt = 0;
        for (int i = 0; i < n; ++ i) cnt += a[i] == (i+1);
        cout << solve(n, cnt, s) << '\n';
    }
} 

---

G. GCD

G. 題意

有$a$和$b$，每次操作可以把其中一個減去$gcd(a, b)$，求最少操作使它們變成0。
a ~ 5e3
b ~ 1e18

操作等價於兩邊都除以$gcd$后$-1$的操作，觀察到可以貪心地構造$gcd$為2的倍數，得到最優解不劣於$2loga$的結論，所以可以直接bfs枚舉這些可能解。

複雜度是 $O(a^2)$。

G. 代碼

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

#define ld long double
#define ll long long

ll gcd(ll a, ll b) {
    return b == 0 ? a : gcd(b, a % b);
}

int bfs(ll a, ll b) {
    queue<pair<ll, ll>> q;
    q.emplace(a, b);
    int d = 0;
    while (!q.empty()) {
        int sz = q.size();
        while (sz --) {
            auto [ca, cb] = q.front(); q.pop();
            if (ca == 0 && cb == 0) return d;

            ll g = gcd(ca, cb);
            ca /= g, cb /= g;
            if (ca) q.emplace(ca-1, cb);
            if (cb) q.emplace(ca, cb-1);  
        }
        ++ d;
    }
    return -1;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
  
    int t; cin >> t;
    while (t --) {
        ll a, b; cin >> a >> b;
        cout << bfs(a, b) << '\n';
    }
} 

---

C. Coin

C. 題意

考慮一個變種的約瑟夫環問題，每次淘汰所有$1+xk$的人，求最后剩下的位置。
n, k ~ 1e12

考慮直接模擬，解完$n - 1 -\lfloor (n-1)/k \rfloor$的問題后把位置分成$k-1$的塊就能映射回來，問題是當$n/k$很小的時候要進行很多輪模擬。觀察到一些連續的輪次的淘汰位置是有規律的，具體來説就是把$n$分成$k$的塊，每個塊裏的淘汰位置形成等差數列。顯然，這樣的最大輪次由最後一個塊決定，記這個輪次為$r$，可以遞歸$n - \lceil n/k \rceil *r$，把子問題的位置分成$k-r$的塊就能映射到原問題答案所在的塊，這個塊對應了一個公差$d$，把這個塊再分成$d$的塊就能算出這個塊的貢獻。

複雜度是 $O(\sqrt{n})$。

C. 代碼

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

#define ld long double
#define ll long long

ll solve(ll n, ll k) {
    if (n <= k) return n-1;
    ll seg = (n+k-1)/k;
    ll rem = n%k;
    ll stp = 1+(rem-1)/seg;
    ll nxt = solve(n - seg * stp, k);

    ll sid = nxt/(k-stp);
    ll pid = sid?(nxt%(k-stp))/sid:nxt;
    return nxt + sid * stp + min(stp, 1 + pid);
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
  
    int t; cin >> t;
    while (t --) {
        ll n, k; cin >> n >> k;
        cout << solve(n, k) + 1 << '\n';
    }
} 

L. Last Chance: Threads of Despair

L. 題意

給定一些士兵，每隻士兵有血量，可以攻擊造成一點傷害，死了會爆炸對所有單位造成一點傷害，判斷能否把殲滅對面的士兵。
n ~ 5e5
h ~ 1e9

不玩爐石啊，一開始以爲只有友方士兵會爆炸，每位血量大於1的士兵必然能攻擊，所有血量等於1的算一次攻擊，把對面的血量排個序，優先打血量低的，過程中纍加爆炸傷害 。但是樣例沒過，才發現敵方士兵也會爆炸，腦子就宕機了，於是把題放給隊友自己去搞C題了。搞完C題剩下半個小時，問了問隊友說沒想法就擺了，看題解說把對面的爆炸也統計進來就行了，最遺憾的一集。

複雜度是 $O(nlogn)$。

L. 代碼

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

#define ll long long

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
  
    int t; cin >> t;
    while (t --) {
        int n, m; cin >> n >> m;
        vector<int> a(n), b(m);
        for (int i = 0; i < n; ++ i) cin >> a[i];
        for (int i = 0; i < m; ++ i) cin >> b[i];

        sort(a.begin(), a.end());
        sort(b.begin(), b.end());

        ll exp = 0, dmg = 0;
        for (int i = 0; i < n; ++ i) dmg += (i == 0 && a[i] == 1) || (a[i] > 1);
        for (int i = 0; i < n; ++ i) -- a[i];

        int i = 0, j = 0;
        while ((i < n && a[i] <= exp) || (j < m && b[j] <= exp + dmg)) {
            if (i < n && a[i] <= exp) {
                ++ i, ++ exp; 
                continue;
            }
            if (j < m && b[j] <= exp + dmg) {
                dmg -= max(0ll, b[j] - exp);
                ++ j, ++ exp;
                continue;
            }
        }

        cout << (j == m ? "Yes" : "No") << '\n';
    }
} 

---

E. Extracting Weights

E. 題解

給定一顆樹，可以詢問路徑距離為$k$的點權異或，已知根節點的點權是0，判斷能否在$n$次詢問内判斷所有節點的權值。
n, k ~ 250

經典看完題解恍然大悟，怎麽就沒想到這種暴力解。考慮所有可能的詢問，總共就$n^2$個，每個詢問和根節點的點權條件對應了一個01係數的異或方程，可以高斯消元找出$n$條綫性無關的方程，詢問這些方程的解再高斯消元就能解出節點的點權。

複雜度是 $O(n^4)$。

E. 代碼

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

#define ll long long

#define N 300

struct equation {
    bool c[N];
    int v;
    int n;

    struct query {
        int u, v;
    } q;

    equation(): n(0), v(0) {
        memset(c, 0, sizeof(c));
        v = 0;
    };
    equation(int n, int i, int qu, int qv): n(n), v(0) { 
        memset(c, 0, sizeof(c));
        q.u = qu;
        q.v = qv;
    }

    inline equation& operator^=(equation& x) {
        assert(n == x.n);
        for (int i = 0; i < n; ++ i) c[i] ^= x.c[i];
        v ^= x.v;
        return *this;
    } 
};

int solve_eqts(vector<equation>& eqts, int n) {
    int res = 0;
    if (eqts.size() < n) return res;

    for (int i = 0; i < n; ++ i) {
        for (int j = i; j < eqts.size(); ++ j) {
            if (eqts[j].c[i]) {
                swap(eqts[i], eqts[j]);
                ++ res;
                break;
            }
        }
        for (int j = 0; j < eqts.size(); ++ j) {
            if (i != j && eqts[j].c[i]) eqts[j] ^= eqts[i];
        }
    }
    return res;
}

vector<int> G[N];
int dep[N], f[N];

void dfs(int u, int fa, int d) {
    f[u] = fa;
    dep[u] = d;
    for (auto v : G[u]) if (v != fa) dfs(v, u, d+1);
}

int get_eqt(int u, int v, equation& e) {
    e.c[u-1] = e.c[v-1] = 1;
    if (dep[u] > dep[v]) return 1 + get_eqt(f[u], v, e);
    if (dep[u] < dep[v]) return 1 + get_eqt(u, f[v], e);
    if (u != v) return 2 + get_eqt(f[u], f[v], e);
    return 1;
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
  
    int n, k; cin >> n >> k;
    for (int i = 1; i <= n-1; ++ i) {
        int u, v; cin >> u >> v;
        G[u].emplace_back(v);
        G[v].emplace_back(u);
    }
    dfs(1, 1, 0);

    vector<equation> eqts;
    eqts.emplace_back(n, -1, 0, 0);
    get_eqt(1, 1, eqts.back());
    for (int i = 1; i <= n; ++ i) {
        for (int j = i+1; j <= n; ++ j) {
            eqts.emplace_back(n, -1, i, j);
            if (get_eqt(i, j, eqts.back()) != k+1) {
                eqts.pop_back();
            }
        }
    }

    int res = solve_eqts(eqts, n);
    if (res == n) {
        eqts.erase(eqts.begin()+n, eqts.end());

        cout << "YES\n? " << n-1 << ' ';
        for (int i = 1; i < n; ++ i) cout << eqts[i].q.u << ' ' << eqts[i].q.v << " \n"[i==n-1];
        cout.flush();

        for (int i = 1; i < n; ++ i) {
            memset(eqts[i].c, 0, sizeof(eqts[i].c));
            get_eqt(eqts[i].q.u, eqts[i].q.v, eqts[i]);
            cin >> eqts[i].v;
        }
        solve_eqts(eqts, n);

        cout << "! ";
        for (int i = 1; i < n; ++ i) cout << eqts[i].v << " \n"[i==n-1];
        cout.flush();
    } else {
        cout << "NO\n";
        cout.flush();
    }
} 

---

F. Flowers

F. 題解

定義一個花圖，有$n$個點，從根節點1分叉出數條無叉的鏈，第一層的所有點兩兩互質，每條鏈都是有序的且是其第一層節點的倍數。求可行花圖的個數。
n ~ 1e10

先化簡題目，質數必然都在第一層，所以合數不能在第一層，問題就變成把合數分到其中一個質因子鏈上的方案個數。

樸素的做法是從小到大枚舉質因子遍歷所有合數，但是這樣的複雜度是綫性的。優化的關鍵在於把所有合數除以自己的最大質因子，這個數集的大小大約是$10^6$，對於遍歷中最外層的合數，考慮在遍歷時判斷當前質因子是不是這樣的合數的最大質因子，是的話就把所有可行的不小於的最大質因子也一并統計，這樣就只需要遍歷這個比較小的數集。具體需要知道$\lfloor n/x \rfloor$内的質數個數，可以用min_25篩預處理出來。

F. 代碼

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

#define ll long long

int MOD = 0;

struct mint {
    ll v;
    mint() {};
    mint(ll v): v(v%MOD) {};
    mint operator+(mint x) {
        return v + x.v;
    }
    mint operator-(mint x) {
        return v - x.v + MOD;
    }
    mint operator*(mint x) {
        return v * x.v;
    }
    mint pow(ll p) {
        if (p == 0) return 1;
        if (p == 1) return v;
        return mint(v*v).pow(p/2) * mint(v).pow(p&1);
    }
};

struct min25 {
    static const int P = 500010;
    ll n, m, s, w[P];
    int p[P], np[P], pc;
    ll g[P];
  
    void sieve(int k) {
        pc = 0;
        memset(np, 0, sizeof np);
        for (int i = 1; i <= k; ++ i) {
            if (!np[i]) p[pc ++] = i;
            for (int j = 1; j < pc && 1ll*i*p[j] <= k; ++ j) {
                np[i * p[j]] = 1;
                if (i % p[j] == 0) break;
            }
        }
    }

    inline int id(ll x) { return x < s ? x : m-n/x; } ;
  
    void init(ll _n) {
        n = _n, m = 0, s = ceil(sqrt(n));

        sieve(s);
        for (int i = 0; i < s; ++ i) w[m ++] = i;
        for (int i = s; i > 0; -- i) if (n/i >= s) w[m ++] = n/i;
        for (int i = 0; i < m; ++ i) g[i] = max(0ll, w[i] - 1);
        for (int i = 1, j = 0; i < pc; ++ i) {
            while (j < m && 1ll*p[i]*p[i] > w[j]) ++ j;
            for (int k = m-1; k >= j; -- k) {
                int u = id(w[k]/p[i]);
                int v = id(p[i-1]);
                g[k] = g[k] - (g[u] - g[v]);
            }
        }
    }

    mint go(ll x, int k, int d) {
        mint res(max(1, d));
        for (int i = max(1, k); i < pc; ++ i) {
            if (x * p[i] * p[i] <= n) {
                res = res * go(x * p[i], i, d + (i != k));
                continue;
            }

            ll pp = id(n/x) >= id(p[i]) ? g[id(n/x)] - g[id(p[i])] : 0;
            if (x * p[i] <= n) res = res * (d+(i!=k));
            res = res * mint(d+1).pow(pp);
            break;   
        }

        return res;
    }
} m25;

int main() {
#ifdef TEST
    freopen("zz.in", "r+", stdin);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
  
    ll n, p; cin >> n >> p;
    MOD = p;
    m25.init(n);
    cout << m25.go(1, 0, 0).v << '\n';
} 

其他

感覺B也能補，沒做到L還是有點意難平，只能説菜就多練吧，香港站大概率也是寄，銅牌封頂了。