# 氣球盃8th 題解

## Overview

致謝：

感謝tester們提供很多題目的反饋：[王淇](https://www.facebook.com/mattwang8152)、[陳克盈](https://www.facebook.com/profile.php?id=100015800760577)、[陳俊安](https://www.facebook.com/profile.php?id=100003237362202)、[林煜傑](https://www.facebook.com/oscar.lin.7186)。
感謝[鄭天均](https://www.facebook.com/chengtienchun)大學長幫忙解決judge的技術問題。
感謝[林煜傑](https://www.facebook.com/oscar.lin.7186)提供優質的題目及準備題目測資。

::: spoiler 各題 AC 人數
|組別|A|B|C|D|E|F|G|
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
|實體組|16|16|3|0|0|0|0|
|線上組|7|6|3|3|2|2|1|

:::

## A 據說這題是一題水題
**Idea:** wcwu
**Task Prepration:** wcwu
**Statement Writer:** wcwu
:::spoiler **Tags:**
`none`
:::

實體組首殺：QuincyHsu
線上組首殺：Darren0724

### Subtask 1
題目**一**題水題:1+**百**年校慶:100+**二千零二十二**年的**七**月**二**日星期**六**:2+1000+2+10+2+7+2+6=1031+第**八**屆:8+第**一**名:1+**九百**元:9+100=109+**二百一十**分鐘:2+100+1+10=113+**七**題:7+**四百分之四十九**:4+100+4+10+9=127+這**一**題:1=**1498**

時間複雜度 $O(1)$ 。

## B 三合一
**Idea:** wcwu
**Task Prepration:** wcwu
**Statement Writer:** wcwu
:::spoiler **Tags:**
`bitmask, greedy`
:::

實體組首殺：MarkHuo
線上組首殺：Darren0724

### Subtask 1
暴力試過每一次合併的項。
時間複雜度 $O(17\times 15\times 13\times 11\times 9\times 7\times 5\times 3)$。

### Subtask 2
觀察到當我們合併三項時，第 $i$ 項的值會更新為 $a_i\oplus a_{i+1}\oplus a_{i+2}$ ， 若我們再合併目前的第 $i, i+1, i+2$ 項時， 第 $i$ 項的值則更新為 $(a_i\oplus a_{i+1}\oplus a_{i+2})\oplus a_{i+3}\oplus a_{i+4}$ ，藉由 xor 的結合律，合併 $\frac{n-1}{2}$ 次後的結果即是 $a_0\oplus a_1\oplus ... \oplus a_{n-1}$ 。所以僅需將所有 $a_i$ xor 起來看結果是否為 $0$ 即可。

時間複雜度 $O(n)$。

## C 加乘遊戲
**Idea:** wcwu, Fysty
**Task Prepration:** wcwu
**Statement Writer:** wcwu
:::spoiler **Tags:**
`brutal force, implementation, math`
:::

實體組首殺：franklee1015
線上組首殺：Darren0724

### Subtask 1, 2
當 $x, y\geq 2$ 時，我們可以發現 $x\times y\geq x+y$ ，所以阿瑋一定會選擇 $\times$ ，而杰哥一定會選擇 $+$ 。詳細作法見下述。

### Subtask 3
我們用一個陣列 $v$ 代表遊戲的狀態，若第 $i$ 個符號還沒被決定則 $v_i=0$，否則 $v_i=1$ 代表第 $i$ 個符號是 $+$，$v_i=2$ 則代表是 $\times$。

考慮利用遞迴函式，令 $f(v)$ 代表從狀態 $v$ 開始，遊戲最後的結果。

考慮 $v$ 中還是 $0$ 的元素，下一步一定是從這些元素裡面選一個位置變成 $1$ 或 $2$。

因此我們可以遞迴計算出所有的下一個狀態，並依照現在是哪個玩家的回合，決定該取最大或最小的那個做為 $f(v)$。

直接做的話複雜度是 $O(8!!\cdot 4)$。

聰明一點用 memoization 的話可以變成 $O(3^4\cdot 4)$。

但設計上就是單純實作，因此兩者都足夠快。

時間複雜度 $O(n!\cdot2^n\cdot n)$。

:::spoiler 官解1(林煜傑)

#include <bits/stdc++.h>
#include <random>
#include <chrono>
using namespace std;
//#pragma GCC optimize("Ofast")
//#pragma GCC optimize ("unroll-loops")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<double,double> pdd;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

template<typename T> void _do(T x){cerr<<x<<"\n";}
template<typename T,typename ...U> void _do(T x,U ...y){cerr<<x<<", ";_do(y...);}
#define dbg(...) cerr<<#__VA_ARGS__<<" = ";_do(__VA_ARGS__);

const int MOD1=1e9+7;
//const int MOD2=998244353;
const ll INF=3e18;
const ld PI=3.14159265358979323846;
ll gcd(ll a,ll b){if(b==0) return a; return gcd(b,a%b);}
ll fpow(ll a,ll b,ll m)
{
    if(!b) return 1;
    ll ans=fpow(a*a%m,b/2,m);
    return (b%2?ans*a%m:ans);
}
ll inv(ll a,ll m) {return fpow(a,m-2,m);}

#define MottoHayaku ios::sync_with_stdio(false);cin.tie(0);
//#define int ll
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define repk(i,m,n) for(int i=m;i<n;i++)
#define F first
#define S second
#define pb push_back
#define uni(c) c.resize(distance(c.begin(),unique(c.begin(),c.end())))
#define unisort(c) sort(c.begin(),c.end()),uni(c)

ll a[8];
ll getans(ll d,vector<ll> v)
{
    if(d==4)
    {
        ll tmp=a[0],ret=0;
        rep(i,4)
        {
            if(v[i]==1)
            {
                ret+=tmp;
                tmp=a[i+1];
            }
            else if(v[i]==2) tmp*=a[i+1];
        }
        ret+=tmp;
        return ret;
    }
    ll ret=INF;
    if(d%2==0) ret=-INF;
    rep(i,4)
    {
        if(v[i]!=0) continue;
        vector<ll> tv=v;
        tv[i]=1;
        ll x=getans(d+1,tv);
        if(d%2==0) ret=max(ret,x);
        else ret=min(ret,x);
        tv[i]=2;
        x=getans(d+1,tv);
        if(d%2==0) ret=max(ret,x);
        else ret=min(ret,x);
    }
    return ret;
}
signed main()
{
    MottoHayaku
    rep(i,5) cin>>a[i];
    vector<ll> v(4);
    cout<<getans(0,v);
}

:::

## D 卡外賣
**Idea:** Fysty
**Task Prepration:** Fysty
**Statement Writer:** Fysty

:::spoiler **Tags:**
`Graph`
:::

實體組首殺：
線上組首殺：Darren0724

### Subtask 1

觀察 $\sum_{i=1}^n \sum_{j=1}^n d(i,j)=m$ 代表甚麼，注意到每個邊一定會對那個總和貢獻至少 $1$，因為 $d(u,v)\ge 1,d(v,u)\ge 1$ 至少有一個成立。

所以這個總和本來就 $\ge m$，因此等號要成立，不難發現這表示對於任兩個相異的點 $u,v$，如果沒有 $u$ 到 $v$ 的有向邊，則 $d(u,v)$ 必須要是 $0$。

這個條件等價不存在長度是 $2$ 的路徑，所以對於一個點 $u$，他必須滿足以下兩個條件之一：

* 對於所有和 $u$ 有連邊的點 $v$，定向後都是 $u\rightarrow v$
* 對於所有和 $u$ 有連邊的點 $v$，定向後都是 $v\rightarrow u$

因此我們可以紀錄一個點的出度和入度，就知道枚舉到的定向方法是否合法。

這樣的複雜度就只有 $O(2^m (n+m))$。

### Subtask 2

我們將滿足第一個條件的點叫做白點，滿足第二個條件的點叫做黑點。

觀察到和白點相鄰的點必須是黑點，和黑點相鄰的點必須是白點。

注意到「和白點相鄰的點必須是黑點，和黑點相鄰的點必須是白點」等於是在說我們可以將所有的點分成兩個集合 $W,B$，滿足 $W$ 都是白點，$B$ 都是黑點，而且所有 $m$ 個邊的兩個端點分別在 $W$ 和 $B$ 中。

這就是所謂的「二分圖」。

因為樹永遠是二分圖，所以不會有不可能的情況。

注意到若我們已經確定所有點的黑白塗色，則可以唯一決定邊要如何定向(方向一定是白點指向黑點)。

在一個連通塊中，若我們已經決定某個點的顏色，則和它相鄰的點的顏色也都會被唯一決定，因此塗色方法會恰有兩種，而且這兩種方法的點的顏色和邊的定向會恰好完全相反。

實作上可以用一個 dfs 解決。

而樹是連通圖，因此兩種塗色中選擇字典序較小的就做完了。

Time complexity: $O(n)$。

### Subtask 3

注意到任兩個連通塊互不影響，因此我們可以依編號由小到大枚舉所有的邊，如果這個邊已經被定向了就不理他，否則強制讓 $u_i$ 變白點，並利用 dfs 決定所有在同個連通塊中的點的顏色(同時決定所有連通塊中的邊的方向)。

如果中途遇到一個邊的兩端顏色相同，則表示不可能，這時就回傳 -1 並結束就好。

否則我們的定向方法，就是字典序最小的方法。

Time complexity: $O(n)$。

## E 碰碰法師
**Idea:** wcwu
**Task Prepration:** wcwu
**Statement Writer:** wcwu

:::spoiler **Tags:**
`binary search, implementation`
:::

實體組首殺：
線上組首殺：Darren0724

### Subtask 1, 2
首先，這題很顯然要對答案二分搜。
$n\le 200$ 時，我們可以直接模擬所有回合，哪些怪物會出現，哪些怪物受到傷害後會死亡，怪物會回多少血，以及最後英雄是否有辦法通關。

時間複雜度 $O(n^2logC)$。

### Subtask 3, 4
我們要優化模擬回合的過程。我們可以發現在每一個回合，我們都會掃過所有怪物，即便已經死亡或還沒出現的怪物都會被檢查到。

我們可以使用 priority_queue 依血量來儲存目前存活在場上的怪物。

令一個變數 $dmg$ 代表玩家對怪物造成的累積傷害，每經過一回合， $dmg$ 會增加 $x$ ，其中 $x$ 是我們二分搜答案的 $mid$ 值。

每次有新的怪物加入時，把此怪物的起始血量 +$dmg$。

檢查 priority_queue 中，血量已低於 $dmg$ 者 pop 掉。

再將 $dmg$ 減掉目前的牧師個數，玩家血量減掉目前的射手個數。

模擬 $n+k$ 個回合後，遊戲必定結束...嗎？

---

遊戲結束有兩個可能：玩家死亡、怪物死亡。

首先，$n+k$ 個回合後，如果有射手仍未死亡，後 $k$ 個回合足以讓此射手擊殺玩家。

但是，如果未死亡的是牧師呢？

**如果玩家回合所造成的傷害$\le$該回合的回血量**，則遊戲不會結束，玩家也不會獲勝。

所以我們執行完 $n+k$ 個回合後，還要檢查剩下的牧師是否可以被完全清除，可以透過數學的計算加速檢查過程。

時間複雜度 $O(nlognlogC+nlogC)$。

註：Subtask 4 測資不夠強讓 franklee 喇到分我十分抱歉

## F 身高排列
**Idea:** wcwu
**Task Prepration:** wcwu
**Statement Writer:** wcwu

:::spoiler **Tags:**
`data structure, binary search`
:::

實體組首殺：
線上組首殺：GrandTiger1729

### Subtask 1
只有第一種詢問，對一個人 $i$ ，找到第 $k$ 小的 $|a_j-a_i|$。

因為 $q$ 很小，我們每次做的時候把對所有 $|a_j-a_i|$ 排序後輸出第 $k$ 個就好。

時間複雜度 $O(qnlogn)$。

### Subtask 2
同樣的，我們可以暴力預處理所有 $a_x-a_y$ ，排序後輸出第 $m$ 個即可。

時間複雜度 $O(n^2+q)$。

### Subtask 3, 4
我們確定答案介在 $[-2\cdot10^8, 2\cdot10^8]$ 間。

接著我們對答案二分搜。

每次二分搜時，我們想知道對所有 $i$ ，共有幾個 $x$ 滿足 $x<i$ 且 $a_i-a_x\le mid$ ，也就是 $a_i-mid\le a_x$ 。

上述步驟可以用 BIT 來查詢與維護。

最後比較 $x$ 和 $m$ 的關係去壓縮左右界。

因 $a_i-mid$ 的範圍很大，所以 Subtask 4 還需要離散化的步驟。

時間複雜度 $O(qnlognlogC+qnlogn)$。

:::spoiler 官解(吳威錡)

#include <bits/stdc++.h>
//#include<random>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll,ll> pll;
typedef pair<int, int> pii;
typedef map<ll, ll> mll;
const int MOD1=1e9+7;
const int MOD2=998244353;
const int iINF=INT_MAX;
const ll INF=LLONG_MAX;
#define IOS ios::sync_with_stdio(false);cin.tie(0);
#define dbg(n) cerr<<#n<<": "<<n<<"\n";
#define optline cout<<"\n";
#define rep(i,n) for(ll i=0;i<n;i++)
#define rep1(i,n) for(ll i=1;i<=n;i++)
#define F first
#define S second
#define All(c) c.begin(), c.end()
#define pb push_back
#define uni(c) c.resize(distance(c.begin(), unique(c.begin(), c.end())))
#define unisort(c) sort(c.begin(), c.end());uni(c)
const int N=100005;
ll bit[N], b[N], a[N];
ll n, q, m;
vector<ll> v;
ll get_id(ll x) {
    return lower_bound(v.begin(), v.end(), x)-v.begin()+1;
}
void upd(ll x) {
    for(;x<=(ll)v.size();x+=x&-x) bit[x]++;
}
ll qry(ll x) {
    ll ret=0;
    for(;x>0;x-=x&-x) ret+=bit[x];
    return ret;
}
bool check(int x) {
    memset(bit, 0, sizeof(bit));
    ll ans=0;
    rep1(i, n) {
        ans+=qry(get_id(a[i]-x+1)-1);
        upd(get_id(a[i]));
    }
    return ans>=n*(n-1)/2-m+1;
}
signed main() {
    cin>>n>>q;
    v.pb(0);
    rep1(i, n) {
        cin>>a[i];
        bit[i]=0;
        v.pb(a[i]);
    }
    unisort(v);
    while(q--) {
        int ty;
        cin>>ty;
        if(ty==1) {
            ll id, k;
            cin>>id>>k;
            vector<ll> d;
            rep1(i, n) {
                if(id==i) continue;
                d.pb((ll)abs(a[id]-a[i]));
            }
            sort(d.begin(), d.end());
            cout<<d[k-1]<<"\n";
        }
        else {
            cin>>m;
            ll l=-1e9-1, r=1e9+1;
            while(r-l>1) {
                ll mid=(l+r)>>1;
                if(check(mid)) l=mid;
                else r=mid;
            }
            cout<<l<<"\n";
        }
    }
}

:::

## G 在樹上走自己的路
**Idea:** Fysty
**Task Prepration:** Fysty
**Statement Writer:** Fysty

:::spoiler **Tags:**
`graph, DP, math`
:::

實體組首殺：
線上組首殺：GrandTiger1729

### Subtask 1

圖是一條鍊。

如果兩個路徑都至少有兩個點，則共有 $\binom{n}{4}$ 組。

如果恰有一個個路徑只有一個點，則共有 $2\binom{n}{3}$ 組。

如果兩個路徑都只有一個點，則共有 $\binom{n}{2}$ 組。

答案就是把以上三個量加起來而已，注意 $\binom{n}{4}$ 會爆 long long，因此要利用模反元素或 __int128。

### Subtask 2

共有 $M=\frac{n(n+1)}{2}$ 個相異的路徑。

枚舉所有 $\binom{M}{2}$ 組可能的相異路徑對，並 $O(n)$ 檢查有沒有一個點在兩條路徑上。

Time complexity: $O(n^5)$。

### Subtask 3

枚舉所有相異的路徑，將路徑上的點和邊都拔掉。

剩下的圖會是森林，假設每個連通塊各有 $a_1,a_2,...,a_k$ 個點，則和目前枚舉的路徑不相交的路徑個數恰為 $\binom{a_1+1}{2}+\binom{a_2+1}{2}+\cdots+\binom{a_k+1}{2}$。

枚舉所有相異路徑 $O(n^2)$，找出所有連通塊的點數 $O(n)$。

記得 $(P_a,P_b)$ 和 $(P_b,P_a)$ 視為相同，因此要除以 $2$。

Time complexity: $O(n^3)$。

### Subtask 4

我們先定節點 $1$ 為樹的根。

對於一個路徑 $P$，定義 $lca(P)$ 為 $P$ 中所有點的最低共同祖先。注意到 $lca(P)$ 一定在 $P$ 中，而且是 $P$ 中距離根最近的點。

* **引理**：對於兩個確定相交的路徑 $P_1,P_2$，$lca(P_1),lca(P_2)$ 中至少有一個是他們的交點，而且如果都是交點，則 $lca(P_1)=lca(P_2)$。

對於一個點 $i$ 我們希望算出：

$cnt_i$：滿足 $lca(P)=i$ 的路徑 $P$ 個數。

$pass_i$：經過 $i$ 但 $lca(P)\neq i$ 的路徑 $P$ 個數。

注意到答案就是：(相異路徑對總個數)$-\sum_{i=1}^n \left(\binom{cnt_i}{2}+cnt_i\times pass_i\right)$。

$cnt,pass$ 都可以利用樹 DP 在 $O(n)$ 內求出。

:::spoiler 引理的證明

假設兩個路徑相交於一個不是 $lca(P_1)$ 也不是 $lca(P_2)$ 的點 $x$，則 $x$ 的父節點 $parent(x)$ 也是一個交點。

所以 $x,parent(x),parent(parent(x)),...$ 會一直都是交點，直到遇到 $lca(P_1)$ 或 $lca(P_2)$。

因此 $lca(P_1)$ 和 $lca(P_2)$ 至少有一個會是交點。

注意到若 $u_1,u_2$ 都是交點，則 $lca({u_1,u_2})$ 也是交點，所以如果 $lca(P_1),lca(P_2)$ 相異且都是交點，則 $lca({lca(P_1),lca(P_2)})$ 也是交點，可是這個點必定是 $lca(P_1),lca(P_2)$ 其中一個的祖先(假設是 $lca(P_1)$ 的祖先)，但這跟 $lca(P_1)$ 是 $P_1$ 中所有點的最低共同祖先矛盾。

因此 $lca(P_1),lca(P_2)$ 若都是交點，則 $lca(P_1)=lca(P_2)$。
:::

Time complexity: $O(n)$。

:::spoiler 官解(林煜傑)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
#define MottoHayaku ios::sync_with_stdio(false);cin.tie(0);
#define rep(i,n) for(int i=0;i<n;i++)
#define rep1(i,n) for(int i=1;i<=n;i++)
#define pb push_back
#define F first
#define S second
const int MOD=1e9+7;

const int N=2e5+5;
vector<ll> ed[N];
ll n,ans=0,cnt[N],pass[N],sz[N];
void dfs(ll u,ll p)
{
    sz[u]=1;
    for(ll v:ed[u])
    {
        if(v==p) continue;
        dfs(v,u);
        sz[u]+=sz[v];
        cnt[u]=(cnt[u]+sz[v]*(sz[v]+1)/2)%MOD;
    }
    cnt[u]=(sz[u]*(sz[u]+1)/2-cnt[u]+MOD)%MOD;
    pass[u]=sz[u]*(n-sz[u])%MOD;
    ans+=(cnt[u]*(cnt[u]-1)/2+cnt[u]*pass[u])%MOD;
    ans%=MOD;
}
void solve()
{
    cin>>n;
    ans=0;
    rep1(i,n)
    {
        ed[i].clear();
        cnt[i]=sz[i]=pass[i]=0;
    }
    rep(i,n-1)
    {
        ll u,v;
        cin>>u>>v;
        ed[u].pb(v);
        ed[v].pb(u);
    }
    dfs(1,0);
    ll k=(n*(n+1)/2)%MOD;
    ans=(k*(k-1)/2-ans+MOD)%MOD;
    cout<<ans<<"\n";
}
signed main()
{
    MottoHayaku
    ll t=1;
    //cin>>t;
    while(t--) solve();
}

:::

:::spoiler 另解(吳柏翰)

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
int n,x,y,ans,ans2,a[200005],b[200005],expand[200005][5],mod=1e9+7,magic=41666667,vis[200005],cnt,power[5],s1,s2,s3,s4,s5;
vector<int> v[200005];
int dfs(int x)
{
    vis[x]=1;
    int degree=1;
    for(int i=0;i<v[x].size();i++)
    {
        if(!vis[v[x][i]])
        {
            a[v[x][i]]=x;
            degree+=dfs(v[x][i]);
        }
    }
    b[x]=degree;
    return degree;
}
signed main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    cin>>n;
    for(int i=0;i<n-1;i++)
    {
        cin>>x>>y;
        v[x].pb(y);
        v[y].pb(x);
    }
    a[1]=-1;
    dfs(1);
    ans=(n+3)*(n+2)*(n+1);
    ans%=mod;
    ans*=n;
    ans%=mod;
    ans*=magic;
    ans%=mod;
    ans+=(200*mod-n*n);
    ans%=mod;
    for(int i=1;i<=n;i++)
    {
        cnt=v[i].size();
        for(int j=0;j<cnt;j++)
        {
            if(v[i][j]==a[i])
            {
                expand[j][0]=n-b[i];
            }
            else
            {
                expand[j][0]=b[v[i][j]];
            }
        }
        for(int j=1;j<4;j++)
        {
            for(int k=0;k<cnt;k++)
            {
                expand[k][j]=(expand[k][j-1]*expand[k][0])%mod;
            }
        }
        for(int j=0;j<4;j++)
        {
            power[j+1]=0;
            for(int k=0;k<cnt;k++)
            {
                power[j+1]=(power[j+1]+expand[k][j])%mod;
            }
        }
        ans2=(power[1]*power[1]-power[2])%mod;
        ans2=(ans2*12*magic)%mod;
        ans=(ans-ans2+mod)%mod;
        for(int j=1;j<=4;j++)
        {
            power[j]++;
        }
        s1=(power[1]*power[1])%mod;
        s1=(s1*power[1])%mod;
        s1=(s1*power[1])%mod;
        s2=(power[1]*power[1])%mod;
        s2=(s2*power[2])%mod;
        s3=(power[2]*power[2])%mod;
        s4=(power[1]*power[3])%mod;
        s5=power[4];
        ans2=(s1-6*s2+3*s3+8*s4-6*s5)%mod;
        ans2=(((ans2*magic)%mod)+mod)%mod;
        ans=(ans-ans2+mod)%mod;
    }
    cout<<ans;
}

:::

吳柏翰：「只要大家學好數學就可以用奇怪的方法做出這題。」