oToToT的code收藏區

題目連結: http://tioj.infor.org/problems/1146 這題其實跟 [TIOJ]1428 很像，只是他不能快速冪，而是要$O(n)$做矩陣乘法，然後每次做完後就把答案加起來 #include <stdio.h> #include <algorithm> int size; auto graph = new int[35][35]; auto temp = new int[35][35]; inline void matrixTimes(int [][35], int[][35], int[][35]); int main(){ scanf("%d",&size); for(int i=0;i<size;i++){ char inp[35]; scanf("%s",inp); for(int j=0;j<size;j++){ temp[i][j]=i==j; graph[i][j]=inp[j]-'0'; } } int x,y,n,ans=0; scanf("%d\n%d\n%d",&x,&y,&n); while(n){ auto tp = new int[35][35]; matrixTimes(graph,temp,tp); std::swap(tp,temp); ans+=temp[x-1][y-1]; n--; } printf("%d",ans); return 0; } inline void matrixTimes(int a[][35], int b[][35], int c[][35]){ for(int i=0;i<size;i++){ for(int j=0;j<size;j++){ c[i][j]=0; for(int k=0;k<size;k++){ c[i][j] += a[i][k]*b[k][j]; } } } }

題目連結: http://tioj.infor.org/problems/1428 其實鄰接矩陣除了MLE外其實還有個功能，那就是你可以直接把他n次方，得到的就是任意兩點走n步有幾種走法的答案，然後n次方都可以用快速冪，所以這題其實就把圖用鄰接矩陣存起來，然後快速冪，複雜度$O(N^3 \log_2{L})$ #include <stdio.h> #include <algorithm> typedef long long lld; int n,m,q,l; auto graph = new lld[160][160]; auto temp0 = new lld[160][160]; auto temp1 = new lld[160][160]; inline void matrixTime(lld [][160],lld [][160],lld [][160]); int main(){ scanf("%d %d %d %d",&n,&m,&q,&l); for(int j=0;j<n;j++){ for(int k=0;k<n;k++){ graph[j][k]=(j==k)?1:0; } } for(int i=0;i<m;i++){ int s,e; scanf("%d %d",&s,&e); temp0[s][e]++; } bool which=0; while(l){ if(l&1){ auto tp = new lld[160][160]; matrixTime(graph,which?temp1:temp0,tp); std::swap(tp,graph); } l>>=1; if(which) matrixTime(temp1,temp1,temp0); else matrixTime(temp0,temp0,temp1); which=!which; } for(int i=0;i<q;i++){ int x,y; scanf("%d %d",&am

題目連結: http://tioj.infor.org/problems/1288 或 http://ioj.infor.org/problems/4 如果你用bottom-up思考方式想這題會發現這題很簡單，因為他要拿最多的石頭，所以必定是挑他下面那兩個比較大的，因此就把所有相鄰的兩個數相加後併到上面，重複做直到沒有上面為止，那那個數就是答案 #include <stdio.h> #include <vector> using namespace std; vector<int> tri[110]; int main(){ int size; scanf("%d",&size); for(int i=0;i<size;i++){ for(int j=0;j<=i;j++){ int temp_inp; scanf("%d",&temp_inp); tri[i].push_back(temp_inp); } } for(int i=size-1;i>0;i--){ for(int j=0;j<i;j++){ if(tri[i][j] > tri[i][j+1]){ tri[i-1][j] += tri[i][j]; }else{ tri[i-1][j] += tri[i][j+1]; } } } printf("%d",tri[0][0]); return 0; }

題目連結: http://ioj.infor.org/problems/19 因為$xor$有神奇(?的性質$a \oplus b = c \Longrightarrow a \oplus c = b$，所以就$O(n)$掃過去建好表，再$O(n)$掃一遍加起來，值得注意的是因為$a \oplus 0 = a$，所以若$x=0$，那要再減掉所有數的個數(自己不能算) #include <stdio.h> void gn(int &_){ _=0;char c=getchar(); while(c<'0'||c>'9')c=getchar(); while(c>='0'&&c<='9')_=_*10+c-'0',c=getchar(); } int MiccWan[100000 + 10]; int wayneTu[1000000 + 10] = {0}; int main(){ int t,x; long long edisonhello=0; gn(t);gn(x); for(int i=0;i<t;i++){ gn(MiccWan[i]); wayneTu[MiccWan[i]^x]++; } for(int i=0;i<t;i++){ edisonhello+=wayneTu[MiccWan[i]]; } if(x==0) edisonhello-=t; printf("%lld",edisonhello>>1); return 0; }

題目連結: http://tioj.infor.org/problems/1509 裸單點源最短路徑，直接寫個dijkstra就好了 #include <stdio.h> #include <vector> #include <queue> #include <bitset> #include <algorithm> using std::vector; using std::priority_queue; using std::bitset; using std::swap; struct node{ int vertex; int dis; }; class cmp{ public: bool operator ()(node a, node b){ return a.dis>b.dis; } }; bitset<1000000 + 10> poped; vector<node> forward[1000000 + 10], backward[1000000 + 10]; int dis[1000000 + 10]; priority_queue<node,vector<node>,cmp> pq; int main(){ //input int m,n; unsigned long long ans=0; scanf("%d %d",&m,&n); for(int i=0;i<n;i++){ node OAO; int a; scanf("%d %d %d",&a,&OAO.vertex,&OAO.dis); forward[a].push_back(OAO); swap(a,OAO.vertex); backward[a].push_back(OAO); } for(int i=0;i<=m;i++){ dis[i] = 2147483647; } dis[1] = 0; node f; f.dis = dis[1]; f.vertex = 1; pq.push(f); wh

題目連結: https://ioj.infor.org/problems/14 由題目可看出這是一個標準的線性遞迴，而居然是線性遞迴的話，那都可以用矩陣乘法搭配快速冪來讓時間複雜度降到$O(m^3 \log_2{(n-m)})$，然後不難發現其要用的$1 \times m$橫矩陣是$\left( \begin{array}{clr} 1 & 1 & \cdots & 1 \end{array} \right)$，而$m \times m$正方形矩陣則是$\left( \begin{array}{clr} k_{1} & 1 & 0 & 0 & \cdots \\ k_{2} & 0 & 1 & 0 & \cdots \\ k_{3} & 0 & 0 & 1 & \cdots \\ \vdots & \vdots & \vdots & \vdots & \ddots \\ k_{m} & 0 & 0 & 0 & \cdots \end{array} \right)$至於會溢位的部分則按照題敘，每次在做加法乘法之類的時候都模一次$10^9+7$，因為可以證明先算再模跟先模再算再模都會得到相同的結果的。 #include <stdio.h> #include <algorithm> typedef long long lld; const lld mmdd = 1000000007; lld m1[110][110]={0}; auto aas = new lld [110][110]; lld n,m; void qPow(lld); void matrixTimes(lld[][110],lld[][110],lld[][110]); int main(){ scanf("%lld %lld",&n,&m); for(lld i=0;i<m;i++){ scanf("%lld",&m1[i][0]); if(i+1<m) m1[i][i+1] = 1; }

題目連結: http://tioj.infor.org/problems/1277 本題等價於做最大子矩陣，而最大子矩陣就等於說枚舉所有高度的矩陣，並把他們都壓起來(同一位加一起)後做最長遞增子序列 #include <stdio.h> #include <vector> using std::vector; vector<long long> matrix[500 + 10]; int main(){ long long size, max=0, cur=0; scanf("%d",&size); for(int j=0;j<size;j++){ matrix[0].push_back(0); scanf("%lld", &matrix[0][j]); if(cur<0) cur=0; cur += matrix[0][j]; if(cur>max) max=cur; } for(int i=1;i<size;i++){ cur = 0; for(int j=0;j<size;j++){ matrix[i].push_back(0); long long t; scanf("%lld", &t); matrix[i][j] = matrix[i-1][j] + t; if(cur<0) cur=0; cur += matrix[i][j]; if(cur>max) max=cur; } for(int k=1;k<=i;k++){ cur=0; for(int j=0;j<size;j++){ if(cur<0) cur=0; cur += (matrix[i][j] - matrix[i-k][j]); if(cur>max) max=cur; } } } printf("%lld\n", max); return 0; }

題目連結: http://tioj.infor.org/problems/1009 我的作法是先把它轉成秒數，然後相減如果變負的就多加一天的秒數，最後再轉回原本的格式 #include <iostream> #include <string> using namespace std; inline int c2i(char k){ return k-'0'; } inline string i2s(int n){ if(n<10) return "0"+to_string(n); return to_string(n); } inline int t2i(string k){ return ((c2i(k[0])*10+c2i(k[1]))*60 + c2i(k[3])*10+c2i(k[4]))*60 + c2i(k[6])*10+c2i(k[7]); } inline string i2t(int n){ string a = i2s(n/3600) + ":"; n-=n/3600*3600; a+=i2s(n/60) + ":"; n-=n/60*60; a+=i2s(n); return a; } int main(){ string n,m; int Tn,Tm; cin>>n; cin>>m; Tn=t2i(n); Tm=t2i(m); if(Tm<Tn) Tm+=86400; cout<<i2t(Tm-Tn)<<endl; return 0; }

題目連結: http://tioj.infor.org/problems/1005 就按照題目做，直接$O(n^2)$把所有組合跑過一遍做gcd，然後算就好，但要記得處理一下浮點數誤差 #include <stdio.h> #include <math.h> int gcd(int a, int b){ int t; if(b>a){ t = b; b = a; a = t; } int last; do{ a %= b; last = a; t = b; b = a; a = t; }while(last!=0); return a; } void read(int sum){ if(sum!=0){ int a = 0, count = 0, all = 0; int temp[50]; for(int i = 0;i<sum;i++){ scanf("%d",&a); temp[i] = a; } for(int i = 0;i<sum;i++){ for(int j = i+1;j<sum;j++){ all++; if(gcd(temp[i], temp[j])==1){ count++;

題目連結: http://tioj.infor.org/problems/1006 基本大數，在這裡我用string做了個簡單的大數，實際上真的要用時，可能還是會採用int array之類的來壓縮空間，且也比較快 #include <iostream> #include <string> using namespace std; namespace BigInt{ //every number must be positive using namespace std; inline int c2i(char n){ return n-'0'; } inline string i2s(int n){ return to_string(n); } inline string n0(int n){ string k=""; while(n--){ k+="0"; } return k; } inline string c2s(char n){ return string(1,n); } inline string r0(string a){ string n=""; bool flag=false; for(unsigned int i=0;i<a.size();i++){ if(a[i]!='0'&&!flag) flag=true; if(flag) n+=c2s(a[i]); } if(n=="") n="0"; return n; } inline int cSize(string a,string b){ string n=r0(a),m=r0(b); if(n==m){ return 0; } if(n.size()>m.size()){ return 1; }else if(n.size()<m.size()){ return -1; }else{ for(unsigned int i=0;i<

題目連結: http://tioj.infor.org/problems/1002 不難發現本題的規律，也就是對於f(n)他是個遞增的奇數數列，而當n為2的冪次時，f(n)重新從1開始遞增 嚴謹證明請見維基百科 https://zh.wikipedia.org/wiki/约瑟夫斯問題 #include <stdio.h> int main(){ int a,b=1; scanf("%d",&a); while(a>=b*2){ b*=2; } printf("%d\n",(a-b)*2+1); return 0; }

題目連結: http://tioj.infor.org/problems/1003 雖然本題叫我們使用遞迴，但其實不難發現這題中f(x)的規律，所以其實直接數學解解掉就好了XD #include <stdio.h> int main(){ int a = 0; scanf("%d",&a); printf("%d",a*(a+1)/2+1); return 0; }

題目連結: http://tioj.infor.org/problems/1002 基礎水題，學習基本io，用cin+cout或scanf+printf都可，我還是用習慣用的scanf+printf做 #include <stdio.h> int main() { int a,b; scanf("%d %d",&a, &b); printf("%d\n",a+b); return 0; }

題目連結: http://tioj.infor.org/problems/1001 經典水題一題，不管用cout,puts,printf,write都可，這裡我用我習慣的printf寫 #include <stdio.h> int main(){ printf("Hello Tmt World XD!"); return 0; }