氣球盃8th 題解

Overview

致謝：

感謝tester們提供很多題目的反饋：王淇、陳克盈、陳俊安、林煜傑。
感謝鄭天均大學長幫忙解決judge的技術問題。
感謝林煜傑提供優質的題目及準備題目測資。

各題 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

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

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

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)\)。

官解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

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

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

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)\)。

官解(吳威錡) 



















































































#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

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)\) 內求出。

引理的證明

假設兩個路徑相交於一個不是 \(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)\)。

官解(林煜傑) 



























































#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();
}
另解(吳柏翰) 




























































































#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;
}

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

Select a repo