PolarisChiba的code收藏區

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

　　之前寫了一個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; } };

　　最近看到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; } };

題目連結： https://oj.infor.org/contests/13/problems/73 　　這題剛開始看到的時候完全沒有頭緒，後來某個晚上我被Andrew Yang嗆了之後感到很不爽，然後就四處亂逛發現了莫隊算法並寫到隔天早上終於AC，不過由於不是最佳解所以被rejudge了QQ，之後要了看不懂的提示之後，再次亂逛發現了BIT解，然後終於AC了。 　　掃過去遇到一個數字a，將a的上次的位置的值歸零並將這次的位置+1，由於要取區間總和所以用BIT維護舊好，然後要使歸零的地方不會影響到就必須離線作，將所有詢問依照右界排序；若不用離散化而用unordered_map來記錄位置的話會TLE。 　　有空再把莫隊的解丟上來吧ＸＤ #include<bits/stdc++.h> # define pi pair<pair<int,int>,int> using namespace std ; int bit[ 2000009 ]; int n,m; int id[ 2000009 ],ss[ 2000009 ]; pi q[ 2000009 ]; int ans[ 2000009 ]; inline void add (int x,int i) { while(i <= n) { bit[i] += x; i += i&-i; } } inline int sum (int i) { int res = 0; while(i > 0) { res += bit[i]; i -= i&-i; } return res; } int main () { ios::sync_with_stdio( 0); cin. tie ( 0); cin >> n >> m; for(int i = 1; i <= n; i++) cin >> id[i], ss[i-1] = id[i]; sort( ss,ss+n); int dis = unique( ss,ss+n)-ss;

題目連結： https://oj.infor.org/contests/13/problems/71 　　考幹題真的讓我學到了很多新的東西（目前PF還沒寫出來），原本以為這題是一般的MST，不過試過範測後才察覺不對，因為分子分母的大小會影響最後值的大小，所以並不是單純以y/x當作權重。 　　看了演算法筆記才發現這有專有名詞叫做：mininum ratio spanning tree，這題的情況必須使用二分搜比例，若以r構出的圖的最小生成樹權重和為負的，代表比例可以更小，等於的話就是找到了最小比例。 　　不過因為二分搜範圍問題我TLE了無數次，一開始還假解過被學長rejudge，最後是用了greedy弄出了一個值之後再使用牛頓法迭帶才終於AC了，牛頓法很快，不過要注意初始就不能差太遠。（不過最終還是不知道OTOTOT學長的正解是甚麼==） # pragma GCC optimize ("Ofast") #include<bits/stdc++.h> # define pii pair<int,pair<int,int>> # define double long double # define pi pair<double,pair<int,int> > # define eps 0.000001 # define getchar getchar_unlocked using namespace std ; inline int input () { int x = 0; char cha; while(cha = getchar()) if(cha >= '0' && cha <= '9') break; x = cha-48; while(cha = getchar()) { if(cha < '0' || cha > '9') break; x = x*10 + cha-48; } return x; } class DSU

題目連結： http://tioj.ck.tp.edu.tw/problems/1014 　　看來是我輕忽了，以前是看別人的code才會寫的，現在想想位元DP我從來好像也只寫過這麼一題而已QQ，我因為這題今天差點陷入低潮，一直錯、懷疑自己之類的，中途還差點想要去看解，不過最後守著最後一絲堅持送上去之後出乎意料的AC了XD。 　　不靠自己解出這題不行，我必須變得更強！ 　　如果知道位元DP的觀念的話很容易寫出轉移式：dp[s][i] = dp[s/i][j]+abs(j-i)+@@@，由於每隻地鼠都有一定的周期才會出來，所以到i隻的時間就必須要是T[i]的倍數，這裡就必須動點腦筋了，我的寫法是dp[s][i] = ceil((dp[s/i][j]+abs(j-i))/T[i])*T[i]，不過網路上其他人的寫法則是 ((dp[s/i][j]+abs(j -i)-1)/T [i]+1)*T[i]。 　　另外，設定邊界dp[0][0] = 1，之後會比較好處理，算是一種熟悉位元DP的人能夠信手拈來的技巧吧，但是我一開始沒想到就去算了dp[1<<i][i]當作邊界了QQ 　　看來我還有很多技巧要學！！ #include<bits/stdc++.h> # define INF 999999999 using namespace std ; int dp[( 1 << 16 )][ 17 ],t[ 17 ],ans,n; int main () { ios_base::sync_with_stdio( 0); cin. tie ( 0); cin >> n; for(int i = 0; i < n; i++) cin >> t[i]; fill( &dp[0][0],&dp[1<<n][n],INF); ans = INF; dp[0][0] = 1; for(int s = 1; s < (1<<n); s++) for(int i = 0; i < n; i++) { if(!(s&(1<<i))) conti

題目連結： http://tioj.ck.tp.edu.tw/problems/1012 　　關於stack的經典問題，不過因為vector比stack快所以就使用了vector，寫到一半忘了為甚麼會有no的case，去翻以前的code才發現我智障QQ，好好模擬就OK了，以前的我用的方法好麻煩，現在這個雖然感覺也很麻煩，不過相比之下清爽多了XD #include<bits/stdc++.h> # define endl '\n' using namespace std ; int n,m; vector< int > sta,rep; int main () { ios_base::sync_with_stdio(0); cin. tie (0); cin >> n >> m; int cnt = 0; for(int i = 0; i < n; i++) { int a; cin >> a; while(!rep. empty ()) sta. push_back (rep. back ()),rep. pop_back (); if(sta. empty () || a > sta. back ()) { for(int j = cnt+1; j <= a; j++) sta. push_back (j); cnt = a; } if(sta. back () == a) sta. pop_back (); else { for(int j = 0; j < m && sta. back () != a; j++) rep. push_back (sta. back ()), sta. pop_back (); if(sta. back () == a) sta. pop_back ();

題目連結： http://tioj.ck.tp.edu.tw/problems/1007 我不會DP QAQ 　　這題我很久以前就寫過了，因為想起來OTOTOT說過的必須要複習學過的東西，所以最近想要將TIOJ裡的我寫過的題目都再刷過一次。 　　　由第 i 個燈泡開始亮0~n個後再接一個暗的，容易可以推出DP式：dp[ i ] = dp[ i-1 ]+dp[ i-2 ]+...+dp[ i-n-1 ] ，複雜度是O(NM)，雖然夠了但其實可以化簡，可以發現dp[ i ]-dp[ i-1 ]=dp[ i-1 ]-dp[ i-n-2 ]，也就是說dp[ i ] = 2*dp[ i-1 ]-dp[ i-n-2 ]，複雜度降到了O(M)。 　　不過在i <n+2時要注意（我數學不好@@，這裡一直搞混），i<=n時可以隨意開關所以是2^n，而 i=n+1 時根據原本的DP式可以知道式所有前面的項相加其實也就是2*(n+1)-1，而後面的直接DP即可 #include<bits/stdc++.h> # define int long long using namespace std ; int n,m; int dp[ 100 ]; main () { cin >> n >> m; dp[0] = 1; for(int i = 1; i <= n; i++) dp[i] = dp[i-1]<<1; dp[n+1] = (dp[n]<<1)-1; for(int i = n+2; i <= m; i++) dp[i] = (dp[i-1]<<1)-dp[i-n-2]; cout << dp[m] << endl; }

這幾天一直用到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)]; } };