歷屆第4題

2016年3月

提示

樹

題解

這題就是在找樹上的最遠距離
建圖，然後從隨便一個點開始dfs
dfs的時候維護"某一方向最多可以延伸多遠"
$O(n)$

C++範例代碼：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    ll n;
    while (cin >> n){
        vector<vector<ll>> connect(n);
        for (int i = 1;i<n;i++){
            ll a,b;
            cin >> a >> b;
            connect[a].push_back(b);
            connect[b].push_back(a);
        }
        ll ans = 0;
        function<ll(ll,ll)> dfs;
        dfs = [&](ll cur, ll p){
            ll h = 0;
            for (ll t : connect[cur]){
                if (t!=p){
                    ll hh = dfs(t,cur);
                    ans = max(ans,hh+h);
                    h = max(h,hh);
                }
            }
            return h+1;
        };
        dfs(0,-1);
        cout << ans << "\n";
    }
}

Python範例代碼：

2016年10月

棒球遊戲
注：本題難度不符合第四題應有的難度

提示

題解

C++範例代碼：

Python範例代碼：

2017年3月

基地台

提示

二分搜、貪心法

題解

對直徑二分搜
用貪心法檢查直徑是否足夠
$O(n\times\log 1e9)$

C++範例代碼：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    ll n,k;
    cin >> n >> k;
    vector<ll> p(n);
    for (int i = 0;i<n;i++) cin >> p[i];
    sort(p.begin(),p.end());
    function<bool(ll)> ok = [&](ll d){
        ll c = 1;
        ll sp = p[0];
        for (ll i : p){
            if (i>d+sp){
                sp = i;
                c++;
            }
        }
        return c<=k;//ans<=d
    };
    ll l = 1,r = 1e9;
    while (l<r){
        ll mid = (l+r)/2;
        if (ok(mid)){
            r = mid;
        }else{
            l = mid+1;
        }
    }
    cout << l << "\n";
}

Python範例代碼：

2017年10月

物品堆疊

提示

排序

題解

考慮只有兩個物品的情況
會發現 $重量\times 另一物次數$ 較小的在上方較優
拓展到一般情況
可以以此規則做排序後直接計算能量消耗值
即為答案
$O(n\log n)$

C++範例代碼：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
bool cmp(pair<ll,ll> &a, pair<ll,ll> b){
    return a.first*b.second<a.second*b.first;
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    ll n;
    cin >> n;
    vector<pair<ll,ll>> a(n);
    for (int i = 0;i<n;i++) cin >> a[i].first;
    for (int i = 0;i<n;i++) cin >> a[i].second;
    sort(a.begin(),a.end(), cmp);
    ll ans = 0;
    ll w = 0;
    for (int i = 0;i<n;i++){
        ans += w*a[i].second;
        w += a[i].first;
    }
    cout << ans << "\n";
}

Python範例代碼：

2019年6月

美麗的彩帶

提示

unordered_map

題解

用unordered_map存各個數字的數量
再由左往右掃描每一個寬度為 $m$ 的區間
注意數字要用

string存

 $O(n+m)$



C++範例代碼：
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    ll m,n;
    cin >> m >> n;
    vector<string> a(n);
    for (ll i = 0;i<n;i++){
        cin >> a[i];
    }
    ll tps = 0;
    unordered_map<string,ll> mp;
    function<void(string&)> add = [&](string &s){
        if (!mp.count(s)){
            mp[s] = 0;
        }
        if (mp[s]==0) tps++;
        mp[s]++;
    };
    function<void(string&)> del = [&](string &s){
        mp[s]--;
        if (mp[s]==0) tps--;
    };
    ll ans = 0;
    for (ll i = 0;i<m;i++){
        add(a[i]);
    }
    ans += tps>=m;
    for (ll i = m;i<n;i++){
        add(a[i]);
        del(a[i-m]);
        ans += tps>=m;
    }
    cout << ans << "\n";
}




Python範例代碼：


2020年1月
貨物分配

提示


樹



題解


直接模擬物品放入的過程

過程中順便維護"切換器下貨箱總重量"

 $O(mn)$ 




C++範例代碼：
#include <bits/stdc++.h>
using namespace std;
vector<int> add;
vector<int> weight;
vector<int> left_node;
vector<int> right_node;
int n, m;
int init(int cur){
    if (cur<n) weight[cur] = init(left_node[cur])+init(right_node[cur]);
    return weight[cur];
}
int main(){
    ios::sync_with_stdio(false);cin.tie();
    cin >> n >> m;
    add.resize(m,0);
    weight.resize(2*n,0);
    left_node.resize(2*n,0);
    right_node.resize(2*n,0);
    for (int i = 0;i<n;i++){
        cin >> weight[n+i];
    }
    for (int i = 0;i<m;i++){
        cin >> add[i];
    }
    for (int i = 1;i<n;i++){
        int p,s,t;
        cin >> p >> s >> t;
        left_node[p] = s;
        right_node[p] = t;
    }
    init(1);
    for (int i = 0;i<m;i++){
        int w = add[i];
        int cur = 1;
        while (cur<n){
            weight[cur]+=w;
            if (weight[left_node[cur]]<=weight[right_node[cur]]){
                cur = left_node[cur];
            }else{
                cur = right_node[cur];
            }
        }
        weight[cur]+=w;
        cout << cur << " \n"[i==m-1];
    }
}




Python範例代碼：


2020年7月
病毒演化

提示


樹、dp



題解


觀察可得每個位置都是獨立的

分別處裡每一個位置

從根開始dfs，過程中dp維護"選某一個字元後，該點以下的距離總合最小值"

 $O(mn)$ 




C++範例代碼：
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    ll n,m;
    cin >> n >> m;
    vector<string> virus(n);
    vector<vector<ll>> childs(n);
    ll root = -1;
    for(ll x = 0;x<n;x++){
        ll i,j;
        cin >> i >> j >> virus[i-1];
        if(i!=j) childs[j-1].push_back(i-1);
        else root = i-1;
    }
    vector<vector<ll>> dp(n);
    const string chs = "AUCG";
    const ll big = 1e10;
    ll ans = 0;
    ll p;
    function<void(ll)> dfs;
    dfs = [&](ll i){
        for (ll ch : childs[i]) dfs(ch);
        char c = virus[i][p];
        for (int a = 0;a<4;a++){
            if(c == '@' || c == chs[a]){
                ll x = 0;
                for (ll ch : childs[i]){
                    ll m = big;
                    for (int b = 0;b<4;b++){
                        m = min(m,dp[ch][b]+(a!=b));
                    }
                    x+=m;
                }
                dp[i][a] = x;
            }
        }
    };
    for (p = 0;p<m;p++){
        for (ll i = 0;i<n;i++) dp[i].assign(4,big);
        dfs(root);
        ll curans = big;
        for (int a = 0;a<4;a++) curans = min(curans,dp[root][a]);
        ans += curans;
    }
    cout << ans << "\n";
}




Python範例代碼：


2020年10月
低地距離

提示


線段樹



題解


從小的數字開始處理

低窪值即為兩個數字之間有幾個處裡過的數字

利用線段樹維護"有幾個處裡過的數字"

 $O(n\log n)$ 




C++範例代碼：
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
struct segtree{
    ll n;
    vector<ll> dat;
    segtree(ll N):n(N){
        dat.resize(4*n,0LL);
    }
    void add(ll i,ll l,ll r,ll p){
        dat[i]++;
        if (l<r){
            ll mid = (l+r)/2;
            if (mid>=p){
                add(i<<1,l,mid,p);
            }else{
                add(i<<1|1,mid+1,r,p);
            }
        }
    }
    void add(ll p){
        add(1,0,n-1,p);
    }
    ll query(ll i,ll l,ll r,ll ql,ll qr){
        ll x = 0;
        if (ql<=l&&qr>=r){
            x += dat[i];
        }else{
            ll mid = (l+r)/2;
            if (mid>=ql){
                x+=query(i<<1,l,mid,ql,qr);
            }
            if (mid<qr){
                x+=query(i<<1|1,mid+1,r,ql,qr);
            }
        }
        return x;
    }
    ll query(ll ql,ll qr){
        return query(1,0,n-1,ql,qr);
    }
};
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    ll n;
    cin >> n;
    vector<vector<ll>> dat(n);
    for (ll i = 0;i<2*n;i++){
        ll x;
        cin >> x;
        dat[x-1].push_back(i);
    }
    segtree t(2*n);
    ll ans = 0;
    for (ll i =0;i<n;i++){
        ll a = min(dat[i][0],dat[i][1]);
        ll b = max(dat[i][0],dat[i][1]);
        ans += t.query(a,b);
        t.add(a);
        t.add(b);
    }
    cout << ans << "\n";
}




Python範例代碼：


2021年1月
飛黃騰達

提示


dp



題解


觀察可得

飛黃吃到的果實在依其中一個座標軸排序後

另一個座標軸的值是(非嚴格)遞增的

所以可以依其中一個座標軸排序後求最長遞增子序列LIS

 $O(n\log n)$ 




C++範例代碼：
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
bool cmp(const pair<ll,ll> &a, const pair<ll,ll> &b){
    return a.first==b.first?a.second>b.second:a.first<b.first;
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    ll n;
    cin >> n;
    vector<pair<ll,ll>> a(n);
    for(ll i = 0;i<n;i++) cin >> a[i].first >> a[i].second;
    sort(a.begin(),a.end());
    vector<ll> dp;
    for (pair<ll,ll> &o : a){
        ll i = o.second;
        vector<ll>::iterator it = upper_bound(dp.begin(),dp.end(),i);
        if (it == dp.end()) dp.push_back(i);
        else{
            *it = i;
        }
    }
    cout << dp.size() << "\n";
}




Python範例代碼：


2021年9月
美食博覽會

注：這題ZeroJudge測資太爛， $O(n^2)$  可以過，但在此還是介紹好一點的作法

提示


dp



題解


先求出每個點做多可以往左吃幾間店

再用dp求答案

 $O(nk)$ 




C++範例代碼：
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    ll n,k;
    cin >> n >> k;
    vector<ll> a(n);
    for(ll i = 0; i<n; i++){
        cin >> a[i];
        a[i]--;
    }
    vector<ll> left(n);
    left[0] = 0;
    vector<bool> used(n,false);
    used[a[0]] = true;
    ll l = 0;
    for (ll i = 1; i<n;i++){
        while (used[a[i]]){
            used[a[l]] = false;
            l++;
        }
        left[i] = l;
        used[a[i]] = true;
    }
    vector<vector<ll>> dp(n+1);
    for (auto &o : dp) o.resize(k+1,0);
    for (ll i = n;i>0;i--){
        for (ll j = k;j>0;j--){
            dp[left[i-1]][j] = max(dp[left[i-1]][j],dp[i][j-1]+(i-left[i-1]));
        }
        for (ll j = 0;j<=k;j++){
            dp[i-1][j] = max(dp[i-1][j],dp[i][j]);
        }
    }
    ll ans = 0;
    for (ll j = 0;j<=k;j++){
        ans = max(ans,dp[0][j]);
    }
    cout << ans << "\n";
}




Python範例代碼：


2021年11月
真假子圖

提示


dsu



題解


用並查集處理

為每個人創造鏡像

看到兩個人合作，將兩人與對方的鏡像放到同一組

如果有人和自己的鏡像同一組就代表出現了矛盾

 $O(m\log m\times ans + pk\log m)$ 




C++範例代碼：
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct dsu{
    ll n;
    vector<ll> p;
    ll gpc;
    dsu(ll N):n(N){
        p.resize(n);
        reset();
    }
    void reset(){
        gpc = n;
        for(ll i = 0; i < n; i++) p[i]=i;
    }
    ll gp(ll i){
        if (i == p[i]) return i;
        return p[i] = gp(p[i]);
    }
    bool merge(ll a,ll b){
        if (con(a,b)) return false;
        p[gp(a)] = gp(b);
        gpc--;
        return true;
    }
    bool con(ll a,ll b){
        return gp(a)==gp(b);
    }
};
int main(){
    ios::sync_with_stdio(false);cin.tie();
    ll n,m;
    cin >> n >> m;
    vector<pair<ll,ll>> a(m);
    for(ll i = 0; i < m; i++) cin >> a[i].first >> a[i].second;
    ll p,k;
    cin >> p >> k;
    dsu d(2*n);
    for (auto &o : a) {
        d.merge(o.first, o.second+n);
        d.merge(o.first+n, o.second);
    }
    for (ll x = 1; x<=p;x++){
        vector<pair<ll,ll>> c(k);
        for(ll i = 0; i < k; i++) cin >> c[i].first >> c[i].second;
        for (auto &z : c) {
            d.merge(z.first, z.second+n);
            d.merge(z.first+n, z.second);
            if (d.con(z.first,z.first+n)){
                cout << x << "\n";
                d.reset();
                for (auto &o : a) {
                    d.merge(o.first, o.second+n);
                    d.merge(o.first+n, o.second);
                }
                break;
            }
        }
    }
}




Python範例代碼：


2022年1月
牆上海報

提示


貪心法、二分搜



題解


用貪心法可 $O(n)$  求出某一高度能否貼海報

能否貼海報 $\leftrightarrow$  此高度 $\le$  最大高度 $=$  答案

且已知答案為 $[1,h_{max}]$  中的一個整數

對 $[1,h_{max}]$  二分搜

 $O(n\log_2h_{max})$ 




C++範例代碼：
#include <bits/stdc++.h>
using namespace std;
int n,k;
vector<int> h,w;
bool check(int ans){
    int t = 0,len=0;
    for (int i = 0;i<n;i++){
        if (h[i]>=ans) len++;
        else len = 0;
        if(len>=w[t]){
            len-=w[t];
            t++;
            if(t>=k) return true;
        }
    }
    return false;
}
int search_ans(int l, int r){
    if (l == r) return l;
    int mid = ((r+l)/2)+1;
    if (check(mid)){
        return search_ans(mid,r);
    }
    return search_ans(l,mid-1);
}
int main(){
    ios::sync_with_stdio(false);cin.tie();
    cin >> n >> k;
    h.resize(n);
    w.resize(k);
    int mh = 0;
    for (int i = 0;i<n;i++){
        cin>>h[i];
        if(h[i]>mh) mh=h[i];
    }
    for (int i = 0;i<k;i++){
        cin>>w[i];
    }
    cout << search_ans(1,mh) << "\n";
}




Python範例代碼：
n=k=0
h=[]
w=[]
def check(ans):
    t = l = 0
    for i in range(n):
        if h[i]>=ans:
            l+=1
        else:
            l=0
        if l>=w[t]:
            l-=w[t]
            t+=1
            if t>=k:
                return True
    return False
def search(l,r):
    if l==r:
        return l
    mid = (l+r)//2+1
    if check(mid):
        return search(mid,r)
    return search(l,mid-1)
n,k = map(int,input().split())
h = [int(s) for s in input().split()]
w = [int(s) for s in input().split()]
print(search(1,max(h)))



2022年6月
內積

提示


dp



題解


用各種排列方式對齊後，直接兩兩相乘，做最大連續區間和

即掃描一次序列 求 目前前綴和 - 最小前綴和 之最大值

 $O(mn)$ 




C++範例代碼：
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
ll solve(vector<ll> &a, vector<ll> &b){
    ll la = a.size();
    ll lb = b.size();
    ll ans = -1e18;
    for (ll d = -la+1;d<=lb-1;d++){
        ll s = 0;
        ll p = 0;
        for (ll i = max(0LL,-d); i<min(la,lb-d);i++){
            s += a[i]*b[i+d];
            ans = max(ans,s-p);
            p = min(p,s);
        }
    }
    return ans;
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    ll m,n;
    cin >> m >> n;
    vector<ll> x(m),y(n);
    for (ll &i : x) cin >> i;
    for (ll &i : y) cin >> i;
    ll ans = solve(x,y);
    reverse(y.begin(),y.end());
    ans = max(ans,solve(x,y));
    cout << ans << "\n";
}




Python範例代碼：