NOI 模擬賽報告 2

2025多校沖刺沖刺國賽 3

1. 排列 T1

   發(fā)現(xiàn)這是一個模板 ccx，然后就做完了。

2. 整除 T2

   我們發(fā)現(xiàn) \(\bmod \sum x^i\) 實在是不太優(yōu)良，我們兩邊同乘一個 \(x - 1\)，這樣變成了 \(\bmod (x^m - 1)\)，十分好看。

   然后我們發(fā)現(xiàn)對于一個數(shù) \(\sum f_ix^i \text{ s.t. } |f| < x\)，若其整除 \(\bmod (x^m - 1)\)，則 \(f_i = 0 \lor f_i = x - 1 \lor f _i = -(x - 1)\)。

   證明也不太難，充分性是顯然的，必要性就是考慮在 \([-x^m + 1, x^m - 1]\) 之間能被整除的數(shù)只有 \(3\) 個。

   然后就是模板數(shù)據(jù)結(jié)構(gòu)維護進位了。

2025多校沖刺沖刺國賽 6

1. reward T1

   模板 wqs 二分：嚴格 wqs 二分

2. 冬之花（hana）T2

   模板最大流轉(zhuǎn)最小割，平面圖最小割轉(zhuǎn)對偶圖最短路。

3. 經(jīng)典游戲 T3

   首先發(fā)現(xiàn)一個點 \(sg\) 函數(shù)值就是其到其最深葉子的距離。

   考慮什么時候 K 勝利，即 \(\bigoplus\limits_{u\in T} sg_u \le \max dep\)（\(T\) 表示棋子的集合），所以現(xiàn)在。

   考慮換根時一個棋子 \(u\) 的 \(sg\) 值，發(fā)現(xiàn)其實際上只有兩種取值，即當根在以 \(u\) 為根時 \(u\) 最深的兒子方向的直接兒子 \(v\) 的子樹內(nèi)時，答案時次深兒子的距離，否則是最深兒子的距離，于是修改相當于是子樹異或。

   考慮如何維護鄰域信息，發(fā)現(xiàn)鄰域大小固定且是 \(1\)，于是我們每個點建一個 trie 樹維護大小為 \(1\) 的鄰域做根的 \(\bigoplus\limits_{u\in T} sg_u\)，修改相當于是 \(\mathcal{O}(1)\) 個子樹異或和 \(\mathcal{O}(1)\) 的單點暴力改，于是就做完了。

   如果鄰域不維護父親會好寫很多。但是直接寫 trie 被卡空間了，可以寫 wang5 度數(shù)分治（就是度數(shù)小于一個值的跑暴力），也可以暴力做 trie 的操作，可以證到 \(\mathcal{O}(\sqrt n)\)，常數(shù)很小，可以通過（但寫根號做法好像根本不用這么麻煩）。

2025多校沖刺沖刺國賽8

這一 water 場。

1. 排列 T3

   考慮第一次一定獲得全局次大值，考慮二分，我們發(fā)現(xiàn)若次大值所在的一邊的次大值依然是全局次大值，則最大值在次大值一邊，否則在另一邊。

   發(fā)現(xiàn)過不去，考慮若進入次大值的一邊可以省掉查詢次大值的一次，直接取中點并不平衡，所以寫個暴力算一下在什么時候平衡即可。

2025多校沖刺沖刺國賽10

1. 祝大家（i） T1

   wang5：我給你一個忠告，不要寫遞歸 trie 樹

2. 取得（ak） T2

   原題等價于找到一些最多的整點構(gòu)成凸殼，容易發(fā)現(xiàn)一個凸殼一定可以構(gòu)造一個函數(shù)來擬合。

   第一個整點一定是 \((0,0)\)，我們差分一下，問題變成了選擇盡可能多的 \((x, y)\)，滿足 \(\frac{y_{i - 1}}{x_{i - 1}} < \frac{y_i}{x_i} \land \sum x_i \le n \land \sum y_i \le m\)。

   發(fā)現(xiàn)這并不好做，但是我們感受一下那股勁，驚異的發(fā)現(xiàn)，我們事實上限制是 \(\frac{y_j}{x_j} \not= \frac{y_i}{x_i} \text{ s.t. } i \not= j\) ，因為我們可以最后排序。

   于是我們可以只保留 \(\gcd(x, y) = 1\) 的點對，做背包即可。

   但是復(fù)雜度還是太高了，考慮優(yōu)化，我們發(fā)現(xiàn)對于一個點對 \((x, y)\)，若存在 \(x'<x, y'<y\) 的點對 \((x', y')\)，我們一定會先選 \((x', y')\)。所以一個點對可能有貢獻當且僅當 \(\sum\limits_{x' < x}\sum\limits_{y' < y} x' \le n \land \sum\limits_{x' < x}\sum\limits_{y' < y} y' \le m\)。這樣的點對只有 \(n^{\frac 23}\) 個。

   考慮到凸殼的點的個數(shù)最多是 \(n^{\frac 23}\) 的，所以交換值域定義域即可 \(\mathcal{O}(n^{\frac 73})\)。

3. 好成績（noi） T3

   卡常是吧。

   容易把鏈并拆成若干條不相交的鏈。

   發(fā)現(xiàn)維護的信息實在是不可做至極，考慮閾值分治。

   我們同時對詢問點數(shù)和一種顏色出現(xiàn)次數(shù)進行分治。

   我們建出虛樹，發(fā)現(xiàn)點數(shù) \(> B\) 的可以直接暴力 \(nB\) 做的，出現(xiàn)次數(shù) \(> B\) 預(yù)處理一下前綴和也是直接做。

   考慮如何做都 \(< B\)，這里有個十分符合直覺又十分反直覺的東西，就是若 \(\sum x_i = n, x_i \le B\)，則 \(\sum x_i^2 \sim nB\)。

   于是我們暴力枚舉邊對和鏈對，問題變成 \(nB\) 個單點加，矩陣求和，復(fù)雜度是 \(nB \log n\)。

   容易調(diào)整 \(B\)，做到 \(n\sqrt{n \log n}\)。

2025多校沖刺沖刺國賽11

1. 自卑

   真·卡常題。

   直接莫隊二次離線拆位就是 \(n\sqrt n \log V\) 的，常數(shù)較小，可以通過。

   有人說能純根號，但是我不會。

   考慮一個繞遠另類解法：掃描右端點，動態(tài)維護每個左端點的貢獻，然后上分塊即可，復(fù)雜度一樣，常數(shù)較大，循環(huán)展開加火車頭即可通過。

2. game

   首先想到將圖補成一個競賽圖且是一個 DAG，這樣兩兩之間的 \(sg\) 函數(shù)值互不相同，我們直接做即可。

   但是我們并不能改這么多邊，且不能查這么多點。我們發(fā)現(xiàn)題目要求可以有環(huán)，我們嘗試用環(huán)搞事。

   環(huán)中最簡單的就是自環(huán)，我們用自環(huán)完成這個事。具體的，我們將集合分成兩部分，設(shè)其為 \(S_1, S_2\)，將 \(S_1\) 補成競賽圖且是一個 DAG，刪除 \(S_1\to S_2\) 的邊，將 \(S_2\) 中的點連自環(huán)，并構(gòu)造向 \(S_1\) 的連邊使得任意兩個點的連邊方案不同。

   我們詢問每個 \(S_1\) 中的點。

   若是先手必敗，則一定是兩點重合，因為首先不可能有點在 \(S_2\)，因為若有點在 \(S_2\) 則先手可以直接將狀態(tài)轉(zhuǎn)移給后手，必不敗。并且 \(S_1\) 中沒有向 \(S_2\) 連的邊，所以必然 \(sg\) 函數(shù)兩兩不同，先手必敗，是兩點重合。

   若是先手必勝，一定先手將一步移動 \(S_2\) 中的點到和 \(S_1\) 中的點重合，對應(yīng) \(S_2\) 中的點向 \(S_1\) 中的點連了一條邊；若是平局，則是先手沒辦法使其重合，對應(yīng) \(S_2\) 中的點和 \(S_1\) 中的點沒有邊。

   由于連邊方式兩兩不同，于是就顯然了。

   構(gòu)造 \(S_1\) 有 \(20\) 個點，\(S2\to S1\) 的邊枚舉一個最小的變化量即可。

2025多校沖刺沖刺國賽12

1. 字符串 T1

   先看一下：runs 相關(guān)理論

   數(shù)據(jù)結(jié)構(gòu)部分是 Easy 的，直接將貢獻拆成 \(R < r\) 和 \(R > r\)（\(R\) 是詢問右端點，\(r\) 是 runs 右端點）樹狀數(shù)組掃描線即可。

2. 矩陣 T2

   很牛的一個 trick。

   發(fā)現(xiàn)對格子做很難，我們對格點做：

   一目了然的一張圖（紅 \(V\) 是值，藍線是邊，可能有奇偶性倒了，湊合看）

   發(fā)現(xiàn)這樣任意兩個不能同時選的值所對的邊都有公共點，于是就是二分圖最大權(quán)匹配。

   xuanxuan001 有插頭 DP 做法，我不會。

3. 冰棒 T3

   考慮若兩兩互質(zhì)是簡單的，容易發(fā)現(xiàn)可以合并 \(l\) 相同的。

   我們嘗試讓其兩兩互質(zhì)，所以我們設(shè)置一個周期 \(K\)，將 \(\bmod K\) 相同的天拿出來考慮，這時循環(huán)節(jié)是 \(\frac l{\mathrm{lcm}(K,l)}\)，\(K = 30240\) 此時循環(huán)節(jié)滿足要么相同要么互質(zhì)，暴力做是 \(\mathcal{O}(KV^2)\) 的。

   我們發(fā)現(xiàn)我們其實不止可以合并相同的，我們也可以合并成倍數(shù)關(guān)系的，此時取 \(K = 2520\) 即可保證任意兩個都成倍數(shù)或互質(zhì)。

2025多校沖刺沖刺國賽13

All Last，所以是 WATER 場。

1. 歐內(nèi)的環(huán) T2

   首先平面圖經(jīng)典結(jié)論：\(\text{點數(shù) } - \text{ 邊數(shù) } + \text{ 面數(shù) } = 2 \Rightarrow \text{點數(shù) } \le 3\text{ 邊數(shù) } - 6\)。

   我們發(fā)現(xiàn)因為其任意點度數(shù) \(\le 3\)，所以不存在鏈的情況，所以其對偶圖也滿足度數(shù) \(\le 3\)，考慮鴿巢，發(fā)現(xiàn)至少有一個點度數(shù) \(\le 5\)。

   因此我們發(fā)現(xiàn)原圖最小環(huán)至多是 \(5\)，判掉三元環(huán)和四元環(huán)后直接輸出 \(5\)即可。

2. 旋轉(zhuǎn)謎圖 T3

   也是一個躺尸題。

   我們發(fā)現(xiàn)可以構(gòu)造一種操作序列每次交換兩個數(shù)，然后就 WATER 了。

NOI2025模擬測試2

1. 猴戲世家 T1

   首先若沒有同一個點能被算多次是簡單的，直接掃一維類似區(qū)間取 \(min\) 做一維維護每個點屬于哪個柵欄即可。

   考慮如何統(tǒng)計同一個點被算多次的情況，發(fā)現(xiàn)將一個點和包含他的點連邊，則相當于是靠后的兒子貢獻給靠前的父親，上個并查集即可。

2. 零糖麥片 T2

   原題 CF468E。

   首先拆一下矩陣，將其 \(v\) 拆成 \(1\) 和 \(v - 1\)，這樣可以看成每個位置在一般情況下增加了 \(v - 1\)。

   其實拆矩陣這步挺牛的。

   狀壓那些行選了，我們發(fā)現(xiàn)若這是一行中最后一個數(shù)，則可以直接不壓了，然后就過了？

   這感覺上是 \(k^22^{\frac k2}\)，有人說可以少個 \(k\)，但反正是 \(2^{\frac k2}\) 的。

   考慮優(yōu)化，發(fā)現(xiàn)每行每列只能選一個很難不想到二分圖，問題相當于是二分圖匹配的邊權(quán)積的和。

   事實上我們只用考慮邊權(quán)不是 \(1\) 的邊，邊權(quán)是 \(1\) 的可以不管，最后乘系數(shù)即可。

   對于每個連通塊分別做。我們壓其中較小的一邊的為狀態(tài)，在另一邊跑狀壓，這樣依然是 \(m2^{\frac n2}\)，其中 \(n\) 是點數(shù)，\(m\) 是邊數(shù)。

   考慮當點數(shù)接近邊數(shù)時，這個做法很劣，考慮建出原圖的一個生成樹，枚舉非樹邊的狀態(tài)跑 dp，復(fù)雜度是 \(n^2k2^{n - m}\)。

   于是平衡一下就是 \(k^22^{\frac k3}\)。

3. 文體雙花 T3

   學(xué)析合樹學(xué)的。

   就是考慮 \(dp\)，直接做是 \(n ^ 2\) 的。

   發(fā)現(xiàn)可以轉(zhuǎn)移的位置滿足 \(\max - \min = r - l\)，移項是 \(\max - \min + l = r\)，而 \(\max - \min \ge r - l\)，于是直接線段樹即可。

   建析合樹估計也行，但是我場上建了一輩子也沒建出來。

UOJ NOI Round #9 day1 day2

太菜了只能改 eps 個題，合起來寫吧。

1. 星圖

   神筆構(gòu)造題別區(qū)分我。

   顯然只考慮偶數(shù)即可。考慮構(gòu)造，我們欽定一條邊是劃分點，容易發(fā)現(xiàn)這條邊有一個端點需要是三度點。

   容易發(fā)現(xiàn)取重心邊（可以盡可能平分這棵樹的邊）最優(yōu)，但是重心邊不一定有三度點。若重心邊沒有三度點，即其在一條鏈上，容易發(fā)現(xiàn)我們最后在做這條鏈最優(yōu)，且做這條鏈不會改變是否合法。

   于是直接做即可。

2. Sing

   考慮 \(k = 0\)。考慮限制，連邊 \(i \to p_i\)，這樣排列合法當且僅當 \(i \to j \text{ s.t. } j > i\) 且 \(\forall k \in (i, j), p_k \le i\)，然后就是簡單 dp。

   \(k \neq 0\) 就是平移一下，有固定數(shù)也簡單。

   細節(jié)很多。

3. 歡迎來到最前線

   很簡單的，難點在于考慮將 \(a, b\) 混合排序。

   首先很簡單就能想到流和反悔貪心。

   先排序，我們發(fā)現(xiàn)匹配肯定不會交叉，更進一步的，將 \(a, b\) 混起來排序以后一定是一段段區(qū)間的匹配。

   發(fā)現(xiàn)一段區(qū)間的反轉(zhuǎn)可以直接類似前綴和維護，于是直接反悔貪心就做完了。

NOI2025模擬測3

簡單場。

1. T1 背包問題模板

   部分分非常啟發(fā)拆位以后做數(shù)位 dp。但是我就不。

   考慮到 \(m\) 巨大但 \(b\) 很小，于是我們經(jīng)典的先貪心。

   考慮調(diào)整，結(jié)論告訴我們?nèi)萘渴?\([-b^2, b^2]\) 的，考慮用 \(b_i\) 個 \(j\) 物品換 \(b_j\) 個 \(i\) 物品顯然不會更優(yōu)（因為前面是貪心）。顯然最多只會有 \(b ^ 2\) 個物品有用，于是直接做多重背包即可。

2. T2 南河泄露

   快進到轉(zhuǎn)移方程：

   \(f_{l, r} = \max_k\{\min\{g_{l, k}, f_{k, r}\} + d_k + (s_k - s_l) ^ 2\}\)。

   考慮 \(l: n \to 0, r: l + 1 \to n + 1\) 轉(zhuǎn)移。

   考慮拆開 \(\min\)，容易發(fā)現(xiàn)其左邊遞增，右邊遞減，于是我們直接雙指針維護分界點 \(p\)。

   然后就是做 \(f_{l, r} = \max_{k\in [l, p)}\{g_{l, k} + d_k + (s_k - s_l) ^ 2\}, \max_{k\in [p, n + 1]}\{f_{k, r} + d_k + (s_k - s_l) ^ 2\}\}\)。

   前面是前綴 \(min\)，后面是斜率優(yōu)化，對每個 \(r\) 維護一個凸殼即可。

   \(g\) 同理。

3. T3 最短路問題模板

   樹剖+線段樹優(yōu)化建圖，對重鏈維護前綴即可 \(n \log^2 n\)，沒意義。

   \(n \log n\) 我還不會，好像是形如將一堆邊一起扔進去做最短路，仙姑了。