2023.04 TOI 潛力組題解

Repo
我終於把專題趕完ㄌ(灑花

A.Icebreaker

problem

給你一堆關係，請你分成兩組，問怎麼分可以讓每一組中的任兩個人沒有關係。

solution

簡而言之又是個二分圖問題，但這題不需要複雜的演算法，直接DFS就可以ㄌ
走到一個點，如果之前沒經過，就幫他上跟父節點相反的顏色（總共只有兩種顏色），但如果之前有經過，就會有兩種情況：

1. 顏色正常（跟父節點相反)
2. 顏色錯誤（跟父節點相同）
   對於第一種情況，因為之前走過，勢必會將其子節點遞迴完，所以不必重複確認，可以直接返回。
   但如果是第二種情況，代表其必跟父節點同一組，但又因為跟父節點有關係，所以無論怎麼分都沒辦法符合題意，所以直接退出。

其實不是找環喔
舉個例：
1 2
2 3
3 4
4 1

code

code

其實code裡面有兩行useless code
閒的人可以找找

// Author : ysh
// 04/25/2023 Tue 10:02:43.14
#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>>f(a);
    for(int i = 0;i<b;i++) {
        int a,b;cin>>a>>b;
        a--;b--;
        f.at(a).push_back(b);
        f.at(b).push_back(a);
    }
    
    bool c = 1;
    vector<bool>mark(a),color(a);
    function<pair<int,int>(int,bool)> check = [&] (int a,bool b) {
        if(mark.at(a) && color.at(a) != b) cout<<0,exit(0); 
        if(mark.at(a)) return make_pair(0,0);
        if(!mark.at(a)) mark.at(a) = 1,color.at(a) = b;
        pair<int,int>now = {1,0};
        for(int &i : f.at(a)) {
            pair<int,int> tmp = check(i,!b);
            now.second = now.second + tmp.first;
            now.first = now.first + tmp.second;
        }
        return now;
    };
    
    int ans = 0;
    for(int i = 0;i<a;i++) {
        if(!mark.at(i)) {
            color = vector<bool>(a);
            auto tmp = check(i,0);
            ans = ans + max(tmp.first,tmp.second);
        }
    }
    cout<<ans;
    return 0;
}

B.Land

problem

給定一列土地，每塊土地都有一個地主 $a_i,1 \leq i \leq n$ 。
蓋房子需要地主同意，但你很懶，最多只想去問$k$個地主，問最多可以連續使用多少土地。

solution

簡單DP，我的做法是先離散化後再直接開個陣列 $now$ 紀錄目前已經使用每個地主幾塊地，再來是 $sig$ ，記錄現在需要徵求多少地主同意，可以在更新範圍時維護， $l$ 則是目前土地的最左端，同樣可以在更新範圍的時候維護。

然後寫個迴圈，從左到右更新範圍，最後將答案對 $(r - l) + 1$ 取最大值即可。

code

code

// Author : ysh
// 04/25/2023 Tue  9:49:45.41
#include<bits/stdc++.h>
using namespace std;
int offline(vector<int>&f) {
    vector<int>v(f);
    sort(v.begin(),v.end());
    v.resize(unique(v.begin(),v.end()) - v.begin());
    for(int &i : f) {
        i = lower_bound(v.begin(),v.end(),i) - v.begin();
    }
    return v.size();
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int a,b;cin>>a>>b;
    vector<int>f(a);
    for(int &i : f) {
        cin>>i;
    }
    int r = offline(f);
    
    vector<int>now(r);
    int ans = 0;
    int l;l = 0;
    int sig = 0;
    assert(b != 0);
    for(int i = 0;i<a;i++) {
        now.at(f.at(i))++;
        if(now.at(f.at(i)) == 1) sig = sig + 1;
        while(sig > b) {
            now.at(f.at(l))--;
            if(now.at(f.at(l)) == 0) sig = sig - 1;
            l++;
        }
        ans = max(ans,(i - l) + 1);
    }
    cout<<ans;
    return 0;
}

C.Name

problem

定義 $f_{i,j} = \{ 1\ when\ i = j\ ,\ 0\ otherwise \}$
給你一堆字串 $s_i,\forall\ 1 \leq i \leq n$ 試求

$$
\sum_{r = 1}^{|s_i|}\sum_{k = \{x | x \geq 1 \wedge x \leq n \wedge x \not= i\}} f_{s_i[1:r],s_k[1:r]}
$$

solution

說說我寫這題的心路歷程，
multiset -> unordered_multiset
拿到TLE後徹底自閉

後來決定直接砸Trie
大概就是建樹的時候每走到一個節點就把那個節點的值+1
取答案的時候照著走一遍，把走過的節點值加起來就是答案ㄌ
對 就是這樣 我相信你們都懂ㄌouob
好啦 看code

code

code

其實這是我第一次寫Trie
真快樂

// Author : ysh
// 04/25/2023 Tue  9:38:37.83
#include<bits/stdc++.h>
using namespace std;
struct box{
    vector<box*>next;
    vector<int>count;
    box() {
        next.resize(26);
        count.resize(26);
    }
};
box root;
void insert(box *t,vector<char>&f) {
    if(f.empty()) return;
    int now = f.back() - 'A';
    if(not t->next.at(now)) t->next.at(now) = new box();
    t->count.at(now) = t->count.at(now) + 1;
    f.pop_back();
    insert(t->next.at(now),f);
    return;
}
int check(box *t,vector<char>&f) {
    if(f.empty()) return 0;
    int now = f.back() - 'A';
    f.pop_back();
    return t->count.at(now) + check(t->next.at(now),f);
}
void insert(string a) {
    vector<char>f;
    for(auto &i : a) {
        f.push_back(i);
    }
    reverse(f.begin(),f.end());
    insert(&root,f);
    return;
}
int check(string a) {
    vector<char>f;
    for(auto &i : a) {
        f.push_back(i);
    }
    reverse(f.begin(),f.end());
    return check(&root,f);
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;cin>>n;
    vector<string>f(n);
    for(string &i : f) {
        cin>>i;
        insert(i);
    }
    for(string &i : f) {
        cout<<check(i) - i.size()<<"\n";
    }
    return 0;
}