歷屆第3題

2016年3月

提示

差值陣列

題解

用差值陣列維護每個點上有多少線段
再數有幾個點上有一以上的字串
$O(N+R_{max})$

C++範例代碼：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    ll C = 10000000;
    ll n;
    cin >> n;
    vector<ll> d(C,0);
    while (n--){
        ll l,r;
        cin >> l >> r;
        d[l]++;
        d[r]--;
    }
    ll cur = 0;
    ll ans = 0;
    for (ll i = 0;i<C;i++){
        cur += d[i];
        if(cur>0)ans++;
    }
    cout << ans << "\n";
}

Python範例代碼：

2016年10月

定時K彈

提示

題解

用rope模擬操作
$O(n\log n)$

C++範例代碼：

#include<bits/stdc++.h>
#include<ext/rope>
using namespace std;
using namespace __gnu_cxx;
using ll = long long;
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    ll n, m, k;
    cin >> n >> m >> k;
    rope<ll> r;
    for (int i = 1;i<=n;i++){
        r.push_back(i);
    }
    ll alive = n;
    ll cur = 0;
    while (k--){
        cur = (cur+m-1)%alive;
        r.erase(cur,1);
        alive--;
    }
    cur = cur%alive;
    cout << r[cur] << "\n";
}

Python範例代碼：

2017年3月

數字龍捲風
注：本題難度較不符合第三題應有的難度

提示

題解

C++範例代碼：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
struct pos{
    ll x,y;
    pos(){}
    pos(ll X,ll Y):x(X),y(Y){}
    ll& get(vector<vector<ll>> &v){
        return v[x][y];
    }
};
pos operator+(const pos &a, const pos &b){
    return pos(a.x+b.x,a.y+b.y);
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    pos fs[4] = {pos(0,-1),pos(-1,0),pos(0,1),pos(1,0)};
    ll n;
    ll f;
    cin >> n >> f;
    ll i = 2;
    ll c = i/2;
    pos cur = pos(n/2,n/2);
    function<bool(pos&)> valid = [&n](pos &p){
        return p.x>=0&&p.y>=0&&p.x<n&&p.y<n;
    };
    vector<vector<ll>> arr(n);
    for (int x = 0;x<n;x++){
        arr[x].resize(n);
        for (int y = 0;y<n;y++){
            cin >> arr[x][y];
        }
    }
    while (valid(cur)){
        cout << cur.get(arr);
        cur = cur + fs[f];
        c--;
        if (c==0){
            i++;
            c = i/2;
            f = (f+1)%4;
        }
    }
    cout << "\n";
}

Python範例代碼：

2017年10月

樹狀圖分析

提示

dfs

題解

先找出根結點(不是其他人的子節點的點)
再從根結點往下dfs
$O(n)$

C++範例代碼：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
ll ans = 0;
vector<vector<ll>> child;
ll dfs(ll i){
    ll h = 0;
    for (ll t : child[i]){
        h = max(h,dfs(t-1)+1);
    }
    ans+=h;
    return h;
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    ll n;
    cin >> n;
    child.resize(n);
    vector<bool> root(n,true);
    for (int i = 0;i<n;i++){
        ll k;
        cin >> k;
        child[i].resize(k);
        for (int j = 0;j<k;j++){
            cin >> child[i][j];
            root[child[i][j]-1] = false;
        }
    }
    for (int i = 0;i<n;i++){
        if (root[i]){
            cout << (i+1) << "\n";
            dfs(i);
            cout << ans << "\n";
        }
    }
}

Python範例代碼：

2019年6月

互補CP

提示

題解

用位元來記錄狀態
用unordered_multiset存每一個CP
再用XOR判斷互補
$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 m,n;
    cin >> m >> n;
    unordered_multiset<ll> dat;
    while (n--){
        string s;
        cin >> s;
        ll cur = 0;
        for (char c : s){
            ll i = c>='a'?((c-'a')+26):(c-'A');
            cur |= 1LL<<i;
        }
        dat.insert(cur);
    }
    ll ans = 0;
    ll full = (1LL<<m)-1LL;
    for (ll i : dat) ans += dat.count(full^i);
    cout << (ans/2) << "\n";
}

Python範例代碼：

2020年1月

砍樹

提示

題解

用linked list處理
由左往右掃描
$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,l;
    cin >> n >> l;
    vector<ll> p(n);
    vector<ll> h(n);
    for(ll i = 0;i<n;i++)cin >> p[i];
    for(ll i = 0;i<n;i++)cin >> h[i];
    list<pair<ll,ll>> line;
    ll big = 1e18;
    line.push_back({0LL,big});
    for (ll i = 0;i<n;i++) line.push_back({p[i],h[i]});
    line.push_back({l,big});
    ll c=0, ans=0;
    auto it = line.begin();
    it++;
    auto ed = line.end();
    ed--;
    while (it!=ed){
        auto left = it;
        left--;
        auto right = it;
        right++;
        ll need = (*it).second;
        if ((*it).first-(*left).first >= need || (*right).first - (*it).first >= need){
            c++;
            ans = max(ans,need);
            line.erase(it);
            if (left!=line.begin()) it = left;
            else it = right;
        }else{
            it++;
        }
    }
    cout << c << "\n" << ans << "\n";
}

Python範例代碼：

2020年7月

圓環出口

提示

二分搜

題解

維護前綴和
對前綴和二分搜來計算目的地
$O(m\log 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,m;
    cin >> n >> m;
    vector<ll> p(n);
    vector<ll> s(n+1,0);
    ll all = 0;
    for (int i = 0;i<n;i++){
        cin >> p[i];
        all+=p[i];
        s[i+1] = all;
    }
    ll cur = 0;
    while (m--){
        ll q;
        cin >> q;
        ll to = (s[cur+1]-p[cur]+q)%all;
        ll en = (lower_bound(s.begin(),s.end(),to)-s.begin())%n;
        cur = en;
    }
    cout << cur << "\n";
}

Python範例代碼：

2020年10月

勇者修煉

提示

題解

逐行做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 m,n;
    cin >> m >> n;
    vector<vector<ll>> a(m);
    vector<vector<ll>> l(m);
    vector<vector<ll>> r(m);
    for (ll i = 0;i<m;i++){
        a[i].resize(n);
        l[i].resize(n);
        r[i].resize(n);
        for (ll j = 0;j<n;j++){
            cin >> a[i][j];
            l[i][j] = r[i][j] = a[i][j];
        }
    }
    for (ll i = 0;i<m;i++){
        if (i>0){
            for (ll j = 0;j<n;j++){
                l[i][j] = r[i][j] = a[i][j] + max(0LL,max(l[i-1][j], r[i-1][j]));
            }
        }
        for (ll j = 1;j<n;j++){
            r[i][j] = max(r[i][j],a[i][j]+r[i][j-1]);
        }
        for (ll j=n-2;j>=0;j--){
            l[i][j] = max(l[i][j],a[i][j]+l[i][j+1]);
        }
    }
    ll ans = -1e18;
    for (ll j = 0;j<n;j++){
        ans = max(ans,max(l[m-1][j],r[m-1][j]));
    }
    cout << ans << "\n";
}

Python範例代碼：

2021年1月

切割費用

提示

set、二分搜

題解

用set維護切割點
並用二分搜取得所切割的棍子的長度
$O(n\log 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,l;
    cin >> n >> l;
    vector<ll> cuts(n);
    for (ll z = 0;z<n;z++){
        ll x,i;
        cin >> x >> i;
        cuts[i-1]=x;
    }
    ll ans = 0;
    set<ll> s;
    s.insert(0);
    s.insert(l);
    for (ll c : cuts){
        set<ll>::iterator L = s.upper_bound(c);
        set<ll>::iterator R = s.lower_bound(c);
        L--;
        ans += ((*R)-(*L));
        s.insert(c);
    }
    cout << ans << "\n";
}

Python範例代碼：

2021年9月

幸運數字

提示

題解

用線段樹求最小值位置
再用前綴和處理總和
$O(n\log n)$

C++範例代碼：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
struct segtree{
    vector<pair<ll,ll>> dat;
    ll n;
    segtree(ll N){
        n = N;
        dat.resize(4*n);
    }
    void build(ll i, ll l, ll r, vector<ll>::iterator &it){
        if (l == r){
            dat[i] = {*it,l};
            it++;
        }else{
            ll mid = (l+r)>>1;
            build(i<<1,l,mid,it);
            build(i<<1|1,mid+1,r,it);
            dat[i] = min(dat[i<<1],dat[i<<1|1]);
        }
    }
    pair<ll,ll> query(ll i, ll l, ll r, ll ql, ll qr){
        if (ql<=l&&r<=qr){
            return dat[i];
        }else{
            ll mid = (l+r)>>1;
            if (qr<=mid) return query(i<<1,l,mid,ql,qr);
            if (ql>mid) return query(i<<1|1,mid+1,r,ql,qr);
            return min(query(i<<1,l,mid,ql,qr),query(i<<1|1,mid+1,r,ql,qr));
        }
    }
};
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    ll n;
    cin >> n;
    vector<ll> a(n);
    vector<ll> sum(n,0);
    for(ll i = 0;i<n;i++){
        cin >> a[i];
        sum[i+1] = sum[i]+a[i];
    }
    segtree s(n);
    auto it = a.begin();
    s.build(1,0,n-1,it);
    ll l = 0, r = n-1;
    while (l<r){
        ll m = s.query(1,0,n-1,l,r).second;
        if (m == l) l++;
        else if (m == r) r--;
        else{
            ll left = sum[m]-sum[l];
            ll right = sum[r+1]-sum[m+1];
            if (left>right) r=m-1;
            else l = m+1;
        }
    }
    cout << a[l] << "\n";
}

Python範例代碼：

2021年11月

生產線

提示

差值陣列、排序

題解

用差值陣列處理每一個位置需要的資料量
把資料量和機器速度分別排序後
$大\times 小、小\times 大$ 的加在一起
透過排序不等式可以知道這樣是最好的
$O(n+m+n\log 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, m;
    cin >> n >> m;
    vector<ll> d(n+1,0);
    while (m--){
        ll l,r,w;
        cin >> l >> r >> w;
        d[l-1]+=w;
        d[r]-=w;
    }
    vector<ll> a(n);
    ll cur = 0;
    for (ll i = 0;i<n;i++){
        cur+=d[i];
        a[i] = cur;
    }
    vector<ll> t(n);
    for (ll i = 0;i<n;i++) cin >> t[i];
    sort(a.begin(),a.end());
    sort(t.begin(),t.end());
    ll ans = 0;
    for (ll i = 0;i<n;i++){
        ans += a[n-1-i]*t[i];
    }
    cout<< ans << "\n";
}

Python範例代碼：

2022年1月

數位占卜

提示

set

題解

用hashset存籤
對於每一個籤，切出不同長度的前後綴，若前綴=後綴且剩下的部分能在set裡找到一樣的則答案+1

原理：
對於一組聖筊 $a+b$
不失一般性設 $a$ 比較長
所以a的前半和a的後半加b一樣
設a的前半=c、a的後半=d
$a+b=(c+d)+b=((d+b)+d)+b=(d+b+d)+b$
可知 $d$ 是 $a$ 的前後綴
所以對每一支籤，切出不同長度的前後綴 $d$ ，只要存在與剩下的部分相同的籤 $b$ ，就可以組成聖筊
因為總是用長的籤去找短的籤，所以不用擔心重複算到的問題
$O(m\times 字串長度)$

C++範例代碼：

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin >> n;
    unordered_set<string> dat;
    while (n--){
        string s;
        cin >> s;
        dat.insert(s);
    }
    long long ans = 0;
    for (string s: dat){
        int l = s.size();
        for (int i = 1;i<(l+1)/2;i++){
            bool sus = true;
            for (int j = 0;j<i;j++){
                if (s[j]!=s[j+l-i]) sus=false;
            }
            if (sus){
                ans += dat.count(s.substr(i,l-2*i))?1:0;
            }
        }
    }
    cout << ans << "\n";
}

Python範例代碼：

m = int(input())
dat = {input() for a in range(m)}
ans = 0
for s in dat:
    for i in range(1,(len(s)+1)//2):
        if s[:i]==s[-i:] and s[i:-i] in dat:
            ans+=1
print(ans)

2022年6月

雷射測試

提示

模擬、二分搜

題解

紀錄各行列上有哪些點有鏡子，並排序
再直接模擬，查詢的時候用二分搜
$O(n\log n)$

C++範例代碼：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll sz = 30000;
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    ll n;
    cin >> n;
    vector<vector<pair<ll,ll>>> rows(sz*3),cols(sz*2);
    while (n--){
        ll x,y,c;
        cin >> x >> y >> c;
        y+=sz;
        rows[y].push_back({x,c});
        cols[x].push_back({y,c});
    }
    for (vector<pair<ll,ll>> &v : rows) if (v.size()>1) sort(v.begin(),v.end());
    for (vector<pair<ll,ll>> &v : cols) if (v.size()>1) sort(v.begin(),v.end());
    bool sus = true;
    ll facing = 1; // 1=positive 0=negative
    ll hv = 1; // 1=horizontal 0=vertical
    ll x = 0;
    ll y = sz;
    function<void(vector<pair<ll,ll>>&,ll&)> query = [&](vector<pair<ll,ll>>& line, ll& p){
        if (facing){
            vector<pair<ll,ll>>::iterator it = upper_bound(line.begin(),line.end(),make_pair(p,1LL));
            if (it!=line.end()){
                p = (*it).first;
                facing ^= (*it).second;
                sus = true;
            }
        }else{
            vector<pair<ll,ll>>::iterator it = lower_bound(line.begin(),line.end(),make_pair(p,0LL));
            if (it!=line.begin()){
                it--;
                p = (*it).first;
                facing ^= (*it).second;
                sus = true;
            }
        }
    };
    ll ans = 0;
    while (sus){
        sus = false;
        if (hv) query(rows[y],x);
        else query(cols[x],y);
        hv^=1;
        ans += sus;
    }
    cout << ans << "\n";
}

Python範例代碼：