10-30 題

Joke - 題目 - QOJ.ac

先把 \(q\) 按照 \(p\) 排序，這樣不會(huì)影響答案。

先假設(shè)我們已知所有的 \(q_i\)，怎么求合法 \(s\) 的方案數(shù)。考慮把 \((i,q_i)\) 畫到二維平面上，那么我們可以畫一條不降的折線表示 \(a_{1,i}\) 的取值，此時(shí)折線下方的點(diǎn) \(s_i=1\)，上方的點(diǎn) \(s_i=0\)。

可以對(duì)本質(zhì)不同的折線計(jì)數(shù)，我們先把折線的頂點(diǎn)都取到給定的點(diǎn)上。相當(dāng)于要選出一個(gè)點(diǎn)集使得存在一條折線分割這個(gè)點(diǎn)集與它的補(bǔ)集，問有多少種選法。考慮到若一個(gè)點(diǎn)被選，那么它右下角的點(diǎn)都要被選，所以兩條折線不同當(dāng)且僅當(dāng)前綴嚴(yán)格最大值的位置集合不同。

折線的頂點(diǎn)現(xiàn)在只能選到前綴嚴(yán)格最大值，所以轉(zhuǎn)化成了求 \(q_i\) 上升子序列的個(gè)數(shù)。

加入 \(q_i=0\) 的情況，可以 DP，設(shè) \(f_{i,j,k}\) 表示前綴最大值為 \(j\)，且折線上選了 \(k\) 個(gè) \(q_i=0\) 的點(diǎn)。轉(zhuǎn)移容易做到 \(O(n^4)\)。

\(k\)-coloring - 題目 - QOJ.ac

\(k=1\) 的情況是跑歐拉路徑，當(dāng)且僅當(dāng)有 \(0\) 個(gè)或 \(2\) 個(gè)奇度數(shù)點(diǎn)時(shí)存在歐拉路徑。

\(k=2\) 的情況，找出任意一棵 DFS 樹，對(duì)于樹邊發(fā)現(xiàn)直接走就是對(duì)的（路徑即歐拉序），考慮到還要返祖邊，只要來回跳一次返祖邊即可。

\(k=3\) 的情況，如果我們已經(jīng)求出了 \(k=2\) 的路徑為 \([a_1,a_2,a_3,a_4,a_5,a_6\dots]\)，那么我們可以執(zhí)行以下策略：\(a_1\to a_2\to a_3\to a_2\to a_3\to a_4\to a_5\)，此時(shí) \(a_5\) 當(dāng)成 \(a_1\) 反復(fù)執(zhí)行相同策略。

對(duì) \(k>3\) 的情況，可以在每次走邊前反復(fù)跳就可以歸約到 \(k-2\) 的問題。

因此這道題對(duì)于 \(k>1\) 的情況都是一定有解的。

Permutation Recovery - 題目 - QOJ.ac

考慮一個(gè)排列建邊 \(i\to p_i\)，那么發(fā)現(xiàn)逆排列中就會(huì)有 \(p_i\to i\) 這條邊。

因此對(duì) \(j\to a_{i,j}\) 連邊，然后把所有相反的邊兩兩組成無向邊。發(fā)現(xiàn)此時(shí)只要找出 \(k\) 組 \(n\) 的置換環(huán)即可。

考慮給每條邊定向，可以跑一遍歐拉回路。對(duì)于一條邊 \(u\to v\) 我們?cè)谧蟛奎c(diǎn) \(u\) 和右部點(diǎn) \(v\) 之間連一條邊，轉(zhuǎn)化為二分圖匹配問題，要求劃分出 \(k\) 對(duì)完美匹配。

這叫做正則二分圖匹配問題，方法就是每次找到一組完美匹配，然后把匹配邊全部刪掉（一定要?jiǎng)h掉而不能保留反向邊），不斷做這個(gè)過程。證明依靠 Hall 定理。

Excluded Min - 題目 - QOJ.ac

Mex 可以為 \(x\) 當(dāng)且僅當(dāng)小于等于 \(x-1\) 的數(shù)至少有 \(x\) 個(gè)。我們要找到最大的 \(x\)。

要注意 \(x\) 不可二分。

考慮從大到小掃描 \(x\)，維護(hù) \(cnt-x\) 的最值，每次把滿足 \(cnt-x\ge0\) 的區(qū)間拿出來刪掉。難點(diǎn)就在如何對(duì)一堆特定區(qū)間做加法操作。

注意到若 \(a\) 區(qū)間包含 \(b\) 區(qū)間，那么 \(a\) 的答案比 \(b\) 的大。考慮只保留極大的區(qū)間，這樣區(qū)間的 \(l\) 是遞增的，每次做加法操作都是對(duì)一個(gè)區(qū)間。

考慮刪掉區(qū)間 \(i\) 后加入哪些極大區(qū)間，找到被刪區(qū)間的前驅(qū)和后繼，那么要找到 \([l_i,l_{nxt}-1]\) 內(nèi)右端點(diǎn)最大（相同則選取左端點(diǎn)更小的）的區(qū)間，若右端點(diǎn)大于 \(r_{pre}\) 則可以加入。加入后將 \(l_{nxt}\) 置為新加入的區(qū)間的 \(l\) 然后不斷加入。

用線段樹做，復(fù)雜度 \(O((q+n)\log n)\)。

Angle Beats 2.0 - 題目 - QOJ.ac

一個(gè) \(L\) 形可以被表示為：在上下和左右各取一個(gè)點(diǎn)。

考慮建圖，上下連一條邊，左右連一條邊，現(xiàn)在要對(duì)每條邊選出一個(gè)端點(diǎn)，選出的端點(diǎn)不交。那么 Center 要連自環(huán)表示必選。

考慮到每個(gè)連通塊的貢獻(xiàn)是獨(dú)立的，對(duì)于一個(gè)連通塊，顯然滿足 \(m\ge n-1\)。

\(m>n\) 則無解；若 \(m=n\) 則是基環(huán)樹，當(dāng)有自環(huán)時(shí)貢獻(xiàn)為 \(1\) 否則為 \(2\)；當(dāng) \(m=n-1\) 時(shí)考慮有一個(gè)點(diǎn)必定不被選，枚舉這個(gè)點(diǎn)，從這個(gè)點(diǎn)開始就能確定所有邊的選法，因此貢獻(xiàn)為點(diǎn)數(shù)。

答案就是所有連通塊的貢獻(xiàn)乘積。

Juggler's Trick - 題目 - QOJ.ac

考慮一個(gè)串什么時(shí)候能被刪空。結(jié)論：充要為長(zhǎng)度為 \(r+b\) 的倍數(shù)且，\(R,B\) 的個(gè)數(shù)之比等于 \(r:b\)。

證明：

考慮把串每 \(r+b\) 個(gè)分段，那么一定存在兩段使得一個(gè)段 \(R\) 的個(gè)數(shù)大于等于 \(r\)，另一個(gè)段 \(R\) 的個(gè)數(shù)小于等于 \(R\)。考慮從一個(gè)段增量移動(dòng)到令一個(gè)段的過程中，由于 \(R\) 的個(gè)數(shù)每次只會(huì)增減一，所以一定有一個(gè)時(shí)刻使得 \(R\) 的個(gè)數(shù)為 \(r\)，這個(gè)時(shí)刻的段則可以被操作。不斷操作即可。

考慮 DP，設(shè) \(f_i\) 表示考慮完前 \(i\) 個(gè)數(shù)最多能執(zhí)行的操作數(shù)。每次枚舉 \(i\) 結(jié)尾的刪空的一段，可以做到 \(O(n^2)\)。

考慮每個(gè) \(R\) 寫一個(gè) \(-b\)，每個(gè) \(B\) 寫一個(gè) \(r\)，然后對(duì)于 \(W\) 一種序列全部寫 \(-b\)，另一種全部寫 \(r\)，那么求這兩種序列的前綴和 \(u_i,v_i\)。此時(shí) \(j\) 能轉(zhuǎn)移到 \(i\) 當(dāng)且僅當(dāng) \(u_i-u_j\le 0\le v_i-v_j\) 且 \(r+b \mid i-j\)。CDQ 分治優(yōu)化即可。

Maximal Subsequence - 題目 - QOJ.ac

每個(gè)結(jié)束點(diǎn)求出 LIS \(f_i\)，然后給 \(j<i \land f_j+1=f_i\) 的 \(j,i\) 連邊，那么我們要找到 \(f_i=1\) 到 \(f_i=L\) 的最小割。

轉(zhuǎn)化為求最大流，要選出最多的最長(zhǎng)上升子序列。

把一條最長(zhǎng)上升子序列在坐標(biāo)系上連起來，選出的兩個(gè)最長(zhǎng)上升子序列的連線是不交的。

先把所有點(diǎn)按照 \(f_i\) 分層，對(duì)于同一層的點(diǎn)的 \(a\) 一定是遞減的。每次取出每層的第一個(gè)點(diǎn)組成一個(gè) LIS，把這些點(diǎn)刪掉，然后把不屬于 LIS 的點(diǎn)也刪掉，被刪掉的點(diǎn)一定是每層的開頭一段。check 一個(gè)點(diǎn)是否屬于一個(gè) LIS 需要看下一層的第一個(gè)點(diǎn)是否大于它，且上一層要有點(diǎn)在其之前。用 vector 維護(hù)每層的點(diǎn)即可。

復(fù)雜度 \(O(n\log n)\)。