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 &l

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

LINK： http://tioj.infor.org/problems/1089 　　經典二分圖匹配問題，直接寫就好了，不過我一直對二分圖匹配不熟，希望這次有好好學起來@@，還有我發現我的模板在TIOJ上面不能compile，要想想辦法QQ 　　也就是每次對新的一顆交錯樹找有沒有擴增路徑之類的。 #include<bits/stdc++.h> using namespace std ; int mx[ 509 ],my[ 509 ]; int n,k,ans; bool adj[ 509 ][ 509 ]; bool vy[ 509 ]; bool DFS (int x) { for(int y = 1; y <= n; y++) if(adj[x][y] && !vy[y]) { vy[y] = 1; if(my[y] == 0 || DFS( my[y])) { tie( mx[x],my[y]) = make_tuple( y,x); return 1; } } return 0; } int main () { cin >> n >> k; while(k--) { int a,b;cin >> a >> b; adj[a][b] = 1; } for(int i = 1; i <= n; i++) { memset(vy,0, sizeof (vy)); if( DFS ( i)) ans++; } cout << ans << endl; }

ＬＩＮＫ： http://codeforces.com/problemset/problem/936/A 　　我一直搞混QQ，因為有t這個變數，然後我就一直以為是時間時麼的，然後跟烤雞烤了的比例搞混，而且感覺我有點心不在焉QQ，就亂亂的debug來浪費時間@@，或許我剛剛忘記帶腦袋了QQ 　　我決定多一個處理精度的標籤!! # include < bits/stdc++.h > using namespace std ; typedef pair< int , int > PII; typedef vector< int > VI; typedef long long ll; # define double long double # 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 = 0 ; void error (auto it) { if(is_debug) cerr << endl; } template < typename T, typename ... Args> void error (auto it,T a, Args... args) { if(is_debug) { cerr <

LINK： http://codeforces.com/contest/937/problem/B 　　 　　原本要virtual這一場，可是寫道這題就放棄了QQ，之前看過濤哥的文覺得很困難，自己估起來好像時間複雜度會狠狠地報炸，可是剛剛看了別人的解後=_="，就是說根本不會要找很久啊@@，1e9之內的質數gap最大也沒多大，然後需要用O(n^0.5)的質數篩法頂多一次要篩個1e5個左右，所以時間複雜度根本過得去@@，根本不知道我昨天在想甚麼QQ 　　順便學到了goto的用法XD # 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 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 (auto it) { if(is_debug) cerr << endl; } template < typename T, typename ... Args

　　看起來好醜QQ ll FAST (ll _a, ll _b, ll _mod) { ll _res = 1; while(_b) { if(_b&1) { _res *= _a; if(_mod) _res %= _mod; } _b >>= 1; _a *= _a; if(_mod) _a %= _mod; } return _res; } 　　 　　加法慢速機，應該是這樣寫的吧？之前寫了一個錯的，所以不確定這次對不對？ ll PLUS (ll _a, ll _b, ll _mod) { ll _res = 1; while(_b) { if(_b&1) _a += _res, _a %= _mod; _b >>= 1; _res <<= 1; } return _a; }

會慢慢擴充的2018/3/6 1. __gcd(a,b)：最大公因數 2. __lg(a)：二進位中首位為1的位置 3. fmod(double a,double b)：回傳a除b的餘數。 4.__builtin_ffs(int x)：二進位中，最後一個1的位置 ex __builtin_ffs(10) = 2 5.__builtin_clz(unsigned int x)：二進位中，最高位的1前面的0的數量 ex __builtin_clz((int)16) = 27 6.__builtin_popcount(unsigned int x)：二進位中，1的數量 ex __builtin_popcount(14) = 3 7.for_each：ex vector<int> a(100,2); for_each(all(a),[](int &b){b *= 2;}); 8.Raw string：用法為string a = R"(....)"; .....為要的字串，Raw string完全保存你寫進來的東西，我不知道有甚麼用，我現在知道正規表達式需要他了。 9.regex，Regular expressions的咚咚，有空再問Andrew Yang來搞懂它好了。

　　學到了template的使用方法，然後開始寫了模板，還有簡陋的debug機。 　　以後會慢慢擴充的。2018/3/6 　　擴充第二版：2018/3/6 　　擴充第三版：2018/3/6 　　擴充第四版：2018/3/7 　　更改第五版：2018/3/7(為了配合tioj的編譯器) # 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 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 << endl; } template < typename T, typename ... Args> void error (istream_iterator<string> it,T a, Args... args) {

　　多虧了輸入、輸出優化我搶到了人生第一次的topcoder，高興XD 輸入優化： # define getchar getchar_unlocked inline void input (int &_x) { _x = 0; int _tmp = 1; char _tc = getchar(); while((_tc < '0' || _tc > '9') && _tc != '-') _tc = getchar(); if(_tc == '-') _tc = getchar(), _tmp = -1; while(_tc >= '0' && _tc <= '9') _x = _x*10+(_tc-48), _tc = getchar(); _x *= _tmp; } 連續輸入時： # define getchar getchar_unlocked 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 == '-') _tc = getchar(), _tmp = -1; while(_tc >= '0' && _tc <= '9') _x = _x*10+(_tc-48), _tc = getchar(); _x *= _tmp; return _x; } 以EOF判斷輸入結束時： # define getchar getchar_unlocked inline bool input (int &_x)

LINK： http://tioj.infor.org/problems/1312 　　很水的disjoint set，合併時由大的併到小的之下的，不過我漏看了有連續輸入這項WA了好多次QQ #include<bits/stdc++.h> using namespace std ; int n,m,a,b,k; class DSU { private: vector<int> fa,sz; public: void init(int n) { fa.resize(n+1), sz.resize(n+1,1); for(int i = 0; i <= n; i++) fa[i] = i; } int find (int x) { return (x==fa[x])?x:fa[x]= find ( fa[x]); } bool same (int x,int y) { return find( x)== find ( y); } void unite (int x,int y) { if( same ( x,y)) return; if( find ( x) > find( y) ) swap( x,y); fa[ find ( y)] = find( x); sz[ find ( x)] += sz[ find ( y)]; } }dsu; int main () { ios_base::sync_with_stdio( 0); cin. tie ( 0); while(cin >> n >> m) { dsu. init ( n); while(m--) { cin &g

LINK： http://tioj.infor.org/problems/1302 　　網路上好像有很多人自己手刻個hash，不過這題應該沒必要(?)，而且我也還不會刻，反正很水，所以就直接用map做了，不過我還是因為忘記打"."而WA了兩次QQ #include<bits/stdc++.h> # define endl '\n' using namespace std ; string a,b,c; unordered_map<string,string> killl,nam; int main () { ios::sync_with_stdio( 0); cin. tie ( 0); while(cin >> a) { if(a == "add") { cin >> b >> c; nam[b] = c, killl[c] = b; } else if(a == "chk") { cin >> b; c = b. substr ( 1,b. length ( )-1); switch(b[0]) { case 'n': if(nam. find ( c) == nam. end ( )) cout << "Not found." << endl; else cout << c << " " << nam[c] << endl; break; default: if(killl. find ( c) == killl. end ( ))

LINK： http://tioj.infor.org/problems/1160 　　由於數字範圍較大，所以要用map去存，除此之後應該算是水題（？ # include < bits/stdc++.h > using namespace std ; unordered_map< int , int > hello; int a; pair< int , int > p; int main () { while(cin >> a && a) { hello[a]++; if(hello[a] > p .first || (hello[a] == p .first && a < p .second )) p = {hello[a],a}; cout << p .first << " " << p .second << endl; } }

LINK： http://tioj.infor.org/problems/1637 　　不得不說，這題對於資料結構來說是非常精湛的一題。 　　我一開始用的是類似merge sort的方法，爆搜最大值TLE後寫了人生第一個的sparse table，MLE後換寫人生第一棵指標型線段樹，MLE之後就放棄而去看別人的code了，結果發現可以O(n)用stack維護出來QQ，我的資料結構還是學術不精啊@@ 　　由於兩個基地台間的電波是以最大值決定，所以可以想到去維護一個遞減的stack(但我一開始沒去想QQ)，然後可以想像，假設在最右邊再蓋一個基地，就看看這個由於這個基地台而產生的新的電波值可以往左延伸多遠(也就是一直延伸到有電波值比它大的基地台之前)，然後就可以維護了XD，不過我是亂寫一個之後再亂debug後就AC了~~ # include < bits/stdc++.h > # define int long long using namespace std ; int n; vector<pair< int , int > > t; int dianboi, ans; main () { ios::sync_with_stdio( 0); cin. tie ( 0); cin >> n; for(int i = 0; i < n-1; i++) { int a; cin >> a; while(!t. empty ( ) && t. back ( ) .first < a) { pair<int,int> p = t. back ( ); t. pop_back ( ); if(!t. empty ( ))dianboi -= (p .second -t. back ( ) .second )*p .first ; else dianboi -= (p .second +1)*p .first ; } if(!t. empty ( )) dianboi += (