最近忙著背科目一和學范疇論，根本沒時間加訓

CodeForces - 1439C. Greedy Shopping

剛看到題就想了很久但是不會做，然后發現自己沒有注意到序列 \(\set{a_i}\) 是單調不增的。首先先考慮問題的弱化形式——沒有修改的情況，實際上印象里以前并沒有見過比較典型的能處理這類問題的模型，于是嘗試分析購物情況，能夠發現購買的商品一定是一段一段的，顯然這是廢話，但是不難發現一個情況：假如一段連續的購買是 \(a_l\) 到 \(a_r\) 這就意味著這個人是買不起 \(a_{r+1}\) 的，即 \(money<a_{r+1}\)，那么嘗試分析下一次購買 \(a_x\) 是怎么樣的，如果 \(a_x>{a_{r+1}\over2}\)，那么錢就會直接減少一半，再下一次的購買 \(a_y\) 一定是 \(a_y\le a_{r+1}-a_x<{a_{r+1}\over2}\)，而如果 \(a_x<{a_{r+1}\over2}\) 那么就直接說明下一次購買變成了原來的一半，這意味著購買的商品的段數一定是 \(O(\log V)\) 級別的，于是就直接在線段樹上二分即可，感覺困難的地方應該在于發現這一個性質，有一點點歐幾里得輾轉相除法的味道。

CodeForces - 1706E. Qpwoeirut and Vertices

求最小的邊使得圖聯通，一聞就是最小生成樹的味道，實際上就是在最小生成樹模擬，一旦最小生成樹的過程中某個要求被滿足了就回答當前處理的邊即可，實現方法應該有很多種，比如重構樹或者整體二分。

CodeForces - 1712E2. LCM Sum (hard version)

這個題目亂七八糟的，感覺就是純亂搞+大力分類討論。首先容易分析出 \(k|lcm(i,j,k)\)，并且如果 \(k<lcm(i,j,k)\) 則 \(2k\le lcm(i,j,k)\)，所以實際上能夠做到 \(lcm(i,j,k)<i+j+k\) 的情形是很少的，只能允許 \(lcm(i,j,k)=k\) 或者 \(lcm(i,j,k)=2k\) 且 \(i+j>k\)。

對于第一種情況，設 \(f(a,b):=\sum_x [x\ge b]\&[x|a]\) ，則第一類就是想辦法維護 \(\sum_{l\le x\le r}f(x,l)^2\) 和 \(\sum_{l\le x\le r}f(x,l)\)。考慮對所有詢問按照 \(r\) 從小到大的順序來掃描線，對于一個固定了的 \(a\) 而言，\(f(a,\cdot)\) 至多有 \(\sigma(a)\) 個不同的值，并且這些值是構成連續的段的，故全體的 \(f(\cdot,\cdot)\) 共有 \(\sum\sigma(i)=O(V\log V)\) 段不同的值，所以每次新加入一個 \(r\) 的時候把 \(f(r,\cdot)\) 對于 \(\sum f^2\) 和 \(\sum f\) 的修改打到線段樹上即可，所以這一部分總的時間復雜度為 \(O(V\log^2 V)\)。

第二種情況和第一種情況類似，對于每個 \(i\) ，直接枚舉 \(2i\) 的因子對，然后以同樣的思路可以發現 \(g(a:b)=\sum_{(x,y)} [x,y\ge b]\& [lcm(x,y,a)=2a]\) 也是 \(\sigma(a)\) 段不同的值，然后全部拍到線段樹上即可，時間復雜度為 \(O(\sum \sigma^2(i)+V\log^2V)\)

QOJ - 7661. Japanese Lottery

精妙的數學題，之前見過，但是當時苦于找不到合適的數學工具來描述交換的行為，前幾天群中有人提及置換故而恍然大悟，故可從置換合成的角度來描述這一題目的行為。

題面：稱二元置換為交換，對交換列 \(\set{\sigma_i}\) ，進行總共 \(q\) 次操作，每次操作形如在該列中某個位置插入一個交換或者移除某個交換，對于操作完后的長度為 \(m'\) 的交換列 \(\set{\sigma'_i}\) ，求最長的遞增序列 \(\set{a_i}:1\le a_1<a_2<...<a_n\le m'\) 的長度 \(n\) 使得 \(\sigma=\sigma_{a_1}\circ\sigma_{a_2}\circ\sigma_{a_3}\circ...\circ\sigma_{a_n}=I\)

先說明上述問題的結論：設 \(\sigma\) 中有 \(s\) 個環，那么至少需要移除 \(|\sigma|-s\) 個置換，并且這個值可以取到。

一波三折，經過一周時間結論得到了證明，但是這個證明很復雜，我要新開一篇文章來寫這個。

QOJ - 11503. Giant Gorilla’s Gift

勢能線段樹，以后看見奇奇怪怪的操作就盡量直接想暴力并利用勢能分析法來證明復雜度。首先直接分析出至多有 \(7\) 個本質不同的質數，然后直接維護 \(8\) 個值即可，但是困難的地方在于第三種操作，但是實際上直接就是在線段樹上二分找到下一個最近的能被修改的值，這是因為一旦有修改那么一個值至少被乘以二，而由于題目保證每個數時時刻刻都小于 \(10^6\) 所以實際上每個數能夠被修改的總次數是 \(O(n\log V)\) 的，于是定義線段樹的總勢能為每個數能被乘以二的次數，顯然一次操作二至多使得總勢能增加 \(\log V\) 而操作三中的每一次暴力操作都會使得總勢能至少減少 \(1\) ,故時間復雜度就是 \(O(n\log V\log n)\)

QOJ - 11509. Minor Maze Modifications

又是這種亂七八糟的題，不過幸好是計數題。感覺題目的核心就是處理出想要把兩個聯通塊打通需要多少步，以及有多少種方案，但是就是亂七八糟的。時間復雜度應該是在 \(O(n^2)\) 級別的

QOJ - 11501. Eirt Eht Esrever

字符串題，注意到實際上在 Trie 樹上的每個節點都代表一個字符串，這樣的字符創要么是一個前綴，要么是一個子串的反轉，而顯然 Trie 樹的節點個數的期望可以轉化為每個節點出現的概率之和，由于需要分析子串，所以考慮在字符串上建立 sam，而一個節點作為子串出現的概率就可以直接通過 fail 樹來計算，但是此時僅考慮了子串而未考慮前綴的情況，這個時候假設字符串為 \(S\) 那么考慮把后綴自動機建立在串 \(S+'\#'+reverse(S)\) 上，之后再在樹上操作一下即可，時間復雜度是 \(O(n)\) 的.

QOJ - 11504. Hidden Hierarchy Hints

有意思的交互題，需要一定的注意力。

首先需要注意到一個結論：對于兩個節點 \(x,y\) 而言，如果一個邊 \(e\) 不在 \(x\) 到 \(y\) 的最短路徑上，那么 \(e\) 相對于 \(x\) 的方向和相對于 \(y\) 的方向是相同的，若反之則方向是反的.

干脆欽定 \(1\) 為樹的根，然后先問一遍 \(000...00\) ，之后對于每個邊都反一下，即問 \(100...00,010..00,...,000..10,000...01\) ，規定邊指向 \(1\) 即為正方向，從而得到每個邊的方向，之后假定零一串 \(s:=0011010...010\) 代表了使得每個邊都正方向的東西，則對于每個節點 \(i\) 詢問 \(i\,\,\,s\) 從而得到每個節點的深度。至此已經詢問了 \(500+499=999\) 次。（稱求出來的 \(s\) 為標準狀態，以后的操作都在標準狀態上操作）

之后依照深度從小到大的順序依次通過詢問獲取每個節點的以下信息：父節點、連向父節點的邊.

首先對于深度為一的點 \(i\) ，已經知道父節點肯定是 \(1\) ，所以只需詢問出哪個邊是連向父節點的，不難發現：如果一個邊不是 \(i\) 連向 \(1\) 的，那么翻轉這個邊會使得對于 \(i\) 的詢問減一，否則加一。推廣它，就是假設翻轉了 \(k\) 個邊，那么如果對于 \(i\) 的詢問的值不等于 \(i\) 的深度減 \(k\) ，那么這個 \(i\) 連向 \(1\) 的邊必在這 \(k\) 個邊中，于是這提供了一種非常自然的二分的思路，這一思路本質上就是在詢問哪個邊在 \(i\) 到 \(1\) 的路徑上。

而對于深度不為一的節點 \(i\)，并不知道父節點是誰，于是還需要詢問父節點是誰，具體的做法是：假定現在正在處理深度為 \(x\) 的節點，那么這意味著所有深度小于 \(x\) 的節點已經獲取了他們全部的父節點、邊編號信息了，于是將全體深度為 \(x-1\) 的節點的邊給抽出來，用上面相似的思路，可以問出 \(i\) 的父節點的邊，從而知道父節點的是誰。

之后處理邊編號，還是一樣的思路，只不過不要再詢問已經確定了的邊了。

上述的做法需要詢問 \(2n(1+\log n)\leq 10000\)，是一種可行的交互策略