oToToT的code收藏區

題目連結: http://tioj.infor.org/problems/1120 基本上就是模擬他做的事，不過走過的點記得存下來，然後會有同樣結果的也先記下來，因為它是以6cm/s繞40cm的正方形，所以很容易可知每20秒會循環一次，大概這樣囉 #include <bits/stdc++.h> using namespace std; #define N 20000 struct TsuoBiaw{ int x,y; }; TsuoBiaw arr[N+5]; bitset<N+5> isset; int main(){ int n; while(scanf("%d",&n)!=EOF){ if(isset[n]){ printf("(%d,%d)\n",arr[n].x,arr[n].y); continue; } TsuoBiaw p; p.x=10; p.y=5; bool flag=true; char fanXian=0; p.x+=6*n; while(flag){ switch(fanXian){ case 0: if(p.x>15){ p.y += p.x-15; p.x=15; }else{ flag=false; } break; case 1: if(p.y>15){ p.x -= p.y-15; p.y=15; }else{ flag=false; } break; case 2: if(p.x<5){ p.y -= 5-p.x; p.x=5; }else{ flag=false; } break; case 3: if(p.y<5){ p.x += 5-p.y; p.y=5; }else{ flag=false; } break; }

題目連結: http://tioj.infor.org/problems/1085 BFS題，記得紀錄一下路徑，然後要check一下起點可不可以走，不然會有一個subtask WA ，我的code那麼長基本上是六個方位一直複製貼上，然後就長爆了(? #include <bits/stdc++.h> using namespace std; #define PB push_back #define null 2147483647 bitset<55> puzzle[55][55]; struct point{ char x,y,z; int last,This; }; vector<point> v; int main(){ int x,y,z; scanf("%d%d%d",&x,&y,&z); for(int i=1;i<=z;i++){ for(int j=1;j<=y;j++){ for(int k=1;k<=x;k++){ int b; scanf("%d",&b); puzzle[k][j][i]=!b; } } } if(puzzle[1][1][1]==0 || puzzle[x][y][z]==0){ puts("no route"); exit(0); } puzzle[1][1][1]=0; point tp; tp.x=1; tp.y=1; tp.z=1; tp.This=v.size(); tp.last=null; v.PB(tp); queue<point> q; q.push(tp); bool flag=false; while(!q.empty()){ point top=q.front(); q.pop(); if(top.x==x&&top.y==y&&top.z==z){ tp=top; flag=true; break; } if(top.x-1>=1 && puzzle[top

題目連結: http://tioj.infor.org/problems/1883 本題看起來很0/1背包吧，不過它跟普通的0/1背包不同的點在於它的物品是無限個的，因此這類問題又被稱作完全背包問題，那完全背包問題該如何做呢，不難發現原本0/1背包問題在滾動的時候要從後面滾是為了維護它不會重複取，不過我們現在不就是要讓它能重複取嗎?，所以其實就把0/1背包原本從後面倒過來做的，改成從前面做就好了 #include <bits/stdc++.h> using namespace std; struct skill{ int cost, damage; }; skill mySkills[1000 + 5]; int dmg[10000 + 5]; int main(){ int t; scanf("%d",&t); while(t--){ int w,b,n,m; scanf("%d%d%d",&w,&b,&n); for(int i=0;i<=w;i++){ dmg[i]=0; } for(int i=0;i<n;i++){ scanf("%d%d",&mySkills[i].cost,&mySkills[i].damage); } scanf("%d",&m); for(int i=0;i<n;i++){ mySkills[i].cost+=m; } for(int i=0;i<n;i++){ for(int j=mySkills[i].cost;j<w;j++){ dmg[j] = max(dmg[j], dmg[j-mySkills[i].cost]+mySkills[i].damage); } } if(dmg[w-1] >= b) puts("Yes"); else puts("No"); } return 0; }

題目連結: http://tioj.infor.org/problems/1228 本題是建中資訊校內複賽題，當時我在寫的時候完全不會線段樹甚麼的，所以我那時是直接照著做，然後稍微二分搜一下他的區間，就拿到了第二組subtask，因此比完之後我一直以為這題很簡單，直到聽完題解說要把樹壓扁、開BIT，我才發現原來沒有想像中的簡單。 --以上廢話-- 本題把樹壓扁後就變成單點修改區間查詢的序列問題了，但什麼是把樹壓扁呢，在本題中可以發現我們會修改以及查詢的其實都是邊權，所以其實可以用一定的方法幫這些邊編號，而因為我們在查區間和時是用DFS的方法去跑，所以不妨就用DFS時碰到邊的順序幫它編號，但記得要開個mapping能讓它之後詢問跟修改時知道要對幾號做動作，大概就醬吧。 p.s本題記憶體有點卡，不能寫線段樹，只能寫BIT(至少我就醬被梗了一段時間 #include <bits/stdc++.h> using namespace std; #define N 1000000 #define lowbit(x) ((x)&-(x)) struct node{ int child,val; }; struct dian{ int l,r; }; vector<node> tree[N+5]; dian dianMap[N+5]; int bianMap[N+5]; int BIT[N+5]; int n,q; int counter=0; int arr[N]; void foldTree(int); void buildBIT(); void edit(int,int); inline int sum(int); int query(int,int); int main(){ scanf("%d%d",&n,&q); for(int i=0;i<n-1;i++){ int a,b,m; scanf("%d%d%d",&a,&b,&m); node tp; tp.child=b; tp.val=m; tree[a].push_back(tp); } foldTree(0); buildBIT(); for(int

題目連結: http://tioj.infor.org/problems/1777 先說本題需要寫個大數，要有減法運算跟比大小的運算，因為我有點懶(?所以就抄了 日月掛長大大的模板 正題:其實不難發現兩人相撞後其實就是兩然交換往哪邊滾動的工作，其他位置什麼的都沒變，而題目也只要求最少需要多久，沒問說誰是最後一個完成的，所以我們其實就直接找離終點最遠的那位就好了，不過值得注意的是如果他兩個方向都可以就要選比較小的那個，大概就醬吧 #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; if(s.size()>v.s.size())return d; if(s.size()<v.s.size())return -d; for(int i=s.size()-1;i>=0;i--){ if(s[i]>v.s[i])return d;

題目連結: http://tioj.infor.org/problems/1947 裸樹重心題，而要怎麼找樹重心呢?直接DFS吧，在DFS時你就知道他小孩的子樹大小，而他祖先那塊子樹不難發現就是點數減下子樹的數量，然後就記個最小值大概這樣吧 #include <cstdio> #include <vector> #include <algorithm> typedef long long lld; using std::max; using std::min; using std::vector; lld n,m=2147483647999; vector<int> graph[1000010]; inline lld DFS(int,int); int main(){ scanf("%d",&n); for(int i=0;i<n-1;i++){ int a,b; scanf("%d%d",&a,&b); graph[a].push_back(b); graph[b].push_back(a); } DFS(0,-1); printf("%lld",m); return 0; } inline lld DFS(int k,int f){ lld size=1; lld sub=0; for(int i=0;i<graph[k].size();i++){ if(graph[k][i] == f)continue; lld each=DFS(graph[k][i],k); sub=max(each, sub); size+=each; } m = min(m,max(sub,(n-size))); return size; }

題目連結: http://tioj.infor.org/problems/1945 這題看到他詢問的次數後，應該很容易想到我們的上限就是$N+\log_2 N+2$，那那$N$必定是先單點詢問一遍，然後$\log_2 N$就是二分搜誰說謊，值得注意的是，你發現右半塊沒問題後不能又去問左半塊，要直接問左半塊的小孩，不然Query的次數會變成$2 \times N$，如果要確認會不會CE之類的話或詢問太多次，可以複製我下面的標頭檔，大概這樣吧 #include <cstdio> #define N 131072 #include "lib1945.h" int q[N+5]; int arr[N+5]; int sum[N+5]; inline int query(int l,int r){ return (l==0)?sum[r-1]&1:(sum[r-1]-sum[l-1])&1; } inline void check(int l, int r){ if(r-l==1){ int k = Query(1,q+l); if(k!=query(l,l+1)) arr[l]=Query(1,q+l); }else{ int m=(l+r)/2; int fromXian = Query(m-l, q+l); int fromOrigin = query(l,m); if(fromOrigin == fromXian) check(m,r); else check(l,m); } } int main(){ Init(); for(int i=0;i<N;i++) q[i]=i; for(int i=0;i<N;i++) arr[i]=Query(1,q+i); sum[0]=arr[0]; for(int i=1;i<N;i++) sum[i] = sum[i-1]+arr[i]; check(0,N); for(int i=0;i<N;i++) printf("%d ",arr[i]); return 0; } 附上我自己在用的lib1945.h #include <

題目連結: http://tioj.infor.org/problems/1040 這題算是數學題吧(?，但也不是什麼難的數學，先說連分數的基本求法就是直接算$\lfloor \frac{a}{b} \rfloor$這東東就會是第一個整數，那顯然的$\frac{a}{b} - \lfloor \frac{a}{b} \rfloor$會是後面那串分數，那就再看$\frac{1}{\frac{a}{b} - \lfloor \frac{a}{b} \rfloor}$(=$\frac{b}{a - b \lfloor \frac{a}{b} \rfloor}$)然後用跟上面同樣的方法算下去，直到$\frac{a}{b} - \lfloor \frac{a}{b} \rfloor = 0$時停止，但是我們在實作時不能真的用double之類的，不然你可能會被浮點數誤差搞死(或許只是我太廢拉XD，所以要做一點基本的數學運算，這邊就不贅述，大概從我的code應該就可看出來在幹嘛了。 溫馨小提示(?有可能一開始b就是0 #include <stdio.h> void weirdGCD(int,int,bool); int main(){ int n; scanf("%d",&n); while(n--){ int a, b; scanf("%d%d",&a,&b); printf("%d/%d = %d",a,b,a/b); weirdGCD(a,b,0); puts(""); } } void weirdGCD(int a,int b,bool tf){ if(b==0)return; int c=a/b; if(!tf){ weirdGCD(b,a-b*c,1); }else if(a-b*c == 0){ printf("+1/%d",c); return; }else{ printf("+1/{%d",c); weirdGCD(b,a-b*c,1); putchar('}'); } }

題目連結: http://tioj.infor.org/problems/1209 直接BFS跑一遍，看他有沒有被設過了，如果有就看他是不是跟他爸一樣，如果沒有就把他設成跟他爸一樣 #include <stdio.h> #include <vector> #include <queue> #include <bitset> #define PB push_back using std::vector; using std::bitset; using std::queue; bitset<40000 + 10> checked; bitset<40000 + 10> which; int main(){ int n,m; scanf("%d %d",&n,&m); while(n!=0||m!=0){ checked=0; which=0; vector<int> graph[40000 + 10]; for(int i=0;i<m;i++){ int a,b; scanf("%d %d",&a,&b); graph[a].PB(b); graph[b].PB(a); } queue<int> q; bool ok=true; for(int i=1;i<=n;i++){ if(checked[i]) continue; checked[i]=1; which[i]=1; q.push(i); while(!q.empty()){ int cur = q.front(); q.pop(); for(int j=0;j<graph[cur].size();j++){ if(checked[graph[cur][j]]){ if(which[graph[cur][j]] == which[cur]){ ok=0; break; } }else{ checked[graph[cur

題目連結: http://tioj.infor.org/problems/1194 本題我覺得答案超難想的...而且我是被別人雷到說這題答案很簡單，然後猜那應該是先手必勝，寫一下發現WA，然後發現他的n似乎沒範圍，所以不能用unsigned long long之類的讀，直接開個char array就好，反正他是沒用的資訊(?。詳細證明我是看了 傅子睿大大的解釋 我才懂。轉述一下，因為假設若本盤面沒有一我就會贏，那因為我拿任何數都會拿到一，所以就同樣方式拿就會贏了，但倘若沒有一我會輸，那加進一後，我就挑一，那對面就輸了 #include <stdio.h> char s1[10001], s2[10001]; int main(){ char n[10001]; scanf("%s",n); while(n[0]!='0'){ scanf("%s %s",s1,s2); printf("%s\n",s1); scanf("%s",n); } return 0; }

題目連結: http://tioj.infor.org/problems/1440 因為本題保證: 營養越高價錢越高，而且都只剩下一份 ，所以可以直接把所有食物都按照價錢或營養價值排好序，然後也把每個人需要的營養排序，然後直接$O(m)$掃過去找最小且符合條件的，然後加起來 #include <stdio.h> #include <algorithm> typedef long long lld; using std::sort; struct food{ int price, value; }; int people[1000000 + 10]; food breakfast[1000000 + 10]; inline bool cmp(food a,food b){ return a.price<b.price; } int main(){ int n,m; scanf("%d",&n); for(int i=0;i<n;i++) scanf("%d",&people[i]); scanf("%d",&m); for(int i=0;i<m;i++){ scanf("%d",&breakfast[i].value); scanf("%d",&breakfast[i].price); } sort(people,people+n); sort(breakfast,breakfast+m,cmp); lld ans=0; int pointer=0; for(int i=0;i<m;i++){ if(breakfast[i].value>=people[pointer]){ ans+=breakfast[i].price; pointer++; if(pointer>=n)break; } } if(pointer < n) puts("Impossible."); else printf("%lld",ans); return 0;

題目連結: http://tioj.infor.org/problems/1465 本題其實跟 TIOJ 1432 很像，一樣都二分搜答案，上界是序列和，下界是序列中最大值-1，不過他比較麻煩的地方是他在輸出時要把劃分好的結構輸出，所以當我們搜到答案以後，還要再從後面爬一遍，然後看要把分隔符號塞在那，不過為何是從後面爬呢，因為他想要讓前面的人的項數最少，那就是要讓後面的人項數最多，所以就讓後面每個人都拿到極限就好，另外一個值得注意的重點是因為他要讓每個人都抄到書，所以我們還要判斷一下剩下的項數根剩下的人數是否一樣了，若是就要在每個地方加上分隔符號 #include <stdio.h> #include <vector> typedef long long lld; #define PB push_back using std::vector; int n,m; int arr[500 + 10]; inline bool test(int); int main(){ int t; scanf("%d",&t); while(t--){ scanf("%d %d",&n,&m); lld l=0,r=0; for(int i=0;i<n;i++){ scanf("%d",&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; } vector<int> point; lld plus=0; int p = m-2; for(int i=n-1;i>=0;i--){ if(plus + arr[i] > r){ plus = arr[i]; point.PB(-1); p--; }else{ if(i == p){ point.PB(-1); p--; }

題目連結: http://tioj.infor.org/problems/1432 本題直接二分搜答案吧，值得注意的是最初始的上界顯然是數列和，但下界要注意的是它是數列中的最大值-1，因為顯然小於最大值-1的數一定會讓他壞掉，然後驗證二分搜就直接跑過去算，大概醬吧XD #include <stdio.h> typedef long long lld; int n,m; lld arr[1000 + 10]; inline bool test(lld); int main(){ scanf("%d %d",&n,&m); while(n!=0 || m!=0){ 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); scanf("%d %d",&n,&m); } } 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; }else plus+=arr[i]; } return 1; }

題目連結: http://tioj.infor.org/problems/1936 這題其實我覺得滿難的，一開始我一直以為他是簡單的矩陣乘法題，結果發現時間好像會超時，然後看了2015校隊培訓講義，發現原來是某種隨機演算法，想說那就直接隨機戳驗驗看吧，結過送了後一直TLE才估了一下複雜度發現也還是慘慘的，然後就莫名被雷到了，發現原來是隨機生成一個$n \times 1$的矩陣然後跟其他人乘，然後因為矩陣乘法有交換律(若$A \times B = C$，則$A \times B \times L = C \times L \rightarrow A \times (B \times L) = C \times L $)，所以若發現$ABL \neq CL$，那AB不等於C，但若$ABL=CL$也不代表$AB=C$所以多生個幾個L算一下吧 #include <stdio.h> #include <stdlib.h> #include <time.h> typedef long long lld; lld mA[1024 + 10][1024 + 10], mB[1024 + 10][1024 + 10], mC[1024 + 10][1024 + 10], l[1024 + 10]; int n; inline void times(lld[][1024+10],lld[],lld[]); inline bool same(lld[],lld[]); int main(){ srand(time(NULL)); int T; gn(T); while(T--){ gn(n); for(int i=0;i<n;i++) for(int j=0;j<n;j++) scanf("%lld",&mA[i][j]); for(int i=0;i<n;i++) for(int j=0;j<n;j++) scanf("%lld",&mB[i][j]); for(int i=0;i<n;i++) for(int j=0;j<n;j++) scanf("%lld",&

題目連結: http://tioj.infor.org/problems/1196 雖然本題理應是要DP，但其實n小小的(才10而已)，直接BFS甚至DFS就好了XD #include <stdio.h> int size, maze[11][11]; int DFS(int x, int y, int val){ if(maze[x][y] == 22) return val; else if(maze[x][y] == -1) return -1; else{ if(x<size-1 && y<size-1){ int a = DFS(x+1, y, val + maze[x][y]); int b = DFS(x, y+1, val + maze[x][y]); return (a>b)?a:b; }else if(x < size-1) return DFS(x+1, y, val+maze[x][y]); else return DFS(x, y+1, val+maze[x][y]); } } int main(){ scanf("%d\n",&size); for(int i=0;i<size;i++){ for(int j=0;j<size;j++){ char c=getchar(); maze[i][j] = (c=='A') ? 71 : (c=='B') ? 22 : (c=='X') ? -1 : c-'0'; } getchar(); } int ans=DFS(0,0,-71); if(ans == -1) puts("X"); else printf("%d",ans); return 0; }

題目連結: http://tioj.infor.org/problems/1029 本題第一眼看到可能會覺得是greedy，但其實這題不能greedy或者是我想不到好的準則XD，那不能greedy的話怎麼辦？就DP吧。不過說的簡單，實際上該如何DP呢？首先可以發現每次你要拿左邊或右邊都是希望拿了之後對方拿到的可以最小，所以不妨就讓子問題變成扣掉這格後對方可以拿到多少，基準點則是在只剩一個的時候，那必定只能拿到那格，有了這個之後就可以開始DP囉~因為所有區間總共只有$O(n^2)$個，所以總複雜度就$O(n^2)$ #include <stdio.h> #include <bitset> #include <unordered_map> using std::bitset; using std::unordered_map; struct q{ int first, second; }; int arr[1000 + 10]; bitset<20000000 + 10> done; unordered_map<int,q> saved; q ask(int,int,bool); int main(){ int n; scanf("%d",&n); for(int i=0;i<n;i++) scanf("%d",&arr[i]); q ans=ask(0,n,1); printf("%d %d",ans.first,ans.second); return 0; } q ask(int l, int r, bool fs){ const int key = l*10000+r; if(done[key]) return saved[key]; q rn={0}; if(l+1==r) fs?rn.first=arr[l]:rn.second=arr[l]; else{ q ll=ask(l+1,r,!fs); q rr=ask(l,r-1,!fs); if(fs){ if(ll.second < rr.second){ rn=ll; rn.first

題目連結: http://tioj.infor.org/problems/1026 本題因為都是走二的冪次，所以可以用二進位的思考方式想一下，就會發現本題可以先走要走的數字在二進位中位數全填一步(e.g. 11在二進位中表示為1101，故先走二進位為1111的15步)，然後再考慮要該往回走幾單位，那必定是全填1的減掉給的數字單位，那我們如果把一個格子改成0則是往回走$2 \times 2^{第幾格}$步，所以把那數除以二並跟原本全填一的數xor後，再看每一格即是答案。 #include <iostream> #include <bitset> using std::bitset; int main() { int n; scanf("%d",&n); int d=32-__builtin_clz(n); bitset<32> b; for(int i=0;i<d;i++) b[i]=1; b^=((b.to_ulong()-n)>>1); printf("%d\n",d); for(int i=0;i<d;i++) putchar(b[i]?'+':'-'); }

題目連結: http://tioj.infor.org/problems/1860 本題並不是甚麼演算法題，而是一種奇特(?的機率模型，有人稱作 秘書問題 ，其詳細的證明可見維基百科，這邊只講做法，就是若總共有n隻小蘿莉是你要比對的，則把前$\frac{n}{e}$當作基準來比會有最好的結果，所以當我們就在前$\frac{n}{e}$個中找出最大值，接下來若遇到比他大的就選，如果都沒有就選最後一個，大概就這樣吧 #include "lib1860.h" #include <math.h> int main(){ int n = Start_The_Loli_Dream(); while(n--){ int m = Count_How_Many_Loli(),max=-2147483648; int size = (int)round(m*(double)0.367879441171442); int a = m-size; while(size--){ int l = Get_Loli_Moeness(); if(l>max) max=l; } bool choosed=false; while(a--){ int l = Get_Loli_Moeness(); if(l>max){ You_Choose_This_Loli(); choosed=true; break; }

題目連結: http://tioj.infor.org/problems/1508 類背包問題，開一條長度為該序列總和的array，然後每次加入一個數都$O(sum)$跑過去比對新的數加進去後可以產生甚麼數，複雜度$O(n \Sigma n)$ #include <cstdio> #include <bitset> using std::bitset; inline long ABS(long a){ return a<0?-a:a; } int main() { int m,n; scanf("%d%d",&m,&n); while(m--){ int arr[100 + 10]; long sum=0; for(int i=0;i<n;i++){ scanf("%d",&arr[i]); sum+=arr[i]; } bitset<100000 + 10> b; b[0]=1; for(int i=0;i<n;i++){ bitset<100000 + 10>temp; for(int j=0;j<=sum;j++){ if(b[j]){ temp[j+arr[i]]=1; temp[ABS(j-arr[i])]=1; } } b=temp; } puts(b[0]?"Yes":"No"); } }

題目連結: http://tioj.infor.org/problems/1164 首先，不難發現本題要先找到鄉鎮最遠距離最小及最大的縣市，不過看起來這題限制滿死的，所以該怎麼做呢?這時就要想到C++內建的一個好用的函數minmax_element，於是就把他給的query塞進去，我們就找到了鄉鎮最遠距離最大及最小的縣市，取得後，就發現我們要找那兩個縣市的直徑(點與點之間最遠的距離)，那該怎麼找直徑呢?，就DFS兩次吧，先隨便從一個點開始DFS，找到最遠的那個點後，再從那個點DFS一遍，求出最大的距離即為該圖的直徑 #include "lib1164.h" #include <bitset> #include <utility> #include <algorithm> #include <vector> using namespace std; struct node{ int child,length; }; vector<node> graph[1000001]; bitset<1000001> list(0); pair<int,int> DFS(int which,int l){ int maxL=l,w=which,size=graph[which].size(); list[which]=1; for(int i=0;i<size;i++){ int next = graph[which][i].child; if (list[next]) continue; pair<int,int> tt = DFS(next,l+graph[which][i].length); if(tt.first>maxL){ maxL=tt.first; w=tt.second; } } return make_pair(maxL,w); } int main(){ int N = init(); vector<int> lol; for(int i = 0; i< N;i++){ lol.push_back(i); } auto result = minm

題目連結: http://tioj.infor.org/problems/1227 序列小技巧，若允許離線或像本題保證修改完才會有查詢，可以用類似懶標記的方式，把序列的修改存下來(修改$[L,R)$則在L加R減，反之亦然)，然後查詢時就把序列累推回去，並加回原序列，不過這題有點煩的地方是奇偶項要分成兩條處理 #include "lib1227.h" long long odd[1000003]={0},even[1000003]={0}; long long* D; int N; bool isSUM=false; void init(int n, long long d[]){ N=n; D=d; } void change(int a, int b, long long k){ if(a%2==0){ //a是偶數 even[a/2]-= k; odd[a/2] += k; if((b-a)%2==0){ //共有奇數個 //因a是偶數，故b為偶 even[b/2+1]+=k; odd[b/2] -=k; }else{ //共有偶數個 //因a是偶數，故b為奇 even[b/2+1]+=k; odd[b/2+1] -=k; } }else{ //a是奇數 even[a/2+1] += k; odd[a/2]-= k; if((b-a)%2==0){ //共有奇數個 //因a是奇數，故b為奇 even[b/2+1]-=k; odd[b/2+1] +=k; }else{ //共有偶數個 //因a是奇數，故b為偶 even[b/2+1]-=k; odd[b/2]+=k; } } } long long query(int c){ if(!isSUM){ for(int i=1;i<N/2;i++){ odd[i] += odd[i-1]; even[i]+=even[i-1]; } if(N%2==1) even[N/2]+=even[N/2-1]; isSUM=true; } if(c%2==0) return D[c]+even[

題目連結: http://tioj.infor.org/problems/1354 因為不確定題目的範圍所以先開個long long壓壓驚(?，這題也是一樣，矩陣乘法快速冪，因為把圖用鄰接矩陣存下來後，其的n次方就是任意點走到任一點走n步的可能方法總數。只是因為也不確定題目給的n是否遞增，所以就把他排個序，然後再做矩陣快速冪，理論上應該會比較快(?，複雜度$O(t log_2 t + log_2 n)$ #include <stdio.h> #include <algorithm> typedef long long lld; inline void gn(lld &_){_=0;char c=getchar();while(c<'0'||c>'9')c=getchar();while(c>='0'&&c<='9')_=_*10+c-'0',c=getchar();} using std::sort; using std::swap; struct inp{ lld i, val; }; inline void matrixTimes(lld [][4],lld [][4],lld [][4]); bool cmp(inp a,inp b){ return a.val<b.val; } int main(){ lld n; gn(n); auto v = new inp[n]; auto ans = new lld[n]; for(lld i=0;i<n;i++){ v[i].i=i; gn(v[i].val); } sort(v,v+n,cmp); inp k = v[0]; auto matrix = new lld[4][4]; auto ta = new lld[4][4]; auto tb = new lld[4][4]; for(int i=0;i<4;i++){ for(int j=0;j<4;j++){ matrix[i][j]=(i==j); ta[i][j]=!(i==j); } } while(k

題目連結: http://tioj.infor.org/problems/1013 其實我覺得題敘沒講清楚，火只會跟人一樣蔓延在可以走的地方.... 先BFS個每個點會在第幾分鐘被火燒到，注意E是不會被燒到的，所以可以偷偷先把它改成不可通行(?，之後再BFS一次找最短路徑。 #include <stdio.h> #include <algorithm> #include <queue> #define INF 2147483647 using std::min; using std::queue; bool graph[10][17] = { {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, {0,1,1,1,0,1,1,1,1,1,1,1,0,0,1,1,0}, {0,0,1,1,0,1,1,1,1,0,1,0,1,0,1,1,0}, {0,1,1,1,1,1,1,0,1,0,0,1,0,0,1,0,0}, {0,1,1,0,0,1,1,1,0,0,1,1,0,0,1,0,0}, {0,0,1,1,1,1,1,0,0,1,1,0,1,0,1,1,0}, {0,1,1,1,1,0,1,1,1,1,1,1,1,1,1,1,0}, {0,1,1,1,1,1,0,0,0,0,1,0,1,1,1,0,0}, {0,0,0,0,1,0,1,0,1,1,1,1,1,1,1,1,0}, {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0} }; struct ff{ int x,y,t; }; struct mm{ int x,y,t,v; }; int tFire[10][17]={0}; int fX,fY; int t; int sX,sY, eX,eY; int main(){ scanf("%d%d%d%d%d%d%d",&fX,&fY,&t,&sX,&sY,&eX,&eY); graph[eX][eY]=0; queue<ff> q1; ff temp; temp.x=fX; temp.y=fY; temp.t=1; q1.push(temp);

題目連結: http://tioj.infor.org/problems/1338 先小抱怨個，我因為通常都比較節省記憶體(?所以原本sparse table用vector array，結果卻因為push_back而被一直卡到時限(這題有夠緊的阿QAQ)，還有我不小心算錯範圍...。 正題:首先很明顯的可以知道若$gcd(C_{[L,R)})=C_k$（$L\leq k< R$），則$C_{[L,R)}$有因數元素。此外若$C_{[L,R)}$有因素元素，則其必定為$min(C_{[L,R)})$。合併兩個條件後，就發現本題可以轉化為類RMQ問題，開個sparse table存gcd跟min，那我們就可以$O(1)$做到query。 #include <algorithm> #include "lib1338.h" typedef long long lld; using std::min; using std::__gcd; lld minSTable[21][1000005]; lld gcdSTable[21][1000005]; void init(int N, lld arr[]){ int obov=0; for(int i=0;i<N;i++,obov++){ minSTable[0][obov]=arr[i]; gcdSTable[0][obov]=arr[i]; } for(int i=1;(1<<i)-1<N;i++){ obov=0; for(int j=0;(1<<i)+j-1<N;j++,obov++){ lld mA = minSTable[i-1][j]; lld mB = minSTable[i-1][j+(1<<(i-1))]; lld gA = gcdSTable[i-1][j]; lld gB = gcdSTable[i-1][j+(1<<(i-1))]; minSTable[i][obov]=min(mA,mB); gcdSTable[i][obov]=__gcd(gA,gB); } } } int query(int L, int R){

題目連結: http://tioj.infor.org/problems/1308 可以看出來很明顯是就是$H{n\choose m}$然後高中數學可以知道$H{n\choose m}=C{(n+m-1)\choose m}=\frac{n!}{m! \times (n-m)!}$ #include <stdio.h> int main() { int n,m; scanf("%d %d",&n,&m); while(n!=0){ double ans=1; int k = n+m-1; for(int i=1;i<=m;i++,k--){ ans*=(double)k; ans/=(double)i; } printf("%.lf\n",ans); scanf("%d %d",&n,&m); } return 0; }

題目連結: http://tioj.infor.org/problems/1823 本地建表暴搜亂搞題(?，可以發現若是那個數無法用這些操作變成一，那必然他是會循環的，所以直接開個表看他有沒有重複就好，附個暴搜用的python code: def modify(x,l): if x in l: return False length = len(str(x)) l.append(x) if x == 1: return True elif length == 1: return modify(x**2,l) else: temp=0 for k in str(x): temp += int(k)**2 return modify(temp,l) count = 0 test = 1 while count <= 10000: if modify(test,[]): count+=1 if count in [10,50,100,1000,10000]: print(test) test+=1 Main Code: main(){write(1,"44\n320\n694\n6899\n67169\n",22);exit(0);}

題目連結: http://tioj.infor.org/problems/1871 裸區間極值題(RMQ)，寫個sparse table就好了，這裡附上個我自己debug用時用的lib1871.h lib1871.h #include <utility> #include <stdio.h> namespace futa{ int size; int *arr; int q; int init(){ scanf("%d",&size); arr = new int[size]; return size; } int* momo_gives_you_list_of_futa(){ for(int i=0;i<size;i++){ scanf("%d",&arr[i]); } return arr; } int momo_tells_you_q(){ scanf("%d",&q); return q; } std::pair<int,int> momo_asks(){ int l,r; scanf("%d %d",&l,&r); return std::make_pair(l,r); } void you_tell_momo(int a){ printf("ANS:%d\n",a); } } Main Code: #include "lib1871.h" #include <utility> #include <vector> #include <algorithm> using std::pair; using std::vector; using std::min; vector<int> sTable[30]; inline int query(int,int); int main(){ int size = futa::init(); auto arr = futa::momo_gives_you_list_of