oToToT的code收藏區

題目連結: https://codeforces.com/problemset/problem/1027/F 我好笨QAQ 本題關鍵大概是想到可以把每個考試當做邊來看吧OAO（看了解才知道 假設知道這件事後，那其實就很簡單，當然對於每個連通元件分開處理，明顯的如果邊數較點數多，那一定無法構造出一個合法的結果。 接著當邊數跟點數一樣多的時候，一定存在解，因為他必定可拆成幾個環跟一些連接的邊，那這時這裡的答案就是點的最大值。 還有邊數是點數減一的時候，不難發現他是顆樹，然後答案會是次大值。 邊數是點數減二的時候則不可能出現，所以討論這幾種狀況就可以得到答案了。 #include <bits/stdc++.h> using namespace std; using lld = int64_t; using PII = pair<int,int>; #define PB push_back #define FF first #define SS second #define ALL(x) begin(x), end(x) #define SZ(x) (static_cast<int>(std::size(x))) const int N = 2000000 + 5; class LiSan{ private: vector<lld> vv; public: template<typename... Args> void insert(lld x, Args& ...oth){insert(x);insert(oth...);} void insert(lld x){vv.PB(x);} void done(){ sort(ALL(vv)); vv.resize(distance(vv.begin(), unique(ALL(vv)))); } in...

題目連結: http://codeforces.com/problemset/problem/731/D 我覺得我的作法感覺不太對(?但還是講一下好了 我的做法是先把大小關係建成一張DAG，而這樣的話會發現題目變成說可不可以找到一種拓樸排序方法使得序列會是循環的字串，而又已經知道循環其實就只有可能中間斷開一個而已，所以我們不妨找到中間斷開的那個關係，並追本朔源到最前面的那個，從他開始拓樸排序，看會不會是好的。 #include <bits/stdc++.h> using namespace std; #define PB push_back #define FF first #define SS second const int N = 500000 + 5; const int C = 1000000 + 5; class DJS{ private: vector<int> arr; public: inline void init(int n){ arr.resize(n); for(int i=0;i<n;i++) arr[i]=i; } int query(int x){ if(arr[x]!=x) arr[x] = query(arr[x]); return arr[x]; } void merge(int a, int b){ int u = query(a), v = query(b); arr[max(u, v)]=min(u, v); } } djs; vector<int> G[C], cur; int in[C]; inline void kill(){cout<<"-1\n...

題目連結: http://codeforces.com/problemset/problem/711/D 小品(?的圖論題。首先有個小觀察，這種給法的圖，在每一個連通塊(?中，只會有一個環，不過還是可能會有很多連通塊就是了。所以先考慮一個連通塊的情況，發現若他的環有$k$個邊，且整個連通塊有$n$個邊的話，他的方法數就會是$(2^k-2)\cdot(2^{n-k})$，想法大致就是，環上每個邊都可以選擇要換或不換扣掉全換跟全部換，再乘以其他大家的可能性就好了。至於多個連通塊的情況就直接把他們乘在一起就好了，畢竟他們是獨立的。 #include <bits/stdc++.h> using namespace std; typedef long long lld; #define PB push_back #define FF first #define SS second const int N = 200000 + 5; const lld MOD_BASE = 1e9 + 7; class DJS{ private: vector<int> arr, sz; public: void init(int n){ arr.resize(n); sz.resize(n); for(int i=0;i<n;i++){ arr[i]=i; sz[i]=1; } } int size(int x){return sz[query(x)];} int query(int x){ if(arr[x]!=x) arr[x] = query(arr[x]); return arr[x]; } void merge(i...

題目連結: http://codeforces.com/problemset/problem/698/B 一開始完全沒想法，被提示(?說就算非法也還是一張圖後才比較有想法。這題我的作法很greedy，就先判斷一下有沒有原本就有可以當根的點，有的話就把他當根，接下來再掃一遍，看看有沒有人會構成環，有的話就直接把他接到根上面，此外，若沒有現成的根的話就直接把他變成根。而要找誰跟誰一樣就用個並查集就好了XD #include <bits/stdc++.h> using namespace std; #define PB push_back #define FF first #define SS second const int N = 200000 + 5; class DJS{ private: vector<int> arr; public: void init(int n){ arr.resize(n); for(int i=0;i<n;i++) arr[i]=i; } int query(int x){ if(arr[x]!=x) arr[x] = query(arr[x]); return arr[x]; } void merge(int a, int b){ arr[query(a)]=arr[query(b)]; } } djs; int arr[N]; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n, ans = 0, root = -1; cin>>n; for(int i=1;i<=n;i++){ cin...

題目連結: http://tioj.infor.org/problems/1448 / http://poj.org/problem?id=1182 經典的並查集應用，想法大概就跟並查集的大多數用途一樣，考慮把每個動物X分三種類型$X_A, X_B, X_C$，代表若X為A的情況或X為B的情況...，那要兩種動物$X, Y$為同一種的話合併的話，顯然就是合併$X_A \equiv Y_A, X_B \equiv Y_B, X_C \equiv Y_C$，吃的話則是$X_A \equiv Y_B, X_B \equiv Y_C, X_C \equiv Y_A$，這樣的話要判斷是否為假話的話就變容易了，仔細想想會發現不可能有一種動物$X$，他在某次操作後$X_A \equiv X_B \lor X_B \equiv X_C \lor X_C \equiv X_A$，所以只要操作前看看沒有要合併的人他的集合是不是原本就一樣就好。 p.s POJ上範圍不太一樣，這裡是TIOJ的範圍(而且動態配置貌似POJ會TLE) #include <bits/stdc++.h> using namespace std; #define FAKE ans++;continue; const int N = 500000; class DJS{ private: int *arr; public: void init(int T){ arr=new int[T]; for(int i=0;i<T;i++) arr[i]=i; } void merge(int a, int b){ arr[query(a)]=query(b); } int query(int x){ if(arr[x]!=x) arr[x]=query(arr[x]); retur...