oToToT的code收藏區

題目連結: http://tioj.infor.org/problems/1998 可以發現其實每個IP都是一個32-bit的東東，所以可以直接用個unsigned int或long long存下來。而遮罩的那個區間其實就是那些x全填0到全填1，而我們要詢問一堆IP是不是在一堆區間內，其實就直接把那些區間當作區間加值，那查詢就只要查詢那個點是不是大於一就好了。不過因為範圍有點大，要先離散化掉就是了。 #include <bits/stdc++.h> using namespace std; #define PB push_back #define ALL(x) begin(x), end(x) typedef long long lld; typedef pair<lld,lld> PLL; #define FF first #define SS second const int M = 200000 + 5; const int N = 300000 + 5; class LiSan{ private: vector<lld> vv; public: inline void init(){vv.clear();} inline void insert(lld x){vv.PB(x);} inline void done(){ sort(ALL(vv)); vv.resize(distance(vv.begin(), unique(ALL(vv)))); } inline int size(){return vv.size();} inline int get(lld x){ return distance(vv.begin(), lower_bound(ALL(vv), x)); } } lisan; ...

題目連結: http://tioj.infor.org/problems/1999 裸著做(?，每次都從當前最早服務完的人中叫他來服務客人，那他服務完的時間就再加上服務這個人的時間。而要早當前最早服務完的就拿個priority_queue就好了XD #include <bits/stdc++.h> using namespace std; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n, m; cin>>n>>m; priority_queue<int,vector<int>,greater<int>> pq; for(int i=0;i<m;i++) pq.push(0); for(int i=0;i<n;i++){ int x;cin>>x; int tp = pq.top();pq.pop(); pq.push(tp+x); } int ans = 0; while(!pq.empty()){ ans=pq.top();pq.pop(); } cout<<ans<<'\n'; return 0; }

題目連結: http://tioj.infor.org/problems/1409 我被雷了才知道原來多邊形也有任$n-1$邊之和大於第$n$邊的事，所以就掃過去紀錄最大值是誰，然後看$sum-max > max$有沒有成立就好了XD #include <bits/stdc++.h> using namespace std; const int N = 1000000 + 5; int main(int argc, char* argv[]){ int n; while(~scanf("%d",&n)){ int mx = -1; long long cnt = 0; for(int i=0;i<n;i++){ int x; scanf("%d",&x); mx = max(mx, x); cnt+=x; } puts((cnt>(mx<<1))?"YES":"NO"); } return 0; }

題目連結: http://codeforces.com/problemset/problem/711/D 小品(?的圖論題。首先有個小觀察，這種給法的圖，在每一個連通塊(?中，只會有一個環，不過還是可能會有很多連通塊就是了。所以先考慮一個連通塊的情況，發現若他的環有$k$個邊，且整個連通塊有$n$個邊的話，他的方法數就會是$(2^k-2)\cdot(2^{n-k})$，想法大致就是，環上每個邊都可以選擇要換或不換扣掉全換跟全部換，再乘以其他大家的可能性就好了。至於多個連通塊的情況就直接把他們乘在一起就好了，畢竟他們是獨立的。 #include <bits/stdc++.h> using namespace std; typedef long long lld; #define PB push_back #define FF first #define SS second const int N = 200000 + 5; const lld MOD_BASE = 1e9 + 7; class DJS{ private: vector<int> arr, sz; public: void init(int n){ arr.resize(n); sz.resize(n); for(int i=0;i<n;i++){ arr[i]=i; sz[i]=1; } } int size(int x){return sz[query(x)];} int query(int x){ if(arr[x]!=x) arr[x] = query(arr[x]); return arr[x]; } void merge(i...

題目連結: http://codeforces.com/problemset/problem/698/B 一開始完全沒想法，被提示(?說就算非法也還是一張圖後才比較有想法。這題我的作法很greedy，就先判斷一下有沒有原本就有可以當根的點，有的話就把他當根，接下來再掃一遍，看看有沒有人會構成環，有的話就直接把他接到根上面，此外，若沒有現成的根的話就直接把他變成根。而要找誰跟誰一樣就用個並查集就好了XD #include <bits/stdc++.h> using namespace std; #define PB push_back #define FF first #define SS second const int N = 200000 + 5; class DJS{ private: vector<int> arr; public: void init(int n){ arr.resize(n); for(int i=0;i<n;i++) arr[i]=i; } int query(int x){ if(arr[x]!=x) arr[x] = query(arr[x]); return arr[x]; } void merge(int a, int b){ arr[query(a)]=arr[query(b)]; } } djs; int arr[N]; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n, ans = 0, root = -1; cin>>n; for(int i=1;i<=n;i++){ cin...

題目連結: http://tioj.infor.org/problems/1410 裸的區間加值，查詢全部最大值問題。因為沒有奇怪的修改之類的，所以我們可以直接用個簡單的技巧，先插入兩個小標記之後再往後推過去一遍的作法做，而這題應為值域太大要先離散話，或是向我一樣懶懶的直接開個map解決他。 #include <bits/stdc++.h> using namespace std; map<long long,int> mp; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n; cin>>n; for(int i=0;i<n;i++){ long long l, r; cin>>l>>r; mp[l]++; mp[r+1]--; } int cur = 0, ans = 0; for(auto i: mp){ cur += i.second; ans = max(ans, cur); } cout<<ans<<'\n'; return 0; }

題目連結: http://tioj.infor.org/problems/1401 我好廢QQ被雷了才會。 很簡單的可以觀察到垂直跟水平可以分開，那這樣的話問題被轉化成給你一堆線段，你要為每條線段選一個點，使得這些點不能重複。做法很greedy直接從左掃到右邊，然後如果有可以放的就放，然後如果遇到一條線段就把他右界放進去之類的。 #include <bits/stdc++.h> using namespace std; #define PB push_back const int N = 100000 + 5; vector<int> hen[N], zhi[N]; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n; while(cin>>n){ for(int i=1;i<=n;i++){ hen[i].clear(); zhi[i].clear(); } bool flag = true; for(int i=0;i<n;i++){ int l, r, u, d; cin>>l>>r>>u>>d; hen[l].PB(r); zhi[u].PB(d); } priority_queue<int,vector<int>,greater<int>> pq; for(int i=1;i<=n;i++){ for(auto j: hen[i]) pq.push(j); if(!pq.empty()){ if(pq.top() <...

題目連結: http://tioj.infor.org/problems/1280 應該很明顯就是要求個凸包的面積，那就先求個凸包，求法就是先求出上凸包，再求下凸包，看上下凸包的方法也不難，就看看兩個相鄰的邊的夾角是不是超過180度就好。接著要求面積就直接算個有向面積加起來，而因為剛剛求凸包的順序關西，我們求有向面積的時候甚至不需要極角排序，直接求就好了。 #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 = 10000 + 5; inline PLL operator-(const PLL &a, const PLL &b){ return {a.FF-b.FF, a.SS-b.SS}; } inline lld cross(const PLL &a, const PLL &b){ return a.FF*b.SS - b.FF*a.SS; } inline lld cross(const PLL &o, const PLL &a, const PLL &b){ return cross(a-o, b-o); } PLL arr[N]; vector<PLL> hull1, hull2; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n; cin>>n; for(int i=0;i<n;i++) cin>>arr[i].FF>>arr[i].SS; sort(arr, arr+n); for(int i=0;i<n;i++){ w...

題目連結: http://tioj.infor.org/problems/1637 枚舉每個點，看有哪些區間會以他為最大值，若是裸著做可能會有個$O(n^2)$的作法，但是其實會發現維護那些區間會以他為最大值，其實可以先找出最長且以他為最大值的區間，而要做這件事就只要用個stack維護一下左邊右邊第一個比自己大的數在哪就好(維護stack的遞減性就可做到)。維護好後算答案其實也不難，區間的可能個數就是右邊元素的數量乘以左邊元素的數量。 #include <bits/stdc++.h> using namespace std; typedef long long lld; typedef pair<lld, int> PLI; #define FF first #define SS second const int N = 1000000 + 5; lld arr[N], LL[N], RR[N]; vector<PLI> ss; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n; cin>>n; for(int i=0;i<n-1;i++) cin>>arr[i]; for(int i=0;i<n-1;i++){ while(!ss.empty() and ss.back() < (PLI){arr[i], i}) ss.pop_back(); LL[i] = ss.empty()?-1:ss.back().SS; ss.push_back({arr[i], i}); } ss.clear(); for(int i=n-2;i>=0;i--){ while(!ss.empty() and ss.back() < (PLI){arr[i], i}) ss.pop_back(); RR[i] =...

題目連結: http://codeforces.com/contest/855/problem/E 早上才學完數位統計DP晚上就寫不出來，我還真垃圾... 這題我的狀態是定成$dp[i][j][k]$代表在$i$進位下，算到第$j$位，而且有$k$個奇數次時的方法數，這狀態的轉移很簡單，就是枚舉多一位奇數或少一位奇數($dp[i][j][k]=dp[i][j-1][k-1] \cdot k + dp[i][j-1][k+1] \cdot (i-k)$)。那這樣的話，對於每一個範圍，我們就只要枚舉他在哪一位開始可以任意選之類的就可以回答了。 #include <bits/stdc++.h> using namespace std; typedef long long lld; const int N = 65; int dig[N]; lld dp[11][N][11]; bool dped[11][N][11]; void init(); lld go(int,int,bool,int,bool); lld calc(int,int,int); int main(){ ios_base::sync_with_stdio(0);cin.tie(0); init(); int q; cin>>q; while(q--){ int b; cin>>b; long long l, r;cin>>l>>r; l--; int cnt; for(cnt=0;l>0;cnt++){ dig[cnt]=l%b; l/=b; } dig[cnt]=0; lld L = go(b, cnt, 0, 0, 1); for(cnt=0;r>0;cnt++){ ...

題目連結: http://tioj.infor.org/problems/1795 想了很久想不出來QQ，被雷了才知道其實就是求最小生成樹跟最大生成樹，然後判斷k是不是介在這兩棵樹的權值之間。證明也不難，就簡單的想一下你要從一棵生成樹變成另一棵生成樹，必定是加加減兩條邊，而且保證邊權都是0或1，所以其實每棵生成樹都最多差一(排序後)，所以只要判是不是介在最大最小就好。 #include <bits/stdc++.h> using namespace std; typedef tuple<int,int,int> III; #define FF(x) get<0>(x) #define SS(x) get<1>(x) #define TT(x) get<2>(x) class DJS{ private: vector<int> arr; public: void init(int n){ arr.clear(); arr.resize(n); for(int i=0;i<n;i++) arr[i]=i; } int query(int x){ if(arr[x]!=x) arr[x]=query(arr[x]); return arr[x]; } void merge(int a, int b){ arr[query(a)]=query(b); } } mx, mi; vector<III> edges; int main(){ int n, m, k; cin>>n>>m>>k; mx.init(n+1); mi.init(...

題目連結: http://tioj.infor.org/problems/1446 稍微想一下就會發現這題就等價於塞到trie後的DFS的順序，但是因為建棵trie有點麻煩，所以在想個兩下就會發現建棵trie再DFS其實跟你直接排序再扣掉相鄰的人的LCP等價，所以就這樣做吧XD #include <bits/stdc++.h> using namespace std; const int N = 100000 + 5; string ss[N]; int main(){ int n, ans=0; cin>>n; for(int i=0;i<n;i++){ cin>>ss[i]; ans+=ss[i].size(); } sort(ss, ss+n); for(int i=1;i<n;i++){ int sz = min(ss[i].size(), ss[i-1].size()); int lcp; for(lcp=0;lcp<sz and ss[i][lcp]==ss[i-1][lcp];lcp++); ans-=lcp; } cout<<ans*2+n<<'\n'; return 0; }

題目連結: http://tioj.infor.org/problems/1062 這題題目好像有點怪，但還在可理解的範圍內，總之就是問你說給你網格內的一堆數，每個人移動都有1單位的cost，問你選哪個點讓大家都移動到他後的cost最小。 可以發現其實左右跟上下是可以分開的，因為他不能斜的走。所以就從左到右枚舉哪個點可以並從上到下枚舉哪個點可以，兩個混和在一起就好了。 #include <bits/stdc++.h> using namespace std; typedef long long lld; typedef pair<lld, int> PLI; #define FF first #define SS second const int N = 100 + 5; const lld INF = 1LL<<60; lld X[N], Y[N]; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n, m; cin>>n>>m; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ int x; cin>>x; X[j]+=x; Y[i]+=x; } } PLI ansX={INF, 0}, ansY={INF, 0}; lld curX=0, curY=0; for(int i=1;i<=m;i++) curX+=X[i]*i; for(int i=1;i<=n;i++) curY+=Y[i]*i; for(int i=1;i<=m;i++) X[i]+=X[i-1]; for(int i=1;i<=n;i++) Y[i]+=Y[i-1]; f...

題目連結: http://codeforces.com/problemset/problem/766/E 貌似是某種樹DP的東東，看到xor就要先想到把bit拆開，這樣的話問題就被轉化成說給你一堆0, 1的節點，問你所有路徑的和。這樣的話有個好處就是，因為只有0跟1，所以我們其實只要計算他的奇偶，然後偶爾交換一下之類的。接下來發現要枚舉所有路徑，其實枚舉lca就好了，所以就先走下去，把子樹算一算，之後提上來的時候稍微看一下自己是0還是1再把大家乘一乘之類的就好了。(想睡覺，可能有點不知所云 #include <bits/stdc++.h> using namespace std; typedef long long lld; typedef pair<int,int> PII; #define FF first #define SS second #define PB push_back const int N = 100000 + 5; int arr[N]; vector<int> G[N]; lld ans = 0; PII dfs(int,int,int); int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n; cin>>n; for(int i=1;i<=n;i++) cin>>arr[i]; for(int i=0;i<n-1;i++){ int u, v; cin>>u>>v; G[u].PB(v); G[v].PB(u); } for(int i=0;i<20;i++) dfs(1, 1, i); cout<<ans<<'\n'; return 0; } PII dfs(int w, int f, int d){...

題目連結: http://tioj.infor.org/problems/1481 一個小觀察，$\forall x \in \mathbb{N},gcd(x, x+1)=1$，所以這題每個邊的編號其實就是DFS時每個邊被遍歷到了順序。 #include <bits/stdc++.h> #include "lib1481.h" using namespace std; typedef pair<int,int> PII; #define FF first #define SS second #define PB push_back const int V = 2000+5, E = 20000+5; bitset<E> visited; vector<PII> G[V]; int ans[E], cnt=0; void dfs(int); int main(){ Init(); int n, m; scanf("%d%d",&n,&m); for(int i=0;i<m;i++){ int u, v; scanf("%d%d",&u,&v); G[u].PB({v, i}); G[v].PB({u, i}); } dfs(1); Possible(); for(int i=0;i<m;i++) Number(ans[i]); Finish(); return 0; } void dfs(int w){ for(auto i: G[w]){ int v = i.FF, id = i.SS; if(visited[id]) continue; visited[id]=1; ...

題目連結: http://codeforces.com/problemset/problem/208/E 稍微轉化一下問題就可以得到問節點$i$的子節點們深度為$d$的有那些，轉法也很簡單，對於一組詢問$(v, p)$就直接變成，對於$v$的$p$倍祖先問在$dep[v]$的數字有哪些(問一個人的$p$倍祖先可以直接用個倍增法做到)。轉化成這樣後就可以直接開個map維護每個深度為$k$時有幾個，然後要合併兩子樹就啟發式合併就好了。 #include <bits/stdc++.h> using namespace std; const int N = 100000 + 5; typedef pair<int,int> PII; #define PB push_back #define FF first #define SS second class K_anc{ private: vector<int> G[N]; int anc[N][20]; void dfs(int w, int f){ anc[w][0]=f; for(auto i: G[w]) if(i!=f) dfs(i, w); } public: inline void AddEdge(int u, int v){ G[u].PB(v); G[v].PB(u); } void solve(int r, int maxn){ dfs(r, r); for(int j=1;j<20;j++) for(int i=0;i<maxn;i++){ anc[i][j] = anc[anc[i][j-1]][j-1]; ...

題目連結: http://codeforces.com/contest/570/problem/D 把詢問依照節點存好，接下來我們就可以對樹DFS，同時記錄一下他的深度與每個字母出現的次數，然後要把兩棵子樹的資訊合併起來時就用啟發式合併，而完成一棵子樹後就可以把每個詢問的答案填上去，而且我們只在意奇偶性，所以甚至還可以用位元運算壓掉一些常數，大概就這樣吧。 #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 = 500000 + 5; vector<int> G[N]; char wh[N]; vector<PII> que[N]; int ans[N], dep[N]; void dfs(int, map<int,int>&); int main(){ int n, q; scanf("%d%d",&n,&q); dep[1]=1; for(int i=2;i<=n;i++){ int x; scanf("%d", &x); G[x].PB(i); dep[i]=dep[x]+1; } scanf("%s", wh); for(int i=0;i<q;i++){ int v, d; scanf("%d%d", &v, &d); if(d < dep[v]) continue; que[v].PB({d, i}); } map<int,int> mp...

題目連結: http://codeforces.com/contest/198/problem/E 被雷了才會QQ 會發現其實他是個圓並不重要，重要的其實是距離，所以不妨把每個人的座標轉換成跟原點的距離，這樣的話每次詢問就變成詢問一個距離內質量小於k的數有誰，而我們其實也不用一次把一坨東西拉出來，只要一次拉一個就好，反正最多拉n個，複雜度不會太慘。而這樣其實就是詢問一個前綴極值就可達到這件事，所以就開個BIT套個單調的queue之類的就可以做到這件事了。 #include <bits/stdc++.h> using namespace std; typedef long long lld; #define PB push_back #define ALL(x) begin(x), end(x) #define FF first #define SS second const int N = 250000 + 5; const lld INF = 1LL<<31; class LiSan{ private: vector<lld> vv; public: inline void init(){vv.clear();} inline void insert(lld x){vv.PB(x);} inline void done(){ sort(ALL(vv)); vv.resize(distance(vv.begin(), unique(ALL(vv)))); } inline int size(){return vv.size();} inline int get(lld x){ return distance(vv.begin(), lower_bound(ALL(vv), x)); } inline lld ...

題目連結: http://codeforces.com/contest/861/problem/D 裸裸的對於每個字串枚舉他可能會有的子字串，然後判斷一下是否沒出現在其他人過就好了，一開始寫了hash但不知道為何一直WA，最後開個unordered_map就過了... #include <bits/stdc++.h> using namespace std; #define PB push_back unordered_map<string,int> ex; vector<string> inp; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n; cin>>n; for(int i=0;i<n;i++){ string ss; cin>>ss; for(int j=0;j<9;j++){ string tp; for(int k=j;k<9;k++){ tp.push_back(ss[k]); ex[tp]++; } } inp.PB(ss); } for(int i=0;i<n;i++){ string ans = "IOI2018Participant"; for(int j=0;j<9;j++){ string tp; for(int k=j;k<9;k++){ tp.push_back(inp[i][k]); ex[tp]--; } ...

題目連結: http://codeforces.com/problemset/problem/835/D 先觀察到一件事，是k回文的他一定也是k-1回文，這樣的話就只要知道一個子字串他最大是幾回文就好了，而這可以DP，狀態是$dp[i][j]$代表$i~j$最大可以是幾回文，而轉移也很顯然的就是$dp[i][j] = dp[i][mid]+1$，如果$i~mid == mid~r$的話，否則的話就是0，而要判斷兩個子字串是否相等其實用個hash就好了，只不過我真的不太會寫hash，搞了好久QQ #include <bits/stdc++.h> using namespace std; typedef long long lld; const int N = 5000 + 5; class Hash{ private: const lld p = 127, q = 1208220623; int sz; lld prefix[N], power[N]; public: void init(const string &x){ sz = x.size(); prefix[0]=0; for(int i=1;i<=sz;i++) prefix[i]=((prefix[i-1]*p)%q+x[i-1])%q; power[0]=1; for(int i=1;i<=sz;i++) power[i]=(power[i-1]*p)%q; } lld query(int l, int r){ // 1-base (l, r] return (prefix[r] - (prefix[l]*power[r-l])%q + q)%q; } }; // dp[4][9] : ...

題目連結: http://codeforces.com/problemset/problem/600/E 詢問子樹區間眾數和，一開始我只想到可以樹壓扁莫隊。後來被雷了之後才知道可以啟發式合併，讓子樹回傳一個map之類的東西記錄每個數字有幾個，而要把子樹們合起來的方式則採用啟發是合併，這樣可以保證每個數字最多被合併$logN$次，要算答案也很簡單，就簡單的看一下現在最大的數字個數有幾個跟維護一下和就好。 #include <bits/stdc++.h> using namespace std; #define PB push_back typedef long long lld; typedef pair<lld,int> PLI; #define FF first #define SS second const int N = 100000 + 5; int col[N]; lld ans[N]; vector<int> G[N]; PLI dfs(int,int,unordered_map<int,int>&); int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n; cin>>n; for(int i=1;i<=n;i++) cin>>col[i]; for(int i=0;i<n-1;i++){ int u, v; cin>>u>>v; G[u].PB(v); G[v].PB(u); } unordered_map<int,int> mp; dfs(1, 1, mp); for(int i=1;i<=n;i++) cout<<ans[i]<<" \n"[i==n]; return 0;...

題目連結: http://codeforces.com/problemset/problem/832/C 煩躁的一題...還因為沒注意到一定要放在整數點卡了一段時間QQ。 作法大概就是對答案二分搜，而驗證的時候，則會發現若是考慮要讓某個人往右的人達到終點，如果直接放在他身上可以，那往他左邊一點可能也可以，所以可以求出一個區間 ；同理往左的也是。這樣就轉化成為先將一堆區間填在數線上，接著詢問一堆區間是否與先前的區間們有碰在一起的地方。而找出對於往右區間的方法這裡是列了$$\frac{x-x^\prime}{s-v}+\frac{10^6-\frac{x-x^\prime}{s-v}\cdot v-x}{s+v} \leq t\\x^\prime \geq 10^6-\frac{v(10^6-x-vt)}{s}-st$$往左的則是$$\frac{x^\prime-x}{s-v}+\frac{x-\frac{x^\prime-x}{s-v}\cdot v}{s+v} \leq t\\x^\prime \leq \frac{v(x-vt)}{s}+st$$ #include <bits/stdc++.h> using namespace std; #define PB push_back typedef pair<int,int> PII; #define FF first #define SS second typedef long double llf; typedef long long lld; const int N = 1e6 + 5; int n, s; vector<PII> L, R; lld arr[N]; inline bool isOK(llf); int main(){ cin>>n>>s; for(int i=0;i<n;i++){ PII tp; cin>>tp.FF>>tp.SS; int x; cin>>x; ...

題目連結: http://tioj.infor.org/problems/1990 每次都照著換就太慢了，所以不妨做個映射$col[i]=k$代表換完後的第$i$個欄其實是原本的第$k$欄，列也是用同樣的方法，這樣的話交換$i, j$就只要$swap(col[i], col[j])$了。 #include <bits/stdc++.h> using namespace std; const int N = 1000000 + 5; string mtx[N]; int col[N], row[N]; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n, m; cin>>n>>m; for(int i=0;i<n;i++){ for(int j=0;j<m;j++) cin>>mtx[i*m+j]; } for(int i=0;i<n;i++) col[i]=i; for(int i=0;i<m;i++) row[i]=i; int q; cin>>q; while(q--){ char type; cin>>type; if(type=='S'){ int x1, y1, x2, y2; cin>>x1>>y1>>x2>>y2; x1--, y1--, x2--, y2--; swap(mtx[col[x1]*m+row[y1]], mtx[col[x2]*m+row[y2]]); }else if(type=='C'){ int a, b; cin>>a>>b; a--, b--; ...

題目連結: http://tioj.infor.org/problems/1993 DP題可以滾動，狀態大概就是$dp[i][j]$代表可否用前j個數湊出i，滾起來後就剩一維了，而且還會發現其實我每次在做的事情其實就是把他在往後移某個格數，所以可以用bitset的位移來達到優化的效果(自己$O(N)$位移會是爛的QQ) p.s. 其實bitset位移好像也是$O(N)$，但常數超小(我這裡真的找不太到資料，但他跑起來超快) #include <bits/stdc++.h> using namespace std; const int N = 100000 + 5; bitset<N> isok; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int t; cin>>t; while(t--){ isok.reset(); isok[0]=1; int n, m; cin>>n>>m; for(int i=0;i<n;i++){ int a, b, c; cin>>a>>b>>c; isok = (isok<<a)|(isok<<b)|(isok<<c); } int ans = 0; for(int i=0;i<=m;i++) if(isok[i]) ans = i; if(ans==0) cout<<"no solution\n"; else cout<<ans<<'\n'; } return 0; }

題目連結: http://tioj.infor.org/problems/1994 就照著做，分成左上左下右上右下四塊遞迴下去，但是很噁心，要判一些case QQ，賽中寫了2hr，然後就沒時間寫其他題了 #include <bits/stdc++.h> using namespace std; const int N = 1<<11; const int A=0, B=1, C=2, D=3, E=4; int n; int ans[N][N]; void dfs(int,int,int,int,int,int); int main(){ ios_base::sync_with_stdio(0);cin.tie(0); cin>>n; int sz = 1<<n; dfs(0, 0, sz, sz, 0, B); for(int i=0;i<sz;i++) for(int j=0;j<sz;j++){ cout<<ans[i][j]<<" \n"[j==sz-1]; } return 0; } void dfs(int l, int u, int r, int d, int x, int f){ if(r-l==1){ ans[l][u]=x; return; } int hal = (r-l)>>1; if(f==A){ dfs(l, u, r-hal, d-hal, x, B); dfs(l+hal, u, r, d-hal, x+hal*hal*3, E); dfs(l+hal, u+hal, r, d, x+hal*hal*2, A); dfs(l, u+hal, r-hal, d, x+hal*hal*1,...

題目連結: http://tioj.infor.org/problems/1991 大概看個一兩眼就會發現其實橫的跟直的可以分開，每個區塊都是獨立的(表示我選了這塊，我再選另一塊並不會影響前面那塊的值(某些奇怪的題目會有))，所以不難發現實作個二維的前綴和就好了，跟普通前綴和差不多，就輸出的時候再扣掉不要的部分就好了。 #include <bits/stdc++.h> using namespace std; const int N = 2000000 + 5; #define Hash(i, j) ((i)*(m+1)+(j)) bool mtx[N]; int preH[N], preZ[N]; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n, m; cin>>n>>m; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cin>>mtx[Hash(i, j)]; if(mtx[Hash(i, j)] and mtx[Hash(i, j-1)]) preH[Hash(i, j)]++; if(mtx[Hash(i, j)] and mtx[Hash(i-1, j)]) preZ[Hash(i, j)]++; preH[Hash(i, j)]+=preH[Hash(i, j-1)]; preZ[Hash(i, j)]+=preZ[Hash(i-1, j)]; } } for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ preH[Hash(i, j)]+=preH[Hash(i-1, j)]; preZ[Ha...

題目連結: http://codeforces.com/problemset/problem/842/D 寫過類似的題目，一看到就認出來了XD。考慮把所有數字塞到bitwise的trie上，這樣xor一個數字時就變成交換左右子樹了，而且其實也不用真的把每個子樹都換過一遍，只要再走下去的時候看一下要誰當左右子樹即可。那這樣就只要在一棵樹上找mex值就好了，這也不難，只要維護一下每個子節點的大小，先看左子樹是不是空的，若是就直接回傳0，因為表示往左走都沒東東了，再看一下左子樹是不是滿的，若是就只能走右邊，不然就繼續走左子樹即可。 #include <bits/stdc++.h> using namespace std; #define PB push_back #define ALL(x) (x).begin(), (x).end() const int N = 300000 + 5; const int MEM = 20*N; class Trie{ private: struct node{ node *l, *r; int size; node(){l=r=nullptr;size=0;} }; node *root, pool[MEM]; int _mem; node* newnode(){ assert(_mem<MEM); pool[_mem]=node(); return &pool[_mem++]; } int size(node *x){return x?x->size:0;} void insert(int x, node *&cur, int d){ if(!cur) cur=newnode(); ...

題目連結: http://tioj.infor.org/problems/1846 想了一段時間才想出來，我的數學一定是太爛了QQ。做法就是先用圓心距跟兩個半徑套餘弦定理求出兩個扇形的夾角，那答案就是兩個扇形的面積扣掉兩組半徑所構成的箏形面積，此外記得多判一下兩園沒交點的情況。 #include <bits/stdc++.h> using namespace std; const double PI = acos(-1); inline double dis(double,double,double,double); int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int t; cin>>t; while(t--){ int x1, y1, r1; cin>>x1>>y1>>r1; int x2, y2, r2; cin>>x2>>y2>>r2; double dd = dis(x1, y1, x2, y2); if(dd >= r1+r2) cout<<"0.00\n"; else if(dd+min(r1, r2) <= max(r1, r2)) cout<<fixed<<setprecision(2)<<min(r1, r2)*min(r1, r2)*PI<<'\n'; else{ double deg1 = acos((dd*dd+r1*r1-r2*r2)/(2*dd*r1)); double deg2 = acos((dd*dd+r2*r2-r1*r1)/(2*dd*r2)); double ans = r1*r1*deg1+r2*r2*deg2 - ...

題目連結: http://codeforces.com/problemset/problem/551/E 把序列分成$\sqrt{N}$塊後，每次操作就變得很簡單了，修改時如果那塊完整被覆蓋就直接在懶標記上修改，而如果沒有就把那塊重新建置一次；詢問時就先看一下懶標記，再查詢即可。複雜度$O(Q \sqrt{N})$ #include <bits/stdc++.h> using namespace std; typedef pair<int,int> PII; #define FF first #define SS second typedef long long lld; const int K = 710; const int N = 500000 + 5; lld arr[N], flag[K]; unordered_map<lld, PII> blk[K]; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n, q; cin>>n>>q; for(int i=0;i<n;i++) cin>>arr[i]; const int k = ceil(sqrt(n)); for(int i=0;i<n;i+=k){ for(int j=i;j<min(n, i+k);j++){ if(blk[i/k].find(arr[j])==blk[i/k].end()) blk[i/k][arr[j]].FF = j; blk[i/k][arr[j]].SS = j; } } while(q--){ int tp; cin>>tp; if(tp==1){ int l, r; lld v; cin>>l...

題目連結: http://tioj.infor.org/problems/1847 題目看了一下下才看懂，原來就是給你一張圖問你最短距離小於D的點權和。那要求最短路徑就寫個dijkstra就好，然後再掃一下看某個點距離是不是小於D，是就加點權，不是就不加。 #include <bits/stdc++.h> using namespace std; typedef pair<int,int> PII; #define FF first #define SS second #define PB push_back const int N = 100000 + 5; const int INF = (1<<30) + 5; vector<int> G[N]; int dis[N], val[N]; bitset<N> visited; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n, m, d; cin>>n>>m; for(int i=0;i<n;i++) cin>>val[i]; for(int i=0;i<m;i++){ int u, v; cin>>u>>v; G[u].PB(v); G[v].PB(u); } cin>>d; fill(dis, dis+n, INF); priority_queue<PII,vector<PII>,greater<PII>> pq; dis[0]=0; pq.push({dis[0], 0}); while(!pq.empty()){ int u = pq.top().SS; pq.pop(); ...

題目連結: http://codeforces.com/contest/854/problem/E 賽中還有一個多小時時一看到這題就知道該怎麼做了，然而想太快有許多細節忽略掉就爛掉了(後來還因為沒開long long又de了約莫5個小時QQ)。 因為保證每一行每一列都只會有一個格子被塗黑，所以其實可以把整張網格壓成一個序列(如同他給的資料一樣)，那這樣詢問一個矩形內有幾個黑格子時其實就是詢問一個區間大於A小於B的數字有幾個，可能很多人直覺就直接持久話做掉，不過我是想到先前寫過的一個做法(歸併樹)：開一顆線段樹，樹上節點是一個排序好的序列，查詢那個比K大的數字時就直接二分搜一下就好了，而若要再查小於B的數字，其實可以用扣掉比B+1大的做法做就好了。 這樣我們就會做查詢一個矩形內黑色的數量了，剩下該怎麼算的問題了。仔細想想(其實好像根本就是高一組合題)後，發現可以用扣的，那問題轉化為給你一個中間挖掉一塊的矩形，問你可以湊出幾個矩形，那顯然就是挖掉那塊矩形的上下左右一大塊都是不能用的，但是扣掉這些後左上、左下、右上、右下會被多扣，再加回來就好了。 #include <bits/stdc++.h> using namespace std; #define PB push_back #define ALL(x) (x).begin(), (x).end() typedef long long lld; const int N = 200000 + 5; class SegTree{ private: vector<int> nodes[4*N]; inline int lc(int x){return 2*x+1;} inline int rc(int x){return 2*x+2;} int size; void build(int l, int r, int arr[], int id){ if(r-l > 1){ int mid=(l+r)>>1; ...

題目連結: http://tioj.infor.org/problems/1214 前面 稍微講了一下用hash的作法，不過當參數取的不好時，hash是很有可能會撞的。如果一定要確定性的算法的話，可以把hash作法改成:對於葉節點先定義一個值，而對於非葉節點則蒐集起他所有子樹的hash值排序好後塞到map之類的容器並訂一個值(例如直接用map的size)，那這樣複雜度會退化成$O(nlogn)$但是就不會有碰撞的問題了。 1214. 樹論 之 樹同構測試 4 1272 Accepted 100 Testdata no. Time (ms) Memory (KiB) Verdict 0 4 1272 Accepted Submitter: ototot Compiler: c++11 Code Length: 1.77 KB #include <bits/stdc++.h> using namespace std; #define FF first #define SS second #define PB push_back #define ALL(x) (x).begin(), (x).end() const int N = 100 + 5; vector<int> G1[N], G2[N]; int sz1[N], sz2[N]; map<vector<int>,int> bkt; inline void init(int); int GetCentroid(vector<int>[],int[],int,int,int); int Hash(vector<int>[],int,int); int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n; while(cin>...

題目連結: http://tioj.infor.org/problems/1214 原本以為可以拿個中序前序之類的來判，但感覺還是慘慘的。後來才知道原來其實可以把一整棵樹的形狀hash起來，這樣的話就可以直接看hash值來判了，不過要怎麼hash呢?這裡的作法是先定義葉節點的hash值，而其他非葉節點則將他所有子樹的hash值平方後加起來，這樣只要根一樣的話那hash出來的值就會一樣(但有可能有碰撞)，但是這題給的是棵無根樹，若沒有用一些好方法定根，那hash出來的值就很有可能不一樣，這裡利用樹的一個特殊的性質－一顆樹的重心最多只有兩顆，所以用重心當根判一下就可以有$O(n)$的複雜度了。 #include <bits/stdc++.h> using namespace std; typedef unsigned long long llu; #define FF first #define SS second #define PB push_back #define ALL(x) (x).begin(), (x).end() const int N = 100 + 5; const int mod = 44478311; vector<int> G1[N], G2[N]; int sz1[N], sz2[N]; inline void init(int); int GetCentroid(vector<int>[],int[],int,int,int); llu Hash(vector<int>[],int,int); int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n; while(cin>>n, n){ init(n); for(int i=0;i<n-1;i++){ int u, v; cin>>u>>v; ...

題目連結: http://codeforces.com/problemset/problem/785/D 應該稍微簡單想兩下就會發現本題可以大致列出一個式子 $$ \sum_{\forall str[i]=(}{\sum_{j=1}^{\min(L_i, R_i)}{\binom{L_i-1}{j-1} \cdot \binom{R_i}{R_i-j}}} $$ 其中$L_i$代表前$i$個字元中左括號的個數，$R_i$則代表第$i$個字元後右括號的個數，這寫法的想法其實是我從左掃到右，然後計算第$i$個字元為最後一個佐括號時有幾種方法數，但是很明顯如果單單的照這樣做複雜度可能會到$O(n^2)$甚至應該會到$O(n^3)$，所以就需要用數學來把他優化，有個易證的組合恆等式 $$ \sum_{i=0}^{n}{\binom{n}{i} \cdot \binom{m}{i}} = \sum_{i=0}^{n}{\binom{n}{i} \cdot \binom{m}{m-i}} = \binom{n+m}{m} = \binom{n+m}{n}$$ (想像你要挑從$n+m$個東西裡挑$m$個，他不是出現在$n$個的那堆就是出現在$m$個的那堆) 於是乎我們就可以把一開始的式子稍微改寫幾下 $$ \sum_{\forall str[i]=(}{\sum_{j=1}^{\min(L_i, R_i)}{\binom{L_i-1}{j-1} \cdot \binom{R_i}{j}}} \\ = \sum_{\forall str[i]=(}{\sum_{j=1}^{\min(L_i, R_i)}{\binom{L_i-1}{j-1} \cdot \binom{R_i}{R_i-j}}} \\= \sum_{\forall str[i]=(}{ \binom{L_i+R_i-1}{R-1} } $$ 這樣就有了可能還是$O(n^2)$的做法，因為算組合需要$O(n)$，用二項式定理DP也還是$O(n^2)$，所以又要再觀察一點小事。發現你每次往右移動時$L$或$R$都頂多動一而已(即$L_i-L_{i-1}+R_i-R_{i-1} \leq 1 $)，所以算組合的時候也可以用一點基本的乘除運算來達到$O(1)$的轉移!!!，這樣我們就有了$O(n)/O(nlogn)$的...