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){ done.reset(); done[0]=1; int used = 0, ans = 0; for(int i=n;i>=1;i--){ if(done[ok[i]]) used=max(used-1, 0); else{ used += need[ok[

題目連結: 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; } inline int tsan(int x){ int r=0; if(x-1 >= 1) r+=abs(arr[x]-arr[x-1]); if(x+1 <= n) r+=abs(arr[x]-arr[x+1]); return r; }

題目連結: 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_back(); mi.push_back({x,i}); mx.push_back({x,i}); if(mx.front().FF - mi.front().FF == k) ans.PB({max(1, i-m+1), min(i, n)}); } for(int i=n+

題目連結: 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), nP+tp); } SciFi operator*=(SciFi k){ p+=k.p; x*=k.x; int tp = floor(log10(x)); p+=tp; x/=pow((double)10, tp); return *this; } SciFi operator+(SciFi k)const{ int newP = std::min(k.p, p); double x1 = x*pow((double)10, p-newP); double x2 =

題目連結: 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; } double yy = getY(r); if(yy<=0) puts("0"); else printf("%.3lf %.3lf\n", yy, r); } return 0; } double getY(double x){ double r = -1e9; for(int i=0;i<

題目連結: http://tioj.infor.org/problems/1734 感覺可以數學解解掉，不過還是寫了個$O(nk)$的DP作法。狀態應該不難想，就是$dp[i][j]$代表有幾顆球，且目前結尾有幾顆黑球，轉移的話就枚舉要放黑球或白球即可。 #include <bits/stdc++.h> using namespace std; const int N = 20 + 5; int dp[N][N]; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n, k; while(cin>>n>>k){ if(n<k) cout<<(1<<n)<<'\n'; else if (n==k) cout<<((1<<n)-1)<<'\n'; else{ fill(dp[0], dp[n]+k+1, 0); dp[1][0]=1; dp[1][1]=1; for(int i=1;i<n;i++){ for(int j=0;j<k;j++){ dp[i+1][0] += dp[i][j]; dp[i+1][j+1] += dp[i][j]; } } int ans=0; for(int j=0;j<k;j++) ans+=dp[n][j]; cout<<ans<<'\n'; } } return 0; }

題目連結: http://tioj.infor.org/problems/1344 DP題，一開始我只想到$2 \cdot 4^5 N$的作法，但估了一估感覺不是很能跑，而且code也不是很好寫，後來聽了講解之後才知道狀態其實可以比我預期的少。 狀態是$dp[i][a_1][a_2][b_1][b_2]$，代表要處理第$i$個餐點，而先前第一區已有$a_1, a_2$號餐點，而第二區則有$b_1, b_2$號餐點，那轉移其實也還好，就是$dp[i+1][a_2][type(str_i)][b_1][b_2] = dp[i][a_1][a_2][b_1][b_2]+G(type(str_i), a_1, a_2)$(轉給第二區也是同樣的方式)，其中G函數為計算那三個中的種類的函數。 #include <bits/stdc++.h> using namespace std; const int N = 100001; char str[N]; int dp[2][4][4][4][4], toId[256]; inline int G(int,int,int); int main(){ ios_base::sync_with_stdio(0);cin.tie(0); memset(dp, -1, sizeof(dp)); toId[(int)'M']=1; toId[(int)'B']=2; toId[(int)'F']=3; int n; cin>>n; cin>>str; dp[0][0][0][0][0]=0; int pos=0; for(int i=0;i<n;i++){ for(int a=0;a<4;a++){ for(int b=0;b<4;b++){ for(int c=0;c<4;c++){ for(int d=0;d<4;d++){ if(dp[pos][a][b][c][d] == -1) continue; dp[pos^1][b][toId[(int)str[i]]][c][d] = max(dp[pos^1][b][toId[(int)str[

題目連結: http://tioj.infor.org/problems/1399 一直都只想到$O(nT^2)$的做法，原來是狀態(甚至是方向)的整個錯了，這題應該可以變成狀態是$dp[i]$代表前$i$個魚池都不會再撈時，最多可以撈到幾隻(而且要記錄每次是撈了多少的魚，但不用照順序)。那轉移的話就變得容易了，因為就代表你要在可以撈的那些魚的量中與先前的比較那些可以多擺進去，假設原本可以撈到的魚量是一條由大到小排好的單調隊列的話，而現在撈到的魚量也是一條單調隊列的話，那就很容易可以用merge sort的方式將其排序好，而顯然要讓自己這條是單調隊列的話，非常容易，畢竟按照次數來看就是$F_i, F_i - D_i, F_i-2D_i, \cdots $，所以轉移也僅需要O(T)的時間，總複雜度就順利地變成$O(nT)$了 #include <bits/stdc++.h> using namespace std; typedef long long lld; #define PB push_back typedef pair<int,int> PII; #define FF first #define SS second const int N = 100000 + 5; PII arr[N]; int T[N]; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int t, n; while(cin>>t>>n){ for(int i=1;i<=n;i++) cin>>arr[i].FF; for(int i=1;i<=n;i++) cin>>arr[i].SS; for(int i=1;i<=n;i++){ cin>>T[i]; T[i]+=T[i-1]; } lld ans=0; vector<int> cur; for(int i=1;i<=n;i++){ vector<int> nxt; lld nans=0; int pp=0; for(int j=0;j<t-T[i];j++){

題目連結: http://codeforces.com/problemset/problem/839/B 第一次會想把Div2的pB拿來放在這XD，這題實在有夠難寫的雖然一眼就知道他是greedy，但是思路要是不夠清楚基本上就會爛掉(這場CF我就這題炸掉了QAQ....)。Greedy的想法還算簡單，只要讓人數多的集團先坐，而且優先先把四人座坐滿即可(因為四人座若要做兩組人，中間一定會少一格(不能當作2格跟2格)，接下來再做兩人座的部分。這時可能會剩一些座位空著就在想盡辦法把所有人都塞進，這裡一樣先把多的人塞到4人座裡面。 #include <bits/stdc++.h> using namespace std; int seat[5], arr[10000 + 5]; int main(){ int n, k; cin>>n>>k; seat[4]=n; seat[2]=2*n; for(int i=0;i<k;i++) cin>>arr[i]; sort(arr, arr+k, [](int a, int b){return a>b;}); for(int i=0;i<k;i++){ int qq = min(arr[i]/4, seat[4]); arr[i] -= qq*4; seat[4]-=qq; } sort(arr, arr+k, [](int a, int b){return a>b;}); for(int i=0;i<k;i++){ int qq = min(arr[i]/2, seat[2]); arr[i] -= qq*2; seat[2]-=qq; } priority_queue<int> pq; for(int i=0;i<k;i++) pq.push(arr[i]); while(!pq.empty()){ if(pq.top()<=0) break; if(seat[4] > 0){ int x = pq.top(); pq.pop(); seat[4]--; if(x==2) seat[1]++; else if(x==1) seat[

題目連結: http://arc080.contest.atcoder.jp/tasks/arc080_c 作法滿greedy的，每次都挑字典序最小的一組pair，而且中間必定要隔偶數個數字，挑出來後就可以直接寫在前面，因為這方法其實就等價於最後再挑這兩個(因為中間隔偶數個，所以中間一定可以拿完)，不過稍微再想兩下就會發現其實還可以知道每次要挑的位置是先奇數再偶數，而且每次後面那個偶數位的一定不能超過前面拔掉的位置之一，稍微處理一下這個細節大概就可以做了。 #include <bits/stdc++.h> using namespace std; typedef pair<int,int> PII; #define FF first #define SS second const int N = 200000 + 5; const int INF = 1<<30; class SegTree{ private: int size; PII nodes[4*N]; inline int lc(int x){return 2*x+1;} inline int rc(int x){return 2*x+2;} void build(int l, int r ,int id, PII arr[]){ if(r-l==1){ nodes[id]=arr[l]; return; } int mid=(l+r)>>1; build(l, mid, lc(id), arr); build(mid, r, rc(id), arr); nodes[id] = min(nodes[lc(id)], nodes[rc(id)]); } PII query(int ql, int qr, int l, int r, int id){ if(qr <= l or r <= ql) return {INF,INF}; if(ql <= l and r <= qr) return nodes[id]; int mid=(l+r)>>1; return min(query(ql, qr, l, mid, l

題目連結: http://acm.csie.org/ntujudge/problem.php?id=2584 在兩棵樹上找LCS，其實跟原本找LCS的方法一樣，因為他還是可以找到字串的上一個字元，只不過原本的是要看前一個字元就好，這變成要看父親的字元，狀態也稍微改動成$dp[i][j]$是第一顆樹的0~i跟第二顆樹的0~j的LCS長度 #include <bits/stdc++.h> using namespace std; #define PB push_back typedef pair<int,int> PII; #define FF first #define SS second const int N = 1000 + 5; string s1, s2; vector<int> G1[N], G2[N]; int dp[N][N], ans; void DFS(int,int,int,int); int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int t; cin>>t; while(t--){ ans=0; int n, m; cin>>n>>m; for(int i=1;i<=n;i++) G1[i].clear(); for(int i=1;i<=m;i++) G2[i].clear(); cin>>s1; for(int i=0;i<n-1;i++){ int u, v; cin>>u>>v; G1[u].PB(v); G1[v].PB(u); } cin>>s2; for(int i=0;i<m-1;i++){ int u, v; cin>>u>>v; G2[u].PB(v); G2[v].PB(u); } queue<PII> BFS; BFS.push({1, 0}); while(!BFS.empty()){ PII u = BFS.front();BFS.pop(); for(auto v:

題目連結: http://poj.org/problem?id=3233 其實看到的時候以為是要用等比級數的公式，可是馬上就發現兩個會慘的點1.不保證有反矩陣, 2.不保證有些東西模m有反元素。後來被提示了才知道原來其實是用DP的想法找的轉移矩陣，然後對他快速冪。稍微列一下式就會得到$ \begin{bmatrix} S_i \\ A_i \end{bmatrix} = \begin{bmatrix} I \cdot S_{i-1}+A \cdot A_{i-1} \\ 0 \cdot S_{i-1}+A \cdot A_{i-1} \end{bmatrix} = \begin{bmatrix} I & A \\ 0 & A \end{bmatrix} \cdot \begin{bmatrix} S_{i-1} \\ A_{i-1} \end{bmatrix} $，所以就照著這個跑就好了。 #include <iostream> using namespace std; const int N = 60 + 2; int (*A)[N] = new int[N][N]; int (*Mtx)[N] = new int[N][N]; int (*Temp)[N] = new int[N][N]; int (*Ans)[N] = new int[N][N]; int (*Res)[N] = new int[N][N]; int n, m, n2; inline void mTimes(int[N][N],int[N][N],int[N][N],int,int,int); int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int k; cin>>n>>k>>m; n2 = n<<1; for(int i=0;i<n;i++) for(int j=0;j<n;j++) cin>>A[i][j]; for(int i=0;i<n;i++){ for(int j=0;j<n;j++){ Mtx[i][j]=(i==j); Mtx[i][j+n] = A[i][j];

題目連結: http://acm.csie.org/ntujudge/problem.php?id=2789 原本想要用離散化在定義一堆其怪的狀態來做這題，不過越寫越寫不出來。被雷了才知道，原來其實把那堆bit看成一堆線段就好了，那其實退位就是讓目前最低位消失，並在低他一位的地方長出一堆一直到現在這位置，而進位就更不用說了，畢竟原本進位就是均攤$O(1)$了。 #include <bits/stdc++.h> using namespace std; #define ALL(x) (x).begin(), (x).end() #define PB push_back typedef pair<int,int> PII; #define FF first #define SS second template<typename T> using minHeap = priority_queue<T,vector<T>,greater<T>>; vector<PII> work, ans; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int t; cin>>t; while(t--){ work.clear(); ans.clear(); minHeap<int> pq1, pq2; int n; cin>>n; for(int i=0;i<n;i++){ char c;int k; cin>>c>>k; if(c=='+') pq1.push(k); else if(c=='-') pq2.push(k); } while(pq1.size()>1){ auto a=pq1.top();pq1.pop(); auto b=pq1.top();pq1.pop(); if(a==b) pq1.push(a+1); else{ work.PB({a,1}); pq1.push(b); } } if(!pq1.em

題目連結: http://poj.org/problem?id=2104 裸的區間第K大值，曾經會過可是又忘記了，只記得關鍵字持久化，被雷了才知道。原來就是原本的序列第K大是直接用樹上的節點作二分搜，但是區間的話就變成要用$[L,R]$的和做節點二分搜，而要算$[L,R]$的和，其實就用持久化線段樹把$roots[R]-roots[L]$即可。 #include <iostream> #include <vector> #include <algorithm> #include <cassert> using namespace std; #define PB push_back #define ALL(x) (x).begin(), (x).end() const int N = 100000 + 5; const int MEM = 2000000; class LiSan{ private: vector<int> v; public: inline void init(){v.clear();} inline void insert(int x){v.PB(x);} inline int size(){return v.size();} inline void done(){ sort(ALL(v)); v.resize(distance(v.begin(), unique(ALL(v)))); } inline int get(int x){ return distance(v.begin(), lower_bound(ALL(v), x)); } inline int inv_get(int x){return v[x];} } lisan; class PSegTree{ private: struct Node{ int val, lc, rc; Node(){val=0;lc=-1;rc=-1;} } nodes[MEM]; int _mem, size; int _new(){ assert(_mem < MEM); nodes[_mem]=Node(); retur

題目連結: http://tioj.infor.org/problems/1144 我DP超廢，被雷了才知道這題狀態該怎麼訂QAQ........... 狀態這裡是訂$dp[i][j][k]$為處理了$k$個，而剩下的車在位置$i$及位置$j$，那轉移其實也不難想，就是考慮是由位置$i$到序列$k+1$的位置或是從位置$j$或是序列$k$。 p.s 丟了submission才發現空間有點緊，所以要滾動QQ #include <bits/stdc++.h> using namespace std; const int N = 200 + 5; const int M = 1000 + 5; const int INF = 1<<30; int arr[M], D[N][N], dp[N][N][2]; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n, m; cin>>n; for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ cin>>D[i][j]; dp[i][j][0]=dp[i][j][1]=INF; } } for(m=0;cin>>arr[m];m++); dp[2][3][0]=dp[3][2][0]=D[1][arr[0]]; dp[3][1][0]=dp[1][3][0]=D[2][arr[0]]; dp[1][2][0]=dp[2][1][0]=D[3][arr[0]]; int pos=0; for(int k=0;k<m-1;k++){ for(int i=1;i<=n;i++){ for(int j=1;j<=n;j++){ dp[i][j][pos^1] = min(dp[i][j][pos^1], dp[i][j][pos]+D[arr[k]][arr[k+1]]); dp[i][arr[k]][pos^1] = min(dp[i][arr[k]][pos^1], dp[i][j][pos]+D[j][arr[k+1]]); dp[arr[k]][j][po

題目連結: http://www.spoj.com/problems/DQUERY/ 本題的另外一種解法，構造方式與 上一種 不同，這裡的構造方式是將每個相同的數字由左至右連邊(如圖) 那這樣對於一個詢問$[L, R]$，就變成詢問$[L,R]$中大於$R$的數有多少個，因為每個數字最終必須往外伸出去。 而詢問$[L,R]$中大於$R$的數有多少個，其實可以用一種跟線段樹很像的做法做，節點存的是排序好的$[L,R]$，那詢問就直接二分搜就好，不過建立的過程退化成$O(n log n)$查詢則變成$O( n log^2 n)$ #include <iostream> #include <vector> #include <algorithm> using namespace std; #define ALL(x) (x).begin(), (x).end() #define PB push_back const int N = 30000 + 5; const int INF = 1<<30; class LiSan{ private: vector<int> v; public: void init(){v.clear();} void insert(int x){v.PB(x);} int size(){return v.size();} void done(){ sort(ALL(v)); v.resize(distance(v.begin(), unique(ALL(v)))); } int get(int x){ return distance(v.begin(), lower_bound(ALL(v), x)); } } lisan; class SegTree{ private: vector<int> nodes[4*N]; int size; inline int lc(int x){return (x<<1)+1;} inline int rc(int x){return (x<<1)+2;} void build(int l, int r, int id, i

題目連結: http://www.spoj.com/problems/DQUERY/ 被雷了才會做QQ，本題有兩種做法，一種是持久化線段樹，作法滿特別的(?，序列要將在每個時間點最遠的各個數字改成一，其他改成零(如圖) 那詢問一個$[l, r]$時，就只要對第$r$時間點的線段樹詢問$[l, r]$即可。 #include <bits/stdc++.h> using namespace std; #define PB push_back #define ALL(x) (x).begin(), (x).end() const int N = 30000 + 5; const int MEM = 900000; class LiSan{ private: vector<int> v; public: inline void init(){v.clear();} inline void insert(int x){v.PB(x);} inline int size(){return v.size();} inline void done(){ sort(ALL(v)); v.resize(distance(v.begin(), unique(ALL(v)))); } inline int get(int x){ return distance(v.begin(), lower_bound(ALL(v), x)); } } lisan; class SegTree{ private: struct Node{ int val, lc, rc; Node(){val=0;lc=-1;rc=-1;} }; static Node nodes[MEM]; static int _mem; inline int _new(){ assert(_mem < MEM); nodes[_mem]=Node(); return _mem++; } int size; int build(int l, int r, int id){ if(id==-1) id = _new(); if(r-l>1){

題目連結: http://tioj.infor.org/problems/1452 前面 有提到，本題有兩種做法，另一種作法算是比較普通的狀態壓縮DP，狀態變成$dp[i][s]$代表第i排整排排完且$s$裡面的東東是突的。轉移時變成類似暴搜的感覺，對每一個點試試看可不可以放，然後轉到$dp[i+1][s ^{\prime} ]$。 #include <bits/stdc++.h> using namespace std; typedef long long lld; const int N = 15; int n, m; lld dp[N][1<<N]; void dfs(int,int,int,int); int main(){ ios_base::sync_with_stdio(0);cin.tie(0); while(cin>>n>>m, n!=0 or m!=0){ if((n*m)&1){ cout<<"0\n"; continue; } if(m > n) swap(n, m); fill(dp[0], dp[n]+(1<<m), 0); dp[0][0]=1; for(int i=0;i<=n;i++) for(int s=0;s<(1<<m);s++) dfs(i, s, 0, 0); cout<<dp[n][0]<<'\n'; } return 0; } void dfs(int i, int s, int j, int sp){ if(j>m) return; if(j==m){ dp[i+1][sp] += dp[i][s]; return; } if(s & (1<<j)) dfs(i, s, j+1, sp); else{ if( !(s & (1<<(j+1))) ) dfs(i, s, j+2, sp); dfs(i, s, j+1, sp+(1<<j)); } }

題目連結: http://tioj.infor.org/problems/1452 就我所知，本題有兩種寫法，一種做法應該是被稱為「插頭DP/輪廓線DP」，想法不難，就是紀錄$dp[i][j][S]$為前$i-1$排都填滿了，且第$i$排由左往右$j$個也填滿了，而S則是記錄哪邊有凸出來(因為填滿也可以用直的填)，然後我這裡是往後轉移，轉移的方式也還算容易，就看他下一格是不是已經被填了(在S裡看)，如果沒被填就表示可以一個往下指的直的，且如果下兩格也沒被填就也可以擺一個橫的。最後看$dp[n-1][m-1][0]$即可。不過這題因為空間有點卡，所以要滾動一下。 #include <bits/stdc++.h> using namespace std; typedef long long lld; const int N = 15; lld dp[2][N][(1<<N)+5]; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n, m; while(cin>>n>>m, n!=0 or m!=0){ if((n*m)&1){ cout<<"0\n"; continue; } if(m>n) swap(n,m); fill(dp[0][0], dp[0][m-1]+(1<<m), 0); dp[0][1][0]=1; dp[0][0][1]=1; for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ if(j==m-1) fill(dp[(i+1)&1][0], dp[(i+1)&1][m-1]+(1<<m), 0); for(int s=0;s<(1<<m);s++){ if(j==m-1){ if(s & 1) dp[(i+1)&1][0][s-1]+=dp[i&1][j][s]; else{ dp[(i+1)&1][0][s + 1]+=dp[i

題目連結: http://tioj.infor.org/problems/1223 前面一直狂WA，但總覺得我的想法沒有錯，最後才發現是某個小地方做錯了QQ 想法大概就是把原本不行的區間轉成可以的區間，然後塞到線段樹，其中線段樹維護的是每個點往右最遠可以到哪裡，並且記錄一下是在第幾號的時候有最遠，那查詢也變得很容易，因為就只要單點查那個點最遠可以到哪裡就好了。 把步行區間轉可以區間的部分是害我一直WA掉的點，原本以為轉法就是排序好一堆$[L_i, R_i)$，接著看$[R_{i-1}, L_i]$是否合法($ R_{i-1} < L_i $)即可，但是其實不能只看$R_{i-1}$而是要看$\displaystyle \max_{1 \leq k < i}R_k$。 另外線段樹的部分因為最後是要取最大值，修改也都是取最大值，所以其實可以直接在節點上修改，然後詢問時把路徑上的所有節點取max就好。 p.s 值域有點大所以要先離散化 #include <bits/stdc++.h> using namespace std; typedef pair<int,int> PII; #define FF first #define SS second #define PB push_back #define ALL(x) (x).begin(), (x).end() const int N = 100000 + 10; class LiSan{ private: vector<int> v; public: inline void init(){v.clear();} inline void insert(int x){v.PB(x);} inline void done(){ sort(ALL(v)); v.resize(distance(v.begin(), unique(ALL(v)))); } inline int size(){return v.size();} inline int get(int x){ return distance(v.begin(), lower_bound(ALL(v), x)); } inline int inv_g

題目連結: http://tioj.infor.org/problems/1875 雖然題目敘述不知道是在講什麼鬼，但他其實就是一題裸的歐拉函數題，根據維基百科上的資料可以知道歐拉函數可以推導成$\displaystyle \varphi (n) = \prod _{{p\mid n}}p^{{\alpha _{p}-1}}(p-1) $，同時把篩法的概念套入後就發現，其實就是$ \forall 2 \leq i \leq \sqrt{n} $，重複將$n$除以$i$直到除不盡為止，在將回傳直乘以$i-1$。 #include <bits/stdc++.h> using namespace std; typedef long long lld; const lld N = 600000000; inline lld Euler(lld); int main(){ ios_base::sync_with_stdio(0);cin.tie(0); lld x; while(cin>>x){ if(x>N) cout<<x-1<<'\n'; else cout<<Euler(x)<<'\n'; } return 0; } inline lld Euler(lld x){ lld r=1; for(lld i=2;i*i<=x;++i){ if(x%i==0){ x/=i; r*=(i-1); while(x%i==0){ x/=i; r*=i; } } } if(x>1) r*=x-1; return r; }

題目連結: http://tioj.infor.org/problems/1406 右界設太大浪費了3hr debug... 回到正題，應該不難猜出可以對答案二分搜，而驗證答案的時候也很簡單，想法就是如果我有多我就往右運過去，然後如果有人少他就拿走那些，如果還不夠就跟右邊的再要，所以其實就是開個變數存說多多少/少多少，如果是多的話運走的時候要是變成小於零，就讓它變成零，但是如果是少的話就算變成小於零，還是要維持著。最後只要看剩下來的是否大於等於零即可。 #include <bits/stdc++.h> using namespace std; typedef long long lld; typedef pair<lld,lld> PLL; #define FF first #define SS second const int N = 100000 + 5; int n; PLL arr[N]; inline bool isOK(lld); int main(){ ios_base::sync_with_stdio(0);cin.tie(0); while(cin>>n){ lld l=0, r=0; for(int i=0;i<n;i++){ cin>>arr[i].FF>>arr[i].SS; r=max(r, arr[i].SS); } r++; while(r-l>1){ lld mid = (l+r)>>1; if(isOK(mid)) l=mid; else r=mid; } cout<<l<<'\n'; } return 0; } inline bool isOK(lld x){ lld con = arr[0].SS-x; for(int i=1;i<n;i++){ if(con >= 0) con = max(0LL, con+arr[i-1].FF-arr[i].FF); else con+=arr[i-1].FF-arr[i].FF; con += arr[i].SS-x; } return con>=

題目連結: http://acm.csie.org/ntujudge/problem.php?id=903 有趣的好題，想了很久只想的到樹鍊剖分的作法，被雷了才知道更好的做法QQ 對於全子樹加一其實很簡單，就把樹壓扁後把$[in[x], out[x]]$全部加一就好，然後詢問時則單點詢問邊即可。但是另外兩個操作就會變得很難做，所以要用另外一種方式想，考慮一條邊若或被加值，則一定是因為它下面的點有被加值，所以其實對最底下的點加值即可，然後為了怕太上面的人也會被算到，記得超過最頂之後要再減一以免多算，這樣就變成單點加值區間查詢了。 #include <bits/stdc++.h> using namespace std; #define PB push_back const int N = 100000 + 5; class BIT1{ #define lowbit(x) ((x)&(-(x))) private: int arr[N], size; inline int query(int x){ int r=0; while(x){ r+=arr[x]; x-=lowbit(x); } return r; } public: inline void init(int x){ fill(arr, arr+size, 0); size=x; } inline int query(int l, int r){ // 1-base (l, r] return query(r)-query(l); } inline void add(int x, int v){ while(x<size){ arr[x]+=v; x+=lowbit(x); } } #undef lowbit } bit1; class BIT2{ #define lowbit(x) ((x)&(-(x))) private: int arr[N], size; inline void add(int x, int v){ while(x){ arr[x]+=v; x-=lowbit(x); }