zhangxyhp

摘要： 問題顯然可以分為兩部分：\(u\) 的子樹內和 \(fa_u\) 到 \(v\) 的鏈上。前者需要樹上背包，后者需要取 \(\max\)。 考慮用線段樹維護這兩個值。子樹內的答案只需要一次區間查詢，再加上樹上背包的 \(O(m^2)\)，總共為 \(O(m^2\log n)\)。鏈上的答案需要進行樹 閱讀全文

摘要： A. Min-Fund Prison (Medium) 考慮一個邊雙連通分量一定不可能分為合法的兩部分，于是進行縮點。縮完后顯然是一個森林。 設 \(dp_{i,j,0/1}\) 表示第一堆有 \(i\) 個點，第二堆有 \(j\) 個點，兩堆點有沒有用一條邊連起來的最小花費。對于每棵樹，考慮將它加 閱讀全文

摘要： A. 牛場圍欄 首先判斷 -1 的情況。 如果可用的長度中有 \(1\)，那么所有長度都能拼出來。 如果所有可用長度的 \(gcd\) 不為 \(1\)，那一定沒有最大值。 證明：設 \(gcd\) 為 \(q\)，則 \(q\mid x_1a_1+x_2a_2+\dots+x_na_n,x_1,x 閱讀全文

摘要： 簡單手摸后發現，答案就是這么一個式子： \( (3^{n-1}-3^{n-2})a_1+(3^{n-2}-3^{n-3})a_1a_2+\dots+(3^1-3^0)a_1a_2\dots a_{n-1}+a_1a_2\dots a_n \) 啊當然證明也是好證的，對于 \(a_1\) 這一項，它后 閱讀全文

摘要： A. 「SDOI2014」旅行 給每個宗教開一棵線段樹，樹剖 \(+\) 線段樹單點修改區間查詢即可。需要動態開點。 Code #include<bits/stdc++.h> #define ll long long #define il inline #define read(x){\ char 閱讀全文

摘要： A. 「NOIP2009」靶形數獨 暴搜。 本著搜索必剪枝的思想，略微做一點優化：優先搜索 \(0\) 少的行。 然后就搜就行。 Code #include<bits/stdc++.h> #define ll long long #define il inline using namespace s 閱讀全文

摘要： A. Arpa's weak amphitheater and Mehrdad's valuable Hoses 用并查集將每個朋友圈找出，然后 DP。 設 \(dp_{i,j}\) 表示前 \(i\) 個朋友圈，重量為 \(j\) 的最大美麗度。轉移分為從這個朋友圈中選一個轉移、用這個朋友圈的和轉 閱讀全文

摘要： 前言 本來早就該學笛卡爾樹了，但暑假打模擬賽就一直沒學成。于是就打算先不學了，結果又發現后面有個笛卡爾樹專題，只好來學學。 定義 笛卡爾樹是一棵二叉樹，每個點有一個鍵和一個值，鍵滿足堆的性質，值滿足二叉搜索樹的性質。沒錯當鍵隨機時，這就是個 Treap。 建樹 如果值單調遞增，那么就可以線性建樹。具 閱讀全文

摘要： 記 \(f(x)\) 為最小的大于 \(x\) 的 \(y\)，使得 \(x\) 是 \(y\) 的子串。易得： \[f(x)=\min(10x,x+10^{|x|}) \]其中 \(|x|\) 表示 \(x\) 的位數。 可以發現，\(f(x)\) 為一個嚴格單調遞增的函數。 考慮貪心策略，顯然選 閱讀全文

摘要： 注：題解中 \(\operatorname{lsh}\)，\(\operatorname{rsh}\)，\(\operatorname{or}\) 分別表示按位左移、按位右移、按位或，即 c++ 語言中的 <<，>>，|。 我也是打上輪廓線 DP 了。 設 \(f_{x,y,S}\) 表示當前在 \ 閱讀全文