題號題目描述解題思路

3306	給出一棵帶點權的有根樹,支持單點修改,換根,詢問x子樹中的權值最小值.	直接在DFS序上用線段樹維護就好了.
3900	給出n個數對,求最小的交換次數,滿足交換后每個數對相差不超過c	壓位,用\(f[i]\)表示\(i\)狀態的數對滿足條件的最小操作次數,初始時\(f[i]\)如果有解,那么答案至少為操作數對-1,然后\(f[i]=min(f[j]+f[i\text{^}j])\)修正一下就好了.
3901	給定一個\(n*n\)的棋盤(\(n\)為奇數),每個格子上有數,設\(X=(n+1)/2\),每次可以將一個\(X*X\)的子棋盤的所有數乘-1,求所有數之和的最大值.	考慮不管子棋盤怎么選,X行X列一定有數會被選上,考慮\(a[1][i],a[1][X],a[1][i+X]\)的關系,發現他們是否被操作的異或值一定為0,因為任意的操作只會包含他們三個點中的其中兩個或零個,然后其他行以及列也有這種關系,枚舉X行前X個格子的操作情況,得出X行的情況,然后每一行第X列的情況枚舉前\(i\)個格子的情況,顯然這個貢獻單獨考慮,所以刷個最大值就行.復雜度\(O(2^XX^2)\)
3920	給出一個長度為\(n\)的序列,詢問一個區間數字出現次數第\(k1\)小的第\(k2\)小的數.	分塊套分塊?神奇的叫法. 把(數字,數字出現次數)看成一個二元組,二元組的個數為\(n\),然后我們用莫隊維護這個二元組即可,首先數字出現次數一個分塊,然后相同出現次數的數用個分塊.
3689	給出\(n\)個數,兩兩異或可以得到\(n*(n-1)/2\)個值,求前\(k\)小的值.	額,對于每個數肯定先找第一小然后第二小... 用個堆維護一下每個數當前的最小異或值,查詢一個數第\(k\)小異或值一棵字典樹就行.
4011	給出一張有向無環圖和一條任意邊,求以\(1\)為根的外向樹的個數.	根據朱劉算法(???),有向無環圖的外向樹個數為除根以外所有點入度的乘積.感覺腦補一下就行,每個點隨便選個fa就可以形成一棵樹...現在多了一條邊,那么減去成環的方案數就行.成環的方案數應該是\(\sum\)所有\(y\)->\(x\)的路徑(設為\(S\))\(\prod_{x\not\in S}dgree[x]\),在拓撲序上DP就行.

轉載于:https://www.cnblogs.com/CHNJZ/p/10435201.html

總結

以上是生活随笔為你收集整理的BZOJ水题计划的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。