oToToT的code收藏區

前言： __gnu_pbds全名為GNU Policy-Based Data Structures，競賽中俗稱黑魔法，因為其內建了許多強大的工具，例如：可合併堆、伸展樹、紅黑樹、字典樹、hash table...，不過因為他放在一個很奇怪的標頭檔底下，且不是所有編譯器都支援(從名稱就知道那是GNU的東西)，所以也沒那麼多人會使用他。 1. 使用方法 要使用其的資料結構時，請先引入ext/pb_ds/assoc_container.hpp，若要使用priority_queue時則還要多引入ext/pb_ds/priority_queue.hpp，而那些東東都包在__gnu_pbds這個namespace底下，所以如果懶的話，可以全部把他倒出來。 p.s不過如果std的也倒出來priority_queue會衝突到，此時建議還是要加個__gnu_pbds::在前面 #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/priority_queue.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; 2. priority_queue 可合併堆是我第一個知道的功能，那我們先看看他的type模板到底寫了甚麼吧 template< typename Value_Type, typename Cmp_Fn = std::less<Value_Type>, typename Tag = pairing_heap_tag, typename Allocator = std::allocator<char> > class priority_queue; 這裡最常會動到的大概就是Value_Type跟Cmp_Fn了吧 Value_type 顯然是你的資料型別 Cmp_Fn 則是一個物件，其必須包含一個bool operator()，他會用來比較你的兩個資料，以知道誰該在你呼叫top時出現 比較神奇的一個東東是Tag，預設為paring_heap_tag，也就是說他預設配...

題目連結: http://tioj.infor.org/problems/1253 本題可以轉化為二分圖最小點覆蓋，因為不妨考慮把每隻皮皮當作邊，連接著一個列跟欄(如下圖) 而我們要求的不就是找到最少的列或欄使得每隻皮皮都被炸掉，剛好就是找到最少的點覆蓋所有的邊，而且這樣轉還有一個好處就是他保證會是二分圖，所以我們要做的事就是找到最小點覆蓋。不過二分圖最小點覆蓋又該如何找呢？可以證明，其實二分圖最小點覆蓋的數量就等於二分圖最大匹配的數量，因此問題又被轉化成了二分圖最大匹配，二分圖最大匹配有很多種作法，一種是新增一個起點連接所有左半圖，並新增一個終點連接所有右半圖，把問題又轉成最大流的流量，所以可以用dinic或ford fulkerson之類的演算法寫掉。不過因為是二分圖，所以其實有好的找匹配數的方法，就對於某一個點如果其還未被匹配，則看他可不可以跟其他點匹配，如果與他相鄰的某個點已經被匹配過了，那就請他試試看可不可以換點，如此遞迴下去即可求得最大匹配數。 p.s 詳細證明可以看 演算法筆記 #include <bits/stdc++.h> using namespace std; #define N 1000 int cnt=1; int ans=0; bitset<N+5> visited; vector<int> X[N+5], Y[N+5]; int matchX[N+5], matchY[N+5]; inline void init(int); bool DFS(int); int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n,k; cin>>n>>k; while(n!=0||k!=0){ init(n); for(int i=0;i<k;i++){ int s,e; cin>>s>>e; ...

題目連結: http://tioj.infor.org/problems/1538 一個小小的數學題(?，做法很greedy，每次的分母都會是$\lfloor \frac{分母}{分子} \rfloor + 1$，直到自己的分子變成一為止，不過很梗的是本題要寫大數，不然會WA...，所以我就摳了 日月卦長的大數模板 #include <bits/stdc++.h> using namespace std; #ifndef SUN_MOON_BIG_INT #define SUN_MOON_BIG_INT #define SM_BASE 1000000000 #define SM_BASE_DIGITS 9 /*SM_BASE 0 的個數為SM_BASE_DIGITS*/ #include<vector> #include<iostream> #include<iomanip> #include<string> #include<utility>/*for pair*/ class bigN{ private: std::vector<int>s; char sign; inline void trim(){ while(!s.empty()&&!s.back())s.pop_back(); if(s.empty())sign=1; } inline char cmp(const bigN &v,bool is=1)const{ if(is){ if(sign>v.sign)return 1; if(sign<v.sign)return -1; } char d=sign>0||!is?1:-1; ...

題目連結: http://tioj.infor.org/problems/1332 可以發現對於每個點的爸爸必定是在他出現前出現過的，且必定是比他大的最小值或比他小的最大值中較後面插入的數，不過詳細的證明我不太會證...如果有大大願意教我一下我洗耳恭聽。 因此就用個map存每個數，因為要快速找到比他大的最小值跟比他小的最大值，所以不妨把值當作key，插入順序當作value，就得到了一個$O(N log N)$的做法了。 不過本題其實還有更快的做法，複雜度可變成$O(N)$，那就是對於這個數列用奇怪的方式(?建出一顆笛卡爾樹，再轉回原數列即可知道答案，雖然你還是會構造出整棵樹，但因為笛卡爾樹有線性的建法，所以複雜度還是$O(N)$ 詳細可參考: 這篇 (我覺得比較好理解在幹嘛) 跟 這篇 有講怎麼線性構造出笛卡爾樹 #include <bits/stdc++.h> using namespace std; #define N 1000000 int ans[N+5]; map<int,int> mp; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n;cin>>n; for(int i=1;i<=n;++i){ int x;cin>>x; int l=-1,r=-1,ll,rr; auto it = mp.insert({x,i}).first; ++it; if(it!=mp.end()){ l=it->second; ll=it->first; } --it; if(it!=mp.begin()){ --it; r=it->second; rr=it->fir...

題目連結: http://tioj.infor.org/problems/1210 其實一開始我在寫這題的時候真的想不出來怎麼做，是看了 黃信元學長的文 才知道的。 本題有兩個定理可以拿來應用，我一開始都只有找到Havel定理的用法，雖然他的複雜度是$O(n^2 log n)$，不過本題還是可以過，所以就稍微講一下他的做法吧，每次都把degree最大的拿出來(假定其degree為k)，則把他跟後k大的所有點連邊，也就是把他後k個的值都減一，並把自己改成零，重複這件事直到出現負數(表示不合法)，或全部都變成0(合法)為止，所以做完後也構造完整張圖了，不過複雜度真的不夠好。 另外一個定理是Erdős–Gallai 定理，我覺得沒那麼直覺，他是要驗證從大到小排序後的$d_k$ $$\forall k,1 \leq k \leq n, \mathop{\sum_{i=1}^{k}} d_i \leq ( k(k-1) + \mathop{\sum_{j=k+1}^{n}} min(k, d_j) )$$ 不過照著定理裸裸的定義做可能會變成$O(n^2)$，不過仔細想想後會發現因為k有單調性，且$d_j$也有單調性，所以當超過一定範圍後，$d_j$就必定小於k，其餘都會是k，而且那個範圍一定會越來越前面，所以可以先處理後綴和後在每次算前先找到那個範圍，之後直接取後綴和就好了，不過仔細想想連後綴和都不需要預處理，在找範圍時就可以好好算了，但因為區間閉開開閉之類的一直讓我有點卡卡的，所以我就沒寫那種常數優化了，反正複雜度都還是$O(n)$ Havel定理版本 #include <iostream> #include <algorithm> using std::cin; using std::cout; using std::sort; int vv[10005]; int main(){ cin.tie(0);std::ios_base::sync_with_stdio(0); int n; cin>>n; while(n!=0){ int k=0; fo...

題目連結: http://codeforces.com/problemset/problem/609/E 本題跟次小生成樹的做法大同小異，畢竟要做 次小生成樹 就要求MST for each edge，所以就按照次小生成樹的做法稍微改一改吧。 #include <bits/stdc++.h> using namespace std; typedef long long lld; typedef pair<int,lld> pil; #define N 200000 #define logN 20 struct Edge{ int s,e,id; lld w; Edge(){} Edge(int a,int b,lld c,int d){s=a;e=b;w=c;id=d;} bool operator<(const Edge& a){return w<a.w;} }; int djs[N+1]; vector<Edge> Es; int Query(int x){if(djs[x]!=x)djs[x]=Query(djs[x]);return djs[x];}; inline void Merge(int a,int b){djs[Query(a)]=Query(b);} vector<pil> MST[N+5]; pil ff[N+1][logN+1]; int time_in[N+5],time_out[N+5],timer=0; void dfs(int,int,lld); inline int lca(int,int); inline bool anc(int,int); inline lld walk(int,int); lld ans[N+5]; int main(){ cin.tie(0);ios_base::sync_with_stdio(0); int n,m; ...

題目連結: http://tioj.infor.org/problems/1445 不難發現本題就是是一題裸次小生成樹題，那次小生成樹該怎麼寫呢？先求一棵最小生成樹後，枚舉所有不在最小生成樹上的邊，把它塞到最小生成樹上，此時必定會產生一個環，而把在環上且在最小生成樹上的最大邊拔掉後就得到了另一個生成樹，不難證明枚舉完這些樹後得到的答案就會是次小生成樹。不過要怎麼有效率的求一個路徑上的最大值呢？不難想到可以樹練剖分，不過礙於記憶體限制，我不太確定會不會MLE。不過想想後如果你是用倍增法求LCA的話，在跑上去的過程中似乎就可以順便算最大值，所以就先求LCA後，再對兩個點倍增到LCA，並同時算最大值就可以解決這問題了。複雜度：$O(E log E)$ #include <bits/stdc++.h> using namespace std; #define endl '\n' #define PB push_back typedef long long lld; typedef pair<lld,lld> pll; #define N 1000 #define logN 15 #define INF 2147483647777 struct Edge{ int s,e; lld v; }; int djs[N+5]; inline int Query(int); inline void Merge(int,int); vector<Edge> Tree; vector<pll> MST[N+5]; pll ff[N+5][logN+5]; int timer=0,time_in[N+5],time_out[N+5]; void dfs(lld,lld,lld); inline bool anc(int,int); inline int lca(int,int); inline lld walk(int,int); int main(){ cin.tie(0);io...

題目連結: 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; ...

題目連結: http://tioj.infor.org/problems/1882 本題是要求一堆二次函數取min疊加起來後的最大值，因為二次函數疊加起來後其實斜率還是有單調性，因此可以三分搜出答案，不過我不太喜歡寫三分搜，因此就寫了個模擬退火(當初是培訓時有人提了這鬼東東ww)，研究了一下發現滿有趣的，簡單來說就是隨邊挑個起點，走走看如果比較好就走，如果比較差就用$e^{\Delta y \times t}$ 來判斷是否要走下去(這裡的t指的是步數，原本是用溫度)，不過因為本題的斜率有單調性，所以不需要往下(這好像又叫爬山法)。此外我裡面還用了C++的random，發現可調的參數真的變多了，但相對的用起來也沒那麼無腦了XD #include <bits/stdc++.h> using namespace std; #define endl '\n' struct wow{ double a,b,c; }; vector<wow> func; inline double getY(double x); int main(){ cin.tie(NULL);ios_base::sync_with_stdio(); default_random_engine rGen; uniform_real_distribution<double> rForm(-1,1); auto random = bind(rForm,rGen); int n; cin>>n; func.resize(n); for(int i=0;i<n;i++) cin>>func[i].a>>func[i].b>>func[i].c; uniform_real_distribution<double> inipos(0,90); double x=inipos(rGen); double y=getY(x); doubl...

題目連結: http://contest.cc.ntu.edu.tw/npsc2011/finalSen_release.zip 不難發現在贏多少匹馬上有單調性，所以可以二分搜答案，驗證的方法用個greedy的方法，就盡量挑能贏他的馬跟他打，也就是最強的跟最強的比，如果打不贏就改成拿最廢的跟他換，大概這樣吧 #include <bits/stdc++.h> using namespace std; typedef long long lld; #define N 10000 struct hr{ lld a,b; }; lld oppo[N+5]; hr my[N+5]; lld n,k; vector<lld> cur; inline bool isOK(lld); inline int fJiao(); int main(){ int t; scanf("%d",&t); while(t--){ lld l=-1,r=100000000; scanf("%lld%lld",&n,&k); for(int i=0;i<n;i++)scanf("%lld%lld",&my[i].b, &my[i].a); for(int i=0;i<n;i++)scanf("%d",&oppo[i]); sort(oppo, oppo+n,[](lld a,lld b){return a>b;}); bool jj = isOK(r); if(!jj){ puts("-1"); }else{ while(r-l!=1){ ll...

題目連結: http://tioj.infor.org/problems/1235 比較trivial的數獨，轉成正常數獨後，就暴搜吧XD #include <bits/stdc++.h> using namespace std; struct pos{ int x,y; pos(){} pos(int a,int b){x=a;y=b;} }; int sudoku[9][9]; bitset<9> ori[9]; vector<pos> need; bool solve(int); inline bool check(int,int); inline int toid(char); inline char toch(char); int main(){ char ss[15]; for(int i=0;i<9;i++){ gets(ss); for(int j=0;j<9;j++){ if(ss[j]=='*'){ sudoku[i][j]=0; need.push_back(pos(i,j)); ori[i][j]=1; }else{ sudoku[i][j] = toid(ss[j]); ori[i][j]=0; } } } solve(0); return 0; } inline int toid(char a){ switch(a){ case 'R':return 1; case 'O':return 2;...

題目連結: http://tioj.infor.org/problems/1429 本題其實有很多種寫法，例如：樹剖、整體二分搜、堆(啟發式合併或可合併)，我這裡的做法是用可合併堆的做法，也是裡面最快的一種(?，可以發現對於某個節點，如果已知他所有小孩的選法，那就把那些節點全部混在一起，然後如果超過預算就把最大的移掉，而因為要找最大的，我們需要用到heap，不過我們還需要快速合併多個堆，所以可以採用可合併堆，或是直接啟發式合併就好。 我在這裡採用的可合併堆是配對堆，雖然大家都寫左偏樹，不過我覺得配對堆比較好寫XDD，一種似乎均攤複雜度接近費波那契堆的東東，詳細證明可以看他的 論文 ，不過我也不是很熟，簡單說一下他的做法:合併跟插入都是直接跟根比大小後決定誰當根，所以有可能一個根下面有一堆小孩，為了解決會因此爛掉的狀況，於使我們在pop的時候讓他的小孩們緊縮一點(?，就是pop時就把他的小孩兩兩合併，直到剩一個為止。似乎跟splay tree有點類似，大概這樣吧 註:這裡採用的合併方式因為有點懶人，根據論文他只能證出$O(\frac{log n log log n}{ log log log n})$的上界，不過$ \frac{ \frac{log n log log n}{ log log log n} }{log n}$在$n #include <bits/stdc++.h> using namespace std; #define PB push_back typedef long long lld; #define N 100000 struct pairingNode{ int val; vector<pairingNode*> child; }; class pairingHeap{ private: pairingNode* root; int count; public: lld sum=0; pairingHeap(){root=NULL;count=0;} ...

題目連結: http://tioj.infor.org/problems/1143 本題顯然是個BFS題，然後記得如果一個點在queue裡面了，那其他比他晚進入的同一個點必定$times \geq 原本的$，所以不妨直接把他設成不能走，免得重複走同一個點。 p.s 這是我第一次寫這種C++的struct跟class，有點醜，抱歉。 #include <bits/stdc++.h> using namespace std; #define N 100 bitset<N+5> block[N+5]; struct pos{ int x,y,times; pos(){}; pos(int t){times=t;} pos(int a, int b){ x=a; y=b; } bool operator==(const pos& a){ return a.x==x&&a.y==y; } pos top(){return pos(x,y-1);} pos down(){return pos(x,y+1);} pos left(){return pos(x-1,y);} pos right(){return pos(x+1,y);} }; inline bool isBlock(const pos &a){ if(a.x<=N-1&&a.x>=0&&a.y<=N-1&&a.y>=0) return block[a.x][a.y]; return 1; } class Q { public: Q(){}; Q(const pos &a){push(a);}...

題目連結: http://tioj.infor.org/problems/1562 本題跟 骨牌遊戲 有8成7像，只差在你一定要在最後一格也要有警報器響而已，所以就直接把警報器次數-1，然後就變一模一樣的骨牌遊戲了www #include <stdio.h> typedef long long lld; int n,m; lld arr[1000 + 10]; inline bool test(lld); int main(){ while(scanf("%d %d",&n,&m)!=EOF){ m--; lld l=0,r=0; for(int i=0;i<n;i++){ scanf("%lld",&arr[i]); r+=(lld)arr[i]; l=(l>arr[i])?l:arr[i]; } l-=1; while(r-l != 1){ if(test((r+l)/2)) r=(r+l)/2; else l=(r+l)/2; } printf("%lld\n",r); } } inline bool test(lld maxS){ int k=0; lld plus=0; for(int i=0;i<n;i++){ if(plus + arr[i] > maxS){ plus=arr[i]; k++; if(k>m) return 0;...

題目連結: http://tioj.infor.org/problems/1367 經典的排序不等式題目，greedy做就好了，把a數列最小的跟b數列最大的乘+a數列次小乘以b數列次大的...就會得到最小值，詳細證明可以查一下，因為不難找的到，這邊就不放了。 #include <bits/stdc++.h> using namespace std; #define N 50000 int arr1[N+5],arr2[N+5]; int main(){ int n; while(scanf("%d",&n)!=EOF){ for(int i=0;i<n;i++)scanf("%d",&arr1[i]); for(int i=0;i<n;i++)scanf("%d",&arr2[i]); sort(arr1,arr1+n,[](int a,int b){return a<b;}); sort(arr2,arr2+n,[](int a,int b){return a>b;}); unsigned long long ans=0; for(int i=0;i<n;i++) ans+=(unsigned long long)arr1[i]*(unsigned long long)arr2[i]; printf("%llu\n",ans); } return 0; }

題目連結: http://tioj.infor.org/problems/1230 本題就照著DFS就好了XD 更新:突然發現我這寫法是假解，還在思索真解怎麼寫。 #include <bits/stdc++.h> using namespace std; typedef long long lld; #define N 3000 int graph[N][N]; struct List{ int x; int y; List* next; List(){ next=NULL; } ~List(){ if(next!=NULL)delete next; } }; bitset<N> walked[N]; lld DFS(int,int,List*); void cList(List*); int n,m; int main(){ scanf("%d%d\n",&n,&m); for(int i=0;i<n;i++){ char inp[N+5]; gets(inp); int inpSZ = strlen(inp); int ctt=0; for(int j=0;j<inpSZ;j++){ if(inp[j]==' ')continue; if(inp[j]=='x'){ walked[i][ctt]=1; graph[i][ctt++]=-100; }else{ graph[i][ctt++]=inp[j]-'0'; }...

題目連結: http://tioj.infor.org/problems/1290 不難發現在走最短路徑的時候不可能會同一邊走兩次(或以上)，所以本題其實直接寫個dijkstra就好了XD #include <stdio.h> #include <vector> #include <queue> #include <bitset> typedef unsigned long long llu; using namespace std; struct node{ int to; llu val; }; struct dian{ int me; llu val; }; class cmp{ public: bool operator ()(dian a, dian b){ return a.val > b.val; } }; vector<node> graph[1000 + 10]; bitset<1000 + 10> poped; llu dis [1000 + 10]; int main(){ int V, E; while(scanf("%d %d",&V,&E)!=EOF){ priority_queue<dian,vector<dian>,cmp> pq; poped.reset(); for(int i=0;i<1010;i++){ graph[i].clear(); dis[i] = 2147483648; } int start, end; s...

題目連結: http://tioj.infor.org/problems/1717 本題要求對於每個專案的最大值，所以想想就直接DFS就好，而且顯然不能同一個點走太多次，所以要DP，而因為我覺得存原本的圖不好判斷誰是起點，所以不妨存個反過來的圖，甚至開一個假點當作起點，反正答案都會對。大概就這樣吧 #include <bits/stdc++.h> using namespace std; #define N 1000 int Time[N+5]; int val[N+5]; bitset<N+5>walked; vector<int> graph[N+5]; inline void init(int); int DFS(int); int main(){ int t; scanf("%d",&t); while(t--){ int n; scanf("%d",&n); init(n); for(int i=1;i<=n;i++){ int v,sz; scanf("%d%d",&v,&sz); Time[i]=v; if(sz==0) graph[0].push_back(i); for(int j=0;j<sz;j++){ int w; scanf("%d",&w); graph[w].push_back(i); } } int ans=DFS(0); printf("%d\n"...

題目連結: http://tioj.infor.org/problems/1035 本題看起來直接naive的比對就好了，而且其實我也不會好好的模糊比對演算法，不過照著做就AC了XD #include <bits/stdc++.h> using namespace std; #define N 50000 char str1[N+5]; int str1Size; char str2[N+5]; int str2Size; int main(){ int ans=0; gets(str1); str1Size=strlen(str1); gets(str2); str2Size=strlen(str2); for(int i=0;i<str2Size;i++){ int cnt=0; for(int j=0;j+i<str1Size;j++) if(str1[j+i]==str2[j]) cnt++; ans=max(ans,cnt); } for(int i=0;i<str2Size;i++){ int cnt=0; for(int j=0;j+i<str2Size;j++) if(str2[j+i]==str1[j]) cnt++; ans=max(ans,cnt); } printf("%d",ans); return 0; }

題目連結: http://tioj.infor.org/problems/1231 顯然最大的一定會被拿到，但是為了防止前免就拿到他，而拿不到次大的，不妨從後面開始，保證大的都會在後面才拿到，所以基本上次大的前面就會拿到，因此就有好的做法了XD #include <bits/stdc++.h> using namespace std; typedef pair<int,int> PII; int main(){ int n,ans=0; scanf("%d",&n); vector<PII> mm; for(int i=0;i<n;i++){ int a,b; scanf("%d%d",&a,&b); mm.push_back({a,b}); } sort(mm.begin(),mm.end(),[](PII a,PII b){return a.second>b.second;}); int k,cursor=0; scanf("%d",&k); priority_queue<int> pq; for(int i=k;i>=1;i--){ while(cursor<mm.size()&&mm[cursor].second>=i){ pq.push(mm[cursor].first); cursor++; } if(pq.empty()){ ans--; }else{ ans+=pq.top(); pq.pop(); } } p...

題目連結: http://contest.cc.ntu.edu.tw/npsc2009/2009sen.pdf 不 本題複雜度大概要做到$O(n)$或$O(n \log n)$，所以明顯naive的枚舉點對做法是不可能會好的，不妨思考其實每個人都只要往一邊看就好了，而且當看到一個比自己大的數就可以停了，那應該可用stack做，而明顯要用stack做的話，要有一定的單調性，想想後發現遞減的是好的，每次都pop掉比自己小的人並把pop了幾個加上去，不過值得注意的是如果是pop掉跟自己一樣的人的話，記得要把他原本的size記錄下來，之後要擺回去，因為其他人都還是可以跟你做匹配之類的，此外因為每個人都還可以跟隔壁的人溝通，所以當隔壁有人時記得多加一。 #include <bits/stdc++.h> using namespace std; class knight{ private: int __val; long long __size; public: knight(int a,int b){__val=a;__size=b;} int operator++(int a){if(a==0)return __size++;} bool operator<=(int a){return __val<=a;} bool operator==(int a){return __val==a;} friend void operator+=(long long &a, knight b){a+=b.__size;} }; stack<knight> ss; int main(){ int t; scanf("%d",&t); while(t--){ int sz; long long ans=0; scanf("%d...