SubaRyaのcode and 廢日常

題目連結: https://tioj.ck.tp.edu.tw/problems/1152 "樹直徑"定義:一顆樹上任兩點距離最大 這是一題裸裸的樹直徑題，不難發現dfs一次找到最遠點，再用那個點當作第二次dfs的根，再找一次最遠點，不外乎就是樹直徑(很greedy的想法(?)。 PS:我的code超爛，ranklist超後面QAQ #pragma GCC optimize("O2") #include<bits/stdc++.h> #define jizz ios_base::sync_with_stdio(false),cin.tie(NULL) #define int long long int #define pb push_back #define po pop_back #define F first #define S second #define CN cout<<"\n" #define MAXN 1000005 #define lson int lson=index*2 #define rson int rson=index*2+1 #define mid int mid=(l+r)/2 using namespace std; vector < int > v[ 10005 ]; int vis[ 10005 ],ans_p = 0 ,ans_s = 0 ,root; void init( int n) { fill(vis,vis + n, 0 ); } void dfs( int now, int sum) { for ( auto x : v[now]) { if (vis[x] == 0 ) { vis[x] = 1 ; dfs(x,sum + 1 ); } } if (sum > ans_s) { ans_p = now; ans_s = sum; ...

我的想法很直觀，就是用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...