Code_Kingdom

摘要： 設狀態時，首先從簡單狀態設起： 一維不行再試二維、簡單狀態應付不了再設復雜的（因為某些狀態可以體現在狀態轉移的過程中，或者說狀態轉移方程中，不一定體現在原式中） E.g. 計算機軟件能力認證考試系統-校門外的樹 我：一開始設狀態想的是$f[i][j][k]$代表 \(i\) 到 \(j\)，化為 \ 閱讀全文

摘要： `#include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define MX Maxn + 5 閱讀全文

摘要： Description: 給你2個長度為n的01串 從中選出$n/2$個,使得選出的數中第一排1的個數等于未選出數中第二排1的個數 輸出一種方案即可,沒有輸出 1 Hint: $n \le 5000$ Solution: 這題比賽的時候傻逼了 后面發現其實就是暴力枚舉解方程 $AuBao$想出一個O 閱讀全文

摘要： Description: 給你n首歌,每首歌有一個長度$a_i$和美麗度$b_i$ 現在可以選出最多k首,動聽值為$\sum a_i min_{\sum b_i}$ Hint: $n \le 10^5$ Solution: 只想到了線段樹做法,比較麻煩,比賽時沒調出來 %%%$Na_2S_2O_3$ 閱讀全文

摘要： Description: 給定一棵樹,每次詢問某點子樹中到其不超過k的所有點的最小點權 強制在線 Hint: $n,m\le 10^5$ Solution: 看到題目第一反應是以深度為下標,dfs序為版本建樹 然而不行,因為min不滿足前綴可減 所以我們換過來,每個$dep$建樹表示$ includ 閱讀全文

摘要： Description: 給你一個序列,每個數可能變化為另一個數,每次最多有一個數變化 求最長的子序列,無論如何變化,這個子序列都不下降 Hint: $n \le 10^5$ Solution: 沒想到是dp 設f[i]表示以i結尾的最長長度,有: $$f[i]=f[j]+1$$ $$當max_j 閱讀全文

摘要： Description: A 國正在開展一項偉大的計劃 —— 國旗計劃。這項計劃的內容是邊防戰士手舉國旗環繞邊境線奔襲一圈。這項計劃需要多名邊防戰士以接力的形式共同完成，為此，國土安全局已經挑選了 $N$ 名優秀的邊防戰上作為這項計劃的候選人。 A 國幅員遼闊，邊境線上設有 $M$ 個邊防站，順時針 閱讀全文

摘要： Description: 給你一個n m的網格,每個格子有一個數字,每行每列只能選一個數字,問所選數字中第k大的數字的最小值是多少 Hint: $n \le 250$ Solution: 顯然是二分圖模型,但是有附加條件 初看十分不可做,主要原因是這個第k大 我們可以考慮二分一個答案,只對小于這個答 閱讀全文

摘要： 1.Tree Description: 求一棵樹中長度不超過$K$的路徑條數 Solution: 直接統計深度,由于深度的貢獻具有單調性 考慮每次統計答案時先排序,然后雙指針每次相減 這樣就比$n^2$統計優秀多了,記得要減掉算重的 2.[模版]點分治1 Description: 求一棵樹中是否存在 閱讀全文

摘要： Description: 給你一棵樹,每個點有權值,你可以修改一些點的權值使得: 1.每個點權值等于子節點權值的和 2.每個點的所有子節點權值相等 Hint: $n \le 2 10^6$ Solution: 比較巧妙的題 首先有一個很顯然的規律: 當一個點權值確定,整棵樹就確定了 (為什么這么顯然 閱讀全文