2025/05/22刷題心得整理

最後編輯時間: 2025/05/23

▌TF::OJ刷的題目

例題 P-3-6. 砍樹 (APCS202001)、例題 P-3-7. 正整數序列之最接近的區間和、例題 P-3-8. 固定長度區間的最大區段差、例題 P-3-9. 最多色彩帶

▌覺得有趣或值得紀錄的題目以及心得感想

腦汁耗盡了，寫不出感想了，主要底下程式蠻簡單的:)

▌程式

例題 P-3-6. 砍樹 (APCS202001)

				
					#include <bits/stdc++.h>
using namespace std;
queue<int> q;
#define oo 1000000001
struct{
    int c,h;
    int ne,ba;
    bool y = false;
} t[100050];
void r(int i){
    if(t[i].y) return;
    int s=t[i].ne,w = t[i].ba;
    if(t[i].c+t[i].h<=t[s].c||t[i].c-t[i].h>=t[w].c){
        t[i].y=true;
        q.push(i);
        t[s].ba= w;
        t[w].ne = s;
    }
    return;
}
int main(){
    int n,k,ma=0,s=0;cin >> n >>k;
    for(int i=1;i<=n;i++) {
            cin >> t[i].c;
            t[i].ne=i+1;t[i].ba=i-1;
    }
    for(int i=1;i<=n;i++) cin >> t[i].h;
    t[0].c=0;t[n+1].c=k;t[0].y=false;
    t[0].h=oo;t[n+1].h=oo;t[n+1].y=false;
    for(int i=1;i<=n;i++) r(i);
    while(!q.empty()){
        int v = q.front();
        q.pop();
        s++;
        ma = max({ma,t[v].h});
        r(t[v].ne);r(t[v].ba);
    }
    cout << s << "\n" << ma << endl;

}

例題 P-3-7. 正整數序列之最接近的區間和

				
					#include <bits/stdc++.h>
using namespace std;
int main(){
    int n,k,left=0,s=0,ma=0,e=0;cin >> n >>k;
    unordered_map<int,int> a;
    vector<int> b(n);
    for(int i=0;i<n;i++) {
        cin >> b[i];s+= b[i];
        while(s>k){
            s-=b[left];
            left++;
        }
        if(ma!=max(ma,s)) e=1;
        if(ma==s) e++;
        ma=max(ma,s);
    }
    cout << ma << "\n" << e <<endl;
}

例題 P-3-8. 固定長度區間的最大區段差

				
					#include <bits/stdc++.h>
using namespace std;
int main(){
    int n,l,m=0;cin >> n >> l;
    vector<int> a(n);
    deque<int> mx,mn;
    for(int i=0;i<n;i++) cin >> a[i];
    for(int i=0;i<n;i++){
        if(mx.front()<=i-l) mx.pop_front();
        if(mn.front()<=i-l) mn.pop_front();
        while(!mx.empty()&&a[mx.back()]<=a[i]) mx.pop_back();
        while(!mn.empty()&&a[mn.back()]>=a[i]) mn.pop_back();
        mx.push_back(i);mn.push_back(i);
        m = max(m,a[mx.front()]-a[mn.front()]);
    }
    cout << m <<endl;
    return 0;
}

例題 P-3-9. 最多色彩帶

				
					#include <bits/stdc++.h>
using namespace std;
int main(){
    int n,l,m=0;cin >> n >>l;
    unordered_map<int,int> a;
    vector<int> e(n);
    for(int i=0;i<n;i++){
        cin >> e[i];
        if(i>=l){
            a[e[i-l]]--;
            if(a[e[i-l]]==0) a.erase(e[i-l]);
        }
        a[e[i]]++;
        m = max(m,(int)a.size());
    }
    cout << m << endl;
}