oToToT的code收藏區

題目連結: http://codeforces.com/problemset/problem/732/D 一開始想爛了，但大方向還算對，原本以為可以直接greedy算，但一直算不太出來(雖然好像還是可)。後來發現其實可以對答案二分搜，然而驗答案的地方我一直寫爛掉，導致這題寫了超久了，但最後AC code其實也沒多複雜，真搞不懂哪裡爛掉。 稍微講一下驗證答案的部分好了，就因為有個簡單的性質就是你若可以今天考，但今天不考之後再考也可以，所以驗證答案的時候都讓每科考試都在最後一次可以考時才考，這樣前面就會有一堆溫書假了。 #include <bits/stdc++.h> using namespace std; const int N = 100000 + 5; int need[N], ok[N]; bitset<N> done; bool isOK(int,int); int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n, m; cin>>n>>m; for(int i=1;i<=n;i++) cin>>ok[i]; for(int i=1;i<=m;i++) cin>>need[i]; int l=1, r=n+1; while(r-l > 1){ int mid = (l+r)>>1; if(isOK(mid, m)) r=mid; else l=mid; } cerr<<ok[r]<<"\n"; if(r==n+1) cout<<"-1\n"; else cout<<r<<'\n'; return 0; } bool isOK(int n, int m){ ...

題目連結: http://tioj.infor.org/problems/1329 裸裸的$O(n^2)$做，算一下交換後是否有變少即可。 #include <bits/stdc++.h> using namespace std; const int N = 1000 + 5; typedef pair<int,int> PII; #define FF first #define SS second int arr[N], n; inline int tsan(int); int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int t; cin>>t; while(t--){ cin>>n; for(int i=1;i<=n;i++) cin>>arr[i]; for(int i=1;i<=n;i++){ PII ans = {0, i}; for(int j=1;j<=n;j++){ if(i==j) continue; PII cur = {-tsan(i)-tsan(j), j}; swap(arr[i], arr[j]); cur.FF += tsan(i)+tsan(j); ans = min(ans, cur); swap(arr[i], arr[j]); } cout<<ans.SS<<" \n"[i==n]; } } return 0; } ...

題目連結: http://tioj.infor.org/problems/ 單調隊列的應用，維護兩條單調隊列，一個存最大值，一個存最小值。然後判一下最大減最小是否恰等於k即可。(單調隊列維護方法就是讓隊列呈現遞(增|減)，在加入元素的時候把比較(小|大)的全部移掉，同時把最(大|小)值移掉，直到他合法。) #include <bits/stdc++.h> using namespace std; typedef long long lld; #define PB push_back typedef pair<lld,int> PLI; typedef pair<int,int> PII; #define FF first #define SS second const int N = 10000000 + 5; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n, m;lld k; while(cin>>n>>m>>k){ deque<PLI> mi, mx; vector<PII> ans; for(int i=1;i<=n;i++){ lld x; cin>>x; while(!mi.empty() and i-mi.front().SS >= m) mi.pop_front(); while(!mx.empty() and i-mx.front().SS >= m) mx.pop_front(); while(!mi.empty() and mi.back().FF > x) mi.pop_back(); while(!mx.empty() and mx.back().FF < x) mx.pop_b...

題目連結: http://tioj.infor.org/problems/1641 看完 CBD的題解 後，覺得自己滿蠢的，其實取個log後最dijkstra就好了www。我這裡是自己寫了個簡單(?的科學記號模板來用，做法就依樣是裸的dijkstra。 #include <bits/stdc++.h> using namespace std; #define PB push_back typedef pair<double,int> PDI; #define FF first #define SS second const int N = 10000 + 5; struct SciFi{ double x; int p; SciFi(){x=0;p=0;} SciFi(double k){ p = floor(log10(k)); x = k / pow((double)10, p); } SciFi(double a, int b){ x=a;p=b; } SciFi operator=(double k){ p = floor(log10(k)); x = k / pow((double)10, p); return *this; } SciFi operator*(SciFi k)const{ int nP = p+k.p; double nX = x*k.x; int tp = floor(log10(nX)); return SciFi(nX/pow((double)10, tp), ...

題目連結: http://tioj.infor.org/problems/1106 葉子個數就只要算*的個數就好了，深度則只要看有幾個括號(若是遇到右括號就要把他移掉)，而幾元樹則是在每一層都把()合成一個之後再加上*的個數。 #include <bits/stdc++.h> using namespace std; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); string ss; while(cin>>ss){ int l=0, d=0, y=0; int cnt=0; stack<int> sk; sk.push(0); for(auto c:ss){ if(c=='('){ sk.top()++; sk.push(0); cnt++; }else if(c==')'){ y=max(y, sk.top()); sk.pop(); cnt--; } d=max(d, cnt); if(c=='*'){ l++; sk.top()++; } } cout<<l<<" "<<d+1<<" "<<y<<'\n'; } return 0; }

題目連結: http://tioj.infor.org/problems/1268 想了兩下後發現可以DP，狀態也很簡單就是$dp[i][j]$代表結尾在$(i,j)$時的最大值，轉移就只要$dp[i][j]=max(0, dp[i-1][j], dp[i][j-1])+mtx[i][j]$其中mtx代表原始的數字。 #include <bits/stdc++.h> using namespace std; const int N = 3000 + 5; int mtx[N][N], dp[N][N]; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n, m, ans=0; cin>>n>>m; for(int i=0;i<n;i++) for(int j=0;j<m;j++) cin>>mtx[i][j]; for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ if(i-1 >= 0) dp[i][j] = max(dp[i-1][j], dp[i][j]); if(j-1 >= 0) dp[i][j] = max(dp[i][j-1], dp[i][j]); dp[i][j]+=mtx[i][j]; ans = max(ans, dp[i][j]); } } cout<<ans<<'\n'; return 0; }

題目連結: https://zerojudge.tw/ShowProblem?problemid=b591 今天去打ISSC時的題目，最後沒寫出來，賽後想兩下就知道哪邊爛了，囧。一開始看到題目時，直覺是對y二分搜，後來寫一寫後發現那東東好像不是很好做(雖然大為學長他們後來也還是做了出來...)，想了一段時間後就發現其實將所有的x跟那個x所對應到最小且合法的y畫在平面上，其實他是會是一個凹向下的圖形(類似二次函數)，所以其實可以三分搜(不過那時不知為何我寫了個爬山，囧)，發現這件事後就直接對x三分搜即可。 #include <bits/stdc++.h> using namespace std; #define PB push_back typedef pair<int,int> PII; #define FF first #define SS second const double eps = 1e-7; vector<PII> con; double getY(double); int main(){ int n; while(scanf("%d",&n), n){ con.clear(); for(int i=0;i<n;i++){ PII x; scanf("%d%d",&x.FF,&x.SS); con.PB(x); } double l=0, r=1e9; for(int _=0;_<500;++_){ if(r-l < eps) break; double ll=l+(r-l)/3, rr=l+2*(r-l)/3; if(getY(rr) < getY(ll)) l=ll; else r=rr; ...