oToToT的code收藏區

題目連結: http://tioj.infor.org/problems/1105 如果我沒猜錯的話，這題應該可以用旋轉卡尺做到$O(n log n)$，但是我實在不熟，加上本題範圍$O(n^2)$就可以過了，所以我就直接寫個裸裸的做法了 #include <bits/stdc++.h> using namespace std; #define N 3000 typedef pair<int,int> PII; #define X first #define Y second #define DIS(a,b) ((arr[a].X-arr[b].X)*(arr[a].X-arr[b].X)+(arr[a].Y-arr[b].Y)*(arr[a].Y-arr[b].Y)) PII arr[N+5]; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n;cin>>n; while(n>0){ int a=0, b=0; for(int i=0;i<n;i++) cin>>arr[i].X>>arr[i].Y; for(int i=0;i<n;i++) for(int j=i+1;j<n;j++) if(DIS(a,b) < DIS(i, j)) a=i, b=j; cout<<a<<' '<<b<<'\n'; cin>>n; } return 0; }

題目連結: http://tioj.infor.org/problems/1271 應該很明顯可以用持久化資料結構做掉，如果知道有rope這東東的話可以直接拿來用，這題就被秒掉了。不過我們還是該秉持個手寫資料結構，所以我就寫了個持久化treap，而因為我每次插入的時候都保證key是遞增的，所以可以不用寫split把它拆掉再合起來，算是一個小常數優化(?，不過注意一下因為treap並不是保證logN的，所以有可能有幾條太長的路徑，導致MLE掉，這裡可能要多試幾次，或者直接用個7122這神秘數字避免(? #include "lib1271.h" #include <random> #include <ctime> #include <algorithm> #define copyNode(a,b) a->l=b->l;\ a->r=b->r;\ a->val=b->val;\ a->pri=b->pri;\ a->key=b->key; #define N 1000000 std::minstd_rand rd(7122); struct Treap{ int key; unsigned short pri; char val; Treap *l, *r; Treap(){} Treap(char c,int k){ pri=rd(); key=k; val=c; l=r=nullptr; } }; int sizes[N+1]={0}; Treap* treaps[N+1]={nullptr}; int opt=0; Treap __[9*N]; int _sz=0; inline Treap* gNode(){return &__[_sz++];} inline Treap* gNode(char c, int k){ __[_sz].pri=rd(); __[_sz].key=k; __[_sz].val=c; __[_sz].l=__[_sz].r=nullptr; return &__[_sz++]; } Treap* Merge(Tre

題目連結: http://tioj.infor.org/problems/1853 本題似乎有DP作法，狀態可能是什麼，強制把前i個都轉成0跟1的方法數。不過，其實也可以greedy做，準則是:從右邊面看到左邊時，若看到一個0，則看其左邊是否也為0，若是的話就用翻的，反之則用點的。因為對於一個XXXXX101111的序列，若在0那點用翻的，則會將下一個一變成0，那必定之後又要用翻的，最後會變成XXXXX111111，花費兩個操作，但是用點的只要一個操作；另外一方面，對於一個XXXXX001111，如果都用點的，需花費兩操作，但是如果用翻的最多也是兩操作，並不會比較慘。 #include <bits/stdc++.h> using namespace std; #define N 10000000 char arr[N+5]; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n;cin>>n>>arr; int ans=0; bool cur=0; for(int i=n-1;i>=1;i--){ if(arr[i]=='0'+cur){ ans++; if(arr[i]==arr[i-1]) cur=!cur; } } if(arr[0]=='0'+cur) ans++; cout<<ans<<'\n'; return 0; }

題目連結: http://tioj.infor.org/problems/1115 計算幾何題OAO，我三角函數有點爛ww，不過大概就是y>0時，就是算整個原扣掉在下面那塊，也就是扇形減三角形，而y<0時，就只要算上面那塊，也就是扇形減三角形 #include <bits/stdc++.h> using namespace std; const double PI = acos(-1); int main(){ ios_base::sync_with_stdio(0);cin.tie(0); double x,y,r,ans; while(cin>>x>>y>>r){ double theta = acos(abs(y/r))*2; if(y>=r) ans=r*r*PI; else if(y<=-r) ans=0; else if(y<=0) ans = r*r*theta/2. - r*r*sin(theta)/2.; else ans = r*r*PI - r*r*theta/2. + r*r*sin(theta)/2.; cout<<fixed<<setprecision(2)<<ans<<'\n'; } return 0; }

題目連結: http://tioj.infor.org/problems/1289 N小小的，所以直接枚舉兩條邊，再看看他的第三邊存不存在就好，至於要如何快速看第三邊存不存在，可以考慮用個unordered_set存下每個邊的平方 #include <bits/stdc++.h> using namespace std; typedef long long lld; lld arr[2000]; unordered_set<lld> isset; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n; while(cin>>n){ isset.clear(); for(int i=0;i<n;i++) cin>>arr[i]; sort(arr,arr+n); int st; for(st=0;st<n&&arr[st]<=0;st++); for(int i=st;i<n;i++) isset.insert(arr[i]*arr[i]); int ans=0; for(int i=st;i<n;i++) for(int j=i+1;j<n;j++) if(isset.find(arr[i]*arr[i] + arr[j]*arr[j]) != isset.end()) ans++; cout<<ans<<'\n'; } return 0; }

題目連結: http://tioj.infor.org/problems/1369 裸裸的DFS題，遞迴遍歷過每個節點即可 #include <bits/stdc++.h> using namespace std; #define N 50000 int arr[N+5], tt=0; vector<int> graph[N+5]; void dfs(int); int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n;cin>>n; for(int i=1;i<=n;i++){ int k;cin>>k; while(k--){ int x;cin>>x; graph[i].push_back(x); } } dfs(1); for(int i=1;i<=n;i++)cout<<arr[i]<<'\n'; return 0; } void dfs(int x){ arr[x]=++tt; for(auto i:graph[x]) dfs(i); }

題目連結: http://codeforces.com/problemset/problem/782/B 其實本題是對答案二分搜，驗證方法是當你把時間乘上速率後可以得到每個人最遠走到哪，看有沒有交集就知道解是否合法，不過本題有更無腦的方式，那就是對集合點模擬退火(其實是因為我當時看一眼就想到這個做法就沒去想正解了XD #include <bits/stdc++.h> using namespace std; #define N 60000 double pos[N+5], speed[N+5]; int n; inline double getY(double x); int main(){ scanf("%d",&n); for(int i=0;i<n;i++)scanf("%lf",&pos[i]); for(int i=0;i<n;i++)scanf("%lf",&speed[i]); double rr=*max_element(pos,pos+n); double ll=*min_element(pos,pos+n); default_random_engine rEng(time(NULL)); uniform_real_distribution<double> Range(-1,1); uniform_real_distribution<double> expR(0,1); auto Random=bind(Range,rEng); auto expRand=bind(expR,rEng); int step=0; double pace=rr-ll, mini=0.95; double x=max(min(Random()*pace+ll, rr), ll), y=getY(x); while(pace>=1e-7){ double newX = max(min(x + Random()*pace, rr), ll); double newY = getY(newX); if(newY < y || expRand() < exp(-step))