第六屆簡單的小競賽題解

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

pG. Waimai 超人與 Hehe 遊俠 (Easy Version)

我們可以將連續的

$1$ 分成很多區間，可以知道一個長度為

$k$ 的區間最多可以使用

$\lceil \frac{k}{2}\rceil$ 個。
於是最後可以

$O(n)$ 算出來。

pD. 【…】，窩的超人

要如何加入字元才能使最終結果最大呢？有一個想法是把

$1$ 通通加在左邊，把

$0$ 通通加在右邊，應該很容易就能知道它是最大的，於是可以

$O(n+m)$ 做出來。

pJ. 給測驗們的電神

費氏數列

$F_i=F_{i-1}+F_{i-2}$，轉成矩陣表示可以寫成

$\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]$，用

$\left[\begin{array}{c}{F}_{i-1}\\ F_{i-2}\end{array}\right]$ 去乘可以得到

$\left[\begin{array}{c}{F}_i\\ F_{i-1}\end{array}\right]$。
於是可以矩陣快速冪求出

$F_a,F_b$，那

$F_b$ 在指數的地方要對什麼取餘數呢？根據費馬小定理，可以知道若

$a$ 不是質數

$p$ 的倍數，那

$a^{p-1}\equiv 1\text{ (mod }p)$，於是

$F_b$ 對

$p-1$ 取餘數，

$F_a$ 對

$p$ 取餘數。

有一點要注意的是

$F_a$ 取完餘數後有可能是

$0$，需要特別判斷，只不過最小的

$a$ 使

$F_a\equiv 0$ 為

${10}^9+8$，在這題的範圍之外。

時間複雜度為

$O(t\times (\log (a)+\log (b)))$。

pH. Waimai 超人與 Hehe 遊俠 (Hard Version)

看到這一題有修改又有區間查詢，就會很想用線段樹，那要如何設計線段樹的節點內容呢，我們可以用

$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. 青蛙

如果沒有移動區間的操作，那用線段樹就可以了，那如果要移動區間呢？可以用一個叫做樹堆 (

$\text{Treap}$) 的東西，它可以

$\text{Merge}$ 和

$\text{Split}$ 區間，總時間複雜度

$O(n\times \log (n))$。

pA. 揩淯愛牌組

可以知道，牌的順序其實不重要，我們只要知道每一種牌有幾張就好了，假設有

$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$ 可以減少記憶體。

hehe

這題有一個很陰險的地方就是模的是

$998244853$。

pI. 確實大師 (Chesh Master)

現在先假設要求的是二維的，那距離有哪些表示法呢？有

$\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. 電橘子與電耗子

可以觀察到如果一個耐電值

$X$ 可以成功融合，那比

$X$ 大的都可以融合；如果一個耐電值

$X$ 無法成功融合，那比

$X$ 小的都無法成功融合。

於是我們可以二分搜答案，那有了給定的

$X$，要如何判斷呢？我們可以先計算出

$a_i$ 和

$b_j$ 的發電值，如果小於等於

$X$ 就建邊。因為我們想要把全部都配在一起，所以可以做二分圖最大匹配，如果匹配數是

$n$，就代表成功了。

總時間複雜度

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

pF. 嗯呀喜歡這個

最短距離

$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\ge v_x$)。那就可以

$a-b\le i\le a$，

$1\sim i$ 都有被選到，再從

$n-i$ 個剩下的找答案。

總時間複雜度

$O(n\times \log (n))$。

pE. 磚牆改

這題叫做磚牆改是因為是從

$\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))$。

心得

大家都好厲害