例題 P-3-6. 砍樹 (APCS202001)、例題 P-3-7. 正整數序列之最接近的區間和、例題 P-3-8. 固定長度區間的最大區段差、例題 P-3-9. 最多色彩帶
腦汁耗盡了，寫不出感想了，主要底下程式蠻簡單的:)
#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; }
#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; }
#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; }
#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; }
