CF2062C Cirno and Operations

由于差分的特性，所以要么反翻轉(zhuǎn)一次，要么不翻轉(zhuǎn)。翻轉(zhuǎn)更多次效果是等效的。

翻轉(zhuǎn)一次就等價(jià)于最后差分出來的取相反數(shù)。于是直接暴力模擬即可。

QOJ9980. Boolean Function Reconstruction

有解的充要條件是對于 \(\forall T\subset S\)，\(f(T)\le f(S)\)。

首先我們可以找到所有滿足 \(f(S)=1\) 的 \(S\)，將其中 \(x_i=1\) 的變量與起來。對于所有表達(dá)式或起來。這樣子長度是 \(O(n2^n)\) 的。

由于按位與和按位或運(yùn)算的特殊性，對于 \(S\)，若 \(f(S)=T\)，那么其超集肯定為真。

我們只需要高維前綴和統(tǒng)計(jì)一下，找到最小的一些 \(S\)，其個(gè)數(shù)最多是 \(15\choose 7\) 的級別。這個(gè)時(shí)候暴力構(gòu)造可以做到 \(O(n{n\choose n/2})\)，還是不行。

可以發(fā)現(xiàn)上述做法浪費(fèi)了一些公共部分，于是我們對于所有變量找到其公共部分，對于含它的放在一起，不含的放在另一側(cè)進(jìn)行構(gòu)造。比如對于包含 \(x_1\) 表達(dá)式 \(f_1\) 和不包含 \(x_1\) 的表達(dá)式 \(f_2\)。我們就是可以列出 \((x_1~\mathrm{and}~f_1)~\mathrm{or}~f_2\) 這樣子的結(jié)構(gòu)，然后在 \(f_1\) 和 \(f_2\) 內(nèi)部分別對于 \(x_2\) 進(jìn)行如上處理。這個(gè)過程可以在字典樹上面完成。

P7738 [NOI2021] 量子通信

注意到 \(256=16^2\)，直接劃分成 \(16\) 份。\(k_i\le 15\)，根據(jù)抽屜原理一定有一個(gè)公共塊，直接暴力尋找然后枚舉判斷即可。其中單個(gè)塊內(nèi)期望個(gè)數(shù)是 \(\dfrac{n}{2^{16}}\)。

CF1758D Range = √Sum

\(\sqrt {f^2(n)}\)，取 \(f(n)=n+1\) 是可以直接構(gòu)造的，\(2n\) 也可以。

構(gòu)造初始序列 \(1,2,3..,n\) 之后，調(diào)整法。令 \(n\to n+2\)，為了保持極差于是可以整體 \(+1\) 和后綴（除了最后一個(gè)數(shù)） \(+1\)。通過這些調(diào)整使得和變成 \((n+1)^2\) 即可。

P6776 [NOI2020] 超現(xiàn)實(shí)樹

只需要判定一條無限長的鏈的存在性。

假設(shè)在右子樹內(nèi)，如果左子樹為空的話直接遞歸，否則必須只有一個(gè)點(diǎn)，不然的話可以構(gòu)造出一個(gè)左邊多一個(gè)無法加的點(diǎn)，右邊不斷伸長的鏈，這樣子就不合法了。于是我們把給的 \(m\) 顆樹重新編號成為一種編號方式的樹。然后遍歷每個(gè)節(jié)點(diǎn)判定即可。

P7736 [NOI2021] 路徑交點(diǎn)

對于 \(k=2\) 的時(shí)候，首先兩兩匹配可以看成排列。交點(diǎn)個(gè)數(shù)其實(shí)就是 \(p_i\) 排列逆序?qū)?shù)量，奇數(shù) \(-1\)，偶數(shù) \(+1\)，可以發(fā)現(xiàn)這個(gè)和行列式定義一樣，于是直接對于鄰接矩陣求一個(gè)行列式，也就是 \(\det(A)\)。

對于 \(n_1=n_i\) 的時(shí)候，可以直接把求出相鄰兩列的行列式，然后再相乘，也就是 \(\prod \det(A)\)。因?yàn)榕紨?shù)貢獻(xiàn) \(+1\)，奇數(shù)貢獻(xiàn) \(-1\)，兩個(gè)奇數(shù)遇到就會(huì)變成偶數(shù)，其貢獻(xiàn)也會(huì)變成 \((-1)\times (-1)=1\)，因此上述按照貢獻(xiàn)法是對的。

對于一般情況就不是排列了，也不是 \(n\times n\) 的矩陣了。其實(shí)很容易猜到就是先 \(\prod A\)，將其變成 \(n\times n\) 的矩陣，然后再求 \(\det\)。至于證明的話，就是 \(\prod A\) 中 \((i,j)\) 就是第一列的 \(i\to\) 最后一列的 \(j\) 的路徑方案數(shù)。而且還自動(dòng)滿足了路徑不能重合這個(gè)條件，因?yàn)橹睾下窂降哪嫘驅(qū)Σ顬?\(1\)，就抵消了。

ARC106E Medals

二分答案之后是一個(gè)二分圖匹配。

有一個(gè)很重要的觀察就是答案不會(huì)超過 \(2nk\)。

直接上 Hall 定理，直接高維前綴和判定一下就行了。注意判定的時(shí)候，交難求，正難則反一下變成并就很好做了。

P8991 [北大集訓(xùn) 2021] 出題高手

利用前綴和轉(zhuǎn)化，設(shè)前綴和序列為 \(S\)。那么對于一個(gè) \(S_r\)，貪心來想其可能的 \(S_{l-1}\) 必然是一個(gè)后綴 \(\min\)（不妨設(shè) \(S_r>S_{l-1}\)）。于是我們放到單調(diào)棧里面求解，隨機(jī)序列前綴和的后綴 \(\min\) 個(gè)數(shù)大概是 \(O(\sqrt n)\) 級別的，這樣子可以大幅減少可能的狀態(tài)數(shù)。

同時(shí)因?yàn)槭请S機(jī)情況，所以可以發(fā)現(xiàn)可能作為答案的區(qū)間長度必然不會(huì)太長，取閾值為 \(B=2000\) 即可。以上兩個(gè)優(yōu)化可以將可能區(qū)間個(gè)數(shù)大幅降低。

然后就是一個(gè)單點(diǎn)加，矩陣求 \(\max\) 了。可以掃描線 \(+\) 樹狀數(shù)組解決。這樣子在 \(\sqrt n\) 的基礎(chǔ)上帶一個(gè) \(\log\)。也可以分塊求解，這樣子 \(O(1)\) 修改，\(O(\sqrt n)\) 查詢就實(shí)現(xiàn)了平衡。

QOJ5061. Allin

由于有 \(4\) 張未知牌，所以手中至少是炸彈。進(jìn)一步分析其實(shí)是必須有同花順。

剩下同花順對于已經(jīng)顯示的 \(5\) 張牌就有要求了。對于十幾種情況進(jìn)行暴力討論一下就行了。

UOJ75.智商鎖

可以用矩陣樹定理算出 \(G\) 的生成樹個(gè)數(shù) \(f(G)\)。

將兩個(gè)圖拼接起來個(gè)數(shù)就是 \(f(G_1)\times f(G_2)\)。我們隨機(jī) \(5000\) 個(gè)大小為 \(20\) 的圖，兩兩拼接之后再兩兩組合，第一次直接暴力枚舉，第二次用哈希表尋找。

ZJU 整潔度

對于兩個(gè)串，其整潔度為最長公共 border 的長度。求一個(gè)串的所有前綴任意排列之后，相鄰整潔度之和。同時(shí)有 \(m\) 次修改，每次在末尾添加或者刪除字符。\(n,m\le 5\times 10^5。\)

第一步是很顯然的轉(zhuǎn)化，就是離線求出 fail 樹上 LCA 深度之和。

如何重排？有一個(gè)結(jié)論就是按照 dfs 序重排就是最優(yōu)的。

直接按照 P3320 [SDOI2015] 尋寶游戲 里面的方法用 std::set 維護(hù) dfs 序即可，可以支持動(dòng)態(tài)維護(hù)。

動(dòng)態(tài)加減字符可能會(huì)讓復(fù)雜度爆掉，我們直接建立 KMP 自動(dòng)機(jī)就行了。

P6113 【模板】一般圖最大匹配

存在線性代數(shù)做法。假如存在邊 \(i\to j\)，我們就在對應(yīng)位置填上 \(x_{i,j}\)，在對稱位置填上 \(-x_{i,j}\)。

求一下行列式，如果存在完美匹配，那么 \(\det(A)\neq 0\)。證明就是對于奇偶環(huán)討論一下，然后會(huì)消掉的。

推論是最大匹配數(shù)就是 \(\dfrac{\mathrm{rank(A)}}{2}\)，高斯消元可解。

其中隨機(jī)數(shù) \(x_{i,j}\in [0,P-1]\)，在模 \(P\) 的意義下求解。

對于多項(xiàng)式 \(\sum a_ix^i\equiv 0\pmod P\)，錯(cuò)誤率是 \(\dfrac{n}{P}\)。