2022.11 TOI 潛力組題解

因為感覺沒甚麼人在寫TOI練習賽題解，而且為了拯救快變成修課筆記的競程筆記，想說來寫看看

Cycle

problem

給定一有向圖，求能夠到達任一環路的所有點集合。

solution

開一個陣列倒著記錄每一個有向邊。
再用一個陣列記錄入度，跑一次拓樸排序，剩下入度不為0的點即是環路及可到達環路的點（因為是倒著紀錄）。

code

code

// Author : ysh
// 11/30/2022 Wed 21:10:47.58
#include<bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int a,b;cin>>a>>b;
    vector<vector<int>>re(a);
    vector<int>to(a);
    for(int i = 0;i<b;i++) {
        int a,b;cin>>a>>b;
        re.at(b).push_back(a);
        to.at(a)++;
    }
    queue<int>q;
    for(int i = 0;i<a;i++) {
        if(to.at(i) == 0) q.push(i);
    }
    while(!q.empty()) {
        int now = q.front();q.pop();
        for(int &i : re.at(now)) if(--to.at(i) == 0) {
            q.push(i);
        }
    }
    bool c = 0;
    for(int i = 0;i<a;i++) {
        if(to.at(i) != 0) {
            cout<<i<<" ";
            c = 1;
        }
    }
    if(!c) cout<<-1;
    return 0;
}

tags: graph tapoo

Serving

problem

恩題敘好複雜，我不知道怎麼寫QAQ

solution

用一顆BIT記錄這個人是否拿到餐點，如果是，則該值為0，否則為1。
我們先使用pair<int,int>記錄客人的餐點跟位置，然後排序。
接著每上一道菜，就使用二分搜對客人位置搜尋第一個還沒上菜的客人位置（因為排過序所以可以直接搜尋）
找到位置後，將答案加上BIT中第0位到該位的和(也就是沒被上到菜的人之怒氣值)。
最後將BIT中該位置的值減一。

code

code

註：<tree>是BIT模板

// Author : ysh
// 11/30/2022 Wed 21:32:09.78
#include<bits/stdc++.h>
using namespace std;
#include<tree>
#define int long long
inline bool cp(pair<int,int>a,int b) {
    return a.first < b;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;cin>>n;
    vector<pair<int,int>>f(n);
    vector<int>tmp(n,1);
    tree<int>t(tmp);
    queue<int>q;
    for(int i = 0;i<n;i++) {
        int a,b;cin>>a>>b;
        q.push(a);
        f.at(i) = {b,i};
    }
    int ans = 0;
    sort(f.begin(),f.end());
    while(!q.empty()) {
        int now = q.front();q.pop();
        auto found = lower_bound(f.begin(),f.end(),now,cp);
        int ffound = 0;
        for(auto i = found;i != f.end();i = next(i)) {
            if(i->second == -1) continue;
            ffound = i->second;
            i->second = -1;
            break;
        }
        t.add(ffound,-1);
        ans = ans + t.sum(0,ffound);
    }
    cout<<ans;
    return 0;
}

tags: BIT sort

Selling

problem

有一農夫沿途賣蔬果，路上有許多城市，他可以選擇是否停下，一旦停下便將進行買賣，同時將車
子的油箱加滿，且當車子沒有油時必須停下加油。
給定每一城市的可能獲利(可為負值）$f_i \space ,1 \leq i \leq n$，以及油箱加滿最多可行駛的距離$k$，問最大獲利？

solution

標準的DP題型，我們開g[]讓$g_i$為行經一個城市$i$所能得到的最大獲利。
經過推導可得
$g_i=max({a_x|(i - k) \leq x<i}) + f_i$
$\text{if } i \leq k \rightarrow g_i = max(g_i,f_i)$
但暴力求前$k$項的最大值會TLE，所以使用priority queue記錄前幾項的最大值。

code

code

// Author : ysh
// 11/30/2022 Wed 21:57:11.30
#include<bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int a,b;cin>>a>>b;
    vector<int>f(a),g(a,INT_MIN);
    for(int i = 1;i<a - 1;i++) {
        cin>>f.at(i);
    }
    priority_queue<pair<int,int>,vector<pair<int,int>>,less<pair<int,int>>>q;
    q.emplace(0,0);
    g.at(0) = 0;
    for(int i = 1;i<a;i++) {
        auto now = q.top();
        while(!q.empty() && now.second < i - b) {
            q.pop();now = q.top();
        }
        g.at(i) = now.first;
        g.at(i) = g.at(i) + f.at(i);
        q.emplace(g.at(i),i);
    }
    cout<<g.at(a - 1);
    return 0;
}

tags: priority_queue DP