BaiBaiShaFeng's Blog :D

摘要： 這一次純純的什么想法都沒有，只好打了一大堆暴力。 T1 loj 5459 這個很神秘了...... 我們維護一個點最右邊 a 不同和 b 不同，\(O(n)\) 不難去做，記錄為 \(nxta[i],nxtb[i]\)。 對于每個詢問，進行如下的判斷。 是否存在，也就是左端點的 \(nxta[l]\ 閱讀全文

摘要： 整理了 NOIP 與某些省份省選的背包題。 NOIP 的背包題 [NOIP 2006 提高組] 金明的預算方案 樹形背包似乎也是可做的，但是由于最多有兩個附件，并且是分為兩類，也就是附件不會再有附件，這個問題就成了最簡單的背包問題了。 我們對于所有主件跑背包，在決策中分類討論只買主件，買一個附件，都 閱讀全文

摘要： 這次做了一次 abc，d 做出來了，但是比較麻煩，又用正確方法寫了一遍，整理一下 d,e,f，g 有一些超綱。 abc408d 考慮把區間 \(l,r\) 最后變成 1，然后嘗試去表示這個時候的答案。 \(sum[i]\) 表示 \(i\) 位置以及之前的 1 的總和。 可以很簡單列出來↓ \(su 閱讀全文

摘要： 整體二分 本來感覺挺神秘的一個東西， 學完了似乎沒有多難， 放幾個板子隨便寫寫吧（今天數學不想做題） 從最最最最人盡皆知的區間第 \(k\) 大問題開始吧 引入 如果我想問你一個序列中的區間的第 \(k\) 大，你會如何？ 顯然我們直接二分就行（主席樹學傻的滾） 時間復雜度為 \(O(nlogn)\ 閱讀全文

摘要： 數位dp 我從就只用記憶化寫數位dp, 隨便寫寫, 因為某天突然不會寫了 首先數位dp一般會把 \([l,r]\) 拆成 \([1,r]\) 和 \([1,l-1]\) , 因為不管你問同一個數什么問題, 它的答案一定都是一樣的, 我們之后就不提這個事了 怎么dp? 我不會, 我不會, 我不會 但是 閱讀全文

該文被密碼保護。 閱讀全文

摘要： 波蘭人太神秘了，竟能出出來如此題目。 題意 給一棵樹（讀入不太尋常，這個容易處理，忽略不計）, 每個葉子節點有一個權值，我們可以選擇交換一些節點的左右子樹（保證是二叉樹，且要么是葉子要么左右子樹都存在）。 經過交換后，跑前序遍歷，求最小化的逆序對數量。 大小不好說，大概是 1e6 左右。 做法 我們 閱讀全文

摘要： 本來以為背背板子就夠用了的，發現有的時候會需要其中的一些東西。 原來樹狀數組也有自己的不可替代性。 但是像用樹狀數組做平衡樹這種我確確實實不感興趣。 當摸魚寫一些吧。 個人認為，樹狀數組是最能體現 OI 魅力的數據結構，它集簡潔，巧妙，智慧與一身，我非常喜歡。 這個是記錄向的，并不是教學向的，就是閑 閱讀全文

摘要： 今天集訓的題我已經寫不動了，下周開始會復習 dp, 現在就提前把一些東西補一補，這個說不好會在之后狀壓里邊用到。 枚舉子集 如何遍歷一個集合的子集 通常我們會采取遞歸的方式，是 \(O(2^n)\) 的，但是這個樣子我們在具體使用的時候是很不方便的，尤其是我們在對于一些二進制的東西做文章的時候。 所 閱讀全文

摘要： 題意 \(N\) 牛 \(M\) 關系，按照編號從小到大，牛依次離開，每一頭牛離開時它認識的牛會互相認識，求最后新增了多少朋友關系。 \(N,M\le 2\times 10^5\) 解法 我們將操作看成每個點邊集合的合并，嘗試使用啟發式合并解決問題。 但是直接做又發現沒有辦法搞，因為我們會算重很多， 閱讀全文