PolarisChiba的code收藏區

LINK： https://tioj.infor.org/problems/1530 　　我看了別人的code才會的orz 　　簡單來說，這題要求一條等級嚴格遞增且使的時間耗費最少的從s到e的路徑，由於等級嚴格遞增，所以假設我們先將邊以等級排序，然後從最小的開始取，若其兩端點分別為x,y，則可以證明若經由邊可以鬆弛某條路徑的話，則其終點肯定在x或y上，事實上是因為我們將邊排序了，所以現在取出來的邊是目前已經有的中等級最大的那個，而不可能以這條邊再接出去了，所以這條邊一定是終邊。 　　特別注意的是等級相同的邊，由於互相不能互通，所以處理時必須一併處理才可以。 #include<bits/stdc++.h> # define int long long # define pi pair<pair<int,int>,pair<int,int> > # define F first # define S second # define INF 1e16 # define getchar getchar_unlocked # define putchar putchar_unlocked inline void output (int _x) { char _buff[20]; int _f = 0; while(_x > 0) { _buff[_f++] = _x%10+'0'; _x /= 10; } for(_f-=1; _f >= 0; _f--) putchar(_buff[_f]); putchar('\n'); } inline void input (int &_x) { _x = 0; int _tmp = 1; char _tc = getchar(); while((_tc < '0' || _tc > '9') && _tc != '-') _tc = getchar(); if(_tc == ...

LINK： https://tioj.infor.org/problems/1257 　　題目就告訴我們要作凸包了=_="，然後我做完之後弄一弄丟上去就不斷地WA!? 　　最後丟了一些case來return -1發現了奇妙的事實(?)，消失的皮皮不管怎樣都是不再凸包上的，以我的理解這樣好像是不符合題意的，不過AC了@@ # include < bits/stdc++.h > using namespace std ; # define int long long typedef pair< int , int > Point; typedef vector< int > VI; # define endl '\n' # define x first # define y second # define debug ( args... ) {string _s = #args; replace(all(_s),',',' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); error(_it,args);} bool is_debug = 0 ; void error (istream_iterator<string> _it) { if(is_debug) cerr << endl; } template < typename T, typename ... Args> void error (istream_iterator<string> it,T a, Args... args) { if(is_debug) { cerr << *it << " = " << a << " "; error( ++it,args...); } } inline double cross (Point o,Point a,Point b) { r...

LINK： https://tioj.infor.org/problems/1603 　　我覺得我差不多沒辦法再拿topcoder了QQ，輸入優化之類的一直爛掉之類的QQ 　　反正還是AC了啦><，就是sparse table套進去~~，但是要注意這題會爆int，但long long我丟會REQQ，所以就是unsigned int啦(但我是看了chino的blog才發現的QQ) #include<bits/stdc++.h> using namespace std ; # define int unsigned int int n,m,l,r; int ihei[ 40 ][ 100009 ]; int ahei[ 40 ][ 100009 ]; inline int rmqi (int a,int b) { int k = __lg( b-a+1); return min( ihei[k][a],ihei[k][b-(1<<k)+1]); } inline int rmqa (int a,int b) { int k = __lg( b-a+1); return max( ahei[k][a],ahei[k][b-(1<<k)+1]); } main () { ios_base::sync_with_stdio( 0); cin. tie ( 0); cin >> n >> m; for(int i = 0; i < n; i++) cin >> ihei[0][i] , ahei[0][i] = ihei[0][i]; for(int j = 1; (1<<j) <= n; j++) for(int i = 0; i+(1<<j) <= n; i++) { ihei[j][i] = min( ihei[j-1][i],ihei[j-1][i+(1<<(j-1))]); ahei[j][i] = max( ahei[j-1][i],...

LINK： http://tioj.infor.org/problems/1256 　　每次看到別人的code收藏區的咚咚，都會覺得別人怎麼那麼厲害已經學到了這麼多東西了，自己卻只能現在看著他的code來學習而覺得別人很厲害，所以我決定我這次不先說圖的關節點是我今天才在演算法筆記學到了，來自我感覺良好一下XD(我到底在說甚麼啊@@) 　　反正看到題目就知道是裸的圖的關節點了，刻一刻就好~~ 　　對不起，現在想想，剛剛寫得太簡略了@@ 　　總之先建一顆DFS樹，然後再分成tree edge和back edge來討論，若是back edge無法走到更高的點的話，也就是說某個點的子樹經由任何路徑最高只能走到那個子樹的第一個父親的話，那麼那顆父親就是關節點啦啦啦~~ # pragma GCC optimize ("O3") # include < bits/stdc++.h > using namespace std ; # define getchar getchar_unlocked # define putchar putchar_unlocked inline void output (int _x) { char _buff[20]; int _f = 0; while(_x > 0) { _buff[_f++] = _x%10+'0'; _x /= 10; } for(_f-=1; _f >= 0; _f--) putchar(_buff[_f]); putchar(' '); } inline bool input (int &_x) { _x = 0; int _tmp = 1; char _tc = getchar(); while((_tc < '0' || _tc > '9') && _tc != '-' && _tc != EOF) _tc = getchar(); if(_tc == '-...

LINK： http://tioj.infor.org/problems/1255 　　看到這題很容易就想到 TIOJ1014 打地鼠那一題，然後就像我一樣完全用那題的方法刻，最後就在TIOJ上刷出了一排排光輝的WA歷史了QQ 　　其實也就只有一個地方不一樣，打地鼠那裏有說過可以將dp[0][0]當作起始值去做，但現在變成二維的就不行了，因為dp[0][0]是基於和p[0]的距離，但有可能有的點的x或y座標比p[0]更小，然後就會爛掉，其餘的都和打地鼠那一題差不多吧~~ 　　複雜度：O(m^2*2^m) # include < bits/stdc++.h > using namespace std ; typedef pair< int , int > PII; typedef vector< int > VI; typedef long long ll; # define INF 999999999 # define endl '\n' # define pb push_back # define mt make_tuple # define F first # define S second # define all ( v ) begin(v),end(v) # define sz ( v ) (int)((v).size()) # define eps 1e-9 # define mod 1e9+7 # define jizz ios_base::sync_with_stdio(0); cin.tie(0); # define debug ( args... ) {string _s = #args; replace(all(_s),',',' '); stringstream _ss(_s); istream_iterator<string> _it(_ss); error(_it,args);} bool is_debug = 1 ; void error (istream_iterator<string> _it) { if(is_debug) cerr ...

LINK： http://tioj.infor.org/problems/1254 　　最小圓覆蓋 　　感覺學到新的東西的感覺真好~~ 　　之前在交大的時候有講過greedy的這題，不過那時候的方法的複雜度很爛@@(其實那時候是要求可以有幾個點不在圓內所以不能用這個方法)，然後我就去看了網路上的解就發現有有人用爬山法唬爛(?)，第一次學到了爬山法，不過我怎麼想就是會有測資可以把它弄爛啊@@，所以就去找了正解發現是超精妙O(N)解!! 　　 　　＂隨機增量法＂，就是假設在(1~i-1)已經有個最小圓覆蓋時，i那點只會有兩種情況：1.在圓內或圓上，也就是可以跳過它(O(1) )，或者2.在圓外，然後又可以證，如果出現這種情況時，i一定在(1~i)的最小圓覆蓋的圓周上，所以就窮舉其他兩點即可(greedy找半徑最大的圓O(i^2) )，看似很爛，不過其實第2種情況發生的機率並不高， 因為i個點中已經有i-1個點在圓內了，所以如果事前先random過的話，所以在圓內的機率是(i-1)/i，在圓外則是1/i，所以總體時間複雜度為(i-1)/i*O(1)+1/i*O(i^2) = O(i)為線性！ 　　 　　所以是前記得先random_shuffle，高斯消去法也是...... # include < bits/stdc++.h > using namespace std ; typedef pair< int , int > PII; typedef vector< int > VI; typedef long long ll; # define endl '\n' # define PB push_back # define MT make_tuple # define X first # define Y second # define ALL ( v ) begin(v),end(v) # define SZ ( v ) (int)(v.size()) # define eps 1e-9 # define MOD 1e9+7 # define JIZZ ios_base::sync_with_stdio(0); cin.tie(0); # d...

　　在交大的時候聽社長和OTOTOT說的時候就想說也要來寫一個了，然後剛剛遇到一題要用得但我一直寫不出來所以就索性先來寫模板了XD 　　有點覺得要整理一下標籤了，感覺好亂@@ class circumcenter{ public: inline double three (double a1,double a2,double a3,double a4,double a5,double a6,double a7,double a8,double a9) { return a1*a5*a9+a2*a6*a7+a3*a4*a8-a3*a5*a7-a6*a8*a1-a9*a2*a4; } inline pair<double,double> center( pair<double,double> a,pair<double,double> b,pair<double,double> c) { double rr = three( a .first ,a .second ,1,b .first ,b .second ,1,c .first ,c .second ,1); double x = three( a .first *a .first +a .second *a .second ,a .second ,1,b .first *b .first +b .second *b .second ,b .second ,1,c .first *c .first +c .second *c .second ,c .second ,1); double y = three( a .first ,a .first *a .first +a .second *a .second ,1,b .first ,b .first *b .first +b .second *b .second ,1,c .first ,c .first *c .first +c .second *c .second ,1); if( abs (r...