oToToT的code收藏區

題目連結: http://tioj.infor.org/problems/1732 應該不難發現買當勞要建的位置就是所有資料的中位數，所以就排個序就可以找到了，複雜度$O(n log n)$ #include <bits/stdc++.h> using namespace std; #define N 100000 int arr[N+5]; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n; while(cin>>n){ for(int i=0;i<n;i++) cin>>arr[i]; sort(arr, arr+n); int mid; if(n&1) mid=arr[n>>1]; else mid = (arr[n>>1]+arr[(n>>1) - 1])>>1; int ans=0; for(int i=0;i<n;i++) ans+=abs(arr[i]-mid); cout<<ans<<'\n'; } return 0; } 不過突然看到聖福學長用超快的作法過了這題，想了三十秒才發現其實根本可以用nth_element做到$O(n)$的複雜度 #include <bits/stdc++.h> using namespace std; #define N 100000 int arr[N+5]; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n; while(cin>>n){ for(int i=0;i<n;i++) cin>>arr[i]; nth_element(arr, arr+(n>>1), arr+n); int mid; if(n&1) mid=arr[n>>1]; else{

題目連結: http://tioj.infor.org/problems/1088 標準的nim遊戲。本題如果知道nim的玩法應該就秒解了，因為nim的遊戲方法就是讓所有數xor起來為零，因為當一個人拿到xor直為零的時候他必定沒辦法再讓版面的xor值為零，而且你也一定可已把盤面xor值弄成零，所以就看兩下吧XD p.s附個我寫的lib1088.h lib1088.h #include <cstdio> int __stones[3]; void Initialize(int *a,int *b,int *c){ printf("How many stones:"); scanf("%d%d%d",a,b,c); __stones[0]=*a;__stones[1]=*b;__stones[2]=*c; } void Take_Stone(int pile_no, int num, int *com_pile, int *com_num){ __stones[pile_no-1]-=num; printf("Now: "); for(int i=0;i<3;i++) printf("%d ",__stones[i]); puts(""); bool flag=1; for(int i=0;i<3;i++) if(__stones[i]>0)flag=0; if(flag){ puts("You Lose!"); exit(0); } printf("Chosse and sum:"); scanf("%d%d",com_pile, com_num); __stones[(*com_pile)-1]-=(*com_num); for(int i=0;i<3;i++) printf("%d ",__stones[i]); puts(""); } 1088.cpp #include "lib1088.h" int ss[3]; int main(){ In

題目連結: http://tioj.infor.org/problems/1137 應該不難看出來題目就是在求一個點使得拔掉後會讓兩個區塊不連通，那這正好就是關節點。而關節點的求法是什麼呢？這裡採用tarjan的算法： 在以某一特定點DFS的情況下，會長出一個類似樹的部分，只不過有些邊會連回上面，也就是樹上不該有的邊，這裡稱其為「回邊」，而正常定義的樹上會有的邊，這裡稱其為「樹邊」。 接著，定義一種值$ low(x), x \in V$其中V為所有點的點集，low(x)為點x不透過連接自己的樹邊，所能到達的深度的最小值(往上最遠可以到哪)，仔細觀察後發現，當一個點p的小孩中，有一個點q的low值$ \leq $自己的深度，意即其必須透過p才能回到上面，那明顯p就會是一個關節點(因為拔掉p之後q就會與一些人不連通了)，不過特別注意一下根的部分，因為顯然所有人的low值都$ \leq $根的深度，但是根不一定關節點，細想一下後會發現根不是關節點的條件為他只有一個小孩的時候，那到這裡算法的架構就大概完整了。 至於low值維護的方式就是邊dfs邊用類似dp的方式維護即可了。 #include <bits/stdc++.h> using namespace std; #define N 10000 vector<int> graph[N+5]; int low[N+5]; bool visited[N+5]; set<int> ap; void dfs(int,int,int); int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int t;cin>>t; while(t--){ ap.clear();fill(visited, visited+N+5, false); int n,m;cin>>n>>m; for(int i=0;i<m;i++){ int st,ed;cin>>st>>ed; graph[st].push_back(ed); graph[ed].push_back(st); } dfs(1,1,1); cout<<ap.siz

題目連結: http://tioj.infor.org/problems/1559 數學不好，想了一下下。我的作法是求出給定兩個點的距離跟夾角，之後以其中一個點為暫時原點，然後用極座標轉回普通座標方式的作法找到60度的點，再平移回剛剛的暫時原點即可。 #include <bits/stdc++.h> using namespace std; typedef pair<double,double> PDD; #define X first #define Y second #define deg2rad(x) (acos(-1)*x/180.) int main(){ PDD a,b, ans1, ans2; while(cin>>a.X>>a.Y>>b.X>>b.Y){ double dis = sqrt((a.X-b.X)*(a.X-b.X)+(a.Y-b.Y)*(a.Y-b.Y)); double theta = atan2((b.Y-a.Y), (b.X-a.X)); ans1 = {a.X+dis*cos(deg2rad(60)+theta), a.Y+dis*sin(deg2rad(60)+theta)}; ans2 = {a.X+dis*cos(deg2rad(300)+theta), a.Y+dis*sin(deg2rad(300)+theta)}; if(ans2<ans1) swap(ans1,ans2); cout<<setprecision(3)<<fixed<<ans1.X<<' '<<ans1.Y<<' '<<ans2.X<<' '<<ans2.Y<<'\n'; } return 0; }

題目連結: http://tioj.infor.org/problems/1586 照著做就好了，練習scanf跟printf #include <cstdio> int main(){ int n;scanf("%d",&n); while(n--){ char s[60]; scanf("%s",s); printf("%s, happy new year!!!\n",s); } return 0; }

題目連結: http://tioj.infor.org/problems/1679 把東東吃進來後排序並取到要取的位置即可，而且C++中有個東西叫做pair，他比大小自動就是先比第一項再比第二項 #include <bits/stdc++.h> using namespace std; typedef pair<int,char> PCI; #define N 52 PCI cards[N]; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n;cin>>n; for(int i=0;i<n;i++) cin>>cards[i].second>>cards[i].first; sort(cards,cards+n,[](PCI a, PCI b){return a>b;}); int m;cin>>m; cout<<cards[m-1].second<<' '<<cards[m-1].first; return 0; }

題目連結: http://tioj.infor.org/problems/1657 兩層for迴圈，裸裸的做就好了 #include <bits/stdc++.h> using namespace std; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n,m; while(cin>>n>>m){ for(int i=1;i<=n;i++){ for(int j=1;j<m;j++) cout<<i<<'*'<<j<<'='<<i*j<<' '; cout<<i<<'*'<<m<<'='<<i*m<<'\n'; } } return 0; }

題目連結: http://tioj.infor.org/problems/1745 這題應該不難想到DP的方式\[ f(x) =ax^2+bx+c \\ dp[i] = \max_{0 \leq j < i}(f(\sum_{k=i+1}^{j}arr[k]) + dp[j]) \]，但是也不難發現它的複雜度會是$O(n^2)$。這時就要優化他，可以發現它可以套用斜率優化，因為對轉移式做一些移項跟變數變換後會變成\[ S_i = \sum_{j=0}^{i} arr[j]\\ dp[i] = \max_{0 \leq j < i}(-2aS_j \cdot S_i + a{S_j}^2 - bS_j + dp[j]) + a{{S_i}^2} + bS_i + c \]那很明顯的可以發現若把j看成是定值，i看成是變數的話，就會發現max裡面那一坨就是一個一次函數，而且斜率會隨j增加而增加。然後我們會發現自己每次在轉移時都會比之前多一項j，所以其實可以看成每次轉移時加入一條線(或每次轉移後加入一條線)，並且會發現當這條線(也就是這個j)，已經有比他新的線比他好時，那他就不會被轉移到，此外，如果有些線在超越比他新的線前，已經被某條更新的線超越，則他也不會是可以拿來轉移的。有了這幾個性質，我們就可以發現要判斷有沒有新的線比他好，就等價於在一個deque中(裡面存著所有先前可以轉移的線)，比較他的前兩個元素，如果第一項在帶入i時會比較小，那他就符合前面所說的第一種情況，可以被移除；第二種情況則是在將當前的線放入deque時，比較pos1(最末項跟當前項的交點)與pos2(最末項跟次末項的交點的x座標)，如果pos1 < pos2，那最末的那條線就可以砍掉。發現每條線只會進deque一次，出一次，所以複雜度就壓到$O(n)$了 #include <bits/stdc++.h> using namespace std; typedef long long lld; #define INF 2147483647 #define N 1000000 lld a,b,c; lld arr[N+5], sm[N+5], dp[N+5]; inline bool detectBeyond(int,int,int); inline lld f(int,i

題目連結: http://tioj.infor.org/problems/1142 笨笨的我完全想不出來該怎麼寫...最後是被雷了才知道的QAQ。不過明顯有幾個點大家應該早就知道，本題其實就是要找最長路，並且看該路上有幾個節點，且如果有兩個人權重相同，則兩個人都要走，因此不妨先求出走到每個點所要花的時間，再從最大的開始dfs回去，這裡為了方便，弄了一個假節點，與所有點連接，這樣比較方便在dfs回去時看誰最大 #include <bits/stdc++.h> using namespace std; #define N 100000 #define PB push_back int val[N+5], deg[N+5], valSm[N+5], cnt=0; vector<int> graph[N+5], rgraph[N+5]; bitset<N+5> visited; void dfs(int); int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n, m;cin>>n>>m; for(int i=1;i<=n;i++){ cin>>val[i]; valSm[i]=val[i]; } for(int i=0;i<m;i++){ int st, ed;cin>>st>>ed; deg[ed]++; graph[st].PB(ed); rgraph[ed].PB(st); } for(int i=1;i<=n;i++) rgraph[N+2].PB(i); queue<int> qq; for(int i=1;i<=n;i++) if(deg[i]==0) qq.push(i); while(!qq.empty()){ int tp=qq.front();qq.pop(); for(auto i:graph[tp]){ deg[i]--; if(deg[i]==0) qq.push(i); valSm[i]=max(valSm[i], valSm[tp]+val[i]); } } d