oToToT的code收藏區

題目連結: https://tioj.infor.org/problems/2039 注意！以下是努力壓常數後過的$O(N \log N)$作法(雖然好像大家也都是$O(N \log C)$的aliens優化解)。 這裡講一下我的作法好了，首先我們將題目視成不斷將k變大並詢問當前最大是多少。若是只有一個k的時候，我們顯然是要找一組左低右高的區間$[a_l, a_r]$，那變成兩個的時候，我們發現其實有幾種可能，一種是在$l$左邊繼續找一組左低右高的區間，或是在$r$右邊找一組左低右高的區間，或是在$(l, r)$中找一組左高右低的區間，把他們的差加進答案即可。 所以我們可以用線段樹維護我們想知道某個區間內左高右低或左低右高的最大值，這樣我們就是每次從heap拿出一個最大的區間加進答案後，把它左右中三個區間同時再塞到heap裡，繼續做到直到沒有東東可以拿，或達到k就好。 不過一般的線段樹實作會TLE，所以我寫了個zkw加上自己寫heap後就可以AC了XD #pragma GCC optimize("Ofast") #include <bits/stdc++.h> using namespace std; namespace { #define FORCE_INLINE __attribute__((always_inline)) constexpr int INF = 1 << 30; constexpr int maxn = 2'000'000; template <typename T1, typename T2> struct Pair { T1 first; T2 second; }; struct V { int val, pos_small, pos_big; }; struct S { Pair<int, int> lo, hi; V v[2]; FORCE_INLINE S(Pair<int, int> small, Pair<int, int> big, V v0, V v1) noexcept : lo{small}, hi{big}, v{v0, v1} {}; FORCE_INLINE

題目連結: http://tioj.infor.org/problems/1711 說個笑話，oToToT會寫程式。 搞了好久都不會做，然後一直假解QAQ 去網路上查到momo學長的解居然也是錯的（詳見底下測資） 10 6 522 288 963 788 756 856 18 412 378 789 2 1 3 2 4 2 5 2 6 5 7 6 8 4 9 1 10 4 最後是去問了minson才知道一個怪怪的解QQ，我到現在還是不知道這為何是好的(他說複雜度是$O(N^2)$)，可能跟CF 729F有類的概念吧。 註(2019/04/24):似乎是因為某種兩個東西只會在他們的LCA被合起來 總之就是用一個顯然的事實就是我們一個(子)樹最多只能走他底下size步，所以我們就只要維護size，並且每次上界都用當前大小做dp即可。 dp狀態也很簡單 $ dp[i][j][0] := \text{第i個節點走j步後且要走回來的最大值}, dp[i][j][1] := \text{第i個節點走j步後，停在他底下某個人的最大值} $轉移就直接暴力混和背包即可。 #include <cstdio> #include <cstring> #include <vector> #include <algorithm> const int N = 1000 + 5; int w[N], dp[N][N<<1][2]; int tmp[N<<1][2], sz[N]; std::vector<int> G[N]; void dfs(int,int,int); int main(){ int n, k; scanf("%d%d", &n, &k); k = std::min(k, n+n); for(int i=1;i<=n;i++) scanf("%d", w+i); for(int i=1;i<n;i++) { int u, v; scanf("%d%d", &u, &v); G[u].push_back(v); G[v].push_back(u);

題目連結: http://tioj.infor.org/problems/1117 學測念不完，可是又要北市賽了QQ只好把市賽題刷一刷，希望至少市賽不要出事 最近真的好笨，只會一些straightforward的題目，這題還是被雷的才出來的。 總之核心問題就是我們不能一次做太多事、要一步一步來，畢竟他每次要輸出的字串也沒多長。 那所以我們就每次要知道第n個矩陣的第i,j元素，而這可以直接根據定義直接看他在哪一塊，並且遞迴下去就會得知答案了。 #include <bits/stdc++.h> using namespace std; bool go(int,int,int); int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); for(int n, i, a, b;cin >> n >> i >> a >> b;){ for(int j=a;j<=b;j++) cout << (go(n, i-1, j-1)?"+1":"-1") << " \n"[j==b]; } return 0; } bool go(int n, int x, int y) { if(n == 0) return 0; int tl = (1<<(n-1)); if(x >= tl and y >= tl) return go(n-1, x-tl, y-tl)^1; if(x >= tl) x -= tl; if(y >= tl) y -= tl; return go(n-1, x, y); }

題目連結: https://tioj.infor.org/problems/1914 搞了好久，才發現我一開始的DP式是錯的QQ 這題難點應該就是DP式吧，不過我也不知道我怎麼想到的，所以這邊就給式子就好：$dp[i][j] = \min_{i \leq k < j }(dp[i][k]+dp[k+1][j])-[a_i==a_j]$(其中[]是 艾佛森括號 )，然後$dp[i][j]$的意思是把$[i, j]$填滿的最小步數，然後轉移方法就是枚舉中點，代表先把$[i, k]$填好再填$[k+1, j]$，而減一的部份則是因為明顯若首尾相同，那我們在填左邊的時候就可以順便拉一條過去到右邊，就不需要右邊又在畫一遍了。 #include <bits/stdc++.h> using namespace std; const int N = 200 + 5; int arr[N], dp[N][N]; int main(){ int t; scanf("%d", &t); while(t--){ int n, m; scanf("%d%d", &n, &m); for(int i=1;i<=n;i++) scanf("%d", arr+i); for(int i=1;i<=n;i++) dp[i][i]=1; for(int i=n;i>=1;i--){ for(int j=i+1;j<=n;j++){ dp[i][j]=1<<25; for(int k=i;k+1<=j;k++) dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j]); if(arr[i]==arr[j]) dp[i][j]--; } } printf("%d\n", dp[1][n]); } return 0; }

題目連結: https://codeforces.com/contest/1051/problem/F 煩人的題目，一開始看到題的時候，忘記字串可以$(N, O(logN))$比較大小，然後想了想，想出一個什麼suffix array上二分搜之類的超噁比大小作法XD 後來發現可以$O(logN)$比大小之後，又因為hash碰撞卡了一段時間，才發現我p, q打反XD 總之，這題應該可以想到一個簡單的DP狀態$dp[i]$代表把後i個弄好的方法數，哪也很明顯的如果$s_i \neq \text{'0'}$，那就是找到一個區間的$j(i \le j \leq n)$使得$L \leq s_i...s_j \leq R$然後明顯$dp[i]=\sum_{j} dp[j]$，因為我們顯然只能把$s_i$跟那些人接在一起，而若$s_i = \text{'0'}$的情況也類似，所以現在變成我們要找到那些j，不過很明顯可以發現若a跟b差不多大，那他們的位數應該也差不多，所以我們只要去比較位數差不多的那個substring，就可以得知他是不是比較大了。 #include <bits/stdc++.h> using namespace std; const int N = 1000000 + 5; const int qs[] = { 1002939109, 1020288887, 1028798297, 1038684299, 1041211027, 1051762951, 1058585963, 1063020809, 1094763083, 1106384353, 1120154459, 1140593173, 1147930723, 1172520109, 1183835981, 1187659051, 1241251303, 1247184097, 1255940849, 1272759031, 1287027493, 1288511629, 1294632499, 1312650799, 1314753281, 1320080669, 1321970357, 1333133947, 1337684419, 1353508067, 1358715989, 1364961029, 1366

題目連結: https://tioj.infor.org/problems/1941 這題應該可以輕鬆想到$O(N^2)$的DP方式，同時也會發現那樣子太慢。 仔細觀察DP的表格後，發現他是一個單調的表格，也就是由左至右遞增，同時由下至上遞增，接著研究一下每個轉移對DP表格的貢獻，發現他必定會將他自己那個區間的DP值+1，而後面則為了要維護單調的性質，會再跟他取max。 那這類題目，其實我們可以維護每一段的DP值，每次加入一個新的轉移來源後，也代表加入了一個斷點，但是同時也有可能把自身後面的斷點吃光光。 所以複雜度會是$O(N log N)$，因為每個斷點只會出現跟消失一次，而單次新增跟刪除了複雜度都是$O(log N)$ #include <bits/stdc++.h> using namespace std; class BIT{ private: int n; vector<int> arr; inline int lowbit(int x){return x&(-x);} void modify(int p, int x){ for(;p;p-=lowbit(p)) arr[p] += x; } public: void init(int n_){ n = n_; arr.clear(); arr.resize(n); } void modify(int l, int r, int v){ modify(l, -v); modify(r, v); } int query(int x){ int ret = 0; for(;x<n;x+=lowbit(x)) ret += arr[x]; return ret; } } bit; set<int> st; int main(){ int n; scanf("%d", &n); bit.init(n+1); st.insert(n); for(int i=0;i<n;i++){ int l, r; scanf("%d%d", &l, &r); st.insert(l);

題目連結: https://codeforces.com/problemset/problem/1027/F 我好笨QAQ 本題關鍵大概是想到可以把每個考試當做邊來看吧OAO（看了解才知道 假設知道這件事後，那其實就很簡單，當然對於每個連通元件分開處理，明顯的如果邊數較點數多，那一定無法構造出一個合法的結果。 接著當邊數跟點數一樣多的時候，一定存在解，因為他必定可拆成幾個環跟一些連接的邊，那這時這裡的答案就是點的最大值。 還有邊數是點數減一的時候，不難發現他是顆樹，然後答案會是次大值。 邊數是點數減二的時候則不可能出現，所以討論這幾種狀況就可以得到答案了。 #include <bits/stdc++.h> using namespace std; using lld = int64_t; using PII = pair<int,int>; #define PB push_back #define FF first #define SS second #define ALL(x) begin(x), end(x) #define SZ(x) (static_cast<int>(std::size(x))) const int N = 2000000 + 5; class LiSan{ private: vector<lld> vv; public: template<typename... Args> void insert(lld x, Args& ...oth){insert(x);insert(oth...);} void insert(lld x){vv.PB(x);} void done(){ sort(ALL(vv)); vv.resize(distance(vv.begin(), unique(ALL(vv)))); } int size() const { return SZ(vv); } int get(lld x){ return static_cast<int>(distance(vv.begin(), lower_bound(ALL(vv), x))); } lld inv_get(in

題目連結: https://codeforces.com/problemset/problem/1017/E 比賽unrated了，不知道好險還是好慘，前面做題真的做超慢，然後到現在還是不知道為什麼C那樣做就好了。 不過這題其實滿有趣的。 可以發現這題其實要問的就是兩個東東他們的凸包是否相同(允許旋轉及位移，但不能鏡射)，原因就是會發現結束的時候，一個engine構成的power field一定會變成一個凸多邊形，然後現在考慮若是拆掉凸多邊形上任意一個頂點，那他必定會縮進去(沒有兩個點在相同的位置)，所以我們一定要用另外一個engine來補，才可以讓他不會縮進去，也因此其實就是每個頂點都要在一樣的位置。 那要怎麼做呢？當然，先求出凸包之後，拿到的凸包顯然會按(順/逆)(看實作)時鐘的方式排序點，所以我們其實就是要求，兩個凸包是否有某種旋轉操作(abc->bca->cab...)使他們相同。 我原先是用booth's algorithm幫兩個東東都求出最小字典序的旋轉，再來一個一個比較是否一樣，但也有其他作法。 字串相關的作法就是將其中一個凸包複製一次貼在自己後面(abc->abcabc)，然後hash或kmp直接求是否另一個凸包出現在裡面。 不過其實暴力枚舉一個東東旋轉後的長相然後判斷相等就可以過了，因為其實整數點上的凸包大小最多只有$\sqrt{C}$，所以直接枚舉的複雜度也才$\sqrt{C} \times \sqrt{C} = C$。 但這題最難的點，我覺得其實要怎麼把凸包變成一個序列，且他可以拿來判斷旋轉位移後可以一樣，但鏡射不行，原本我的想法只有判斷所有邊的長度跟所有角的角度是否一樣，但是卻被 Hack 掉了，後來才發現我需要把角跟邊擺在一起才可以成立，不然鏡射的話他拿的邊順序及角順序也可以一樣，但實際卻長得不一樣。 #include <bits/stdc++.h> using namespace std; #define PB push_back #define ALL(x) begin(x), end(x) #define SZ(x) (static_cast<int>((x).size())) using lld = int64_t; struct PT{ lld x, y;

題目連結: http://tioj.infor.org/problems/1067 直接DP餘數即可，因為餘數$gcd(a, b) = gcd(a%b, b)$ #include <bits/stdc++.h> using namespace std; const int N = 1000 + 5; const int C = 10000 + 5; inline int gcd(int a, int b){return b?gcd(b, a%b):a;} int dp[2][C]; int main(){ ios_base::sync_with_stdio(0); cin.tie(0); bool me=0, he=1; int n, m; while(cin >> n >> m, n or m) { memset(dp[me], -1, sizeof(dp[me])); dp[me][0] = 0; for(int i=0;i<n;i++){ int x; cin >> x; for(int j=0;j<m;j++) if(dp[me][j] >= 0) { dp[he][j] = max(dp[he][j], dp[me][j]); dp[he][(j*10+x)%m] = max(dp[he][(j*10+x)%m], dp[me][j]+1); } memset(dp[me], -1, sizeof(dp[me])); swap(me, he); } int ans = 0; for(int i=0;i<m;i++) if(gcd(i, m) == 1){ ans = max(ans, dp[me][i]); } cout << ans << '\n'; } return 0; }

題目連結: http://tioj.infor.org/problems/1852 有趣的題目XD，看到24先猜砍半枚舉，但想了一段時間才知道該怎麼讓枚舉出來的兩個集合跟答案有關連。 首先發現，假設最後選出來的三個數字分別是$(a, b, c)$(不失一般性假設$a \geq b \geq c$)，也就是說假設在枚舉出來的第一個集合中有一個三元組$(x, y, z)$(沒有大小關係)，那只要在第二個集合中找到$(x^\prime, y^\prime, z^\prime)$使得$x+x^\prime \geq y+y^\prime \geq z+z^\prime$就好。 接著考慮$a-b, c-b$，發現只要$a-b\geq 0 \land c-b \leq 0$就可以代表$a \geq b \geq c$，也就是說對於第一個集合中的$(x, y, z)$，我們就是要找到使得$x+x^\prime-(y+y^\prime) \geq 0 \land z+z^\prime - (y+y^\prime) \leq 0$(也就是$y^\prime - x^\prime \leq x-y \land y^\prime - z^\prime \geq z-y$)成立的$(x^\prime, y^\prime, z^\prime)$中，$x^\prime - z^\prime$最小的那個，因為他就代表$(x, y, z)$可以配出的最小值($x+x^\prime - (z+z^\prime)$)。 這樣，就會發現問題轉換成給你一堆二維帶權資料點($(y^\prime - x^\prime, y^\prime - z^\prime)$, $x^\prime - z^\prime$)，請求出第一維大於等於某個數且第二維小於等於某個數中，值最小的那個。這問題簡單的對一維排序後，加上一些前(後)綴極值資料結構，再利用雙指針就可以解決了 #include <bits/stdc++.h> using namespace std; typedef int64_t lld; const int N = 24; const lld INF = 1LL<<60; class BIT{ private: vector<lld> arr; inl

題目連結: http://tioj.infor.org/problems/1696 看來我對重心剖分的理解還不夠QQ，一直想成重心樹的父子關係會跟原本的樹一樣。 我對於每個重心樹上的點維護他重心子樹們中$ dis \leq i, \forall 0 \leq i \leq D_{max} $的人有幾個(其中dis代表在原樹上的距離)，以及扣掉某個小孩的子樹後的這坨值。接著對於每個人就當做一個詢問，從葉子往上走訪重心樹，同時查詢不走剛剛來的那個點的子樹，距離好的點有幾個。 #include <bits/stdc++.h> using namespace std; #define ALL(x) begin(x), end(x) #define PB push_back #define SZ(x) ((int)(x).size()) const int N = 100000 + 5; struct node{ int cur, dis; node(int a=-1,int b=0):cur(a),dis(b){} }; vector<node> path[N]; vector<int> sum[N], fa_sum[N]; bool done[N]; int sz[N], M[N], fa[N], dis[N], que[N], cen[N]; vector<int> G[N]; int CenDe(int); int Query(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 >> que[i]; for(int i=0;i<n-1;i++){ int u, v; cin >> u >> v; G[u].PB(v); G[v].PB(u); } int cent = CenDe(1); partial_sum(ALL(sum[cent]), sum[cent].begin()); for(int i=1;i<=n;i++) cout << Que

題目連結: http://tioj.infor.org/problems/1094 這題有三種作法，一種是我看完馬上想到的砍半枚舉後套trie #include <bits/stdc++.h> using namespace std; const int LOG_C = 20; const int N = 30 + 5; inline int two(int x){return 1<<x;} class Trie{ private: static constexpr int MEM = 5000000; struct node{ int lc, rc; node(): lc(0), rc(0){} } nodes[MEM]; int mem_, root; inline int new_node(){ assert(mem_ < MEM); nodes[mem_] = node(); return mem_++; } void insert(int x, int& cur, int d){ if(!cur) cur = new_node(); if(d == -1) return; if(x & two(d)) insert(x, nodes[cur].rc, d-1); else insert(x, nodes[cur].lc, d-1); } int query(int x, int cur, int d){ if(d == -1) return 0; if(x & two(d)) swap(nodes[cur].lc, nodes[cur].rc); int ret = 0; if(nodes[cur].rc) ret = query(x, nodes[cur].rc, d-1) + two(d); else ret = query(x, nodes[cur].lc, d-1); if(x & two(d)) swap(nodes[cur].lc, nodes[cur].rc); return ret; } public: void init(){

題目連結: http://codeforces.com/problemset/problem/909/C 我不會DP QAQ 本題狀態可以訂成$dp[i][j]$代表到第$i$個statement時有$j$個intent的方法數，那轉移想了想後就可以得到，如果前面是for statement，那顯然現在的東西就只能擺在跟他同一個intent，而若前一個是普通的statement，則我們可以擺到intent比較小的任意一個位置。而這樣的話複雜度會變成$O(N^3)$，但是其實我們可以透過預處理前綴和以達到$O(N^2)$的複雜度。 #include <bits/stdc++.h> using namespace std; typedef long long lld; const int MOD = 1000000007; const int N = 5000 + 5; bool arr[N]; lld dp[N][N], sum[N]; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n; cin>>n; for(int i=1;i<=n;i++){ string ss; cin>>ss; if(ss[0]=='s') arr[i] = 1; else arr[i] = 0; } auto psum = [](int l, int r){ // 0-base [l, r] if(l) return sum[r]-sum[l-1]; else return sum[r]; }; dp[0][0] = 1; for(int i=1;i<=n;i++){ if(arr[i-1]){ sum[0] = dp[i-1][0]; for(int j=1;j<=n;j++) sum[j] = (sum[j-1]+dp[i-1][j])%MOD; if(arr[i]) for(int j=0;j<=n;j++) dp[i][j] = (psum(j, n)+MOD)%MOD; else for(int j=1;j<=n;j++) dp[i][j] = (psum

題目連結: http://tioj.infor.org/problems/1134 想了想覺得把1換成-1, 0換成1之後會有好事情，然後似乎可以做類似最大子矩陣的方式，但是我不知道該怎麼用。 被雷了之後才發現其實我只要把兩個問題合在一起就好了，一個是最大子矩陣，一個是某種找有多少大於零的序列的問題。首先我們可以先對一維用前綴和之後枚舉頂跟底，接著就變成一維的問題了，變成一維的問題後就是要問說對於所有大於零的序列中，最長是多少，作法也是考慮枚舉前綴和，每次只要查小於當前前綴和的所有鍵值中最小的值是多少，接著就把當前前綴和當做鍵值，現在的位置當作值插到某種資料結構就好了。 #include <bits/stdc++.h> using namespace std; #define ALL(x) begin(x), end(x) const int N = 200 + 5; const int INF = 1<<30; class LiSan{ private: vector<int> vv; public: inline void init(){vv.clear();} inline void insert(int x){vv.push_back(x);} inline void done(){ sort(ALL(vv)); vv.resize(distance(vv.begin(), unique(ALL(vv)))); } inline int size(){return vv.size();} inline int get(int x){ return distance(vv.begin(), lower_bound(ALL(vv), x)); } inline int inv_get(int x){return vv[x];} } lisan; class BIT{ private: vector<int> arr; int n; inline int lowbit(int x){return x&(-x);} public: void init(int n_){ n = n_; arr.resize(n);

題目連結: http://poj.org/problem?id=1067 我通靈不出來，盯了他一個晚上只發現對於每個$i$都有一個$j$使他慘掉(?，而且似乎有個1.6左右的比例，但我就不會了QAQ 正解是這個： 威佐夫遊戲 結論就是只要看符不符合$i < j \land (j-i)\frac{1+\sqrt{5}}{2} == i$就可以了。 我缺少知識QQ #include <iostream> #include <cmath> using namespace std; int main(){ ios_base::sync_with_stdio(0);cin.tie(0); long double TongLing = (sqrt((long double)5)+1)/2; int n, m; while(cin>>n>>m){ if(n > m) swap(n, m); cout << ((int)((m-n)*TongLing) != n) << '\n'; } return 0; }

題目連結: http://codeforces.com/contest/912/problem/E 記錄一下覺得滿有趣的題目。 首先要知道$10^{18}$以內的只包含包個質因數的數，大約只有$10^6~10^7$種左右，所以我們可以把給定的$n$個質數採用砍半枚舉產生出所有$10^{18}$以內僅包含給定的質因數的數，但是因為如果真的把全部都長出來了會太大，所以我們還可以二分搜第k大會是誰，這樣就只要知道比某個數小的數字有幾個就好了，而計算這個的方法很簡單，就枚舉一邊，再二分搜另外一邊即可。 #include <bits/stdc++.h> using namespace std; typedef uint64_t llu; #define PB push_back #define ALL(x) begin(x), end(x) const llu C = 1000000000000000000LL; llu primes[20], p1[10], p2[10]; vector<llu> num1, num2; inline llu calc(llu); void dfs(int,llu,llu[],int,vector<llu>&); int main(){ ios_base::sync_with_stdio(0);cin.tie(0); int n; cin>>n; for(int i=0;i<n;i++) cin>>primes[i]; sort(primes, primes+n); int n1 = 0, n2 = 0; for(int i=0;i<n;i+=2) p1[n1++] = primes[i]; for(int i=1;i<n;i+=2) p2[n2++] = primes[i]; dfs(0, 1, p1, n1, num1); dfs(0, 1, p2, n2, num2); sort(ALL(num1)); num1.resize(distance(num1.begin(), unique(ALL(num1)))); sort(ALL(num2)); num2.resize(distance(num2.begin(), u