P14046

題面

考慮到對于一個會放回書的點(diǎn)，其一定滿足單調(diào)性，考慮用這個東西做題。

那我們就考慮求出來這個單調(diào)的分界點(diǎn)就可以在復(fù)雜度正確的情況下做了。

考慮直接算出分界點(diǎn)，就是 \(lst_i\to i\) 中的顏色數(shù)量。直接掃描線 \(+\) BIT 就好了。

然后算答案是區(qū)間 \(+\)，單點(diǎn)查，用差分 BIT 就好了。

很好的根號分治題

題面

題解

大概意思是對于一次函數(shù) \(kx+b\)，有幾種分治方向：

1. 可以對于 \(k\) 分治，如果其有上限，那么分治范圍為 \(\sqrt V\)，兩部分中大的部分值分散，直接處理。
2. 可以對有取模操作的數(shù)/整除操作的數(shù)分治，原理也是分散，但是若取模的數(shù)很小，可以尋找取模后的數(shù)直接討論。

復(fù)雜度分析的時候用均值不等式/底數(shù)相同來權(quán)衡一下，不一定直接就是 \(\sqrt n\)。

P9584

題面

我不會換根，考慮計(jì)數(shù)器。經(jīng)典結(jié)論就是這條邊會用 \(siz_u\times n-siz_u\) 次。考慮新加的點(diǎn)怎么搞。

對于其子樹，貢獻(xiàn)為 \(siz_u\) 次，否則貢獻(xiàn)為 \(n-siz_u\) 次。我們維護(hù)這玩意 \(\times w_i\) 的子樹和就好了，查詢的時候就扣出來加上。

P11624

題面

考慮答案的組成：

1. \(dep\) 相同。
2. \(LCA\) 為根節(jié)點(diǎn)。

第一種直接用桶。第二種先考慮根節(jié)點(diǎn)的貢獻(xiàn)，然后用乘法原理把根連的子樹一個一個加上就好了。

P11627

題面

原作者：Genius_Star

考慮轉(zhuǎn)化式子：

故我們只需要最大化：\(\sum_{u = 1}^n \operatorname{dis}(u, t)\)

容易預(yù)處理出 \(siz_i\)，設(shè) \(w_i\) 表示邊權(quán)，則要最大化：\(\sum_{i = 1}^{n - 1} siz_i w_i\)

由于 \(w\) 是一個排列，故考慮貪心即可，按照 \(siz\) 的值從大到小分配 \((n - 1) \to 1\)。

由于我們需要枚舉 \(t\)，故考慮換根 dp。即相當(dāng)于在原來 \(\{siz_i\}\) 集合中刪除 \(siz_u\)，加入新的 \(siz'_{fa_u}\)。

故我們現(xiàn)在只需要做單點(diǎn)修改，全局下面式子的最大值：\(\sum_{i = 1}^{n - 1} siz_{v_i} w_i\)

考慮維護(hù)值域線段樹 \([1, n]\)，對于每個區(qū)間 \([l, r]\) 維護(hù)有多少個 \(siz_i\) 在這里面（設(shè)有 \(cnt\) 個），以及這些 \(siz\) 的和 \(sum\)，以及考慮 \(w\) 是 \(1 \sim cnt\) 的排列時的最大值。

合并兩個區(qū)間 \(cnt_l, sum_l, ans_l, cnt_r, sum_r, ans_r\) 時，顯然有：\(cnt = cnt_l + cnt_r\)，\(sum = sum_l + sum_r\)

對于右區(qū)間的 \(w\)，顯然要由 \(1 \sim cnt_r\) 的排列變?yōu)?\(cnt_l + 1 \sim cnt_l + cnt_r + 1\) 的排列，即 \(w\) 整體添加了 \(cnt_l\)，故：\(ans = ans_l + ans_r + cnt_l sum_r\)

Karma

題面 回顧一下這道好題。

考慮貪心，怎么貪呢，嘗試合并，看一下有那些貢獻(xiàn)。我們設(shè)一個串有 \(3\) 種值 \(a,b,c\) 分別代表 \(0,1,\text{逆序?qū)\) 個數(shù)。

考慮兩個串合并，如果 \(i\) 串在 \(j\) 串前。增加的貢獻(xiàn)是 \(a_j\times b_i\)，考慮如果要這樣最小，那么滿足 \(a_j\times b_i\le a_i\times b_j\)，也就是 \(\frac{b_i}{a_i}\le \frac{b_j}{b_j}\)。直接排序即可。

同桌與室友

題面 原作者：BILL666

先習(xí)慣性連邊，將雙人宿舍關(guān)系看做是黑邊，雙人桌關(guān)系看做是白邊，那么就是一個圖同構(gòu)的計(jì)數(shù)。

但是這個題每個人度數(shù)不超過 \(2\)，所以每一個連通塊要么是一個簡單環(huán)，要么是一條鏈。

然后考慮分類計(jì)數(shù)：

• 如果有 \(x\) 個大小為 \(i\) 的環(huán)，那么這一部分答案為 \(x!\times i^x\)。
• 如果有 \(x\) 個長度相同，兩段邊同為黑或同為白的鏈，那么這一部分答案為 \(x!\times 2^x\)。
• 如果有 \(x\) 個長度相同，兩段邊不同色的鏈，那么這一部分答案為 \(x!\)。

P5921

題面

題面轉(zhuǎn)化：給定一張有向圖，設(shè)添加最少 \(m\) 條邊 可以使得整張圖存在歐拉路徑。 請輸出 \(m+n+1\)。

歐拉路徑是指經(jīng)過圖中每一條邊的路徑。

先看一下一些性質(zhì)：

有向圖下：\(\sum_{i\in G}in_i-\sum_{i\in G}out_i=0\)。

關(guān)于有向圖歐拉路徑：

• 若滿足\(\sum_{i\in G} |in_i-out_i|=0\)，則這張圖存在歐拉回路。
• 若滿足\(\sum_{i\in G} |in_i-out_i|=2\)，則這張圖存在歐拉路徑。
• 若滿足\(\sum_{i\in G} |in_i-out_i|> 2\)，則一定可以添加一條邊使得這個和 \(-2\)。
• \(\sum_{i\in G} |in_i-out_i|\) 一定是偶數(shù)。

考慮對每個聯(lián)通塊計(jì)算答案，假設(shè)一共有 \(s\) 個聯(lián)通塊，那么最終答案就是：

直接并查集就好了。

CF859E

題面

依舊計(jì)數(shù)，考慮建圖。我們發(fā)現(xiàn)每個點(diǎn)的出度 \(\le 1\)。所以會構(gòu)成如下情況。

• 樹
• 基環(huán)樹（環(huán)可能是自環(huán)）
• 自環(huán)

對每一個圖形分別考慮答案，然后用乘法原理乘起來就好了。

1. 對于樹：定點(diǎn)一定是空的，其他都是有人的，考慮把一條鏈向前挪一步。所以方案數(shù)為 \(siz\)。
2. 對于自環(huán)基環(huán)樹：只有一種答案。
3. 對于長環(huán)（環(huán)長 \(\le2\)）基環(huán)樹：有兩種答案，就是環(huán)上挪一步/不動。
4. 對于自環(huán)，只有一種答案。

接下來用并查集就可以維護(hù)這幾種圖形了。

HDU-4336

題面

方法一，直接用期望，設(shè)計(jì)狀態(tài) \(f_S\) 表示已經(jīng)獲得 \(S\) 需要拿滿的期望天數(shù)。那么有：

時間復(fù)雜度 \(O(n2^n)\)。

方法二，用 min-max 容斥，有這個式子。

而且顯然 \(\min_{i\in S}{x_i}=\frac{1}{\sum_{i\in S}p_i}\).

所以我們直接 \(dfs\) 把所有可能找到就好了。時間復(fù)雜度 \(O(2^n)\)。

bzoj2565

題面

考慮用回文形式表達(dá)答案。我們設(shè)計(jì)兩個數(shù)組 \(l_i,r_i\) 來表示以 \(i\) 作為左端點(diǎn)/右端點(diǎn)的最大長度，那么答案就是：

考慮從回文數(shù)組得到這個東西，那么我們可以直接把這個答案轉(zhuǎn)移到邊界，然后再取 \(\max\) 轉(zhuǎn)移到中間，用 \(l\) 舉例子來說就是：

當(dāng)然在回文處理過的數(shù)組中略有不同。

loj6048

題面

比較高妙的題。

考慮最終答案是什么，其實(shí)就是把這個數(shù)列以左側(cè)對稱后的 \(LIS\)，然后就是板子了。

比如 \(123\to 321123\)。

計(jì)數(shù)的話，離散化完了用樹狀數(shù)組維護(hù)最大值及其方案數(shù)。