省選前的考試記錄

日拱一卒功不唐捐
什么沙雕玩意兒

2018.12.24
T1 如果對 \(A\) 數組求出來高度遞減的單調棧的話，會發現只有單調棧里的元素是有用的。因為如果有 \(A[i]<A[j] \And i<j\)，那電梯就可以在帶 \(j\) 上樓的時候順便把 \(i\) 帶上并不會影響結果。所以第一步先求出來單調棧。
列出 \(DP\) 式 \(f[i]=\min\left\{\max(f[j],T[i])+A[j+1]\right\}\) 。打表發現 \(f\) 數組是單調不降的，所以可以把式子中間的 \(\max(f[j],T[i])\) 拆成兩部分，前面一部分是 \(f[j]\)，后面一部分是 \(T[i]\)。然后對這兩部分分別取 \(min\) 即可。
暴力復雜度 \(O(n^2)\)，線段樹優化 \(DP\) 復雜度 \(O(n\log n)\)。

T2 一個顯然的 \(DP\) 狀態是 \(f[i][j]\) 表示決策完左部點的前 \(i\) 個，最后一個匹配的右部點小于等于 \(j\)，形成的最大匹配。
轉移就是對于 \(l[i]\le p\le r[i]\) 的 \(f[i][p]=f[i-1][p-1]+1\)，然后再對所有的 \(j\) 取個前綴最大值即可。 可以發現如果第一維固定那這個數組的值是單調不降的。
第一維可以滾動數組優化掉，第二維可以拿平衡樹維護 \(DP\) 值。具體點就是來了一個區間 \([l_i,r_i]\)，那我們把 \([l_i,r_i]\) 這段區間 \(+1\)，然后刪掉 \(r_i\) 位置的元素，再在 \(l_i\) 位置插入一個新的元素，它的 \(DP\) 值應該是 \([1,l_i-1]\) 的 \(DP\) 值的 \(\max\)。
對于這個做法我們并不能舉出反例所以這個做法就是正確的 廢tm話 總時間復雜度 \(O(n\log n)\)。

T3 這誰能想出來啊...日常懷疑人生
直接上做法 離線+掃描線。
如果當前掃描到了 \(r\)，那我們需要維護前面有哪些左端點 \(l\) 滿足 \([l,r]\) 是一個值域連續的區間。維護的方法就很神仙了。
建一棵線段樹，支持查詢區間最大值以及最大值出現的位置，如果出現多次則記錄最靠右的位置。每個點的初值是下標。設 \(pos[i]\) 表示點 \(i\) 在給出的排列中出現的位置。在掃描過程中這樣寫:

if(a[i]>1 and pos[a[i]-1]<i) modify(1,1,n,1,pos[a[i]-1],1);
if(a[i]<n and pos[a[i]+1]<i) modify(1,1,n,1,pos[a[i]+1],1);

結論：如果 \(val[l]=r\) 那么 \([l,r]\) 是一段值域連續的區間。

證明：如果 \(val[l]=r\) 那么說明 \(l\) 這個位置被加了 \(r-l\) 次。也就是說在 \([l,r]\) 這個區間內，存在 \(r-l\) 個權值連續的數對，感性理解一下發現這和 \([l,r]\) 是一段值域連續的區間是等價的。
這樣就可以動態維護哪些區間是值域連續的區間了。對于一個詢問 \([ql,qr]\)，我們在 \(qr\) 時將這個詢問放進以左端點為第一關鍵字的大根堆里，在線段樹上查詢是否存在 \(i\in[ql,qr]\And val[i]=r\) 。如果存在那就說明找到了一個合法的區間，否則根據單調性應該 \(break\) 掉表示如果左端點更小的話就更沒有符合的區間了，這時應該讓當前掃到的右端點 \(+1\) 然后繼續判斷。
時間復雜度 \(O(n\log n)\)。

2018.12.25

T1 啊woc最煩這種tm刷顏色還帶覆蓋的題了。xjb貪心就行了woc是真不愿意寫這種惡心題的題解告辭。

T2 首先設 \(f[i]\) 表示從 \(i\) 到 \(n\) 的期望步數,\(deg[i]\) 為 點 \(i\) 的度數。那么有 \(f[n]=0\)，\(f[1]\) 即為答案。轉移方程就是

\[f[x]=\frac{m+\sum_{x\rightarrow y}min(f[x],f[y])}{deg[x]}\]

題目里的最優決策在這里就可以體現出來了，具體是只選擇 \(f[y]<f[x]\) 的那些 \(y\) 來對 \(x\) 進行轉移。為什么是對的可以證明 \(f[x]\) 被 \(f[y]\) 更新前后的值是 \(f'[x]<f[x]\) 的（\(f[y]<f[x]\)）。

所以我們就可以開心的跑 \(dij\) 了。每次選取 \(f\) 最小的節點去更新其它節點，這樣就可以保證當前取到的 \(f\) 一定比要去更新的 \(f\) 更小，更新的時候動態記錄每個點的 \(deg\) ，直接更新就吼了。

T3 其實可以暴力分塊艸過去的
對于 \(\le \sqrt n\) 的那些 \(k\) 暴力求出答案，因為只有 \(\sqrt n\) 個所以這部分復雜度為 \(O(n\sqrt n\log n)\)。
對于 \(\ge \sqrt n\) 的那些 \(k\) 它們的答案一定小于 \(\sqrt n\) （感性理解一下并不會證），所以這部分就可以枚舉最后的答案 \(x\) ，然后求出最少有多少個關鍵點時最遠距離 \(\le x\)。最后取個前綴 \(min\) 九星了。這部分的復雜度是 \(O(n\sqrt n)\) 的。
同時我們還需要一點卡常技巧。比如說在 \(check\) 函數里加個記憶化會跑的飛快（\(check\) 函數就是求最遠距離 \(\le x\) 的時候最少要放幾個關鍵點），同時第二部分枚舉的答案要是 \(min(\frac n{block},ans[block])\)。一定記得和 \(ans[block]\) 取個 \(min\) 。因為如果放多于 \(block\) 個關鍵點答案一定會比 \(ans[block]\) 變得更小。加上這兩個優化就可以 \(1500ms\) 通過本題了。嗷對了還有一個忘了說了就是遞歸 \(dfs\) 的話 太！慢！了！所以我們要把這棵樹的后序遍歷 \(dfs\) 序存下來，然后每次 \(O(n)\) 的掃一遍。這樣比遞歸快到不知道哪里去了。

2018.12.26

明天終于不考試了耶

T1 隨便哈希亂搞就行了

T2 可以拿單調棧維護每個小球領先的時間段，然后雙指針掃就行了。把 double 開成了 int 少了25pts凎哦。

T3 考場上的思路只是單純的三進制狀壓質因子...然而會有bug就是放一個6再放一個6是合法的...所以狀態要額外記一些東西。再額外開15位狀壓，存每兩個質數對能不能選。實現比較有意思，可以拿map存狀態，然后每次找map的首迭代器，然后把它刪掉。原因是每次轉移必然是從較小的數轉變為較大的數，所以用map而不用隊列存下來就可以保證每個節點不會重復入隊。把三進制換成四進制比較好寫。還要注意的就是如果先放個2再放個3那就不能放6了，這種情況要考慮到就沒啥了。

2018.12.28

三道水題...

T1 隨便分塊就行了

T2 就是一個AC自動機但是字符集太大所以可持久化數組搞一下

T3 SG函數再記錄一個'如果想輸是否一定能輸'，然后分類討論即可。

不知道考試的時候在干點啥

2018.12.30

T1 挺妙的吧...顯然每次要取集合中最大的元素，同時每次只會新加進來一個數。如果這個數大于當前集合中最大的元素那就取了它，否則就取集合中的那個元素，然后暴力找當前集合中最大的元素。這個暴力找具有單調性所以復雜度 \(O(NK)\)。但是卡常就很過分了。

T2 首先一個性質就是選中鏈的兩個端點一定是一個為 \(maxn\) 一個為 \(minn\)，第二個性質是一條鏈不是單增就是單減。這兩個性質都可以反證法證出來。然后常規樹形DP就行了。

T3 先咕著。

woc我竟然咕了9天了 藥丸藥丸

2019.01.02

T1 并沒有去寫...說一下大概思路吧

就是答案最多在 \(9n\log n\) 范圍內，所以考慮狀態中加上答案。

設 \(f(c,x)\) 表示一個 \(\max y\) ，使得 \([x,y]\) 的答案不超過 \(c\)。

考慮轉移，假如 \([x,y]\) 選了 \(i\)，那么就要求 \(f(c-a_i,x)\ge i-1,f(c-a_i,i+1)\ge y\)。

先咕著

T2 設 \(f(i)\) 表示長度為 \(i\) 的沒有回文后綴的字符串個數。考慮往末尾添加一個元素，長度從 \(i\) 變為 \(i+1\)，有 \(s\) 種填法，但是可能形成一些回文后綴，長度一定是 \(i+1\)，所以遞推式就是 \(f(i)=s\cdot f(i-1)-f(\frac i2)\)。

T3 傻逼斯特林數

2019.01.07

T1 觀察到答案一定在 \(\log \text{值域}\) 范圍內。把給定序列的生成函數搞出來，枚舉答案，然后FWT起來就行了。

T2 毒瘤容斥題

容斥，枚舉哪些格子強制有車

然后再容斥，枚舉哪條對角線放車

T3 什么垃圾min25篩咕掉 抵制日貨從我做起

2019.01.09

三道亂搞題

T1 把9000種地圖都搞出來然后從頭開始問，問不了幾個就都排除了。

T2 構造題啊...先咕著

T3 有一萬種方法過這題啊...誰能證明一下我的方法的充分性啊...

2019.01.10

T1 70分暴力就是把所有環塞進線性基里，然后求出有多少個本質不同的每個點到 \(1\) 的距離。然后這些本質不同的距離乘2^{線性基大小}就是答案。本質不同指的是放進線性基中最后被識別出來是不一樣的。

然后滿分做法就是套路離線，考慮加邊的種類。

假如當前邊的兩個端點都不在1號點所在聯通塊，那么不管它。

否則，如果兩個端點都在1所在聯通塊，此時就加了一條非樹邊，我們在線性基中插入它對應的環，如果插入成功，這種情況最多只會發生logW次，此時就暴力把所有樹鏈重新跑一遍。

否則，兩個端點一個在1所在聯通塊，一個不在，這時就dfs一下新的聯通塊來得到新的聯通塊帶來的樹邊和非樹邊，然后插入線性基即可。

T2 一個很常見但是我又沒有見過的性質就是 如果一個多項式是k次多項式，那么它的 k+1 或更高階差分始終為0，也就是說這個多項式的每一項都為0.

假如當前有了兩個多項式 \(a,b\)，如何判斷是否存在這個多項式 \(P\) 呢？我們記 \(a\) 數組的 \(k\) 階差分為 \(\Delta^k a\)。不難發現，\(\Delta^{m+1}P_i=\Delta^{m+1}a_i-\Delta^{m+1}b_i\)。

因為 \(P\) 是 \(m\) 次多項式，所以它的 \(m+1\) 階差分肯定為 \(0\) 。問題就轉化成了求出 \(a\) 和 \(b\) 的 \(m+1\) 階差分，然后判斷它們是否相等就好了。

怎么求一個多項式的 \(k\) 階差分呢？公式就是 \(\Delta^k A_i=\sum\limits_{j=0}^k (-1)^j\cdot C_k^j\cdot A_{i-j}\)，\(NTT\) 即可。

那怎么解決 \(B\) 串的循環同構呢？倍長一遍接在后面就好了。

整理一下思路：把 \(B\) 倍長，求出倍長后數組和 \(A\) 數組的 \(m+1\) 階差分，然后做字符串匹配就行了。

一個小細節需要注意就是如果原串 \(A\) 和原串 \(B\) 的匹配位置是 \(A\) 的 \([l_1,r_1]\) 和 \(B\) 的 \([l_2,r_2]\)，那在 \(k\) 階差分后的數組上匹配的就是 \(\Delta^kA\) 的 \([l_1+k,r_1]\) 和 \(\Delta^k B\) 的 \([l_2+k,r_2]\)。

T3 簡化題意就是找出 \(k\) 條不相交且邊權和最大的鏈，每次找直徑然后取反即可。

2019.01.11

T1 傻逼貪心

T2 之前做過一道這題的弱化版 然后把那題的思路拿過來改了改就過了

T3 線段樹維護凸包... 還是第一次寫 這種動態添加元素的有個套路就是，如果線段樹上的一個節點對答案有完整貢獻（也就是被詢問區間完整包含），那這個區間的元素一定全部添加完畢，也就是說區間右端點的元素一定已經添加。所以每次插入第 \(i\) 個元素的時候只需要將線段樹上所有右端點等于 \(i\) 的區間求出來凸包就好了。然后求凸包emmm，終于徹底會用叉積了，\(cross(a,b)>0\) 表示的是 \(a\) 能逆時針轉到 \(b\)。判斷 (top-1)->(top) 和 (top-1)->(i) 的叉積，如果維護的是上凸包且叉積為正那就要彈棧，下凸包且叉積為負同樣需要彈棧。

2019.01.12

心態爆炸導致棄療

T1 傻逼樹套樹+啟發式分裂 但是過不了。觀察到啟發式分裂+樹套樹是三個log的，如果換成啟發式分裂+平衡樹就是兩個log就能過了。強行湊復雜度沒啥意思啊....

T2 咕咕咕咕

T3 啊這題 首先求出來遞推式：\(f[i]=f[i-1]+\sum\limits_{j=1}^{i-1} f[j]\cdot f[i-j]\) 邊界條件是：\(f[0]=0,f[1]=1\)

把 \(f\) 的生成函數搞出來得到 \(F=xF+F^2+x\) ，求根公式一下變成 \(F=\frac{1-x-\sqrt{x^2-6x+1}}{2x}\)

留坑

好的現在徹底搞懂了。

就是它的分母沒有常數項不能求逆怎么辦

我們可以先設一個 \(G=xF\)，這樣先求出來 \(G\)，然后把 \(G\) 整體平移一位就得到 \(F\) 了。

2019.01.14

T1 如果沒有 \(a\) 的限制的話就是一個斜率優化，但是增加了一維限制，考慮 \(CDQ\) 分治降維。注意先遞歸左邊再算中間再遞歸右邊，這樣就不能歸并了，復雜度 \(O(n\log^2n)\) ，不是很跑的過去。考慮預處理這個東西，即 \(CDQ\) 過程中每層的每個元素都是什么，這個直接歸并就好了。復雜度 \(O(n\log n)\)。

T2 T3 咕咕咕咕咕

哇不知不覺我已經咕了一個多月了

中間好像有一個重要的考試啊

沒錯就是WC

唔考的很爛很爛

考試的時候什么狀態呢？

第一次經歷這種全國高端玩家在一個體育場里同臺競技，感覺確實和平時考試的感覺不一樣吧

一個十分清晰的感受就是考試的時候時間過得太快太快了，而且由于沒有特殊訓練過五個小時的比賽，對時間沒什么概念

開場之后掃了一眼題，看看部分分，目標分數大概是 70+60+50，這樣大概就能au了？

開T1 只會opt=0,y=1和n<=5的點，感覺藥丸，想著無論如何也要想出來opt=1的，這樣T1就有70+了，但是越想越想不出來，然后心態漸漸失衡

滾去想T2 感覺前三個點應該很快能寫完，但第二個子任務一直在想著怎么在程序里用兩個數字遞推斐波那契，忘記了打表，然后就涼涼了。第二次，第二次我忘記打表這個工具了。第三個子任務其實就是一個最短路，但是考場上犯sb覺得十分繁瑣，感覺需要多路增廣，然后就沒有再去想。

T3 最后兩個小時的時候去想T3 看第一個子任務的分值十分誘人，想著就是暴力分類討論我也要寫出來第一個點，然后就開始漫長的分類討論，大概40分鐘后碼完了130+行的分類討論，此時心情已經十分煩躁了。但是還是要感謝考場上的自己沒有放棄，而是用下發的交互庫繼續去調了20分鐘代碼，不然的話連cu有沒有都還是個問題。其實再仔細想想的話前兩個點都可以直接歸并排序做，第三個點二分也就沒什么大問題。但是沒想到就是沒想到吧。

下來之后反思自己，還是對時間的掌控不夠好。而且心態極其容易受到干擾，一道題做不出來導致整場比賽發揮不理想這也不是第一次了，上次這樣的大型比賽是noip2018的D2。

結局沒有達到自己的預期，但是意外的在這個弱省不錯？而且寫了的分基本都拿到了只有T1掛了4分。稀里糊涂拿了個Ag吧但是并沒有滿意，還得繼續努力啊。

↑好了上面就是WC的游記

2019.02.22

T1 最開始看T1沒什么思路，但是剛了半天T2又反過頭來看之后思路一下子清晰了。就是按照期望DP的套路那樣做就行，沒什么好說的，因為沒有特判1掉了10pts

T2 其實如果把想到的都寫上可以拿75分啊。。。然而因為T3暴力寫掛的原因一直在調T3導致心態爆爆爆爆爆炸。其實就是一個折半，然后map隨便記錄一下就好了。

T3 推一推式子發現A,B,F都可以O(1)算，然后樹套樹隨便搞就行了。然而掉了10pts不知道是wa了還是T了。垃圾暴力毀我青春。

操犯傻逼了并不是T3暴力寫錯了

樹套樹寫GG了

大概就是因為是單點修改區間查，所以在修改的時候，在第一棵線段樹上經過的每個節點都要進入該節點的線段樹，然后修改一下，所以這里應該在內層線段樹里累加答案。

但是自己的寫法是直接覆蓋掉值，所以就會導致后修改的覆蓋先修改的。

哎呦這都有90分真是撞大運了。

所以如果按照我的寫法，那可以再開一個map記錄一下每個點有沒有被修改過，如果修改過cnt+0，sum+now-v就行了。

2019.02.26

T1 哎呀這個想不出來不應該啊。首先有個顯然的DP式子，然后發現這樣數組開不下，這時候就要考慮優化狀態，比如說線段樹優化DP啊，或者單調隊列斜率優化去掉一維啊等等。這里就可以用線段樹優化DP，但是還有一個問題就是當第 \(i\) 個柱子的水位高度為 \(j\) 時，怎么求這個柱子對答案的貢獻。

我們可以換一種思考方式，對于每個條件去計算它的貢獻，比如在高度 \(v\) 要求沒有水，那就對 \(0\sim v\) 區間加 \(1\)。這樣就可以不重不漏算出每個的貢獻了。

還有就是線段樹上維護加和取\(\max\)標記的時候要想清楚真正的值 \(x\) 等于什么，是 \(\max(x+add,mx)\) 還是 \(\max(x,mx)+add\)。

代碼

T2 emmm把m打成n了...

如果這張二分圖有完美匹配的話肯定無解，否則就找可能不在最大匹配中的點就好了。

T3 考場上一眼看出對 \(kq\) 分塊... 然而后綴數組會T... 而且字符數組最大值只能是127...

所以我們用SAM就好了嘛。

對于\(k\leq block\)的部分很顯然

對于\(q\leq block\)的部分，記錄 \(L[i],pos[i]\) 分別表示在SAM上匹配了 \(s[1...i]\) 之后在SAM上的 \(pos[i]\) 節點，且當前最大匹配長度為 \(L[i]\)。

然后找到 \(pos[r[i]]\)，如果 \(L[i]>len\)，那么 \(i\) 在\(\text{parent}\)樹上的所有子樹中的點都是符合條件的。所以我們從 \(pos[r[i]]\) 開始向上倍增找出第一個 \(p\) 使得 \(L[p]>len\)，那么 \(p\) 的 \(sze\) 就是答案了。

2019.02.28

2月的最后一天！

T1 emm想了半天的貪心+二分，最后發現直接大的匹配小的就是最優的了。

T2 就是trie樹上跑2-SAT，直接連邊的話發現邊數有n^2種，優化一下，搞出來前綴后綴節點就好了。

T3 咕

2019.03.01

T1 跟之前做過的一道題挺像的，隨便寫了寫就過了，但是兩個log的做法跑的飛慢（喜提rk倒一）。

正解是這樣的 ：

首先有個大家都知道就我不知道的性質：在樹上給定兩個點集，求兩個點集之間最遠的兩個點的距離。性質是這兩個點一定是兩個點集中的直徑中四個端點中的兩個。問題推廣到多個點集也是成立的，就是兩兩取直徑端點算一下，最后取最大值就好了。

那這道題就可以維護把詢問點看成一個點集，聯通塊內剩下所有點看成另一個點集，所以維護聯通塊直徑就行了。

T2 考場上看出來大概是決策單調性了但是...不會寫啊

第一步：發現這似乎就是個01背包沒什么特別的，但是如果這數據范圍能推廣的話那以前學的01背包豈不是屁用沒有了？所以發掘數據的隱藏性質。

發現每個物品的體積都很小很小，考慮對每個體積單獨做。

有個顯然的性質是如果要選 i 個體積為 j 的物品，那選出來的一定是體積為 j 的物品中價值前 i 大的。

首先枚舉一個體積 v ，可以列出來DP式子 \(f[i]=\max(g[x]+w[i-x])\)，其中 \(w[i]\) 表示前 i 大的體積為 v 的物品的價值和。

這東西看上去很難精簡狀態了，所以考慮優化轉移。

優化轉移就那幾個套路的東西，比如說單調隊列優化，數據結構優化，斜率優化，決策單調性優化等等。這里就是決策單調性優化，套上個分治就行了。

T3 咕了咕了

2019.03.04

T1 因為樹的計數問題經常和prufer序列混在一塊，所以在這里我們也可以考慮prufer序列。

設 \(f[i][j]\) 表示選了 \(i\) 個點，在prufer序列中出現了 \(j\) 次的方案數，然后就可以轉移了。

T2 考場上就差一步容斥啊

首先可以用樹形DP求出來 \(f[i]\) 表示選原樹上至少 \(i\) 條邊的樹的個數，然后就可以容斥一下了。

注意這里的至少是：欽定選 \(i\) 個，其它任選的方案數，這跟正常的至少還是有點不一樣的。

再設 \(g[i]\) 表示選原樹上恰好 \(i\) 條邊的樹的個數，那么根據容斥，就有：\(f[i]=\sum\limits_{j\ge i} \binom jig[j]\) 。含義就是統計恰好在至少中的貢獻，怎么統計呢？枚舉通過至少欽定的這些邊中，有多少是恰好中的邊，共有 \(\binom ji\) 種情況。

這個式子就可以二項式反演或者直接減都行了。

T3 首先這個風扇平衡的條件是，扇葉由若干個環組成，每個環都滿足：相鄰兩個扇葉都相差同樣的距離。

環有兩種，一種跟s連，一種跟t連，有交點的再連。

這就成了最大獨立集問題，求方案比較麻煩，可以從源點bfs，能走到的左部點與不能走到的右部點都是沒有割掉的點。

2019.03.05

考試再不好好考就要完了啊

T1

emmm是一道結論題，結論就是這雖然是一個環但是肯定有某一條邊不會有人經過的。也就是說存在一條邊使得，從這條邊出發后的每個時刻都有前綴和不小于經過的點數和。然后就可以按照從這個起點按照這個順序貪心了。

T2

哇這個確實沒想到可以反轉接在后邊的神仙操作...

知道了這個結論就可以很方便的做了，對權值開個樹狀數組維護以 i 結尾的最長上升子序列以及方案數就行了。

T3

sb計算幾何+NTT

不想調

2019.03.07

今天海星

T1

被老師叫上樓D了一頓之后突然有個神奇的想法，不知道這是不是對的，好虛啊不敢寫啊...

糾結了半天之后寫了寫調了調，發現過了樣例... 然后又亂搞了一下記憶化一下就A了

就是設 \(f[i][j]\) 表示從A串的第 \(i\) 位 B串的第 \(j\) 位開始放數的方案數，如果 \(a[i]\ne a[j]\) 很好轉移，但是如果 \(a[i]=a[j]\) 就很麻煩...

自閉了半天忽然想到對于連續的一大段相等的一起轉移，再記憶化一下就贏了。

upd：艸卡特蘭數都沒看出來，最近有做DPD傻了的趨勢，我退役吧

T2

考過無數次了。不講

T3

寫完T1之后只有一個小時了啊...

感覺大方向就是線段樹上維護標記但是實在沒想到...

正解挺巧的，如果這個區間的最大值和最小值的變化量相等的話，那么直接給整個區間加上變化量，否則遞歸計算。復雜度有保證，是因為除一遍之后區間最大最小值的差都會至少減半，最多減\(\log\)次就可以合在一起計算了。

2019.03.09

md這場策略嚴重失誤

剛了兩個半小時T1 發現了結論但是又給否定了 然后心態爆炸棄療 滾去做T2 花了15min切掉，一眼秒掉T3是個傻逼倍增+大模擬 還剩一個半小時大概能寫完 然后

碼碼碼碼碼碼碼碼碼碼碼碼碼碼碼碼碼碼碼碼碼碼碼碼碼碼碼

臥槽怎么就一個小時了

碼碼碼碼碼碼碼碼碼碼碼碼碼碼碼碼碼碼碼碼碼碼碼碼碼碼碼

臥槽怎么就二十分鐘了

碼碼碼碼碼碼碼碼碼碼碼碼碼碼碼碼碼碼碼碼碼碼碼碼碼碼碼

臥槽碼不完了啊

摔鍵盤

mdzz

T1

打表找規律發現第一個和第三個數要模2，第二和第四個數要模三。emm我記得清清楚楚考場上明明發現這個規律了，但是不知道當時怎么想的就沒管？

T2

傻逼題直接盒子放球就行

T3

傻逼倍增

細節真他媽的多

你們隨意感受一下

2019.03.12

T1

考試的時候想當然，然后就走遠了

先考慮弱化版本，即遍歷一棵樹的最小時間花費，顯然是2(n-1)-樹的直徑。

對于基環樹也類似，我們先求出來基環樹的直徑，如果這個直徑完全在某個子樹內，那答案就是2n-D-H，其中D是直徑，H是環長。

否則答案就是2(n-1)-D

那么怎么求基環樹直徑呢？

首先找環出來，然后對于每個子樹求出子樹內直徑和每個子樹向下最長延伸多長。

然后求出直徑經過環上的情況，拆環成鏈后面倍長，之后單調隊列優化就行了。

代碼

T2

這不就是購票那題啊？

還好前幾天做過不然GG了

zyz是tm真的能亂搞（驚嘆

T3

垃圾騎士毀我青春

2019.03.14

我怎么這么菜了啊

T1

這個編輯距離只能n^2求所以正解就是亂搞...

這個考場上應該意識到的

T2

考場上把式子推到了要在n個數里選k個求\(\sum3^{sum}\)這個玩意兒，然而沒發現這是分治FFT。。。我菜死了

所以直接分治FFT就行了，模數比較小，可以預處理單位根之后直接FFT，或者拆系數FFT也行。

T3

肯定是在虛樹上面亂搞，寫了一種好寫的做法。

設兩個倍增數組 \(f[i][j],g[i][j]\) 分別表示從 \(i\) 到上面第 \(2^j\) 個祖先，經過的點的子樹中，刨掉 \(i\) 的子樹后的最深深度，\(g[i][j]\) 則表示刨掉 \(i\) 的子樹后到 \(i\) 的最大距離。

這兩個數組合并和初始化都沒什么問題，然后就可以在虛樹上倍增了。

2019.03.18

T1

就是先找出來環，然后把環上每個點伸出去的子樹都先縮成一條鏈，然后把這些鏈接進環里就行。

T2

發現如果對于一個格子，規定了來的方向，那么所有格子來的方向就都固定了，于是可以得到一個 n^2m^2 的dfs做法。

然后發現對于一行從前往后掃，每次不清空vis標記也是可行的，就變成n^2m了

T3

分塊傻題。

標記憑啥可以合并啊。。。

2019.03.19

T1

簡單貪心？

就是設當前點為now，如果下一個是R的話那就走到左上方的點，否則就走到右下方的點，觀察到這樣之后下一步不管去哪個點都會是按照要求的。所以這么做就行了。

T2

找性質，然后就沒了。

T3

找性質，然后就摸了。

2019.03.21

T1

啊跟自己想的差不多，但是yjc的寫法明顯要優秀許多。

首先就是那個區間置為0，可以變成區間置為1，然后主要是棧序不會做，因為涉及到標記下放。

實際上可以不用下放標記，類似于標記永久化，如果當前區間全部為1，直接return查詢區間長度即可。 然后棧序撤銷就能做了，就是每次存下區間賦為1的區間是哪個，然后賦值之前的值是啥。

T2

T3

模擬費用流

2019.03.25

T1

woc這題牛逼

觀察到這題有1和2的區別，但是有兩個1相當于捆綁成一個2，所以我們暴力枚舉有多少個小塔取了奇數個，那么剩下的小塔用了偶數個，可以兩兩在組內配對，然后和大塔一起盒子放球就行。

T2

傻逼題，啊呀又犯傻逼錯誤

T3

那個tp=1的很好想，就是從一個點出發選很多條鏈。犯傻逼的地方是，做背包的時候到了3個就不再往上加了，實際上只要大于等于3個都行，mdzz。

2019.03.26

T1

主要是這個拓撲序沒想到

首先發現這個黑點和白點都是DAG，都沒有環，所以先把他們的拓撲序搞出來。

對于一個黑點，設mn表示黑點連到的白點中，最小的拓撲序，mx表示連到黑點的白點中，最大的拓撲序。

一個黑點一定會被刪當且僅當mn<mx

然后剩下的點還有一些應該被刪去，兩個黑點i,j同時被保留的條件是mn[i]<=mn[j]，做一遍lis就行了。

T2

水

T3

還是得手玩+歸納。

---