OwO
03.03 [USACO19JAN]
A. Redistricting
題意：給 \(g\) ，求 \(f(n)\) 。 \(f(i)=f(j)+[g(i)\ge g(j)],j \in (i-k,i]\) 。
離散化之后線段樹優化 DP ；或者發現額外貢獻最多只有 \(+1\) ，單調隊列。
B. Exercise Route
題意：給一棵樹和一些路徑，求有邊交的路徑的對數。
把與 LCA 關聯的點都 \(+1\) ，查詢除 LCA 外路徑上的點。這樣除了兩條路徑 LCA 相同的情況外是沒有問題的。相同的時候開 map 暴力統計答案，也可以科學一點，最后把每個點作為 LCA 對應的一堆二元組排序再統計答案。
C. Rain Tracking 2
題意：給 \(k\) ，以及 \(c_i=\min\{a_{i},a_{i+1},\cdots, a_{i+k-1}\}\) ，求合法 \(a\) 序列數量。
連續 \(i\) 個相等的 \(c\) ，設 \(x=10^9-c\) ，方案數是 \(f(i)=\sum_{j=1}^{k}x^{j-1}f(i-j)\) ，擾動一下得到 \(f(l+1)=(x+1)f(l)-x^kf(l-k)?\) 。
相鄰的 \(c_x>c_i\) 時，發現可以確定 \(c_i\) 對應區間一個 \(a\) 的值，并且另外 \(k-1\) 個位置要滿足的限制是 \(\ge c_x\) 。當前討論的是 \(c_i\) 的貢獻，所以長度 \(l\) 應該減去 \(k\) ，然后再統計答案。
多個部分的答案乘起來就是最終答案。
03.14 [FJOI2018]
所羅門王的寶藏
限制如 \(a_i+b_i=c_k\) ，線性關系相加減還是線性關系，連邊之后任意給一個未知數一個值， DFS 判斷是否矛盾。
領導集團問題
% Newuser 大佬神仙貪心。
按第一關鍵字權值降序，第二關鍵字深度降序排序。討論點 \(p\) ，在到根路徑上如果有點被標記，把最近的點取消標記， \(ans\) 不變；如果沒有， \(ans+1\) 。然后標記自己。之后樹剖。
我想的是 DP ， \(f(i,j)\) 表示 \(i\) 為根子樹內選擇的點最小權值恰好為 \(j\) 的最大可選點數。
\[f(i,j)=\sum \max_{son,k \ge j}\{f(son,k)\}+[A(i)=j]\]
想把第二維合在一起用線段，使得真正維護的元素的后綴和，等于 \(f\) 的后綴最大值。
葉節點的信息顯然就是 \(A(i)\) 位置是 \(1\) ，其余是 \(0\) 的線段。
可以發現如果忽略 \([A(i)=j]\) ，直接把兒子合并（每一位置對應相加），就能得到當前節點的信息。
然后把 \(A(i)\) 位置 \(+1\) ，前驅 \(-1\) ，就可以得到完整的信息了。有點差分的意思吧，可以發現這樣的確得到了正確的信息。
等等，前驅 \(-1\) ，取消標記，那這本質就是前面的神仙貪心？
代碼特別好寫， dsu +multi_set 可以 49 行寫完。
郵遞員問題
\(S,T\) 均兩條線段兩端時，畫圖運用三角不等式可以發現最優路徑必不存在交叉的情況。
然后我就不明白了 QAQ 。咕咕咕。
Orz
10 + 0 +０ 分，爆零預訂。
A 題以為不用圖論直接判標記，確定值就行。這樣不對，線性關系必須依次推，不能把兩堆東西合并之后判是否合法。這樣的話合法的情況也很有可能被判為非法。
B 題嘛……腦子有點亂，寫錯了迭代器。暴力被我誤刪了，太智障了。
C 題想到了 \(S,T\) 在兩端的結論，其他情況想枚舉分割線，因為情況太多所以隨機枚舉一部分，然后兩邊用 DP 求解。可行但不一定最優，感覺很不正確，感覺收益率不大，棄了。
好慘啊 Orz 。
03.22 [來自浙江的不可告人的比賽]
A 容斥還是常見套路的，然而我認定了不能從新圖推舊圖，在求舊圖上耗死了； B 題有點神仙，以為網絡流或者圖論，結果是生成樹 + 圖論； C 題需要考慮組合意義，沒聽明白，咕咕咕。
3.24 [51nod 2019 省選第二場]
A. 抽卡大賽
枚舉每個人，每張卡的 \(a\) 值 \(a_0\) ，然后 DP ， \(f(i,j)\) 表示前 \(i\) 個人抽卡后恰好 \(j\) 張卡滿足 \(a_i>a_0\) ，然后算下貢獻，加上去。整體 \(O(n^4)\) 。
設 \(t_i=f(n,i)\) 的 OGF 為 \(T(x)\) ，有 \(T(x)= \prod (p_i x + 1 - p_i)\) ，其中 \(p_i\) 是某個人抽卡 \(a_i>a_0\) 的概率，實際上是某人若干張卡片 \(p\) 值的和。
將所有人的所有卡片按 \(a\) 值排序，然后從大到小討論。每次移動對 \(T\) 的影響僅僅是某個 \(p_i\) 增加了一個值，除以舊的，乘上新的。一次除法操作是 \(O(n)\) 的，因為有每次除的都是以前乘過的東西這個性質。乘法也是。
所以整體 \(O(n^3)\) ，據說多加 \(\log\) 會掛。
B. 異或約數和
整除分塊，需要求異或前綴和。打表可得它的循環節是 4 。
C. 小朋友的笑話
對于每個笑話，以人為下標建立線段樹。同時維護笑話和答案的線段樹。
勢能分析，對于笑話線段樹，其實是在不停涂黑色，涂色區間原來是純色區間時才可以結束。注意黑色區間是會合并的，并不會拖延之后的操作多次，整體就 \(O(n \log n)\) 了。
也可以用 set, map 之類的維護區間的并？差不多吧。
03.25 [USACO18DEC]
A.
設答案是 \(g(x)\) 有：
\[g(x)=\max\{f(x),\dfrac{g(x-1)+g(x+1)}{2}\} \tag{1}\]
注意 \(c=\max(a,b)\) 等價于 \(a \ge c, b \ge c\) 同時成立，且至少一個取等。
\((1)\) 式第二項限制使得：
\[g(x)-g(x-1) \ge g(x+1)-g(x)\]
對點集 \(\{(x,g(x))\}\) ，在 \(x\) 單增時，增量 \(h(x)=g(x)-g(x-1) \ge h(x+1)\) ，所以這個點集是一個上凸包。
對 \(\{(x,f(x))\}\) 建上凸包，如果點在凸包上，那就取 \(g(x)=f(x)\) 了；如果不在，增量 \(h\) 需要取等，就讓斜率取等，取 \(x\) 在凸包上對應的值。實際上就是把點都取到凸包上。
B.
問題轉化，一個元素的移動并不影響其他元素的相對位置。最終集合單增，因此選取的集合的補集單增。為了最小化最終集合大小，應該最大化補集大小，即求補集的 LIS 。原集第 \(k\) 小，因此求補集第 \(k\) 大 LIS 。
然后每個點維護二元組 \((len,f)\) ，表示以它作為開始的 LIS 長度和對應方案數， \(O(n \log n)\) DP 一下。
然后長度從大到小枚舉，注意相同長度的 LIS 對應的開始位置的元素的值，從左到右單調遞減。由于求第 \(k\) 大，所以盡量先考慮大的，從左往右考慮。然后類似權值線段樹查第 \(k\) 大那樣的貪心，取一下就可以了。
注意每個長度取到元素了就 break 掉，并標記不要再討論左邊的元素，然后枚舉長度 \(-1\) 。算方案數的過程中和 \(10^18\) 取 \(\min\) （因為這個方案數隨便構造一下，上界至少可以到 \((^n_{n/2})\) ）。
C.
貪心，合法刪除過程中一直只有一個連通塊。每個先刪 \(a\) 才能刪 \(b\) 的限制連邊 \(a \rightarrow b\) ，樹邊當作兩條單向邊。 \(a\) 為根的子樹答案是 \(0\) ，問題是不知掉根在哪里。類似拓撲排序，取出入度 \(1\) 的節點，更新周圍節點入度。最后剩下的點度數為 \(0\) ，就把它作為根，然后 DFS 一下，不要經過 \(\{a\}\) 中的點，標記到的點答案為 \(1\) ，沒有到的點答案為 \(0\)。如果沒有這樣的點，說明有環，畫圖可以發現所有點答案都是 \(0\) 。
Orz
記住先打暴力，這樣至少不會爆 0 吧……輸出格式，看好了小朋友！
03.26 [JSOI2018] [AGC]
A. 戰爭
裸的柯和（ Minkowski Addition ），運氣可能比較好碰巧看過，就是求 \(\{c\}=\{a+b\}\) ，把兩個凸包上的輪廓向量極角排序之后再做一次凸包就可以得到 \(\{c\}\) ，然后判斷點是否在新的凸包內：二分，叉積。
B. 機器人
除了斜率 \(1\) 方向的格子全是同一個方向以外我好像啥也不懂，挖坑。
C. 列隊
貪心。找到最大的 \(t\) 使得 \(a_t \le k+t-1\) ，然后 \(t\) 就將兩邊的人劃分開，算答案時就不需要加絕對值符號了。
持久化線段樹，維護區間內人的數量，人的位置的和，最右的人的位置，然后在遞歸中傳一下可以放人的區間，根據左區間最右的人的位置決定一邊貢獻答案，另一邊遞歸一下， \(O(n \log n)\) 。
然而卡常， awsl ，悄悄說一句被卡常的部分我空間也少開了一個 \(\log\) ，完蛋。
Orz
快一個月沒碰幾何了，差點裸題不會做，那真就白給了呀……
所以看了一波模板，補了兩個小東西：
- 線段判交。快速排斥實驗，就是 Kd-Tree 用來剪枝的那個東西，用線段的外接矩形判交，然而這只是線段相交的必要條件；跨立實驗，就是當且僅當 \(a\) 兩端點跨過直線 \(b\) 且 \(b\) 兩端點跨過直線 \(a\) 時，線段 \(a,b\) 相交。 跨過直線的充要條件是，設 \(x=(a_0 \rightarrow b_0) \times (a_0 \rightarrow b_1),y=(a_1 \rightarrow b_0) \times (a_1 \rightarrow b_1)\) ，則 \(xy < 0\) 。
- 多邊形重心。就是各個三角形重心，以面積為權值的加權平均數。把各個三角形重心數乘上三角形面積，加起來作為分子，分母是多邊形面積。
[AGC021E Ball Eat Chameleions]
紅色和藍色，分別作為 \(x,y\) 坐標，枚舉紅球藍球數量 \(r,b\) ，轉化為 \((0,0)\rightarrow (r,b)\) 。
有的路徑不合法。貪心地，優先先后給除一號寵物外的每個寵物 \(r,b\) ，無法做到時就給一號寵物。分析可以發現這樣盡量讓所有寵物變紅了。一號寵物的紅色球個數是 \(r-(n-1)\) 。
- 當 \(r>b\) ，如果 \(y-x \ge r-(n-1)\) ，那一號寵物就不能變紅了。
- 當 \(r=b\) ，如果 \(y-x \ge r-(n-1)\) ，或者最后一個球，也就是最后給一號寵物的球，是紅色，那一號寵物也不能變紅。所以這時路徑是 \((0,0) \rightarrow (r,b-1)\) 。
然后就是快速算不能經過直線的路徑數，用 Catalan 的分析方法算一算就好了。好神仙啊這題。
抱歉，我忘了名字
題意：序列中有 \(0,1\) 和通配符，相鄰三個數字可以變成出現最多次的那個，求最后剩下 \(1\) 的方案數。
wxh 的 DP 沒看懂，大概能理解“畢克自動機”做法。就是普通的自動機構造，但是神奇地貪心了，有的狀態總是比能同樣能轉移到的另一個狀態好，所以每個點 \(0,1\) 對應的轉移可以貪心地恰好構造為唯一的，這很重要。然后跑匹配， DP 算最后停在某個節點的方案數。
序列自動機
聽到有大佬在說序列自動機，看了 OB's blog 里面 FJOI2015 那道序列自動機的題。就是維護每個字符后面添加一個字符能匹配到的最近的位置，類似鏈式前向星，用處是在公共子序列相關問題， \(O(|S| \cdots n)\)。聽說 PopoQQQ 用主席樹能把復雜度中字符集大小那里加個 \(\log\) ，沒仔細看，咕咕咕。
03.27 [某名校 NOI 模擬] [雅禮 2018 Day10]
A.
題意：長度 \(2n\) 的序列，比如 \(0829\) 是 good 的，因為 \(02+98=10^n\) 。給一個含通配符的序列，求是 good 的方案數。
性質是兩個數字對位相加的結果做高到低是若干個 \(9\) ，一個 \(10\) ，然后若干個 \(0\) 。
然后枚舉 \(a\) 是結果為 \(10\) 的那個數字，即方案中一定有 \(a+b=10\) ， DP 。
B.
題意：環上有一些權值，有一個點權均勻分布在 \([a,b]\) ，然后求什么概率。
把未知點權設為 \(x\) ，每個點的答案是一個一次函數，假設已經知道了。然后就是一些半平面 (\(k>0\)) 求上凸包，每條直線的答案的分子就是它在凸包上 \(x\) 坐標的差。
然后求那些一次函數，發現可以 \(O(n)\) 暴力 \(1\) 號點答案，前綴和推出其他的點 \(i\) 作為起點的答案。但是由于環的性質需要分類討論 \(j\ge i\) 和 \(j>i\) 兩種情況。
C.
咕咕咕。
A. 「雅禮集訓 2018 Day10」足球大戰
式子寫出來，注意特判 \(p,q\) 為 \(0,1\) 的情況，因為不存在逆元。開空間，開常，只能 \(O(n)\) ，只能開一個逆元數組。
B. 「雅禮集訓 2018 Day10」文明
據 Newuser 大佬說是虛數裸題 世界樹 弱化版。某個點屬于一個國家的充要條件是距離最小，或者距離相等時，國家的行動標號最小。
C. 「雅禮集訓 2018 Day10」貪玩藍月
裸線段樹分治，注意背包時需要開一個臨時變量存答案，因為模意義下不能簡單通過枚舉順序來保證物品僅有一個。
03.28 [小概率是雅禮集訓]
A. arg
題意：給出長度 \(m\) 的序列，求 \(1\) 到 \(n\) 排列中， LIS 是該序列的個數。
DP 套 DP ，求 LIS 的一種做法是： \(f(i,x)\) 表示前 \(i\) 個數字，長度 \(x\) 的 IS 的最小末尾數字，然后每次貪心地更新狀態，或者把當前數字接到某個 IS 后面，作為當前最長的 IS 的末尾數字。
按照套路，果然又發現第二維是單調不降的。所以如果隨便放數字而不是恰好放一個排列的話，直接差分，然后二進制狀壓內層 DP 第二維就可以。考慮數字有限制時，對數字狀壓，三種狀態：未討論，討論過并且在內層 DP 的第二維，討論過但不在內層 DP 第二維。每次枚舉未討論的數字進行轉移，如果放了一個給定序列中的數字 \(a_i\) ，需要保證 \(a_{i-1}\) 已經討論過。模仿內層 DP 更新狀態，或者把數字接到末尾就行了。
B. bsh
題意：給三角剖分圖，邊權為 \(1\) ，詢問兩點間最短路。
類似 旅行者 （好像是這個名字），那是一道網格圖分治。這道題對多邊形分治就好了。
然而我碼力太差，寫了非常久，第一次用 vector<vector> 。
C. cti
題意：一些有向炮臺，可以打一炮，但是彈道不能相交，求最大收益。
網絡流。某條彈道過了交叉點，另外一邊就不能過。轉化一下限制，調整邊的方向，拆點，加上限制，跑最小割。
Orz
今天翻車了 Orz ……雖然一直很菜，不過……一言難盡。
三道題開場就看出了考察方向，然后挑了最熟悉的 DP 模型，以為是裸題能很快水過，然后 3h 過去了。分治題一開始以為是有簡單性質，最后一個小時才覺得只能分治。思路簡單，然而沒寫過類似的題，暴力。網絡流日常心理障礙，嘗試克服，無法克服，開始暴力，發現暴力打著真費勁，放棄。
然后就翻車了。
教訓：網絡流還是多想想吧，畢竟性價比比較高，不像復雜 DP 或者數據結構之類的東西容易白耗時間。然后相信：我一定能在 30min 內寫對 200 行代碼。
03.29
上午打我和 211 的互測題。
A 題裸 Mobius + 莫隊，成功用 \(n=m=a_i=100\) 的假樣例讓 hdhd 大佬看錯輸入格式，拍了一個小時沒掛，最后 10 分。我沒有被阿，嘿嘿。
B 題組合數求和，需要模型轉化，考慮一三象限有一些點，求路徑方案數， DP 一下。
C 題正解是差分之后線段樹維護，找右邊第一個大于 \(v\) 的位置。 hdhd 大佬 map + 勢能分析通過。考慮許多單調區間，修改操作會使得一些區間合并，一開始有 \(n\) 個長度 \(1\) 的區間，修改操作只會增加至多 \(2\) 個區間。
03.30 [自閉省選模擬]
A.
題意：給一棵樹，有一些炸彈在節點上，造成的傷害每擴展一條邊就 \(-1\) ，直到為 \(0\) ，求每個節點受到的傷害和。
點分治，計算子樹中炸彈對其他子樹的傷害（實際上也貢獻到了炸彈所在子樹中，所以每次統計答案時需要對所有兒子再進行一次負貢獻來消除影響）。然后差分 + 后綴和統計每個深度的答案。
B.
小C的錦標賽弱化版， \(n=5000\) 。
題意：求至少含一個 \(k\) 元環的帶標號競賽圖數量。
考后補的競賽圖性質：
- 如果競賽圖含有 \(k\) 元強連通分量，那么存在所有 \([3,k]\) 元環。
- 競賽圖的拓撲序唯一，即縮點后入度為 \(0\) 的點僅一個。
問題轉化：求至少包含一個 \(\ge k\) 元強連通分量的競賽圖數量。
先考慮 \(n\) 個點且包含 \(n\) 元強連通分量的競賽圖數量 \(f(n)\) ，設 \(g(n)\) 表示任意競賽圖數量，枚舉點集中最小點最小的強連通分量，然后關聯的所有邊起點只能是該點集：
\[g(n)=\sum_{i=1}^{n}f(i)g(n-i)(^n_i)\]
再次轉化問題，設僅由 \(<k\) 元強連通分量組成的競賽圖數量 \(s(n)\) ：
\[s(n)=\sum_{i=1}^{k-1}f(i)s(n-i)(^n_i)\]
答案是 \(g(n)-s(n)?\) 。然后變化一下式子，多項式求逆。
C
題意：給一棵樹，代價輕邊 \(1\) ，重邊 \(\lceil \log_2^{l}+1 \rceil\) ，葉子代價為到根代價和。求葉子代價最大值最小是多少？
正解神仙貪心 + DP ，長鏈剖分可過 60 。
Orz
注意卡常，調整心態，信仰暴力能得分，就算 Subtask 什么的也要信仰。
03.31 [自閉 AGC030] [51nod 省選模擬 2019 第三輪]
AGC030 E
模型轉化，紅線藍線，選一個匹配， \(O(n)\) 計算當前答案，總共 \(O(n^2)\) 。
AGC030 F
全 -1 時是 Catalan 數，推廣， DP 。
[51nod] A.
兩個分母互素的分數之和為整數，這兩個分數分別為整數。如果明白了這一點，并且會寫 Pollard Rho ，您就可以通過此題。
[51nod] B.
咕咕咕，神仙計數。
[51nod] C.
SBT 套 Trie ，可是我不明白 Trie 維護權值是什么意義，但據說這種操作是一種對給定區間排序的套路。
04.01 [長樂一中集訓]
A. 遮天蔽日
計算幾何，多邊形重心。
B. 三元組
題意：求序列中 \(A[l,mid],B[mid+1,r]\) 滿足 \(A,B\) 是回文串的所有情況的 \(\sum l \times r\) 。
\(Ans = \sum x_i y_{i+1}\) ， \(x_i\) 表示以 \(i\) 結尾的回文串的左端點下標和， \(y_i\) 表示以 \(i\) 開頭的回文串右端點下標和。 Manacher ，差分，前綴和。
C. 最優價值
最大權閉合子圖。
Orz
又翻車了，再不提前打暴力我就 XX 。網絡流模型以為套不上最大權，一直卡在最小割上了。主要是策略有問題，最后幾十分鐘一道題沒做，竟然還不打暴力，企圖搞出 C 題。
04.02 [HNOI 2018 省隊集訓 6-25] [Newcoder 2018 ACM]
A. gift
題意：定義序列 \(A\) 變成到 \(B\) 的代價為需要執行交換兩個位置的數字這個操作至少進行的次數。給兩個有空位的序列，求代價為 \([0,n-1]\) 的方案數。
神仙題。至少交換次數等于 \(n-p\) ，其中 \(p\) 為置換中循環節個數。如果兩個序列都是給定的，那么問題就是求環的數量。
對于空位，分為三類連邊：空位僅在左，僅在右，左右有。然后斯特林和容斥部分我還不太理解。
B. girl
題意：給出 \(a,b,c,n\) ，求 \(\sum_{0 \le i < j < k < n}ai+bj+ck\) ，滿足 \(i,j,k\) 中任取兩個均不存在于給出的限制集合 \(\{(x,y)\}\) 中。
沒有限制，算下 \(a,b,c\) 的系數就可以了，得到答案 \(s\) 。
有限制，設 \(x\) 表示至少滿足 \(i,j\) 存在于限制集合的三元組的貢獻和，類似地，設出 \(y,z\) ，答案為 \(s-|x \cup y \cup z|\) ，容斥一下。
形如 \(|x|,|x \cap y|\) 的部分比較容易求，考慮計算 \(|x \cap y \cap z|\) ，即三元環的貢獻。
根據 luogu 上的 post ，這個可以 \(O(m \log m)\) 做。對于無向圖，度數大的向度數小的定向，相等時根據標號隨便定一下。
這樣構造的是一個 DAG 。然后：
for (0 <= i < n) {for (i -> j)mark[j] = i;for (i -> j)for (j -> k)if (mark[k] == i)papapa}string
SAM + LCT 。
[Newcoder] The number of circuits
看一下 BEST Theorem ，暴力高斯消元算下答案，扔進 BM 里。
所以營養成分主要是 BEST Theorem 和復習高消。
04.04 [FJWC2019 DAY1]
全連
一開始粗略算了下數據范圍以為要寫高精，看了下時限以為要用一個 long long 和一個 int 模擬高精卡常。然而并不需要，兩個限制，主席樹會爆空間，所以每次并不直接加入狀態，扔到堆里面，需要用到的時候再拿出來，在線段上上做對應修改。
原樣輸出
從后往前建立 SAM ，然后對于沒有轉移的點，連向上一個字符串的轉移位置，得到一張 DAG ，拓撲排序算一下從起點出發的方案數。
不同的縮寫
搜索 + 剪枝 + 二分圖匹配。一個串如果有超過 \(n\) 個子序列，一定可以完美匹配。
染色問題
題意： \(n \times m\) 的棋盤， \(c\) 種顏色。要求每行每列至少一個格子要染色，每種顏色至少出現一次，求方案數。
容斥一下，發現形如 \((-1)^i(^n_i)f(i)\) 的式子還可用二項式定理收起來， \(O(n^2 \log n)\) 。
子集
題意：求數列 \(\{a\}\) 所有子集中前 \(k\) 大的數和的和，對所有 \(i \in [1,n]\) 輸出答案。
設從大到小排名為 \(i\) 的數字為 \(a_i\) ，所有子集中第 \(k\) 大的數的和是 \(c_k\) ，有：
\[c_k = \sum_{i=k}^{n} (^{i-1}_{k-1})2^{n-i}\]
可以得到一個 \(c_k=\sum_{i=k}^{n} f_i g_{i-k}\) 的式子，卷積。
)
