SubaRyaのcode and 廢日常

題目來源: https://neoj.sprout.tw/problem/80/ 這題只是單純的RMQ問題，只要好好地維護遞迴的性質並且只要單點修改(不須推下去)，因此就變成了普通的模板題。 #pragma gcc optimize("o2") #include<bits/stdc++.h> #define int long long int #define IOS ios_base::sync_with_stdio(false) #define TO cin.tie(NULL) #define MAXN 1000000 using namespace std; struct Node{ int l,r; int lson,rson; int data; }; Node segtr[MAXN * 2 ]; int str[MAXN]; int ptr = 0 ; void build( int l, int r, int index) { segtr[index].l = l; segtr[index].r = r; int mid = (l + r) / 2 ; if (l == r - 1 ) segtr[index].data = str[l]; else { int lson = segtr[index].lson =++ ptr; int rson = segtr[index].rson =++ ptr; build(l,mid,lson); build(mid,r,rson); segtr[index].data = min(segtr[lson].data,segtr[rson].data); } } void modify( int x, int val, int index) { if (segtr[index].l == segtr[index].r - 1 ) segtr[index].data =

https://zerojudge.tw/ShowProblem?problemid=b229 發現了這個關係式 len[i]=2*len[i-1]+len[i-2] 就變水題 #pragma gcc optimize(o2) #include<bits/stdc++.h> #define int unsigned long long int #define IOS ios_base::sync_with_stdio(false) #define TO cin.tie(NULL) using namespace std; int len[ 55 ] = { 0 , 3 , 7 }; signed main() { for ( int i = 3 ;i <= 50 ;i ++ ) len[i] = 2 * len[i - 1 ] + len[i - 2 ]; int N; cin >> N; cout << len[N] << '\n' ; return 0 ; }

我的想法很直觀，就是用array儲存入和出的人(記得出的時間點也算，所以要加1)，然後掃過去紀錄時間軸的max值。 PS:我最後發現我這樣寫不管是時間上還是空間上都很爛，所以我去看了幾位大神的寫法才發現這題可以用離散化或是用map揍掉 m(_ _)m #pragma gcc optimize(o2) #include<bits/stdc++.h> #define int long long int #define IOS ios_base::sync_with_stdio(false) #define TO cin.tie(NULL) using namespace std; int str[ 100005 ]; signed main() { IOS;TO; int range = 0 ,a,b,n,maxu,ans; while (cin >> n) { ans = 0 ;maxu = 0 ; while (n -- ) { cin >> a >> b; str[a] ++ ; b += 1 ; str[b] -- ; range = max(range,b); } for ( int i = 0 ;i <= range;i ++ ) { maxu += str[i]; ans = max(maxu,ans); } cout << ans << endl; } return 0 ; }

雖然有一點煩(連續輸入我看漏了)，但只是裸裸的dsu題(模板+1/0) 據說我是題目連結(?  https://tioj.ck.tp.edu.tw/problems/1312 #pragma gcc optimize("o2") #include<bits/stdc++.h> #define int long long int #define IOS ios_base::sync_with_stdio(false) #define TO cin.tie(NULL) using namespace std; struct disjointset { int mem[ 10005 ],rank[ 10005 ]; void init( int num) { for ( int i = 0 ;i <= num;i ++ ) { mem[i] = i; rank[i] = 0 ; } } int find( int N) { if (mem[N] == N) return N; return mem[N] = find(mem[N]); } int same( int a, int b) { return find(a) == find(b); } void Union( int l, int r) { i f ( ! same(l,r)) { if (find(l) < find(r)) swap(l,r); mem[find(l)] = find(r); rank[find(l)] += find(r); } } }; signed main() { IOS;TO; int n,m,a,b,k; struct