嘎嘎喵

摘要： \(\mathcal{Preface}\) 分數(shù)分布：\(100+100+100+100= 400\)。 AK 了，開心呀！ \(\mathcal{Problem \space{} A}\) Tag：詐騙，排序，貪心。 賽時看到題，一下子沒反應(yīng)過來，以為是超難 DP 題。 過了 B & C 之后回過 閱讀全文

摘要： 比賽鏈接：https://vjudge.net/contest/751527。 題這么多，我這總結(jié)該寫到什么時候啊。 A - 二叉樹深度 根本算不上樹形 DP，只是一個簡單的 DFS 深搜遍歷。 由于題目已經(jīng)固定根節(jié)點編號為 \(1\)，所以從 \(1\) 出發(fā) DFS 即可。分別算出每個節(jié)點的 \ 閱讀全文

摘要： 比賽鏈接：https://vjudge.net/contest/750011。 A - 煩人的數(shù)學作業(yè) 是計算數(shù)位上數(shù)字和類型的數(shù)位 DP。 定義 \(dp_{x,y,k}\) 表示當前的上界標記是 \(x\)，前導(dǎo)零標記是 \(y\)，并且當前枚舉到第 \(k\) 位。 為了讓后續(xù)轉(zhuǎn)移更加便捷，需 閱讀全文

摘要： 本文章同步發(fā)表在洛谷博客。 什么是根號分治？ 根號分治。聽起來好像是一個很高級的什么遞歸做法，但實質(zhì)上。它，只是一個暴力縫合怪而已。僅此而已。 根號分治很簡單的。其實，就是解決一個題目有兩種暴力方法，第一種方法的時間復(fù)雜度是 \(O(k)\)，第二種方法的時間復(fù)雜度則是 \(O(n \div k)\ 閱讀全文

摘要： 本篇文章同步發(fā)表在洛谷博客。 字典樹 什么是字典樹？ 字典樹，顧名思義它是一棵類似于字典的樹，用樹的形態(tài)存儲字符串集合。具體地，它有一個自定義的無意義的根節(jié)點（通常編號為 \(0\) 或 \(1\)），所有存儲進去的字符串都可以順著根節(jié)點從某條固定的路線往下走并連接頂點上的所有字母得到。 字典樹的插 閱讀全文

摘要： 比賽鏈接：https://vjudge.net/contest/748191。 致敬逆天場之所有題的首 A 都是我的。 A - 互不侵犯 最最最最最最最板子的狀壓 DP。 大概就是一行一行去弄。然后的話，DP 維護三個量，當前遍歷到第 \(i\) 行，目前總共放了 \(j\) 個國王，以及這一行的放 閱讀全文

摘要： 9.2 P11619 種南瓜 Tag：線段樹分治，線段樹。 犯的錯誤有： stack 中使用的數(shù)據(jù)類型為 int 而非 long long 導(dǎo)致極大值變化，進一步導(dǎo)致答案錯誤。 存邊集的 vector 的大小沒有 \(\times 8\) 導(dǎo)致數(shù)組訪問越界。 之后在 RE 的情況下一定要檢查到位所有 閱讀全文

摘要： 本文章同步發(fā)表在洛谷博客。 CDQ 好強，拜謝 CDQ /bx CDQ 是我教練的學姐喵！ 什么是 CDQ 分治？ CDQ 分治一般用于求解偏序問題，二維偏序問題一般可以不使用 CDQ 分治而用普通分治或樹狀數(shù)組輕松解決，三維偏序問題 CDQ 分治是最佳選擇，而四維偏序問題就需要 CDQ 套 CDQ 閱讀全文

摘要： 本文章同步發(fā)表在洛谷博客。 什么是博弈 DP？ 博弈，是一個多名玩家參與的競爭游戲。每次只允許一個人行動，并且通常采用輪流行動的方式。 每個人的目標都是在游戲中獲勝，并且題目一般會假定所有人都足夠聰明，都會采用最優(yōu)策略。 一般的獲勝或者失敗條件，可能是分數(shù)達到一定值（或者最大或者最小），也可能是運轉(zhuǎn) 閱讀全文

摘要： 什么是倍增？ 倍增？倍增？倍增！ 之前學了最近公共祖先 LCA，其是倍增的子問題。 倍增是什么，什么是倍增？倍增，顧名思義，就是一倍兩倍往上增。其實上，就是一步跳 \(2^k\)，可把速度從 \(O(n)\) 直降到 \(O(\log n)\)，是一個非常 nice 的算法。 ST 表！ ST 表？ 閱讀全文