近期刷题总结[2019 03 09]
目錄
尋找段落?[分數規劃+單調隊列]
P4319 變化的道路?[LCT + 線段樹分治]
P2485 [SDOI2011]計算器?[exgcd, bsgs] [模板]
P4458 [BJOI2018]鏈上二次求和?[線段樹][二次前綴和]
嚴格次小生成樹?[最小生成樹+倍增]
P2120 [ZJOI2007]倉庫建設?[斜率優化板子]
P2155 [SDOI2008]沙拉公主的困惑?[推式子]
P4559 [JSOI2018]列隊?[主席樹]
P4139 上帝與集合的正確用法?[擴展歐拉定理]
[SCOI2015]國旗計劃?[倍增]
[SCOI2015]小凸玩矩陣?[二分+網絡流] [算網絡流模板吧]
P3165 [CQOI2014]排序機械臂?[Splay]
[BJOI2014]大融合?[樹剖 / 線段樹分治+并查集 / LCT]
[BJOI2012]算不出的等式?[直接打表]
[BJOI2012]最多的方案?[DP]
[BJOI2012]連連看?[費用流板子吧]
尋找段落?[分數規劃+單調隊列]
首先二分一個mid, 找是否存在長度為l--r之間的一段使??
轉化為前綴和來看就可以單調隊列維護了
?
P4319 變化的道路?[LCT + 線段樹分治]
對于每個道路出現的時間li, ri, 插入線段樹的這個區間,? 然后就是線段樹分治
這里補充一下, 就是先將根中有的做一遍, 然后遞歸左右兒子(這是根上面的信息還在)
最后清除該子樹的信息(因為遞歸它父親的另一個兒子不能有它的信息) , 然后就是LCT 動態維護最小生成樹
?
P2485 [SDOI2011]計算器?[exgcd, bsgs] [模板]
復習一下bsgs, 找??? 相當于是???也就是?
然后m取sqrt(p), 將b^j插入map, 枚舉i就可以了
?
P4458 [BJOI2018]鏈上二次求和?[線段樹][二次前綴和]
首先將詢問改為前綴和模式, 對前綴和再求一個前綴和
然后考慮修改對哪些有影響, 要討論 l<=i<=r, 和i>r兩種情況討論
巨神博客https://blog.csdn.net/dreaming__ldx/article/details/85735495
?
嚴格次小生成樹?[最小生成樹+倍增]
先求最小生成樹, 然后枚舉沒在樹上的邊, 用它去替換環上的最大, 因為是嚴格次小, 所以要維護最大和次大
不帶修就倍增解決
?
P2120 [ZJOI2007]倉庫建設?[斜率優化板子]
?
P2155 [SDOI2008]沙拉公主的困惑?[推式子]
非常巧妙啊
?
因為? ?, 而n! 可以分為 n! / m! 段
所以??
預處理后面那個就可以了, n!, 及逆元就可以了
?
P4559 [JSOI2018]列隊?[主席樹]
很明顯有一個界點, 前面的到界點前, 貢獻是l -- 界點的和 - 界點前的位置之和, 后面就反過來
因為詢問原序列的l-r, 需要將l-r的區間搞出來, 所以就主席樹了
?
P4139 上帝與集合的正確用法?[擴展歐拉定理]
令?, 然后遞歸求解
?
[SCOI2015]國旗計劃?[倍增]
倍增的思想巧妙啊, 預處理往后跳2^i個最遠跳到多少就可以了
?
[SCOI2015]小凸玩矩陣?[二分+網絡流] [算網絡流模板吧]
?
P3165 [CQOI2014]排序機械臂?[Splay]
我們可以先排序, 然后將哪個點splay到根, 有兒子的siz就是第幾個
然后就是splay區間翻轉了
?
[BJOI2014]大融合?[樹剖 / 線段樹分治+并查集 / LCT]
樹剖: 先離線, 然后每次刪一條邊, 子樹就沒了, 就是子樹修改, 然后每次跳到最近的斷的地方fa, 答案就是siz * (fa-siz)
LCT : LCT 維護子樹大小, 可以用Splay維護實鏈大小, siz維護虛邊的大小, access時更新(雖然我不會)
線段樹分治+并查集 : 考慮暴力, 每次詢問可以將前面所有的重新插入并查集(除了那條邊), 發現每一條都有一個出現時間的范圍, 然后就是線段樹分治
?
[BJOI2012]算不出的等式?[直接打表]
?
[BJOI2012]最多的方案?[DP]
既然我們不能直接背包, 那能不能先找到一種分解, 然后來換呢, 十分巧妙
?
[BJOI2012]連連看?[費用流板子吧]
總結
以上是生活随笔為你收集整理的近期刷题总结[2019 03 09]的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： shell获取目录的上级目录_Shell
- 下一篇： 安装系统时出现“ 计算机意外地重新启动或