2022.12 TOI 潛力組題解

嗯為什麼我覺得這次好難QAQ

BST

problem

給定一顆二元搜尋樹的後序走訪，請你復原這顆二元搜尋樹。

solution

因為左子樹的值會小於自己，而右子樹會大於自己，所以我可以採用「認領」的方式實作。

整理一下會發現對於每一個節點，其值必在所有右祖先節點與左祖先節點之間，我們令這兩個值分別為$max,min$$\text{, while}$ $min \leq max$ 。

由於不知道根結點很麻煩，所以將儲存後序走訪的陣列f[]倒轉，如此可以發現，在進入子樹之前，必會經過父節點。

令

• 目前即將處裡的點在f[]的座標為$p$
• 現在所在節點為$x$
• 目前最大值與最小值分別為$max$,$min$

遞迴:

• 如果$f_p > max$ or $f_p < min$則結束迴圈
• 當$f_x < f_p$ ，將$p$加一，往右子樹走訪。
• 如果$f_p > max$ or $f_p < min$則結束迴圈
• 當$f_x > f_p$，將$p$加一，往左子樹走訪。

最後整理輸出即可。

code

code

// Author : ysh
// 12/29/2022 Thu 20:15:34.16
#include<bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n;cin>>n;
    vector<int>f(n);
    for(int &i : f) {
        cin>>i;
    }
    vector<int>re(n,-1);
    reverse(f.begin(),f.end());
    bool r = 0;
    int p = 0;
    function<int(int,int,int,int)> check = [&] (int last,int x,int mmax,int mmin) {
        if(p + 1 == n) return 0;
        if(f.at(p + 1) < mmin || f.at(p + 1) > mmax) return 0;
        if(f.at(p + 1) > f.at(x)) {
            p++;
            re.at(p) = x;
            check(x,p,mmax,f.at(p - 1));
        }
        if(p + 1 == n) return 0;
        if(f.at(p + 1) < mmin || f.at(p + 1) > mmax) return 0;
        if(f.at(p + 1) < f.at(x)) {
            p++;
            re.at(p) = x;
            check(x,p,f.at(p - 1),mmin);
        }
        return 0;
    };
    check(0,0,INT_MAX,INT_MIN);
    vector<pair<int,int>>ans;
    for(int i = 0;i<n;i++) {
        if(re.at(i) == -1) ans.push_back({f.at(i),-1});
        else ans.push_back({f.at(i),f.at(re.at(i))});
    }
    sort(ans.begin(),ans.end());
    for(auto &i : ans) {
        cout<<i.first<<" "<<i.second<<"\n";
    }
    return 0;
}

tags: DFS

Ants

problem

一堆螞蟻走來走去，問你他們想講什麼。(對我不會摘錄，給我乖乖看題目)

solution

因為答案具有單調性，因此可以對答案使用二分搜尋法。

其中有趣的是當兩隻螞蟻相撞時，可以完全不管牠們。

自己推推看 :)

code

code

// Author : ysh
// 12/29/2022 Thu 21:00:55.24
#include<bits/stdc++.h>
using namespace std;
vector<pair<int,int>>f;
vector<int>mark;
int l;int m;
int check(int r) {
    mark.clear();
    int n = f.size();
    int ans = 0;
    for(auto &i : f) {
        if(i.second == 1) {
            if(i.first + r > l) ans++;
            else mark.push_back(i.first + r);
            continue;
        }
        if(i.first - r <= 0) ans++;
        else mark.push_back(i.first - r);
    }
    return ans >= m;
}
int ck(int l,int r) {
    if(l == r) return l;
    int mid = (l + r) >> 1;
    if(check(mid)) return ck(l,mid);
    else return ck(mid + 1,r);
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin>>l;
    string a;cin>>a;
    int n;cin>>n;
    cin>>m;
    for(int i = 0;i<n;i++) {
        int a,b;cin>>a>>b;
        f.push_back({a,b});
    }
    check(ck(0,l));
    sort(mark.begin(),mark.end());
    mark.resize(unique(mark.begin(),mark.end()) - mark.begin());
    for(int &i : mark) {
        cout<<a.at(i - 1);
    }
    return 0;
}

tags: binary_search

Numbers

本題維修中==

problem

有一個數列f[]，請寫出一程式以執行下列操作。

• 給定$a,b$，求出$\displaystyle \sum _{k = a}^b f_k$。
• 給定$a,b$，將f[]中$[a,b]$範圍內的數除以$10$(整數除法)。
• 給定$a,b$，將$f_a$更改為$b$。

solution

這題根本超毒(還是我線段樹中毒?)
因為直接做複雜度過高，所以使用客製化線段樹(?)+lazy tag模擬操作。

為了避免線段樹除法的進位問題，直接開一個struct，其中包含一個陣列，紀錄除以$10$ ($[1,19]$)次後的狀況，如此在合併兩個葉節點時只需要將陣列中的每一項相加就可以了。

也因此遇到lazy tag時可以直接取用該節點的陣列中的值。
但要注意不需要乘上$(r - l + 1)$，不然會出錯(別問我為甚麼知道)。

code

code

// Author : ysh
// 12/29/2022 Thu 21:25:07.10
#include<bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include<debug.h>
#else
#define debug(...) '*'
#define printf(...) '*'
#endif

#define int long long
struct box{
    int n;
    deque<int>f;
    box() {
        n = 0;
        f.resize(20);
    }
    box(int n) {
        this->n = n;
        int r = n;
        f.resize(20);
        f.at(0) = n;
        for(int i = 1;i<=19;i++) {
            f.at(i) = r = r / 10;
        }
        // debug(n,f);
    }
    box operator+(box a) {
        box tmp = *this;
        tmp.n = tmp.n + a.n;
        for(int i = 0;i<=19;i++) {
            tmp.f.at(i) = tmp.f.at(i) + a.f.at(i);
        }
        return tmp;
    }
    box operator+(int r) {
        if(r >= 20) {
            return box();
        }
        box tmp = *this;
        tmp.n = f.at(r);
        while(r--) {
            tmp.f.pop_front();
            tmp.f.push_back(0);
        }
        return tmp;
    }
    box operator+=(box a) {
        *this = a;
        return *this;
    }
    box operator+=(int r) {
        // box tmp;
        if(r >= 20) {
            f = deque<int>(20);
            n = 0;
            return *this;
        }
        n = f.at(r);
        while(r--) {
            f.pop_front();
            f.push_back(0);
        }
        return *this;
    }
};
// template<typename box>
struct seg_tree{
    int n;
    vector<box>f;
    vector<int>hold;

    seg_tree(int n) {
        this->n = n;
        f.resize(n << 2);
        hold.resize(n << 2);
    }

    seg_tree(vector<box>&v) {
        this->n = v.size();
        f.resize(n << 2);
        hold.resize(n << 2);
        mt(1,0,n - 1,v);
    }
    
    void push(int t,int l,int r) {
        //debug(f.at(t).n,hold.at(t));
        f.at(t) += hold.at(t);
        hold.at(t << 1) += hold.at(t);
        hold.at((t << 1) | 1) += hold.at(t);
        hold.at(t) = 0;
        //debug(f.at(t).n);
        return;
    }

    box exact(int t,int l,int r) {
        return f.at(t) + hold.at(t);
    }

    box re(int t,int l,int r) {
        return f.at(t) = (exact((t << 1),l,(l + r) >> 1) + exact((t << 1) | 1,((l + r) >> 1) + 1,r));
    }

    box mt(int t,int l,int r,vector<box>&v) {
        //debug(l,r,t);
        if(l == r) return f.at(t) = v.at(l);
        int mid = (l + r) >> 1;
        return f.at(t) = mt((t << 1),l,mid,v) + mt((t << 1) | 1,mid + 1,r,v);
    }

    void add(int nl,int nr,int v,int t = 1,int l = 0,int r = -1) {
        if(r == -1) r = n - 1;
        if(nr < l || nl > r) return;
        if(l == r) {
            f.at(t) += v;
            return;
        }
        push(t,l,r);
        int mid = (l + r) >> 1;
        if(nl <= l && nr >= r) {
            hold.at(t) += v;
            return;
        }
        add(nl,nr,v,t << 1,l,mid),add(nl,nr,v,(t << 1) | 1,mid + 1,r);
        re(t,l,r);
        return;
    }

    void fix(int nl,int nr,int v,int t = 1,int l = 0,int r = -1) {
        if(r == -1) r = n - 1;
        if(nr < l || nl > r) return;
        if(l == r) {
            f.at(t) = box(v);
            hold.at(t) = 0;
            return;
        }
        push(t,l,r);
        int mid = (l + r) >> 1;
        if(nl <= l && nr >= r) {
            hold.at(t) += v;
            return;
        }
        fix(nl,nr,v,t << 1,l,mid),fix(nl,nr,v,(t << 1) | 1,mid + 1,r);
        re(t,l,r);
        return;
    }

    box sum(int nl,int nr,int t = 1,int l = 0,int r = -1) {
        if(r == -1) r = n - 1;
        if(nr < l || nl > r) return box();
        if(l == r) return f.at(t) + hold.at(t);
        push(t,l,r);
        int mid = (l + r) >> 1;
        if(nl <= l && nr >= r) return exact(t,l,r);
        return sum(nl,nr,t << 1,l,mid) + sum(nl,nr,(t << 1) | 1,mid + 1,r);
    }

    void print() {
        for(int i = 0;i<n;i++) {
            cerr<<sum(i,i).n<<" ";
        }
        cerr<<"\n";
        return;
    }
};
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int a,b;cin>>a>>b;
    vector<box>f(a);
    for(box &i : f) {
        int tmp;cin>>tmp;
        i = box(tmp);
    }
    seg_tree t(f);
    // t.print();
    while(b--) {
        int a,b,c;cin>>a>>b>>c;
        if(a == 1) cout<<t.sum(b - 1,c - 1).n<<"\n";
        if(a == 3) t.fix(b - 1,b - 1,c);
        if(a == 2) t.add(b - 1,c - 1,1);
        // t.print();
    }
    // t.print();
    return 0;
}

---

brute code

附上暴力code

不知道為甚麼這效率似乎比較好(?)

// Author : ysh
// 12/31/2022 Sat 14:47:06.12
#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);
    for(int &i : f) {
        cin>>i;
    }
    for(int i = 0;i<b;i++) {
        int a,b,c;cin>>a>>b>>c;
        if(a == 1) {
            long long ans = 0;
            for(int i = b - 1;i < c;i++) {
                ans = ans + f.at(i);
            }
            cout<<ans<<"\n";
        }
        if(a == 3) {
            f.at(b - 1) = c;
        }
        if(a == 2) {
            for(int i = b - 1;i <= c - 1;i++) {
                f.at(i) = f.at(i) / 10;
            }
        }
    }
    return 0;
}

---

test case generater

# Author : ysh
# 12/31/2022 Sat 14:50:32.74
from random import randint as ri
for i in range(1,int(input()) + 1):
    f = open(str(i) + '.in','w')
    n = ri(0,500000);
    p = ri(1,500000);
    f.write(str(n) + ' ' + str(p) + '\n')
    for j in range(n):
        f.write(str(ri(0,100)) + ' ')
    f.write('\n')
    for j in range(p):
        t = ri(1,n)
        # f.write(str(ri(1,3)) + ' ' + str(t) + ' ' + str(ri(t,10)) + '\n')
        r = ri(1,3)
        if r == 1:
            f.write('1 ' + str(t) + ' ' + str(ri(t,n)) + '\n')
        if r == 2:
            f.write('2 ' + str(t) + ' ' + str(ri(t,n)) + '\n')
        if r == 3:
            f.write('3 ' + str(t) + ' ' + str(ri(1,10)) + '\n')
    f.close()

tags: seg_tree lazy-tag struct