PolarisChiba的code收藏區

總之一直就是壓不過？ 然後就去查查看別人的code了 最後就發現，無解的時候會變得很肥，所以就先判掉吧

LINK： https://tioj.ck.tp.edu.tw/problems/1481 梗題？但我沒想出來絕對是個大失敗，可悲QQ

LINK： https://tioj.ck.tp.edu.tw/problems/1101 奇妙，看了解才恍然大悟，覺得不久前一直去找規律的自己像是個白癡一樣。

題目連結： https://tioj.ck.tp.edu.tw/problems/1827 　　人生第一次寫了持久化資料結構>< ! 不過是參考了cbd的code才順利寫出來的。 　　b[i]的範圍在1e5以內所以不用離散話，二分搜答案，建持久化線段樹。 # include<bits/stdc++.h> using namespace std; const int N = 100000+10; struct node{ int val; node *l,*r; node( int v) { val = v; l = r = NULL; } }*root[N]; node* build( int L, int R) { if (L == R) return ( new node(0) ); int mid = (L+R)>>1; node *v = new node(0); v -> l = build(L,mid); v -> r = build(mid+1,R); return v; } node* modify( int L, int R,node* u, int pos ) { if (L == R) return ( new node(u -> val+1) ); node* v = new node(0); int mid = (L+R)>>1; if ( pos <=mid) { v -> r = u -> r; v -> l = modify(L,mid,u -> l, pos ); } else { v -> l = u -> l; v -> r = modify(mid+1,R,u -> r, pos ); } v -> val = v -> l -> val+v -> r -> val; re...

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...

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; }

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 ...

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 += (...

link： http://tioj.infor.org/problems/1489 　　啊啊啊！甚麼咚咚啊@@，一直看錯題看錯題，而且我還是通宵來寫的，結果好生氣><(雖然問題大部分出在我身上)，不過我還真的看不懂第一個核心字串原來是指長度最小的那個@@，看了別人的code後才終於知道了，但也順便學了一下別人的作法了XD 　　而且看錯題以為是找相同前後綴的時候還看懂了KMP演算法的failure function！ 　　要判斷是不是核心字串很簡單，就測過26字母就可以了，但找最短的時候，就必須使用到爬行法，一次增加右邊一個，再看看左邊可以砍掉幾個，若最後長度較小就更新。 #include<bits/stdc++.h> using namespace std ; int n; string a; int main () { ios_base::sync_with_stdio( 0); cin. tie ( 0); while(cin >> n,n) { cin >> a; int used[30] = {}; int cnt = 26; int i; for(i = 0; i < a. length ( ) && cnt > 0; i++) { if(used[a[i]-'a'] == 0) cnt--; used[a[i]-'a']++; } if(i == a. length ( ) && cnt != 0) { cout << "not found" << '\n'; continue; } int len = i; int l = 0, r = i-1; for(int front = 0; i < a. len...

problem link： http://tioj.infor.org/problems/1063 　　這題好像是經典題，可是我總是無法好好掌握QQ，今天重寫也是想了好久~~ 　　作法是先選定一行，維護每個元素的最高高度，再往左計算面積，嗚嗚...我講的好抽象，不過因為要往左計算面積，所以複雜度是O(NM^2)，所以可以將N、M交換來加速......嗎？有空再問學長好了，不過唯一確定的事是交換的話會有點麻煩QQ (剛剛高興地想要試一下就...) 　　感覺tag好像有點不夠......也再說啦XD #include<bits/stdc++.h> using namespace std ; int rec[ 209 ][ 209 ]; int r[ 209 ]; int main () { int n,m; cin >> n >> m; int ans = 0; for(int i = 1; i <= n; i++) { for(int j = 1; j <= m; j++) { cin >> rec[i][j]; r[j] = (rec[i][j])?r[j]+1:0; for(int t = j, rr = r[j]; t >= 1 && rec[i][t]; t-- ,rr = min( r[t],rr)) ans = max( ans,rr*(j-t+1)); } } cout << ans << '\n'; }

problem link： http://tioj.infor.org/problems/1176 　　這題看起來就很"單調"，實際上就是要維護遞減，由於有更高的牛的話，之前比它矮的都可以不管了，所以用個當作stack的vector就很好實作了，不過我還是智障到一直寫不好QQ 　　最後發現我的時間爆多！？好像是因為我亂reverse的關係吧，不過應該也不會多到四十倍有餘吧@@，目前無解，有空去問問看別人好了。 #include<bits/stdc++.h> # define pb push_back # define pi pair<int,int> # define all ( v ) (v).begin(),(v).end() using namespace std ; int t; vector<pi> a,inc; vector< int > ans; int main () { cin >> t; for(int i = 0; i < t; i++) { int b; cin >> b; a. pb ( {b,i}); } reverse( all ( a)); int ok = 0; for(auto i:a) { while(!inc. empty ( ) && inc. back ( ) .first <= i .first ) inc. pop_back ( ); if(inc. empty ( )) ans. pb ( t-i .second -1); else ans. pb ( inc. back ( ) .second -i .second ); inc. pb ( i); } reverse( all ( ans)); for(auto i:ans) cout << i << endl; }

題目連結： http://tioj.ck.tp.edu.tw/problems/1410 　　很可惜這題式靜態的，又或者不是區間查詢的，如果是的話，就可以寫個刺激的BIT了或者練習其他資料結構了XD 　　反正就先離散化，然後掃過去，進入的時刻就加一、出去的話就減一，最後求前綴和就是那個時候的人數，有點無聊QQ #include<bits/stdc++.h> using namespace std ; int t; 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 ( )); retur...

題目連結： http://tioj.infor.org/problems/1080 　　這題我知道有兩種做法，一種是merge sor、一種是BIT，由於merge sort我沒研究、沒寫過，而且感覺起來是侷限於這一題的，所以我傾向於寫BIT，可能有空會寫寫看merge sort吧XD 　　每讀入一個數字，就看看若排序完的話，在它前面應該要有幾個數，再看看實際上有多少數在它前面，相減後就代表有多少個比它小但在它後面，為了看有幾個數要用BIT，要用BIT就要先將資料離散化。 #include<bits/stdc++.h> # define int long long using namespace std ; int t; vector< int > s; int cnt[ 1000009 ]; 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; } }li; class BIT { private: vector<int> BITT; int dis; public: i...