oToToT的code收藏區

題目連結: http://tioj.infor.org/problems/1401 我好廢QQ被雷了才會。 很簡單的可以觀察到垂直跟水平可以分開，那這樣的話問題被轉化成給你一堆線段，你要為每條線段選一個點，使得這些點不能重複。做法很greedy直接從左掃到右邊，然後如果有可以放的就放，然後如果遇到一條線段就把他右界放進去之類的。 #include <bits/stdc++.h> using namespace std; #define PB push_back const int N = 100000 + 5; vector<int> hen[N], zhi[N]; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n; while(cin>>n){ for(int i=1;i<=n;i++){ hen[i].clear(); zhi[i].clear(); } bool flag = true; for(int i=0;i<n;i++){ int l, r, u, d; cin>>l>>r>>u>>d; hen[l].PB(r); zhi[u].PB(d); } priority_queue<int,vector<int>,greater<int>> pq; for(int i=1;i<=n;i++){ for(auto j: hen[i]) pq.push(j); if(!pq.empty()){ if(pq.top() <...

題目連結: http://tioj.infor.org/problems/1161 考慮把力量跟敏捷當成兩維把所有技能繪製在平面上，接著用掃描線的概念，從左掃到右，那這時其實就是要對當前的點集尋找第k小，然後跟自己的值加上去。也可以想像成枚舉其中一維的最大值來做計算。而維護點集第k小，其實開個heap維護他的size是k就好了。(我原本寫平衡樹但一直MLE) #include <bits/stdc++.h> using namespace std; typedef pair<int, int> PII; #define FF first #define SS second const int INF = 2e9; const int N = 1000000 + 5; int n, k; PII arr[N]; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int t;cin>>t; while(t--){ cin>>n>>k; for(int i=0;i<n;i++) cin>>arr[i].FF>>arr[i].SS; sort(arr,arr+n); int ans=INF; priority_queue<int> pq; for(int i=0;i<n;i++){ pq.push(arr[i].SS); while((int)pq.size() > k)pq.pop(); if((int)pq.size() == k) ans=min(ans, arr[i].FF+pq.top()); } cout<<an...

題目連結: http://tioj.infor.org/problems/1224 一個非常經典的掃描線應用，利用掃描線把原本二維的問題降成一維的，再搭配線段樹，就可以做到$O(n log n)$的複雜度，不過本題的線段樹要存的東東有點特別，我想了一段時間才寫出比較精簡的版本，不然我原本是寫讓他存區間和，可是這樣就會再詢問有幾個非空節點上有困難，所以不妨再存一個值紀錄當前非空節點有幾個，而顯然當你懶標記值大於0時整段都被覆蓋，所以就是整段的長度，而沒有整段被覆蓋的時候，那當然就是去看小孩的值囉，不過仔細想想就會發現區間和根本沒用，所以就砍掉他吧XDD #include <bits/stdc++.h> using namespace std; #define ALL(x) (x).begin(), (x).end() #define PB push_back typedef long long lld; typedef pair<int, int> PII; #define FF first #define SS second const int N = 1000000 + 5; struct bian{ PII pos; int cnt; bool operator<(const bian& a)const{ return pos<a.pos; } }; vector<pair<int,bian>> E; class SegTree{ private: struct Node{ int len=0; int cnt=0; } arr[4*N]; void pull(int id, int l, int r){ if(arr[id].cnt) arr[id].len = r - l; ...