oToToT的code收藏區

題目連結: http://tioj.infor.org/problems/1092 本題是個對稱遊戲，所以應該只需要管該點是先手贏或後手贏，那顯然最後一點是先手贏，而連到最後一點的都輸，所以可以導出該點一定跟他下一點相反，而如果前面的點有必勝的點，那對方也一定走過去，所以只要看他連到的點有沒有必勝的，若有自己就必輸，若無則自己必贏，所以DFS一遍就可以解決了XD #include <bits/stdc++.h> using namespace std; #define N 10000 vector<int> graph[N+10]; int n,e; bitset<N+10> isset; bitset<N+10> val; inline void init(); bool dfs(int); int main(){ scanf("%d%d",&n,&e); while(n+e!=0){ init(); while(e--){ int a,b; scanf("%d%d",&a,&b); graph[a].push_back(b); } isset[n]=1; val[n]=1; dfs(1); char name[7]; scanf("%s",name); if((!val[1] && name[1]=='i') || (val[1] && name[1]=='o')) puts("Moumou"); else puts("Mimi"); ...

題目連結: http://tioj.infor.org/problems/1034 本題N超小的，估了一下到$O(N^6)$甚至$O(N^7)$可能都會過，不過該怎麼做這題呢XD 仔細想想我們如果可以快速得到任意兩點的最短距離的話，那就直接枚舉炸掉所有位置，看看哪樣比較短，也就是說答案就是$\min\limits_{\forall k \in V} dis[a][k]+dis[k][b]-2 \times val[k]$(其中v是所有點的集合)(這是先把二維圖轉一維後的寫法)，而任兩點最短路徑的話就直接寫個floyd-warshall就好了XD 不過說直接floyd-warshall很容易，但本題給的是點權，可能沒辦法好好做，所以我直接用了一個小技巧(或許可以不用用拉XD):把a到b的距離設成$2 \times val[b]-val[a]$，最後算a到b時再加回$2 \times val[a]-val[b]$他的值就會是好的了 #include <bits/stdc++.h> using namespace std; typedef long long lld; #define N 20 #define INF 100000 int g[N+5][N+5]; lld sg[3000][3000]; int n; inline int Hash(int,int); int main(){ scanf("%d",&n); for(int i=0;i<n;i++)for(int j=0;j<n;j++)scanf("%d",&g[i][j]); for(int i=0;i<n;i++)for(int j=0;j<n;j++)for(int p=0;p<n;p++)for(int q=0;q<n;q++)sg[Hash(i,j)][Hash(p,q)]=INF; for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ ...

題目連結: http://tioj.infor.org/problems/1292 裸樹上最小點覆蓋。而樹上最小點覆蓋該如何做呢?，不妨考慮先DFS一遍取得整棵樹的構造，之後從葉子走上去(可直接用DFS序列倒著跑)，若自己及自己的爸爸都沒有被任何點覆蓋，則把自己的爸爸放到點覆蓋集，因為這樣可以保證把所有點都放進去，而且因為是放爸爸進去，所以可以拿到最小的點覆蓋集。 #include <bits/stdc++.h> using namespace std; #define N 10000 vector<int> tree[N+10]; int deep[N+10]; vector<int> arr; bitset<N+10> poped; void DFS(int,int,int); int n; int main(){ scanf("%d",&n); for(int i=0;i<n-1;i++){ int s,e; scanf("%d%d",&s,&e); tree[s].push_back(e); tree[e].push_back(s); } int cnt=0; DFS(1,-1,0); for(int i=arr.size()-1;i>0;i--){ int cc=arr[i]; int ff=arr[i-1]; if(deep[ff]>=deep[cc])continue; if(!poped[ff]&&!poped[cc]){ poped[ff]=1; poped[cc]=1; cnt++; } ...

題目連結: http://tioj.infor.org/problems/1337 本題一樣也是校內補選題，當時在寫的時候我一值莫名其妙唬爛到60分，學長一直rejudge掉我，但我又有其他騙分的方式，所以最後就因為這題我上機變第一www，不過說實在那時寫的是假解，實在不太好 正題：本題雖然可以轉成區間最大值，然後用個線段樹可以應付沒有炸彈的情況，但是若用線段樹很難維護要炸掉誰，所以不妨對答案二分搜，驗證那個答案可不可能的方式就是從左掃到右，發現疊起來值太大時就把右界最遠的線段pop掉，因為他一定後面還會影響到很多人，掃過去看要炸的數量是不是比炸彈多，過多就表示不可能，反之就有可能。不過要特別注意一下，二分搜時上界記得設成n-k，免得不小心因為常數TLE掉。複雜度$O(n log^2 n)$ #include <bits/stdc++.h> using namespace std; #define FF first #define SS second int n,k; struct block{ vector<int> end; int val; }; map<int,block> mm; inline bool test(int); int main(){ scanf("%d%d",&n,&k); for(int i=0;i<n;i++){ int l,r; scanf("%d%d",&l,&r); mm[l].end.push_back(r); mm[l].val++; mm[r].val--; } int uBound=n-k, lBound=-1; while(uBound-lBound!=1){ bool qq = test((uBound+lBound)/2); if(qq) uBound=(uBound+lBound)/2; else lBound=(uBound+lBound)/2; } printf("%d...

題目連結: http://tioj.infor.org/problems/1136 因為我們知道若把圖用鄰接矩陣存下來，他的t次方就是走t步後有幾種走法，所以就可以看下面的做法做了。 本題要求的其實就是從所有a($0 \leq a \leq n$)開始走到x的機率和最後再除以n，但是顯然直接乘再算機率會overflow(除非你寫大數)，所以有個比較方便的技巧就是一開始就算機率，之後做矩陣乘法的時候就不會因此而overflow了，大概這樣就可以AC了吧 #include <bits/stdc++.h> using namespace std; typedef double lf; typedef long long lld; #define N 100 auto m1 = new lf[N+10][N+10]; auto m2 = new lf[N+10][N+10]; auto m3 = new lf[N+10][N+10]; lld mm[N+10][N+10]; inline void mTimes(lf[][N+10],lf[][N+10],lf[][N+10]); int n,t; int main(){ scanf("%d%d",&n,&t); while(n+t!=0){ for(int i=0;i<n;i++)for(int j=0;j<n;j++)m1[i][j]=m2[i][j]=m3[i][j]=mm[i][j]=0; int x; scanf("%d",&x); while(x--){ int s,t; scanf("%d%d",&s,&t); s--,t--; mm[s][t]=1; mm[t][s]=1;...

題目連結: http://tioj.infor.org/problems/1336 建中校內補選題，我開賽19分鐘才AC，覺得太廢了QAQ，本題就照著DFS，記得記一下誰已經走過了，走到他就別再走，大概這樣吧 #include <bits/stdc++.h> using namespace std; typedef long long lld; typedef unsigned long long llu; typedef double lf; typedef long double llf; #define F1(i,a,n) for(int i=a;i<n;i++) #define F(i,a,n,m) for(int i=a;i<n;i+=m) #define WC(x) while(x--) #define N 100 int graph[N+10][N+10]; bitset<N + 10> checked[N + 10]; void check(int,int,int); int n,m; char str[N+10]; int main(){ scanf("%d%d",&m,&n); F1(i,0,n){ scanf("%s",str); F1(j,0,m){ char c=str[j]; switch(c){ case '-': graph[i][j]=1; break; case 'G': graph[i][j]=2; break; case 'W': ...

題目連結: http://tioj.infor.org/problems/1097 本題就是一個經典的最大0/1子矩陣問題，且限制只能圈正方形，所以就DP吧，dp[i][j]意思是以(i,j)為右下角，最大可以劃出邊長為多少的正方形，而轉移即是看他左上角一格，或上面，或左邊，最小可以畫到多少，然後加一。 參考資料 不過本題很陰險的是直接開記憶體會噴掉，所以要滾動或是跟我一樣用個爛爛的做法:開short #include <bits/stdc++.h> using namespace std; #define N 5000 bitset<N + 10> graph[N + 10]; short dp[N + 10][N + 10]; int main(){ int n,m; scanf("%d%d",&n,&m); while(n+m!=0){ for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ int t; scanf("%d",&t); graph[i][j] = (t==2); } } //1 means ummovable, 0 means movable for(int i=0;i<n;i++)if(!graph[i][0])dp[i][0]=1; for(int i=0;i<m;i++)if(!graph[0][i])dp[0][i]=1; short ans=!graph[0][0]; for(int i=1;i<n;i++){ for(int j=1;j<m;j++){ if...

題目連結: http://tioj.infor.org/problems/1869 本題我一開始以為可以開個N棵線段樹之類的，結果我就TLE了QAQ，後來想想才發現N棵線段樹的話，複雜度是$O(Q N \log N)$難怪會TLE，想了想發現似乎可以樹套樹(二維BIT)，畢竟他只有區間和跟單點修改，那就直接做吧XD，複雜度$O(Q \log ^2 N)$ #include <bits/stdc++.h> using namespace std; #define N 1024 #define lowbit(x) (x)&(-x) int BIT[N+10][N+10]={0}; int n; void edit(int,int,int); int query(int,int); int main(){ scanf("%d",&n); int type; while(scanf("%d",&type)!=EOF){ if(type==1){ int x,y,z; scanf("%d%d%d",&x,&y,&z); x++,y++; edit(x,y,z); }else{ int x1,y1,x2,y2; scanf("%d%d%d%d",&x1,&y1,&x2,&y2); x1++,y1++,x2++,y2++; int s = query(x2,y2) + query(x1-1,y1-1) - query(x1-1,y2) - query(x2,y1-1); printf("%d\n",s); ...

題目連結: http://tioj.infor.org/problems/1497 本題是個裸後綴陣列題，基本上只要你懂它就寫得出來，不過我好像寫這題寫了一整天，倒最後是參考 這篇 的$O(n \log ^2 n)$的作法才刻了出來，不過後來還是有寫一份radix sort的版本，但效率不知為何很差就是了... $O(n \log ^2 n)$的作法 #include <bits/stdc++.h> using namespace std; #define N 100000 #define PB push_back struct sfx{ int index; int r,nr; }; char str[N + 10]; int len; int mapping[N + 10]; sfx sa[N + 10]; bool cmp(sfx a,sfx b){ if(a.r==b.r){ return a.nr<b.nr; }else{ return a.r<b.r; } } void SA(); int main(){ gets(str); len = strlen(str); SA(); for(int i=0;i<len;i++){ printf("%d\n",sa[i].index); } return 0; } void SA(){ for(int i=0;i<len;i++){ sa[i].index = i; sa[i].r=str[i]; sa[i].nr=(i+1>=len)?-1:str[i+1]; } sort(sa,sa+len,cmp)...

題目連結: https://judge.ioicamp.org/problems/57 因為不知道是不是大家都看的到題敘，所以稍微敘述一下好了: 總共有T測資，給定一個N，請你選出三個數$1 \leq i,j,k \leq n$使得其最小公倍數最大($N \leq 10^6$) 然後我一開始不知道該怎麼做，只知道明顯要拿最大且互質的三組數，直到虞樸學長很電的跟我們說其實答案只會在$n,n-1,n-2,n-3$，想了很久並跟別人討論後才發現，考慮$n \geq 4$的情況下(前面三種特判就好)，因為顯然兩個相鄰的數必定互質(由輾轉相除可知)，所以只要考慮弟三個數要跟這兩個數互質。那假如現在已有$n,n-1$兩個數，若$2|n$那$2|n-2$也必定發生，所以這時我們就只能考慮$n-3$，若$gcd(n,n-3) \neq 1$那應該可以確定$3|n$，而我們也知道$2|n-2$，表示若取了n就不能取n-2及n-3，那不妨改成取$n-1,n-2,n-3$試試看，因為已經有前面的條件，所以應該可以證明出取他們必定互質，所以就知道了完整的規則了。 #include <bits/stdc++.h> using namespace std; typedef long long lld; int main(){ int t; scanf("%d",&t); while(t--){ lld n,ans; scanf("%lld",&n); if(n==1){ ans=1; }else if(n==2){ ans = 2; }else if(n==3){ ans = 6; }else if(n%6==0){ ans=(n-1)*(n-2)*(n-3); }else if(n%2==0){ ans=n*(n-1)*(n...

題目連結: http://tioj.infor.org/problems/1952 或 http://codeforces.com/problemset/problem/558/E 本題要每次都對某個區間按小到大或大到小排序，那字串排序大概會想到counting sort，不難發現counting sort就是在對那個區間的a-z各自求和，之後再按順序填回去。這時就會有似曾相似的感覺了吧......吧，那就是區間求和跟區間修改，顯然用線段樹可以做到，不過要開a-z共26顆線段樹，每次要修改前就區間查和然後先歸零再把前面都改成一，最後輸出的時候就每個字元都查詢一下是哪一個，大概就這樣吧 p.s 第一次寫區間修改區間查詢的線段樹，怎麼運用懶標記卡了有點久ww 再p.s 其實這題有更快的作法，詳細解法可以看看 余柏敘大大的code #include <bits/stdc++.h> using namespace std; #define unset -1 #define N 100000 struct segNode{ int l,r,val; int m; }; void buildTree(int,int,int,int); segNode segTree[26][N*4]; void modify(int, int, int, int, int); int query(int, int, int, int); void push(int,int); int gVal(int,int); int main(){ int n,m; scanf("%d%d",&n,&m); char str[N+5]; scanf("%s",str); for(int i=0;i<26;i++){ buildTree(i,0,n,0); } for(int i=0;i<n;i++){ modify...

題目連結: http://tioj.infor.org/problems/1103 先說顯然本題不能開一個$n \times 2n$的矩陣，不然你一定會 MLE 掉，那該怎麼做呢？ 大家高中可能學過類似這種題目的做法:填格子，沒錯，就是填格子，每次從左到右填一橫條，把它下面跟他左邊(也就是相鄰的)的值加起來，那顯然我們每次都只會用到它下面那條，其他用完就可以扔了，所以不妨用兩條滾動，然後記得先把表完全建好，不然每次要問都要建一次，複雜度會變成$O(t \times n^2)$，明顯會慘掉.. #include <bits/stdc++.h> using namespace std; #define modBASE 10000 #define N 10000 int graph[2][N + 10]; int val[N + 10]; int main(){ int sz=0; for(int i=0;i<=N;i++) graph[0][i]=1; for(int i=1;i<=2*N;i++){ if((i-1)%2==0)sz++; for(int j=0;j<=N;j++) graph[i%2][j]=0; for(int j=sz;j<=N;j++){ graph[i%2][j]=graph[i%2][j-1]; graph[i%2][j]%=modBASE; graph[i%2][j]+=graph[(i-1)%2][j]; graph[i%2][j]%=modBASE; if(j*2==i)val[j]=graph[i%2][j]; } } int n; scanf("%d",&n); while(n!=0)...

題目連結: http://tioj.infor.org/problems/1557 邊DFS邊DP，只要知道起點到起點的走法是一種，然後每次都詢問他的來源走法有幾種，大概這樣吧 #include <bits/stdc++.h> using namespace std; typedef long long lld; #define PB push_back #define N 10000 #define modBASE 1073741824 vector<int> graph[N + 10]; lld val[N + 10]={0}; bitset<N + 10>dped; lld dp(int); int main(){ int n,m; scanf("%d%d",&n,&m); for(int i=0;i<m;i++){ int a,b; scanf("%d%d",&a,&b); graph[b].PB(a); } int Start,End; scanf("%d%d",&Start,&End); val[Start]=1; dped[Start]=1; lld ans = dp(End); printf("%lld",ans); return 0; } lld dp(int w){ if(!dped[w]){ lld sum=0; for(int i=0;i<graph[w].size();i++){ sum += dp(graph[w][i]); sum %= modBASE; }...

題目連結: http://codeforces.com/contest/764/problem/C 每次都找degree為1的人，看他跟他連接的那個人顏色一不一樣，如果依樣就把那條邊刪掉，直到每個degree為一的都找過為止，然後看是不是只有一個人degree不為一或零，如果有，他就是唯一的答案。但是要注意一下，因為有可能沒有唯一解，因此需要特判最後若degree度和為零(所有人都被砍掉了)，那一定是因為所有人顏色一樣，所以隨便輸出一個範圍內的數就好了；degree和為二的時候，表示最後只剩兩點，那答案也必定是那兩點之一，隨便輸出一個就好了。 #include <bits/stdc++.h> using namespace std; #define N 100000 set<int> tree[N+5]; int color[N + 5]; int deg[N + 5]={0}; int main(){ int n; scanf("%d",&n); for(int i=0;i<n-1;i++){ int a,b; scanf("%d%d",&a,&b); tree[a].insert(b); tree[b].insert(a); deg[a]++; deg[b]++; } for(int i=1;i<=n;i++) scanf("%d",&color[i]); queue<int> deg1; for(int i=1;i<=n;i++) if(deg[i]==1)deg1.push(i); while(!deg1.empty()){ int top=deg1.front(); deg1.pop(...

題目連結: http://tioj.infor.org/problems/1751 本題就直接每次都拿不比他大中最大的那個換，所以就把再int範圍內的費式數列倒著跑一遍，每當比他小就把原數扣掉他，最後驗原數是不是被換成0了就好了 int範圍內的費式數列共有46個 #include <bits/stdc++.h> using namespace std; vector<int> f; int main(){ f.push_back(1); f.push_back(1); for(int i=2;i<46;i++) f.push_back(f[i-1]+f[i-2]); int t; scanf("%d",&t); while(t--){ int n,ans=0; scanf("%d",&n); for(int i=f.size()-1;i>0;i--){ if(f[i]<=n){ n-=f[i]; ans++; } } if(n==0) printf("%d\n",ans); else puts("iyada~"); } return 0; }

題目連結: http://tioj.infor.org/problems/1212 本題要找最小環，那要怎麼做呢?其實就直接做Floyd-Warshall，然後看哪一組自己到自己最小，大概就這樣吧XD #include <bits/stdc++.h> using namespace std; #define INF 999999 #define N 500 int graph[N + 10][N + 10]; int main(){ int n,m; scanf("%d%d",&n,&m); while(n!=0||m!=0){ for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) graph[i][j]=INF; for(int i=0;i<m;i++){ int a,b; scanf("%d%d",&a,&b); graph[a][b]=1; } for(int k=1;k<=n;k++) for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) graph[i][j] = min(graph[i][j], graph[i][k]+graph[k][j]); int mm=INF; for(int i=1;i<=n;i++) mm = min(graph[i][i], mm); if(mm==INF) puts("0"); ...

題目連結: http://tioj.infor.org/problems/1096 本題要找最小環，那要怎麼做呢?其實就直接做Floyd-Warshall，然後看哪一組自己到自己最小，大概就這樣吧XD #include <stdio.h> #define INF 9999999 int graph[101][101]; int main(){ int n; scanf("%d",&n); while(n!=0){ for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ scanf("%d",&graph[i][j]); if(graph[i][j]==0)graph[i][j]=INF; } } for(int k=0;k<n;k++) for(int i=0;i<n;i++) for(int j=0;j<n;j++) if(graph[i][k]+graph[k][j] < graph[i][j]) graph[i][j] =graph[i][k]+graph[k][j]; int min=INF; for(int i=0;i<n;i++) if(graph[i][i]<min) min=graph[i][i]; if(min==INF) puts("-1"); else printf("%d\n...

題目連結: http://tioj.infor.org/problems/1948 首先可以發現反彈其實就是兩個人交換工作而已，所以其實時間不會改變，再來就是若由左到右有abc三人，則a或c一定比b早出來，甚至ac都出來了，b才出來，由這兩個性質可以$O(1)$得出是誰先出來的，只要先對位置排序，然後從左往右掃紀錄往左的人，並從右往左掃，紀錄往右的人，然後每次比他們兩個最外面的那個人的距離如果右邊比較小，則讓整個隊列右邊的人出去(代表是他幫忙做完事情)，反之亦然，直到整串隊伍剩下一個人為止，它就是最晚出來的那個 #include <bits/stdc++.h> using namespace std; typedef long long lld; #define N 1000000 #define xianL 0 #define xianR 1 struct dg{ lld pos,xian,id; }; dg dragon[N + 5]; bool cmp(dg a,dg b){return a.pos<b.pos;} int main(){ lld n,l; scanf("%lld%lld",&n,&l); for(int i=0;i<n;i++){ scanf("%lld%lld",&dragon[i].pos,&dragon[i].xian); dragon[i].id=i; } sort(dragon,dragon+n,cmp); queue<lld> ll,rr; for(int i=0;i<n;i++) if(dragon[i].xian==xianL)ll.push(dragon[i].pos); for(int i=n-1;i>=0;i--) if(dragon[i].xian==xianR)rr.pu...