oToToT的code收藏區

題目連結: http://main.edu.pl/en/archive/oi/2/drz 不難發現其實就照著他說的插入就好，不過因為我寫不太出來該如何判斷往哪邊插跟何時要開點，所以我用另外一種寫法。每次都把最大且相鄰的兩個點合併起來成為一個新節點，而當有人找不到人配時就是不合法的。構造完完整的樹後就直接DFS輸出他要的結果即可。 #include <bits/stdc++.h> using namespace std; #define N 2500 struct lNode{ lNode *l, *r; int next, dep; lNode(){l=NULL;r=NULL;} }; lNode *List[N+5], __nn[4*N]; lNode* nNode(){ static int __cnt=0; return &__nn[__cnt++]; } void dfs2(lNode*); int id=0; void dfs1(lNode*); int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n;cin>>n; for(int i=0;i<n;i++)List[i]=nNode(); for(int i=0;i<n;i++)List[i]->next=i+1; List[n-1]->next=n-1; int mx=-1; for(int i=0;i<n;i++){ cin>>(List[i]->dep); mx=max(mx, List[i]->dep); } bool flag=1; for(int i=mx;i>=1;i--){ if(!flag)break; for(int j=0,k=0;k<n;j=List[j]->next,k++){ if(List[j]->dep == i){ if(List[j]->next==j || List[List[j]->next]->dep != i){ flag=0; break; }else{ int nn

題目連結: http://tioj.infor.org/problems/1163 本題看似給定一張無向圖，實在不好求得所有路徑最大值的最小值，但是很明顯可以發現因為是要最小的最大值，所以其實先把最小生成樹找出來後，再在上面求路徑最大值就會是好的，而且如果是寫kruskal演算法，你還可以快速知道兩個點是不是連通的。而要求一棵樹上路徑的最大值，不難發現你可以把路徑拆成a到LCA(a,b)跟b到LCA(a,b) (其中LCA指的是最低共同祖先)，然後通常求LCA時會用倍增法，而這時就會發現其實求路徑最大值也可以用倍增法，一樣每次更新這段的最大值，然後找的時候也差不多。 p.s 比較好的講法可以看 這篇 #include <bits/stdc++.h> using namespace std; #define N 30000 #define logN 16 typedef pair<int,int> PII; int djs[N+5]; 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);} struct Edge{ int s,e,p; bool operator>(const Edge& x)const{return p>x.p;} }; vector<PII> Tree[N+5]; int time_in[N+5], time_out[N+5],timer=0; PII ff[N+1][logN+1]; void dfs(int,int,int); inline bool anc(int,int); inline int lca(int,int); inline int getMax(int,int); bitset<N+5> walked; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int v,e;cin>>v>>e; for(int i=1;i<=v;i++)djs[i]=i; for(in

題目連結: http://tioj.infor.org/problems/1827 不難發現本題可以對答案二分搜，因為S有單調性，那驗證的時候就是要驗證一個區域是不是有至少k個數小於S，我原本想說用個BIT套treap之類的，但估完複雜度後發現會TLE，實在苦思不知該如何做，直到有人雷了我說誰區間和在用BIT的，我才發現可以用維護前綴和的精神做這題，也就是說每個前綴變成存一棵treap，但是如果每一個前綴都重新插一遍所有東東到treap裡面會發現預處理變成$O(n^2 log(n))$，明顯會TLE，所以不妨用持久化的概念，也就是讓一部分是共用的，有修改到的部分再複製出來就好了，因為複製時最多只會動到一條跟到葉的路徑也就是最多$log(n)$個節點，因此複雜度還是$log(n)$，只是記憶體有點龐大而已。 #include <bits/stdc++.h> using namespace std; #define N 100000 struct treap{ treap *l, *r; int pri,val,size; treap(){l=r=nullptr;size=0;} treap(int x){l=r=nullptr;pri=rand();val=x;size=1;} }; inline int gSize(treap* x){return x?x->size:0;} inline void pull(treap* x){x->size=gSize(x->l)+1+gSize(x->r);} int arr[N+5], n; treap* root[N+5]; bool isOK(int,int,int); void split(treap*,int,treap*&,treap*&); treap* merge(treap*, treap*); int query(treap*,int); int main(){ ios_base::sync_with_stdio(0);cin.tie(0); srand(time(NULL)); int m;cin>>n>>m; for(int i=0;i<n;i++)cin>>arr[i]; root

題目連結: http://tioj.infor.org/problems/1160 其實只要記錄每個數字有多少個，跟紀錄一下當前的眾數是誰以及他的量，當插入一個數字使得他的數量大於原本的眾數時就更新一下眾數資訊，不過不能用array因為他的值域太大，所以不妨考慮用個hash_table(unordered_map) #include <stdio.h> #include <unordered_map> using namespace std; int main(){ unordered_map<int, int> arr; int inp, which=0, size=0; scanf("%d",&inp); while(inp!=0){ if(arr.find(inp) == arr.end()){ arr[inp] = 1; }else{ arr[inp] ++; } if(arr[inp]>size){ which = inp; size = arr[inp]; }else if(arr[inp]==size){ which = (inp<which)?inp:which; } printf("%d %d\n",size, which); scanf("%d",&inp); } return 0; }

題目連結: http://tioj.infor.org/problems/1609 其實一棵二元搜尋樹中序遍歷就是大小關係，所以直接把他給你的數字由小到大sort過一遍後印出來就是答案了 #include <bits/stdc++.h> using namespace std; int arr[1000005]; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n;cin>>n; for(int i=0;i<n;i++)cin>>arr[i]; sort(arr,arr+n); for(int i=0;i<n;i++)cout<<arr[i]<<' '; return 0; }

題目連結: http://tioj.infor.org/problems/1371 裸的凸包，由左至右掃過去維護上凸包跟下凸包，維護方法就是看加入當前這個點是不是在前面兩個所連線的上方(上凸包的話)，如果是就把前一個砍掉，不然就塞進去，下凸包也同理。 不過本題要注意相同高度的點就不用輸出了 #include <bits/stdc++.h> using namespace std; typedef long long lld; struct point{ lld x,y; int id; point(){} point(lld a,lld b,lld c){x=a;y=b;id=c;} point(lld a,lld b){x=a;y=b;} }; inline lld cross(const point& a,const point& b){ return a.x*b.y-a.y*b.x; } vector<point> dots; vector<point> cHull; vector<point> ans; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n;cin>>n; for(int i=1;i<=n;i++){ lld a,b;cin>>a>>b; dots.push_back(point(a,b,i)); } sort(dots.begin(),dots.end(),[](const point& a,const point& b){return (a.x!=b.x)?(a.x<b.x):(a.y<b.y);}); for(int i=0;i<dots.size();i++){ while(cHull.size()>=2){ int sz=cHull.size()-1; if(cross(point(cHull[sz-1].x-cHull[sz].x, cHull[sz-1].y-cHull[sz].y), \ point(dots[i].x-cHull[sz].x, dots[i

題目連結: http://tioj.infor.org/problems/1178 裸裸的凸包題，不過凸包該如何做呢?可以用掃描線的概念，從左至右掃一遍，試試看某個點會不會是凸包的一部分，試驗方法就是看這個點與相鄰且在暫時凸包的兩個點的夾角，如果大於180則中間那個點將不會是凸包的一部分(可用外積判斷是否大於180)，這樣可求出上凸包，從右至左再掃一遍就可以找到下凸包了XD #include <bits/stdc++.h> using namespace std; typedef long long lld; struct point{ lld x,y; point(lld a,lld b){x=a;y=b;} }; inline lld cross(point a, point b){ return a.x*b.y-a.y*b.x; } vector<point> dots; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n,ans=0;cin>>n; for(int i=0;i<n;i++){ lld a,b;cin>>a>>b; dots.push_back(point(a,b)); } vector<point> cHull; sort(dots.begin(), dots.end(), [](const point& a, const point& b){return a.x<b.x;}); for(auto i:dots){ while(cHull.size()>=2){ int sz=cHull.size()-1; if(cross(point(cHull[sz].x-cHull[sz-1].x,cHull[sz].y-cHull[sz-1].y),\ point(i.x-cHull[sz-1].x, i.y-cHull[sz-1].y))<0)break; cHull.pop_back(); } cHull.push_back(i); } ans+=cHull.size(); cHull.clea

題目連結: http://tioj.infor.org/problems/1025 又是一題數獨，同樣的按照對的順序dfs，則你輸出答案的順序也會是好的，所以就爆搜吧XD #include <bits/stdc++.h> using namespace std; struct pos{ int x,y; pos(int a,int b){x=a;y=b;} }; vector<pos> need; int sudoku[9][9]; int sum=0; void solve(int); inline bool isOK(); int main(){ ios_base::sync_with_stdio(0);cin.tie(0); for(int i=0;i<9;i++){ for(int j=0;j<9;j++){ cin>>sudoku[i][j]; if(sudoku[i][j]==0)need.push_back(pos(i,j)); } } solve(0); cout<<"there are a total of "<<sum<<" solution(s)."; return 0; } void solve(int w){ if(w==need.size()){ for(int i=0;i<9;i++){ for(int j=0;j<9;j++)cout<<sudoku[i][j]<<' '; cout<<'\n'; } cout<<'\n'; sum++; }else{ auto cur=need[w]; for(int i=1;i<=9;i++){ sudoku[cur.x][cur.y]=i; if(isOK())solve(w+1); } sudoku[cur.x][cur.y]=0; } } inline bool isOK(){ for(int i=0;i<9;i++){ int sm[

題目連結: http://tioj.infor.org/problems/1208 不太確定該如何下手時，就先二分搜一陣吧，而且他還特別保證所有項的絕對值都不超過10,000，所以感覺二分搜有機會，那二分搜答案要怎麼驗證呢?其實對於一個數我們有能力可以知道有幾個連續和比他大，因為如果要看x是第幾大，則就是對於每個前綴和$a_i$我們都要找有多少個$a_j$使得$a_i - a_j > x$(其中$i>j$)，移項發現變成找有多少個$a_j+x < a_i$，那不就是一個平衡數常帶有的功能嗎?所以就先找看看對於這個前綴和$a_i$有多少個$a_j+x$比他小，算完後再把$a_i+x$丟到平衡樹內，如此就可以知道他是第幾大的了，複雜度$O(n log n log C)$其中C是值域 #include <bits/stdc++.h> using namespace std; #define N 20000 class Treap{ private: struct __node{ __node* l; __node* r; int __pri,__size,__val; __node(){l=NULL;r=NULL;__pri=rand();__size=0;} __node(int x){l=NULL;r=NULL;__pri=rand();__size=1;__val=x;} ~__node(){if(l)delete l;if(r)delete r;l=NULL;r=NULL;} }; __node* __root; inline int __gSize(__node* __x){return (__x==NULL)?0:(__x->__size);} __node* __merge(__node* __x,__node* __y){ if(__x==NULL||__y==NULL)return __x?__x:__y; else if(__x->__pri > __y->__pri){ __x->r = __merge(__x->r,__y); __x->__size = __gSize(__x->

題目連結: http://tioj.infor.org/problems/1639 本題是校隊題，那時我根本不知道題目在幹嘛，後來被雷(解析)了後才知道原來是個裸最佳二元樹，不過要套四邊形不等式優化，但我根本不知道最佳二元樹的$O(N^3)$作法該怎麼做ww，想了很久加被雷後才知道，因為給定一棵最佳二元樹，其左右子樹也皆為最佳二元樹，所以可以列出$dp[l][r] = \displaystyle\min_{\forall l \leq k \leq r}(dp[l][k]+dp[k][r])+sum[l][r], $的轉移式，這時就可以$O(N^3)$的拿到大部分測資，不過最後那組要套2D/1D四邊形優化，簡述一下：對於一條轉移式$dp[i][j] = \displaystyle\min_{\forall i \leq k \leq j}(dp[i][k]+dp[k][j])$，定義$K_{i,j}$為會使dp[i][j]最小的那個k，則$K_{i,j-1} \leq K_{i,j} \leq K_{i+1,j}$，但是要如何運用這神奇的性質呢?那顯然要讓你的j-i值由小到大出現，不過可以其實也可以偷懶，就是從第一維從後跑回來，第二維再負責維持使j-i由小到大就好。然後就照著做就好www這應該是最簡單的四邊形不等式優化了吧XD，仔細觀察: \[\cdots \leq \cdots \leq \cdots \\ K_{i-2,j-3} \leq K_{i-2,j-2} \leq K_{i-1,j-2} \\ K_{i-1,j-2} \leq K_{i-1,j-1} \leq K_{i,j-1} \\ K_{i,j-1} \leq K_{i,j} \leq K_{i+1,j} \\ K_{i,j+1} \leq K_{i+1,j+1} \leq K_{i+2,j+1} \\ K_{i+2,j+1} \leq K_{i+2,j+2} \leq K_{i+3,j+2} \\ \cdots \leq \cdots \leq \cdots \] 你會發現每個元素都只會出現兩遍，也就是說總轉移最多O(2N)，所以在轉移時的複雜度就變成均攤$O(1)$了!! #include <bits/stdc++.h> using namespace std; typedef

題目連結: http://tioj.infor.org/problems/1198 經典的8-puzzle問題，那就來寫個IDA*吧，不過要注意一下你推過來就別推回去，這樣是沒意義的XD(其實就是各種剪枝然後dfs) #include <bits/stdc++.h> using namespace std; #define INF 21474836 int final[3][3]; int cur[3][3]; int dx[]={0,0,1,-1}, dy[]={1,-1,0,0}; int pre[]={1,0,3,2}; int ida_star(int,int,int); inline bool isOK(int,int); int main(){ cin.tie(0);ios_base::sync_with_stdio(0); for(int i=0;i<3;i++)for(int j=0;j<3;j++)cin>>cur[i][j]; for(int i=0;i<3;i++)for(int j=0;j<3;j++)cin>>final[i][j]; for(int i=1;i<=INF;i*=2){ int test=ida_star(0,i,-1); if(test!=INF){ cout<<test; break; } } return 0; } int ida_star(int cnt, int MAX,int howto){ int xx,yy,h=0;bool flag=1; for(int i=0;i<3;i++){ for(int j=0;j<3;j++){ if(cur[i][j]==0){xx=i;yy=j;} if(cur[i][j]!=final[i][j]){flag=0;h++;} } } if(cnt+h>MAX)return INF; if(flag)return cnt; int rr=INF; for(int i=0;i<4;i++){ if(isOK(xx+dx[i], yy+dy[i])&&pre[i]!=howto

題目連結: http://tioj.infor.org/problems/1108 因為二元搜尋樹有幾個棒棒的性質，那就是依照前序遍歷插入會得到原樹(後序倒著插入也會是好的)，而中序遍歷即為其大小關係，故只要用中序得到如何比大小，用前序插入就可建構出原樹，再自己後序一遍就好XDD，而雖然這題是二元樹，但你還是可以把它當二元搜尋樹搞 #include <bits/stdc++.h> using namespace std; int Map[256]; struct node{ node* l; node* r; char x; node(){l=NULL;r=NULL;} node(char a){l=NULL;r=NULL;x=a;} }; void insert(node*,node*&); void remove(node*); void dfs(node*); int main(){ char pre[60], in[60]; while(scanf("%s\n%s",pre,in)!=EOF){ vector<node*> vv; int sz=strlen(in); for(int i=0;i<sz;i++)Map[in[i]]=i; auto root = new node(pre[0]); for(int i=1;i<sz;i++){ auto tmp = new node(pre[i]); insert(tmp,root); vv.push_back(tmp); } dfs(root);putchar('\n'); remove(root); } return 0; } void insert(node* x,node*& rr){ if(rr==NULL) rr=x; else{ if(Map[x->x]>Map[rr->x]) insert(x,rr->r); else insert(x,rr->l); } } void remove(node* rr){ if(rr->l)remove(rr->l); if(rr-&g

題目連結: http://tioj.infor.org/problems/1382 原本用黑魔法過了這題，但覺得沒寫過平衡樹覺得還是該練練，所以就寫了個怪怪treap版本的(因為我會按照1,2,3,4...insert，所以不需要split)。這題的做法基本上就是每次查好你要砍那個，先輸出一下再刪掉就好，複雜度$O(n log n)$ #include <bits/stdc++.h> using namespace std; class tree{ private: struct node{ int size,val,pri; node* l; node* r; node* f; node(){f=NULL;l=NULL;r=NULL;size=0;pri=rand();} node(int x){f=NULL;l=NULL;r=NULL;size=1;val=x;pri=rand();} }; node* root; inline int gSize(node* x){return (x==NULL)?0:x->size;} node* merge(node* x, node* y){ if(x==NULL)return y; if(y==NULL)return x; bool xfa = (x->pri)>(y->pri); if(xfa){ if(y->val < x->val){ x->l=merge(x->l,y); x->l->f=x; }else{ x->r=merge(x->r,y); x->r->f=x; } x->size=gSize(x->l)+gSize(x->r)+1; return x; }else{ if(x->val < y->val){ y->l=merge(y->l,x); y->l->f=y; } else{ y->r=merge(y-&g

題目連結: http://tioj.infor.org/problems/1107 裸卡特蘭數題，而卡特蘭數可由$C_0=1$及$C_{n+1}=\frac{2(2n+1)}{n+2} \times C_{n}$的遞迴關係式算出，不過本題要輸出成科學記號有點麻煩，記得處理一下ww #include <bits/stdc++.h> using namespace std; #define N 1000000 struct sciF{ double _a; int _n; inline sciF operator=(int x){ _a=x; _n=0; while(_a>10){ _n++; _a/=10.; } return *this; } inline sciF operator*(int x){ _a*=x; while(_a>10){ _n++; _a/=10.; } return *this; } inline sciF operator/(int x){ _a/=x; while(_a<1){ _n--; _a*=10.; } return *this; } }; bitset<N+5> isset; sciF cc[N+5]; sciF cat(int); int main(){ int n;scanf("%d",&n); cc[0]=1; isset[0]=1; for(int i=1;i<=N;i++)cat(i); while(n!=0){ sciF ans=cat(n); printf("%0.3lfE+%d\n",ans._a,ans._n); scanf("%d",&n); } return 0; } sciF cat(int n){ if(!isset[n]){ sciF xx=cat(n-1) * 2 *(2*(n-1)+1); xx=xx/((n-1)+2); cc[n]=xx; } isset[n]=

題目連結: http://tioj.infor.org/problems/1417 梗梗的題目，不能用long long但又會超過int，這時大部分人都會選擇手爆大數，不過其實還有一招是__int128，他是一種GCC內建的型別，一個單純128bit的整數型別，不過他沒有包在cin之類的輸入函數裡面，所以要先用int讀進來後轉型之類的，不過反正這題一開始就是好的，所以就直接用吧XDD不過要注意一下你要幫他的標頭檔引入IO的函式庫 更新:用__int128的已經被rejudge掉了QQ，只能手爆大數了QQ #include <bits/stdc++.h> using namespace std; #include "lib1417.h" int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int t;cin>>t; while(t--){ int n,s,t;cin>>n>>s>>t; __int128 ans=0; vector<int> arr(n); for(int i=0;i<n;i++) cin>>arr[i]; sort(arr.begin(),arr.end()); for(int i=s-1;i<t;i++)ans+=arr[i]; bool less0=(ans<0); if(less0)ans=-ans; string ss=""; if(ans==0)ss="0"; while(ans!=0){ ss=char('0'+(ans%10))+ss; ans/=10; } if(less0)ss='-'+ss; output(ss.c_str()); } return 0; }

題目連結: http://tioj.infor.org/problems/1839 經典的二分搜題，對於每個門都二分搜一次他的開關是哪一個，記錄下來並使他保持開著的狀況，如此便可以往下繼續走下去，一次檢驗出一個門，所以複雜度是$O(n^2 log n)$，不過該怎麼二分搜呢?不妨每次都反轉一串開關(已知道的就不要轉)，看結果有沒有變成跟上一次不一樣(這裡的不一樣指的是說有沒有動到你要問的那個人)，也就是說如果按下去發現原本只能通到i，但現在可以走到i+1之類的，那你剛剛必定按到i了，反之如果現在可以到達i+1你按完之後只能到i那，也是有按到的，所以依此性質就可以二分搜每個門對應到的開關是誰，同時也知道如何開關才好。 p.s沒看到多筆測資害我被梗了一下下ww #include "lib1839.h" #define N 5000 int MAP[N+5], OPENED[N+5]; inline void SWAP(int,int); int main(){ while(1){ int n=Initialize(); for(int i=0;i<n;++i) MAP[i]=-1; for(int i=0;i<n;++i){ int sks = tryCombination(OPENED);if(sks==-1)sks=n; bool preSAME = (sks==i); int l=0, r=n;bool ff=(sks>i); while(r-l>1){ int mid=(l+r)/2; SWAP(l,mid); int kawaii=tryCombination(OPENED);if(kawaii==-1)kawaii=n; bool curSAME = (kawaii==i); if(curSAME==preSAME) l=mid; else r=mid; ff=(kawaii>i); preSAME=curSAME; } MAP[l]=i; if(!ff) OPENED[l]=(OPENED[l]+1)&1; } answer(OPENED,MAP); } re

題目連結: http://tioj.infor.org/problems/1087 經典的NIM題，可以用SG Value發現本題先手必勝，但要怎麼玩呢??，不難發現若且為若對方的盤面SG值為0他就輸了，因此我只要想辦法構造讓對方的三堆石頭xor起來是0，特別的是當剩兩堆且一堆為一時，顯然我們只要把那堆不為0的拿走就好了，而剩一堆時顯然把那堆拿到剩一就好了，所以記得特判一下 #include "lib1087.h" int stone[] = {10,15,20}; inline bool all0(); inline bool only1(int); int main(){ Initialize(); while(!all0()){ for(int i=0;i<3;i++){ int cnt,pile; if(stone[0]+stone[1]==1){ Take_Stone(3, stone[2], &pile, &cnt); stone[2]=0; stone[pile-1]-=cnt; break; }else if(stone[0]+stone[2]==1){ Take_Stone(2, stone[1], &pile, &cnt); stone[1]=0; stone[pile-1]-=cnt; break; }else if(stone[1]+stone[2]==1){ Take_Stone(1, stone[0], &pile, &cnt); stone[0]=0; stone[pile-1]-=cnt; break; } if(only1(i)){ while(stone[i]==1){i++;--i;} Take_Stone(i+1, stone[i]-1, &pile, &cnt); stone[i]=1; stone[pile-1]-=cnt; break; } int xx=0; for(int j=0;j<3;j++)if(i!=j) xx^

題目連結: http://tioj.infor.org/problems/1089 跟 TIOJ 1253. 砲打皮皮 一模一樣的題目，可以轉成二分圖最小點覆蓋，然後用最大匹配的做法去做，詳細可以去看那篇的題解 #include <bits/stdc++.h> using namespace std; #define N 500 vector<int> X[N+5],Y[N+5]; int fX[N+5], fY[N+5]; bitset<N+5> walked; bool dfs(int); int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n,k;cin>>n>>k; for(int i=1;i<=n;++i)fX[i]=fY[i]=-1; while(k--){ int s,e;cin>>s>>e; X[s].push_back(e); Y[e].push_back(s); } int ans=0; for(int i=1;i<=n;i++){ walked.reset(); if(dfs(i))ans++; } cout<<ans; return 0; } bool dfs(int x){ for(auto i:X[x]){ if(walked[i])continue; walked[i]=1; if(fY[i]==-1||dfs(fY[i])){ fY[i]=x;fX[x]=i; return 1; } } return 0; }