BaiBaiShaFeng's Blog :D

摘要： 神秘題目，本人用的貪心做的，發現一個二分寫法，故記錄一下。 題意 有 \(2N\) 個燈泡，分為 \(A\) 組和 \(B\) 組各 \(N\) 個。 你可以從中選取任意個燈泡，每選取一個燈泡需要花費 1 的代價。 在你選取完之后，系統會隨機在A類和B類中選擇一個類型，并點亮那一類的所有燈泡。你選取 閱讀全文

摘要： 雖然并沒有任何的意義，但是我覺得很有意思，所以記錄一下： #include <bits/stdc++.h> #define int long long using namespace std; const int MN=1e6+116; struct Node{ int lc, rc, siz, r 閱讀全文

摘要： 整理一下關于 exgcd 的內容，都說寫完這道題就會做所有 exgcd 的題了，是不是我不知道，反正今天又做了一遍，記錄一下我的過程，感覺沒有太難。 題意 求不定方程 \(ax+by=c\) 的解。 以下稱正整數解為 \(x,y\) 都是正整數的解，其中有一個是非正整數就不行。 如果沒有任何整數解， 閱讀全文

摘要： 最近模擬賽打的都不是太好，先隨便復習復習吧，馬上就要 CSPS 了，我可以考好的。 這里放一些單調棧的題目，笛卡爾樹先不說，這個我已經忘了，后天復習一下。 本體 棧中維護有單調性的數據，入棧時維護這個單調性，這是計算結果。 是個人都會，不想多寫。 直接進入 dlc 環節。 最大子矩形。 就是一個平面 閱讀全文

摘要： 這道題看起來并不是那么好做，看到題解神秘做法，記錄下來。 考慮枚舉右端點，統計符合條件的左端點數量。 發現 3 這個數字很小，發現區間中的數我們僅僅需要知道它 %3 的值。 我們如果可以記錄一個位置前綴中所有值的出現情況就好了，但是明顯不現實，整個數據是 \(n^2\) 級別的。 就算我們搞一棵主席 閱讀全文

摘要： 如果在正常的字符串匹配的基礎上，如果我們加入可以有 \(K\) 個地方不一樣該怎么做？ 有一道這個問題的弱化，這篇文章記錄一下這道題：P3763 [TJOI2017] DNA 這到題是允許有 3 個以下地方不一樣，但不影響這種問題的思路。 就是正常的二分哈希。 我們記錄兩個串的哈希，到時候查找區間的 閱讀全文

摘要： 題意十分甚至有九分的簡單，但是這個東西似乎是不好做的，我想不出來任何已知的 log 數據結構維護它。 突然發現這個東西增長是緩慢的，我于是乎寫了個程序驗證，最后發現答案最多是 1e6 左右的一個數。 果然有的時候觀察答案上下界有奇效。 我們發現可以使用差分轉化為對于每個點跳多少次。 因為這個跳的值域 閱讀全文

摘要： 我們觀察到移動中 11 這樣的結構是一直貼在一起的，而孤立的 1 是隨著 11 的移動而移動的，所以我們僅僅需要在乎 0 和 11 的組合情況。 發現任意的 11 和 0 都是可以互換的，所以直接 \(\binom{cnt11+cnt0}{cnt0}\) 代碼↓ 點擊查看代碼 #include <b 閱讀全文

摘要： 鏈接：https://sjzezoj.com/contest/428/problem/2449 代碼借鑒了 aqz 大蛇，考場上想到差不多的東西，只是最后我沒有想出來具體怎么對中間的點進行統計，所以打了性質 A, 拿到了 40 pts。 記錄一下我自己的辦法怎么轉化成正解。 還是一樣的建 Krusk 閱讀全文

摘要： 自己寫一遍插板法的東西，順便補上 oiwiki 上沒有的一個證明。 偏向整理，別人估計不知道我在干什么。 基本模型：\(x_0+x_1+...+x_k=n\) 的正整數或非負整數解數量，可以抽象為元素組的劃分。 正整數解的數量 也是插板法最基本的模型。 有 \(n\) 個相同的元素，將它們分成 \( 閱讀全文