oToToT的code收藏區

題目連結: https://tioj.infor.org/problems/2050 上次來這裡寫東西好像是超級久以前ㄌXD 貼一下昨天吃飯聽到的做法，但是我不會證明，求知道的人貼個 paper 給我 (｡･∀･)ﾉﾞ，只知道這是蔡孟宗教授在我高二那年二階講的算法。 這題重點是如何把一張圖的邊減少到 $O(N)$ 量級，但還是保持著一些必要的連通性。如果我昨天吃飯的時候沒聽錯的話，我們可以做 $k$ 次 BFS 來找出生成森林，每次找出來後就把它從原圖中拔掉，並記錄到我們最後要取的邊集中，如果要求雙連通分量的話，那 $k=2$ ，而像這題是某種三連通，所以 $k=3$。 所以這題就把邊減少到 $O(N)$ 量集後就可以拔掉每個點，跑一次 tarjan 找出所有其他割點，不過有一些小細節要注意一下，例如拔掉一條鍊的最邊邊兩個點不會讓圖變得不連通之類ㄉ。 &num;include <bits&sol;stdc&plus;&plus;&period;h> using namespace std&semi; const int N &equals; 2000 &plus; 5&semi; const int M &equals; 2000000 &plus; 5&semi; class BCC&lowbar;AP &lcub; &Tab;p...

題目連結: https://zerojudge.tw/ShowProblem?problemid=e201 稀有的過來寫個解。大學生活好累，每天都在被作業QAQ 一開始看錯題目了，不過因為沒看錯太多所以改個幾行就過了XD 看到這題我的第一個想法是樹DP，所以想說先想想看有沒有甚麼有用的性質。感受了一下發現我可以定義$f_u(x)$代表在$x$時間點進入$u$後再出來的時間點，那可以發現$f_u(x)=\max(a_{u0},x+d_u)$，其中$d_u$代表可以不用等待就都檢查完$u$的子樹的時間，$a_{u0}$代表如果是第0個時間點就從$u$出發那要多久後才能回到$u$並把所有教室都檢查完的時間。證明這部分成立的方法也很簡單(不過我很笨想了很久QAQ)，假設在時間點$t\geq 0$，存在一種走法最佳，那我們可以知道他的時間一定$\geq t+d_u$，因為不管怎樣我們至少一定要把底下整棵子樹都走過一遍才能回來，另外我們也知道那個最佳走法的時間也$\geq a_{u0}$，因為如果他更小的話，我們在時間點$0$的時候就可以故意等到時間點$t$在走，這樣可以走出更加的解，與假設不合，這樣我們就證明了在任意時間點$t$的任意解$g$都有$g \geq f_u(t)$，而且明顯$f_u(t)$是可以達到的，因為我們可以照著$t=0$的路徑走，那如果中間很順利不用逗留的話就達到了$f_u(x)=x+d_u$，而若是要逗留的話，那在逗留的當下我們接著的時間就會跟$t=0$的時候同步了，所以這時$f_u(x)=a_{u0}$。 講了這麼多我們現在終於知道一個人在時間點$x$進入$u$後出來的時間，那接下來就是要決定當我們在$u$的時候該以怎樣的順序走訪他的子樹們$v$了，而這時我盯著$f_u(x)=\max(a_{u0},x+d_u)$的圖(一堆平移過後的 ReLU 函數w)一段時間後猜想順序就是按著$f_u$的轉折點的$x$座標由小到大拜訪就會是好的，也就是按照$a_{u0}-d_u$由小到大走訪就會是最佳的，不過這部分我證不太出來，所以後來就依靠 Z3 證明了對於任意$s,t,x_0\geq 0$都有$a_{s0} - d_s \leq a_{t0} - d_t \Rightarrow f_t(f_s(x_0)) \leq f_s(f_t(x_0))$，那我...

題目連結: https://tioj.infor.org/problems/2027 不知道多久沒來這裡了XD，來提供一下兩個這題的做法。 一個是gamegame跟我講的做法，我覺得我應該以前都沒想過，所以紀錄一下這個有趣的作法。 這裡我們將一棵二元樹的節點集合用$\mathbb{T}$表示，並且定義幾個函數 $\text{lch}:\mathbb{T}\rightarrow\mathbb{T}, \text{lch}(x)=\text{left child of }x$ $\text{rch}:\mathbb{T}\rightarrow\mathbb{T}, \text{rch}(x)=\text{right child of }x$ $\text{sz}:\mathbb{T}\rightarrow\mathbb{N}\cup\{0\}, \text{sz}(x)=\text{size of }x$ $\text{w}:\mathbb{T}\rightarrow\mathbb{N}\cup\{0\}, \text{w}(x)=\min(\text{sz}(\text{lch}(x)), \text{sz}(\text{rch}(x)))$ 那首先有個引理：對於任意二元樹$T$都有$\displaystyle\sum_{u \in T}\text{w}(u) = \mathcal{O}(\text{sz}(T) \log \text{sz}(T))$，證明的部分就留給讀者好了(X) 白話文講一點就是如果有一個$N$個節點的二元樹，而我們對於他每個節點作的演算法都只跟那個節點小的子樹的大小有關的話，複雜度就會是$\mathcal{O}(N \log N \cdot \text{單一操作的複雜度} )$。 回到這題，可以發現如果一個區間$[L, R]$的最大值是$a_i$若且唯若$L \in [j, i]$（其中$j$是使得$j a_i$發生的最大的$j$）跟$R \in [i, j]$（其中$j$是使得$i a_i$發生的最小的$j$），而若是我們把這種性質拿去建成一棵二元樹（也就是讓可能的編號$L$都在$i$的左子樹，可能的編號$R$都在$i$的右子樹）的話我們就會拿到 笛卡爾樹 。 有了笛卡爾樹後，我們還需要一個支援插入、刪除、統計有多...

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