ICPC 2024 Thailand - Chulalongkorn University Internal Round
===
比賽鏈結
---
https://codeforces.com/gym/105307

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

記分板
---

題解
---
### A. Card Dealer Game
---
#### 題目摘要

兩個人玩遊戲，有$\,n\,$疊卡牌，第$\,i\,$疊裡有$\,p\,$張紅牌跟$\,q\,$張藍牌，其中一個人一開始是莊家
每一輪遊戲中莊家會選擇一疊還沒被選過的卡牌
從中隨機抽一張，如果是紅色就不變，藍色就換另一個人當莊家，然後進行下一輪，玩到每疊都被選過為止

問一開始是莊家最後還是莊家的機率
#### 想法

簡單DP，維護兩個變數好好轉移就好

:::spoiler 實作

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

#define rep(a, b, c) for (int a = b; a < c; a++)
#define ll long long
#define PEPPA ios_base::sync_with_stdio(0), cin.tie(0)

const int MOD = 1e9 + 7;

ll fpow(ll x, ll exp) {
    ll res = 1;
    while (exp) {
        if (exp & 1) res = res * x % MOD;
        x = x * x % MOD;
        exp >>= 1;
    }
    return res;
}

void solve() {
    int n; cin >> n;
    ll deal = 1, op = 0;
    rep (i, 0, n) {
        ll p, q; cin >> p >> q;
        ll div = fpow(p + q, MOD - 2);
        ll nd = (deal * p % MOD * div % MOD + op * q % MOD * div % MOD) % MOD,
           no = (deal * q % MOD * div % MOD + op * p % MOD * div % MOD) % MOD;
        deal = nd;
        op = no;
    }
    cout << deal << '\n';
}

int main() {
    PEPPA;
    int t = 1;
    // cin >> t; 
    while(t--) solve();
}

:::

### B. Emma and the Pixie dust
---
#### 題目摘要
有$M$元素$A_i$(元素兩兩不相等)，要挑$N$個元素，並合併$K$次，合併的方式是選兩數$X,\ Y$，把兩數移除後並將$gcd(X,\ Y)$放進去，問
最後的元素和最大為多少

#### 想法
已知最後只會有$(N-K)$個元素，而現在先證明這$(N-K)$個元素只有一個是被$gcd$過的是最好的：
在$a>x的情況下，gcd(a, x)的最大可能是a/2$，而假設$a,\ b都在(N-K)的元素中(b>a)，若取兩個gcd會答案最少減少(b-\frac{b}{2})+(a-\frac{a}{2})=\frac{a+b}{2}$，取一個$gcd答案做多減少(a-\frac{a}{2})+(\frac{a}{2}-1)=a-1$，因為$a,\ b$都是2的倍數，所以$\frac{a+b}{2}\ge a-1$，因此選只有一個$gcd$的比較好
因此先對$A$排序，並先假設前$(N-K)$大的是答案，再枚舉所有因數，去看$A$有多少元素包含這個因數，若數量超過$K+1$個(因為要做$K次gcd需要K+1$個數)，則這因數有可能能變成最後的元素之一。接下來有3種case：
1. $K+1$的數中沒有前$(N-K)$大的數：將第$(N-K)$大的元素換成$gcd$
2. $K+1$的數中有一個前$(N-K)$大的數：將出現的那個元素換成$gcd$
3. $K+1$的數中有兩個以上前$(N-K$)大的數：$(N-K)$個元素中有兩個以上被取$gcd$，因此不會是答案

實作能用調和級數做事，複雜度$O(N\log N)$

:::spoiler 實作

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

#define rep(a, b, c) for (int a = b; a < c; a++)
#define ll long long
#define PEPPA ios_base::sync_with_stdio(0), cin.tie(0)

const int N=5e6+10;
bool spe[N], vis[N];

void solve() {
    int m, n, k;
    cin >> m >> n >> k;
    vector<int> a(m);
    for(auto &x:a) cin >> x;
    sort(a.begin(), a.end(), greater<int>());
    for(int i=0;i<n-k;i++) spe[a[i]]=1;
    for(int i=0;i<m;i++) vis[a[i]]=1;
    ll ans=0;
    ll sum=0;
    for(int i=0;i<n-k;i++) sum+=a[i];
    for(int i=1;i<=5000000;i++){
        ll mn=a[n-k-1];
        int cnt=0;
        for(int j=0;j<=5000000;j+=i) if (vis[j]){
            cnt++;
            if (spe[j]){
                mn=j;
                break;
            }
            if (cnt>=k+1) break;
        }
        if (cnt>=k+1) ans=max(ans, sum-mn+i);
    }
    cout << ans << '\n';
}

int main() {
    PEPPA;
    solve();
}

:::

### C. Chopsticks
---
#### 題目摘要
給一陣列，求$\max\limits_{1<i<j<n}a_i \times a_j$

#### 想法
$N^2 \,$爆做

:::spoiler 實作

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

#define rep(a, b, c) for (int a = b; a < c; a++)
#define ll long long
#define PEPPA ios_base::sync_with_stdio(0), cin.tie(0);

int main() {
    int n; cin >> n;
    vector<ll> a(n);
    rep (i, 0, n) cin >> a[i];
    ll ans = 0;
    rep (i, 0, n) rep (j, i + 1, n) ans = max(ans, a[i] * a[j]);
    cout << ans << '\n';
}

:::

### D. Animal Circus
---
#### 題目摘要
有$N$種動物，每種各有$\,a_i\,$隻。$\,Q\,$筆修改，每次會將其中一種動物的個數增加或減少$\,y\,$。每筆修改之後需要在線回答：若將一個籠子能裝$K$種不同的動物，最多能裝滿幾個籠子。
#### 想法
先想想沒有修改的情況下怎麼回答問題，我們可以對答案二分搜，check時想像有$\,mid\,$個籠子，那麼只要檢查$K\times mid \leq\sum\limits^n_{i=1}\min(a_i, mid)$就好。
那麼現在對於每筆修改詢問，我們會想要很快地得出$\sum\limits^n_{i=1}\min(a_i, mid)$，可以觀察到我們只需要維護一個遞增的序列$a$，找到第一個$<mid$的點位置，就可以用前綴和跟他的位置好好算出來。因此可以使用好資結，大部分人都用動態開點線段樹，我用了非常好Treap。
Treap上記val跟size跟sum，把val當rank，在修改時就刪掉那個val的點，再插一個新的點就好，找答案時一樣二分搜，check用Treap上二分搜來找到上面要的資訊就能在$O(\log n)$完成一次check。
總複雜度$O(Q\log C\log n)$
特別注意二分搜上界不能太小，在check時乘法很可能會炸到int128，要小心值域。

:::spoiler 實作

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

#define rep(a, b, c) for (int a = b; a < c; a++)
#define ll long long
#define PEPPA ios_base::sync_with_stdio(0), cin.tie(0)
#define all(x) (x).begin(), (x).end()

const int MOD = 1e9 + 7;
const ll LINF = 1e18 + 5;

struct Treap {
    Treap *l, *r;
    int size, pri;
    ll sum, val;
    Treap(ll v) : l(nullptr), r(nullptr), size(1), pri(rand()), val(v), sum(v) {}
    void pull();
};

inline int sz(Treap *p) {
    return (p == nullptr ? 0 : p->size);
}

inline ll sm(Treap *p) {
    return (p == nullptr ? 0 : p->sum);
}

inline ll va(Treap *p) {
    return (p == nullptr ? 0 : p->val);
}

void Treap::pull() {
    size = sz(l) + sz(r) + 1;
    sum = sm(l) + sm(r) + val;
}

Treap *merge(Treap *a, Treap *b) {
    if (a == nullptr) return b;
    if (b == nullptr) return a;
    if (a->pri < b->pri) {
        a->r = merge(a->r, b);
        a->pull();
        return a;
    } else {
        b->l = merge(a, b->l);
        b->pull();
        return b;
    }
}

void split(Treap *root, Treap *&a, Treap *&b, ll k) {
    if (root == nullptr) {
        a = b = nullptr;
        return;
    }
    if (root->val <= k) {
        a = root;
        split(root->r, a->r, b, k);
        a->pull();
    } else {
        b = root;
        split(root->l, a, b->l, k);
        b->pull();
    }
}

void output(Treap *p) {
    if (p == nullptr) return;
    output(p->l);
    cerr << p->val << ' ';
    output(p->r);
}

void erase(Treap *&p, ll k) {
    if (p == nullptr) return;
    if (p->val == k) {
        p = merge(p->l, p->r);
        return;
    }
    if (p->val < k) erase(p->r, k);
    else erase(p->l, k);
    p->pull();
}

void insert(Treap *&p, ll k) {
    Treap *a, *b;
    split(p, a, b, k);
    p = merge(a, merge(new Treap(k), b));
    p->pull();
}

int rk(Treap *&p, ll key) {
    if (p == nullptr) return 0;
    if (p->val <= key) return sz(p->l) + 1 + rk(p->r, key);
    else return rk(p->l, key);
}

void solve() {
    int n, k; cin >> n >> k;
    vector<ll> a(n);
    rep (i, 0, n) cin >> a[i];
    Treap *root = nullptr;
    rep (i, 0, n) insert(root, a[i]);
    int q; cin >> q;
    ll ans = 0;
    while (q--) {
        int x, y; cin >> x >> y;
        x = (ans ^ x) % n;
        erase(root, a[x]);
        a[x] += y;
        insert(root, a[x]);
        __int128 l = 0, r = LINF << 2;
        while (r - l > 1) {
            __int128 mid = l + r >> 1;
            Treap *tmp;
            split(root, root, tmp, mid);
            __int128 sum = sm(root);
            root = merge(root, tmp);
            int id = rk(root, mid);
            sum += mid * (n - id);
            if (__int128(sum) >= __int128(k * mid)) l = mid;
            else r = mid;
        }
        ans = l;
        cout << ans << '\n';
    }
}

int main() {
    PEPPA;
    int t = 1;
    // cin >> t; 
    while(t--) solve();
}

:::

### E. Hidden Project
---
#### 題目摘要
你有$N$天，每天會獲得$a$的薪水，你可以做很多專案，選擇一段區間$[l,\ r]$，第$i$天的薪水是$l-i+1$，並做專案的日子拿不到$a$的薪水，問最大薪水和
#### 想法
比較$\frac{n\times(n+1)}{2}及a*n$

:::spoiler 實作

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

#define rep(a, b, c) for (int a = b; a < c; a++)
#define ll long long
#define PEPPA ios_base::sync_with_stdio(0), cin.tie(0)

ll calc(ll x){return x*(x+1)>>1;}

void solve() {
    int n;
    ll a;
    cin >> n >> a;
    ll ans=max(a*n, calc(n));
    cout << ans << '\n';
}

int main() {
    PEPPA;
    int t;
    cin >> t; 
    while(t--) solve();
}

:::

### F. Portal Maintenance
---
#### 題目摘要
#### 想法

:::spoiler 實作

#pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx,popcnt,sse4,abm")
#include<bits/stdc++.h>
using namespace std;
#define ZTMYACANESOCUTE ios_base::sync_with_stdio(0), cin.tie(0)
#define ll long long
#define ull unsigned long long
#define pb push_back
#define all(a) (a).begin(), (a).end()
#define debug(x) cerr << #x << " = " << x << '\n';
#define rep(X, a, b) for(int X = a; X < b; ++X)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pld pair<ld, ld>
#define ld long double
#define F first
#define S second

pii operator + (const pii &p1, const pii &p2) { return make_pair(p1.F + p2.F, p1.S + p2.S); }
pii operator - (const pii &p1, const pii &p2) { return make_pair(p1.F - p2.F, p1.S - p2.S); }
pll operator + (const pll &p1, const pll &p2) { return make_pair(p1.F + p2.F, p1.S + p2.S); }
pll operator - (const pll &p1, const pll &p2) { return make_pair(p1.F - p2.F, p1.S - p2.S); }

template<class T> bool chmin(T &a, T b) { return (b < a && (a = b, true)); }
template<class T> bool chmax(T &a, T b) { return (a < b && (a = b, true)); }

#define lpos pos << 1
#define rpos pos << 1 | 1
 
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << "," << p.second << ')'; }
template<typename A> ostream& operator << (ostream &os, const vector<A> &p) { for(const auto &a : p) os << a << " "; os << '\n'; return os; }
 
const int MAXN = 2e5 + 5, MOD = 998244353, IINF = 1e9 + 7, MOD2 = 1000000007;
const double eps = 1e-9;
const ll LINF = 1e18L + 5;
const int B = 320;

// mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
// int get_rand(int l, int r){ return uniform_int_distribution<int>(l, r)(rng); }
 
ll fpow(ll x, ll exp, ll mod = LLONG_MAX){ ll res = 1; while(exp){ if(exp & 1) res = res * x % mod; x = x * x % mod; exp >>= 1;} return res; }

void solve() {
    int n, c; cin >> n >> c;
    ll ans = 0;
    vector<vector<int>> adj(n);
    rep (i, 0, n - 1) {
        int a, b, w; cin >> a >> b >> w;
        a--, b--;
        adj[a].pb(b);
        adj[b].pb(a);
        ans += w;
    }
    vector<int> dfn(n, 0);
    int cnt = 0;
    auto dfs = [&](auto self, int u, int pa) -> void {
        dfn[u] = ++cnt;
        for (int v : adj[u]) {
            if (v == pa) continue;
            self(self, v, u);
        }
    };
    dfs(dfs, 0, -1);
    vector<int> odd;
    rep (i, 0, n) if (adj[i].size() & 1) odd.pb(i);
    ans += 1LL * (odd.size() / 2) * c;
    vector<pii> ope;
    sort(all(odd), [&](int i, int j) {
        return dfn[i] < dfn[j];
    });
    for (int i = 0; i < odd.size(); i += 2) {
        ope.pb({odd[i], odd[i + 1]});
    }
    cout << ans << ' ' << ope.size() << '\n';
    for (auto [x, y] : ope) cout << x + 1 << ' ' << y + 1 << '\n';
}
 
int main() {
    ZTMYACANESOCUTE;
    int T = 1;
    // cin >> T;
    while (T--) {
        solve();
    }
}

:::

### G. Ki Chang Jab Takkataen
---
#### 題目摘要
有$N$隻蚱蜢、$M$個網子，每隻蚱蜢會在$(x_i,\ y_i)$。你會坐在高度為$H$的大象上。網子$j$能抓到蚱蜢$i$的條件為$H−l_j\le y_i\le H+l_j$，並且每個網子只能用一次。有$Q$筆詢問，問x座標從0開始，最近需要走多遠才能抓到$q_i$隻蚱蜢，不能輸出-1
#### 想法
要預處理若要抓$i$隻蚱蜢，則我最近要走到哪的表。只要從x座標從小做到大，看有沒有網子最小的網子滿足$l_j\ge abs(H-y_i)$，若有的話將抓到蟋蟀數+1、更新答案並刪除網子。詢問時直接查表輸出答案

:::spoiler 實作

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

#define rep(a, b, c) for (int a = b; a < c; a++)
#define ll long long
#define PEPPA ios_base::sync_with_stdio(0), cin.tie(0)
typedef pair<int, int> pii;
#define F first
#define S second

void solve() {
    int n, m, h, q;
    cin >> n >> m >> h >> q;
    vector<pii> p(n);
    for(auto &[x, y]:p){
        cin >> x >> y;
        y=abs(y-h);
    }
    multiset<int> s;
    for(int i=0;i<m;i++){
        int l;
        cin >> l;
        s.insert(l);
    }
    int cnt=0;
    vector<int> ans(n+1, -1);
    for(auto [x, y]:p){
        auto it=s.lower_bound(y);
        if (it==s.end()) continue;
        cnt++;
        ans[cnt]=x;
        s.erase(it);
    }
    while(q--){
        int len;
        cin >> len;
        cout << ans[len] << '\n';
    }
}

int main() {
    PEPPA;
    int t = 1;
    // cin >> t; 
    while(t--) solve();
}

:::

### H. Final Quiz
---
#### 題目摘要
給$N$個格子及$K$種可以選擇的顏色，求合法著色的方法數。

* 最多只能有連續三個相同顏色的格子
* 要讓連續三個相同顏色的格子數最大化

#### 想法

因為要最大化連續三個相同，可以直接將三格三格綁在一起做排組
因此只要對$N\,\%\,3$的餘數分開討論求答案就好

:::spoiler 實作

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

#define rep(a, b, c) for (int a = b; a < c; a++)
#define ll long long
#define PEPPA ios_base::sync_with_stdio(0), cin.tie(0)

const int MOD = 1e9 + 7;

ll fpow(ll x, ll exp) {
    ll res = 1;
    while (exp) {
        if (exp & 1) res = res * x % MOD;
        x = x * x % MOD;
        exp >>= 1;
    }
    return res;
}

void solve() {
    ll n, k; cin >> n >> k;
    ll cnt = n / 3;
    if (n == 1) {
        cout << k << '\n';
        return;
    }
    if (n == 2) {
        cout << k * k % MOD << '\n';
        return;
    }
    ll ans = 0;
    if (n % 3 == 0) {
        ans = k * fpow(k - 1, cnt - 1) % MOD;
    } else if (n % 3 == 1) {
        ans = k * fpow(k - 1, cnt) % MOD * (cnt + 1) % MOD;
    } else {
        ans = k * k % MOD * fpow(k - 1, cnt) % MOD * (cnt + 1) % MOD;
        ll C = (cnt * (cnt + 1) / 2) % MOD;
        ans += C * k % MOD * fpow(k - 1, cnt + 1) % MOD;
        ans %= MOD;
    }
    cout << ans << '\n';
}

int main() {
    PEPPA;
    int t = 1;
    // cin >> t; 
    while(t--) solve();
}

:::

### I. Lulu And The Magical Array
---
#### 題目摘要
互動題，會有一個長度為$n$的陣列，當詢問$i,\ j$會得到$a_i\oplus a_j$，要在$n$次詢問內求得$\min_\limits{1\le i,\ j\le n}a_i\oplus a_j$
#### 想法
因為xor滿足$a\oplus b=(a\oplus c)\oplus (b\oplus c)$，因此可以查詢$a_1\oplus a_i,\ 2\le i\le n$，並兩兩xor與答案取min，然而複雜度是$O(n^2)$
可以建一顆trie，並把數字以二進位表示並丟進trie，若建立新點，將點的權值設為目前數字，並且若從一個點開始出現之前數字沒走過的點，就和答案與(點權$\oplus$目前數字)取min，最後只要注意重複出現的數字要讓答案是0就好

:::spoiler 實作

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

#define rep(a, b, c) for (int a = b; a < c; a++)
#define ll long long
#define PEPPA ios_base::sync_with_stdio(0), cin.tie(0)

const int N=7e6+10;
int ch[N][2], val[N];

int ans;
int tot;
void insert(int x){
    int now=0;
    bool phlag=0;
    for(int i=30;~i;--i){
        if (ch[now][(x>>i)&1]==0){
            ch[now][(x>>i)&1]=++tot;
            val[tot]=x;
            if (!phlag) ans=min(ans, val[now]^x), phlag=1;
        }
        now=ch[now][x>>i&1];
    }
}

int query(int i, int j){
    cout << "? " << i << ' ' << j << endl;
    int x;
    cin >> x;
    ans=min(ans, x);
    return x;
}

void solve() {
    int n;
    cin >> n;
    tot=0;
    ans=INT_MAX;
    map<int, int> mp;
    for(int i=2;i<=n;i++){
        int z=query(1, i);
        if (mp[z]==1){
            ans=0;
            continue;
        }
        mp[z]=1;
        insert(z);
    }
    for(int i=0;i<=tot;i++){
        ch[i][0]=ch[i][1]=0;
        val[i]=0;
    }
    cout << "! " << ans << endl;
}

int main() {
    PEPPA;
    int t = 1;
    cin >> t;
    while(t--) solve();
}

:::

### J. Rook Placement
---
#### 題目摘要

#### 想法

:::spoiler 實作

:::

### K. A Potion Shopping On This Wonderful World!
---
#### 題目摘要

#### 想法

:::spoiler 實作

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

#define rep(a, b, c) for (int a = b; a < c; a++)
#define ll long long
#define PEPPA ios_base::sync_with_stdio(0), cin.tie(0)

const int MOD = 1e9 + 7;
const ll LINF = 1e18 + 5;

ll fpow(ll x, ll exp) {
    ll res = 1;
    while (exp) {
        if (exp & 1) res = res * x % MOD;
        x = x * x % MOD;
        exp >>= 1;
    }
    return res;
}

void solve() {
    int n, m, k; cin >> n >> m >> k;
    vector<ll> dp(1 << k, LINF);
    vector<int> b(n), cc(n);
    dp[0] = 0;
    rep (i, 0, n) {
        int p; ll c; cin >> p >> c;
        int bit = 0;
        rep (j, 0, p) {
            int t; cin >> t;
            t--;
            bit |= 1 << t;
        }
        b[i] = bit;
        dp[bit] = min(dp[bit], c);
        cc[i] = c;
    }
    rep (bit, 0, 1 << k) if (dp[bit] != LINF) {
        rep (i, 0, n) dp[bit | b[i]] = min(dp[bit | b[i]], dp[bit] + cc[i]);
    }
    while (m--) {
        int K; cin >> K;
        int bit = 0;
        rep (i, 0, K) {
            int w; cin >> w;
            w--;
            bit |= 1 << w;
        }
        ll ans = LINF;
        rep (i, 0, 1 << k) if ((i & bit) == bit) {
            ans = min(ans, dp[i]);
        }
        if (ans == LINF) cout << -1 << '\n';
        else cout << ans << '\n';
    }
}

int main() {
    PEPPA;
    int t = 1;
    // cin >> t; 
    while(t--) solve();
}

:::