發表文章

目前顯示的是有「Template Library」標籤的文章

[Codeforces] 1042D

LINK: http://codeforces.com/contest/1042/submission/43004397

[Template] Trie

人生第一顆TRIE http://codeforces.com/contest/1037/submission/42430678 哇,我應該專門開個小帳來存code的XD

[模板] 外心公式

  在交大的時候聽社長和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...

[模板]快速冪、加法慢速機

  看起來好醜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)...

[模板] 樹狀數組 Binary indexed tree

  之前寫了一個BIT模板失敗了,今天練習逆序數對時心血來潮再試一次成功了XD,不過可能是還有潛在的錯誤只是我沒發現罷了@@ (取名叫sum好像怪怪的......)   I used to fail to make a BIT template; however, I tred it again on a whim when practicing Inversion count problem and succeeded this time. Maybe there are still some mistake not found@@ (the name "sum" seems to be weird......) class BIT { private: vector<int> BITT; int dis; public: inline void init(int n) { BITT.clear(); BITT.resize(n+1,0); dis = n; } inline void update (int i,int x) { while(i <= dis) { BITT[i] += x; i += i&-i; } } inline int sum (int i) { int res = 0; while(i > 0) { res += BITT[i]; i -= i&-i; } return res; } };

[模板] 離散化 Discretization

  最近看到OTOTOT的離散化模板(雖然現在他的blog鎖住了),所以就心血來潮的也寫了一個XD (有點弱QQ) (第N次校稿@@) (model這個名字也怪怪的@@)   I saw OTOTOT's template of discretization recently, so I make one for myself on a whim. XD class discretization { private: vector<int> lisan,status; public: inline vector<int> com(vector<int> a) { status.resize(a.size()); lisan = a; sort ( lisan.begin( ) ,lisan.end()); lisan.resize(unique(lisan.begin(),lisan.end())-lisan.begin()); for(int i = 0; i < (int)a.size(); i++) status[i] = lower_bound(lisan.begin(),lisan.end(),a[i])-lisan.begin(); return status; } inline vector< int > model (vector<int> a) { lisan = a; sort( lisan. begin ( ),lisan. end ( )); lisan. resize ( unique ( lisan. begin ( ),lisan. end ( ))-lisan. begin ( )); return lisan; } };

[模板] Disjoint Set

這幾天一直用到disjoint set,而且正好要寫考幹題的 蓋捷運 那一題,反正DSU也不難刻,所以就決定真正開始準備自己的模板庫了,以下為以前參考了OTOTOT的程式碼後才寫出來的。 class DSU { private: vector<int> fa,sz; public: void init(int n) { fa.resize(n+1), sz.resize(n+1,1); iota(fa.begin(),fa.end(),0); } 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(sz[ find (x)] < sz[ find (y)]) swap(x,y); fa[ find (y)] = find(x); sz[ find (x)] += sz[ find (y)]; } };