oToToT的code收藏區

題目連結: https://tioj.infor.org/problems/1975 首先本題要可以觀察到對於只有即時性工作時我們很簡單的就是計算他重疊最多的部分是多少，而對於非即時性工作則是要透過由deadline由小到大排後，每次選取被加值最少的那些不重疊區間來分配，最後計算最大值。 合併這兩個思考之後就可以發現本題變成一個用treap可以維護的題目了XD #include <bits/stdc++.h> using namespace std; const int N = 100000 + 5; const int C = 1000000 + 5; namespace Treap{ #define sz( x ) ( ( x ) ? ( ( x )->size ) : 0 ) #define sm( x ) ( ( x ) ? ( ( x )->sum ) : 0 ) struct node{ int size, cnt, sum; uint32_t pri; node *lc, *rc; node(): size( 0 ), cnt( 0 ), sum( 0 ), pri( rand() ), lc( nullptr ), rc( nullptr ) {} node( int x ): size( 1 ), cnt( x ), sum( x ), pri( rand() ), lc( nullptr ), rc( nullptr ) {} void pull() { sum = cnt; if ( lc ) sum += lc->sum; if ( rc ) sum += rc->sum; size = 1; if ( lc ) size += lc-...

題目連結: http://tioj.infor.org/problems/1726 為什麼$O((N+Q)\sqrt{N})$跑得比$O((N+Q)\sqrt{N}log(N))$還要慢啊，我居然是倒數的，明明上面的人複雜度都慘的（？ 總之我的想法是分塊，然後對每塊都用$O(N^2)$的方式算完每塊內的答案，接著如果答案是跨多個塊的話，則我們只要掃過每一塊，並記錄當前遇到最後面的a跟b出現在哪，然後再看看現在看到這塊的a跟b最前面出現在哪就好，完成後更新a,b的最後位置，再去檢查下一塊。 易知當塊大小為k時，複雜度為$O(Nk+\frac{NQ}{k})$故取$k=\sqrt{N}$時最佳。 #include <iostream> #include <vector> #include <utility> #include <unordered_map> using namespace std; const int N = 60025 + 5; const int SQRT_N = 245; const int INF = 1<<30; vector<pair<int,int>> que; unordered_map<int,int> ans[N], fi[SQRT_N], se[SQRT_N]; int arr[N]; int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); int n, q; cin >> n >> q; for(int i=0;i<n;i++) cin >> arr[i]; n = (n+SQRT_N-1)/SQRT_N*SQRT_N; for(int i=0;i<q;i++){ int x, y; cin >> x >> y; if(x > y) swap(x,y)...

題目連結: 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...

題目連結: 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; ...

題目連結: 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 艾佛森括號 )，然後$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]--; } } pr...

題目連結: 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, ...