# 第六屆簡單的小競賽題解

我會按照我覺得的難度由簡單到困難排序。

## [pG. Waimai 超人與 Hehe 遊俠 (Easy Version)](https://zerojudge.tw/ShowProblem?problemid=h989)

我們可以將連續的 $1$ 分成很多區間，可以知道一個長度為 $k$ 的區間最多可以使用 $\lceil \frac{k}{2} \rceil$ 個。
於是最後可以 $O(n)$ 算出來。

## [pD. 【…】，窩的超人](https://zerojudge.tw/ShowProblem?problemid=h927)

要如何加入字元才能使最終結果最大呢？有一個想法是把 $1$ 通通加在左邊，把 $0$ 通通加在右邊，應該很容易就能知道它是最大的，於是可以 $O(n + m)$ 做出來。

## [pJ. 給測驗們的電神](https://zerojudge.tw/ShowProblem?problemid=h992)

費氏數列 $F_i = F_{i - 1} + F_{i - 2}$，轉成矩陣表示可以寫成 $\begin{bmatrix} 1 & 1\\1 & 0 \end{bmatrix}$，用 $\begin{bmatrix} F_{i - 1}\\F_{i - 2} \end{bmatrix}$ 去乘可以得到 $\begin{bmatrix} F_{i}\\F_{i - 1} \end{bmatrix}$。
於是可以矩陣快速冪求出 $F_a, F_b$，那 $F_b$ 在指數的地方要對什麼取餘數呢？根據[費馬小定理](https://zh.wikipedia.org/zh-tw/%E8%B4%B9%E9%A9%AC%E5%B0%8F%E5%AE%9A%E7%90%86)，可以知道若 $a$ 不是質數 $p$ 的倍數，那 $a^{p-1}≡1\text{ (mod }p)$，於是 $F_b$ 對 $p-1$ 取餘數，$F_a$ 對 $p$ 取餘數。

有一點要注意的是 $F_a$ 取完餘數後有可能是 $0$，需要特別判斷，只不過最小的 $a$ 使 $F_a≡0$ 為 $10^9 + 8$，在這題的範圍之外。

時間複雜度為 $O(t\times (\log(a)+\log(b)))$。

## [pH. Waimai 超人與 Hehe 遊俠 (Hard Version)](https://zerojudge.tw/ShowProblem?problemid=h990)

看到這一題有修改又有區間查詢，就會很想用線段樹，那要如何設計線段樹的節點內容呢，我們可以用 $sum$ 表示這個節點最多幾人能使用，$lcnt$ 代表與節點最左邊相連，有幾個連續的馬桶，$rcnt$ 代表與節點最右邊相連，有幾個連續的馬桶。

$sum$ 的更新方法就是左子節點的 $sum\ +$ 右子節點的 $sum$，然後中間的相連的部分要合併，於是可以扣掉左子節點的 $\lceil\frac{rcnt}{2}\rceil$ 與右子節點的 $\lceil\frac{lcnt}{2}\rceil$，再加上 $\lceil\frac{nl.rcnt + nr.lcnt}{2}\rceil$。

$lcnt$ 與 $rcnt$ 的更新方法就是若左子節點的 $lcnt =$ 左子節點的長度，那就將 $lcnt$ 設成 $nl.lcnt + nr.lcnt$，否則設成 $nl.lcnt$，$rcnt$ 同理。

最後總時間複雜度 $O(n + q\times \log(n))$

## [pC. 青蛙](https://zerojudge.tw/ShowProblem?problemid=h925)

如果沒有移動區間的操作，那用線段樹就可以了，那如果要移動區間呢？可以用一個叫做樹堆 ($\text{Treap}$) 的東西，它可以 $\text{Merge}$ 和 $\text{Split}$ 區間，總時間複雜度 $O(n\times\log(n))$。

## [pA. 揩淯愛牌組](https://zerojudge.tw/ShowProblem?problemid=h924)

可以知道，牌的順序其實不重要，我們只要知道每一種牌有幾張就好了，假設有 $m$ 種牌，每種牌有 $cnt[i]$ 張，我們可以用 $dp$ 找出答案。

令 $dp[i][j]$ 代表到了第 $i$ 種牌，拿了 $j$ 張，那 $dp[i][j] = dp[i - 1][j] + cnt[i]\times dp[i - 1][j - 1]$，答案就是 $dp[m][k]$。

總時間複雜度為 $O(n\times(\log(n) + k))$，如果用滾動 $dp$ 可以減少記憶體。

:::spoiler hehe
這題有一個很陰險的地方就是模的是 $998244853$。
:::

## [pI. 確實大師 (Chesh Master)](https://zerojudge.tw/ShowProblem?problemid=h991)

現在先假設要求的是二維的，那距離有哪些表示法呢？有 $\sqrt{(x_i - x_j)^2 + (y_i - y_j)^2}, |x_i - x_j| + |y_i - y_j|, \max(|x_i - x_j|, |y_i - y_j|)$，前兩個都很難用在此題，但第三個只要找到兩邊的最大跟最小相減，然後取 $\max$ 就好了。

我們要如何將 $|x_i - x_j| + |y_i - y_j|$ 轉到 $\max(|x_i - x_j|, |y_i - y_j|)$ 呢？ 可以令新的 $x$ 座標變成 $x_i + y_i$，$y$ 座標變成 $x_i - y_i$，那後面的式子就會等於原本前面的。

那三維的要如何轉換，可以用一個四維的 $(x, y, z, w)$ 表示，$x = x_i + y_i + z_i$，$y = x_i + y_i - z_i$，$z = x_i - y_i + z_i$，$w = x_i - y_i - z_i$，這樣就可以用 $4$ 個 $\text{multiset}$，每次回答 $4$ 個 $\text{multiset}$ 裡最大值與最小值的差的最大值，並且可以 $O(\log(n))$ 加入與刪除數字。

總時間複雜度 $O(n\times \log(n))$。

## [pB. 電橘子與電耗子](https://zerojudge.tw/ShowProblem?problemid=h901)

可以觀察到如果一個耐電值 $X$ 可以成功融合，那比 $X$ 大的都可以融合；如果一個耐電值 $X$ 無法成功融合，那比 $X$ 小的都無法成功融合。

於是我們可以二分搜答案，那有了給定的 $X$，要如何判斷呢？我們可以先計算出 $a_i$ 和 $b_j$ 的發電值，如果小於等於 $X$ 就建邊。因為我們想要把全部都配在一起，所以可以做二分圖最大匹配，如果匹配數是 $n$，就代表成功了。

總時間複雜度 $O(n^3\times \log(C))$，如果用一些特別的作法說不定可以更好？

## [pF. 嗯呀喜歡這個](https://zerojudge.tw/ShowProblem?problemid=h988)

最短距離 $v_i$ 可以用 $\text{dijkstra}$ 在 $O(n\times \log(n))$ 算出來。

剩下的就是如何挑選 $a$ 個和 $b$ 個節點了，我們令 $u_i = d_i\times v_i + c_i$，然後將 $(v_i, u_i)$ 由大排到小。最後會選 $a - b$ 個 $v_i$ 與 $b$ 個 $u_i$，假設選的 $v_i$ 裡面，編號最大的是 $x$，那可以知道 $x$ 之前的都會被選到，因為如果有沒被選到的，假設編號是 $y$，那就不要選 $v_x$，改選 $v_y$ 就好了 (因為 $v_i$ 遞減，$v_y \geq v_x$)。那就可以 $a - b \leq i \leq a$，$1\sim i$ 都有被選到，再從 $n-i$ 個剩下的找答案。

總時間複雜度 $O(n\times \log(n))$。

## [pE. 磚牆改](https://zerojudge.tw/ShowProblem?problemid=h936)

這題叫做磚牆改是因為是從 $\text{IOI 2014 Wall}$ 改編過來的，只是這題沒有取 $\min$ 操作，是因為會跟等一下要講的東西有關。

如果是單純的詢問、操作，那就用線段樹就可以了，每個節點可以設一個 $mx$ 跟 $mn$，代表此節點涵蓋的區間裡的最大值與最小值，而 $\text{push}$ 跟 $\text{pull}$ 的方法需要好好想一下。

$\text{push}$ 的方法為：

node[lpos].mx = max (node[lpos].mx, node[pos].mn);
node[lpos].mx = min (node[lpos].mx, node[pos].mx);
node[rpos].mx = max (node[rpos].mx, node[pos].mn);
node[rpos].mx = min (node[rpos].mx, node[pos].mx);
node[lpos].mn = min (node[lpos].mn, node[pos].mx);
node[lpos].mn = max (node[lpos].mn, node[pos].mn);
node[rpos].mn = min (node[rpos].mn, node[pos].mx);
node[rpos].mn = max (node[rpos].mn, node[pos].mn);

$\text{pull}$ 的方法為：

node[pos].mx = max (node[lpos].mx, node[rpos].mx);
node[pos].mn = min (node[lpos].mn, node[rpos].mn);

那有了刪除操作要怎麼做呢？可以觀察到對區間 $[l_1, r_1]$ 取 $\max$，再對區間 $[l_2, r_2]$ 取 $\max$，順序其實沒差，並且我們做了一個操作後，只要把變化前的值記錄下來，就可以還原。所以就能想到可以用時間線段樹，進入一個節點時執行操作，出去節點時還原操作，就能 $\text{AC}$ 了！

總時間複雜度 $O(q\times\log(q)\times\log(n))$。

## 心得

大家都好厲害