dyc2022's Blog

摘要： 更差的閱讀體驗(yàn) 考慮一個(gè)很菜的 dp。假設(shè) \(f_{i, j}\) 表示前 \(i\) 個(gè)人，對(duì)著 \(i\) 砍了 \(j\) 刀的方案數(shù)。那么很顯然有轉(zhuǎn)移： \[f_{i, j} = \max_{k} \{f_{i-1, k} - m \times \max(0, j-k)\} + [j \g 閱讀全文

摘要： 更差的閱讀體驗(yàn) 注意到，增加一個(gè)障礙物至少可以減少一對(duì)互相攻擊的車(chē)，最多減少兩對(duì)互相攻擊的車(chē)。 考慮兩對(duì)車(chē)什么時(shí)候可以同時(shí)消除，當(dāng)且僅當(dāng)兩對(duì)車(chē)的連線有交。所以可以轉(zhuǎn)換成一個(gè)二分圖匹配的模型，具體地，每個(gè)左部點(diǎn)是每一對(duì)橫坐標(biāo)相同的可以相互攻擊的車(chē)，右部點(diǎn)是每一對(duì)縱坐標(biāo)相同可以相互攻擊的車(chē)。如果一對(duì)車(chē)可 閱讀全文

摘要： 更差的閱讀體驗(yàn) 我們考慮如何確定一個(gè)點(diǎn) \(v\) 是否是 \(u\) 的兒子。 如果我們已經(jīng)確定了 \(v\) 的深度為 \(u\) 的深度 \(+1\)，那么我們只需要檢查 \(u, v\) 的距離是否為 \(1\)。如果距離為 \(1\) 就說(shuō)明有邊相連。 如果我們已經(jīng)確定了 \(v\) 在 閱讀全文

摘要： 更差的閱讀體驗(yàn) 今天，我，學(xué)會(huì)了，K-D Tree。 簡(jiǎn)單講一下這個(gè)數(shù)據(jù)結(jié)構(gòu)的流程：我們把平面上的點(diǎn)按照某個(gè)維度上過(guò)某個(gè)點(diǎn)的一條分割線切開(kāi)，以分割線穿過(guò)的這個(gè)點(diǎn)為根，遞歸處理左右兩個(gè)子樹(shù)。這樣靜態(tài)建出的樹(shù)高度是 \(O(\log n)\) 當(dāng)然是理想的，但是插入的時(shí)候會(huì)影響平衡性。所以可以用一些替罪 閱讀全文

摘要： 更差的閱讀體驗(yàn) 經(jīng)典套路，我個(gè)人認(rèn)為是橙題。 相鄰相等不好刻畫(huà)，我們直接把偶數(shù)位置反轉(zhuǎn)，這樣一組相鄰相等中恰好有一個(gè)被反轉(zhuǎn)，變成刪除相鄰不同。 那么假設(shè)沒(méi)有 \(2\)，最終序列中一定只有 \(0\) 或 \(1\)。所以假設(shè) \(0,1\) 個(gè)數(shù)分別是 \(c_0, c_1\)，那么由于一次消除一 閱讀全文

摘要： 更差的閱讀體驗(yàn) 袋鼠題。 考慮先暴力模擬一輪中每個(gè)袋鼠的運(yùn)動(dòng)。我們假設(shè)位于 \((i, j)\) 的袋鼠，經(jīng)過(guò)一輪之后到達(dá) \((i', j')\)，那么我們連邊 \((i, j) \to (i', j')\)，形成一個(gè)內(nèi)基環(huán)樹(shù)。 那么我們考慮一個(gè)格子在多少輪以前會(huì)有袋鼠。我們發(fā)現(xiàn)，一輪以后，每一個(gè) 閱讀全文

摘要： 更差的閱讀體驗(yàn) 首先，我們預(yù)處理出 \(f_i\) 表示當(dāng)進(jìn)攻能力為 \(i\) 時(shí)防守能力最大能有多少。 對(duì)于一組詢(xún)問(wèn)，假設(shè)我們派出的進(jìn)攻、防守兵力分別為 \(a,d\)，對(duì)方分別為 \(a',d'\)。那么我們考慮己方和對(duì)方進(jìn)球 \(\max(0, a-d')\) 和 \(\max(0, a'- 閱讀全文

摘要： 更差的閱讀體驗(yàn) 注意到，對(duì)于式子 \(a \bmod b\)，如果 \(a > b\) 則 \(a\) 的值不變；如果 \(a \le b\) 則 \(a\) 的值至少折半。 這意味著，我們對(duì)數(shù)字 \(X\) 多次取模，實(shí)際上只有 \(O(\log X)\) 次取模真正修改了它的值。所以我們可以暴力 閱讀全文

摘要： 更差的閱讀體驗(yàn) 【模板】生成函數(shù) Problem 1 無(wú)標(biāo)號(hào)數(shù)球盒問(wèn)題，果斷想到普通生成函數(shù)。 對(duì)于第一個(gè)盒子，如果盒子個(gè)數(shù)是 \(A\) 的倍數(shù)，就產(chǎn)生 \(1\) 的貢獻(xiàn)。容易構(gòu)造 \[f_A(x) = \sum _{k \isin \N} x^{kA} \]同理有 \[f_B(x) = \su 閱讀全文

摘要： 更差的閱讀體驗(yàn) 我們會(huì)發(fā)現(xiàn)，如果我們知道了等比數(shù)列的公比，問(wèn)題會(huì)容易很多。具體地，如果我們知道等比子序列的開(kāi)頭元素，然后我們往后掃。假設(shè)我們目前等比子序列的最后一個(gè)元素是 \(a_i\)，公比為 \(m\)，則我們往后找到第一個(gè) \(a_j\) 使得 \(a_i \times m = a_j\)，那 閱讀全文