十月雜記
CF
構(gòu)造
CF2154D *1900
想到的：注意到操作二的作用在于限制貓咪能走的邊。但是注意到有一個(gè)問題那就是不能出現(xiàn)兩個(gè)相鄰的第二條指令，也就是說每次移動(dòng)前最多只能刪除一個(gè)點(diǎn)，這是個(gè)問題。那么也就是說在貓移動(dòng)一次后把它接下來可能移動(dòng)到的點(diǎn)刪除。操作次數(shù)的限制很松，所以可以直接任意刪一個(gè)當(dāng)前不可能走到的且不在路徑上的點(diǎn)刪除就行了。不行，這樣不行。重新更換思路，注意到整個(gè)過程類似一個(gè) bfs，每次尋找可能會(huì)走到的最深的點(diǎn)，將這個(gè)點(diǎn) push 入隊(duì)。如果沒有點(diǎn)要 push 說明已經(jīng)走到了樹最深的點(diǎn)。不 bfs 了，觀察發(fā)現(xiàn)這題和奇偶最短路有點(diǎn)關(guān)聯(lián)，即欽定節(jié)點(diǎn) \(0\) 為根，然后樹上拓?fù)鋭h點(diǎn)，對(duì)于每一個(gè)節(jié)點(diǎn)到它的距離，如果和此時(shí)走過的步數(shù)奇偶性是相同的，則進(jìn)行 \(1\) 操作，否則刪掉該點(diǎn)。
數(shù)論
CF2065G *1700
想到的：觀察發(fā)現(xiàn)，\(a_i\) 與 \(a_j\) 的乘積中必然只能包含小于等于兩個(gè)不同的質(zhì)因數(shù)。此時(shí)分討一下：
- 如果只包含一個(gè)，那么 \(a_i\) 與 \(a_j\) 中任意一個(gè)數(shù)的質(zhì)因數(shù)個(gè)數(shù)不能超過 \(2\) 并且必有一個(gè)等于 \(2\)。
- 如果包含兩個(gè)，那么兩個(gè)數(shù)的質(zhì)因數(shù)的指數(shù)只能為 \(1\) 且兩個(gè)數(shù)包含兩個(gè)不同的質(zhì)因數(shù)。
然后組合一下應(yīng)該就行了。
貪心
CF2162E *1600
想到的：考慮進(jìn)行一次操作會(huì)有怎樣的后果。定義一個(gè)數(shù)的貢獻(xiàn) \(f_i\) 表示以 \(i\) 結(jié)尾的回文子串的個(gè)數(shù)。容易貪心的考慮，如果前面的數(shù)中有未出現(xiàn)過的，那么肯定放這個(gè)是最優(yōu)的，因?yàn)樗粫?huì)產(chǎn)生任何貢獻(xiàn)。對(duì)于前面已經(jīng)出現(xiàn)過的數(shù)，新添加的 \(a_i\) 都有可能和其匹配然后變成回文，所以能否用 vector<vector<int>> pos(n) 記錄每一個(gè)數(shù)的下標(biāo)然后貪心的找滿足 \(pos_{x,j}+1\sim i-1\) 是回文的最少的數(shù)，然后添加？發(fā)現(xiàn)往后添加數(shù)的過程中產(chǎn)生的回文數(shù)量取決與之前的數(shù)所可能產(chǎn)生的回文，所以不妨每次都找一個(gè) \(x\) 使得 \(lst_x\) 最小，然后把 \(x\) 添加到末尾，更新 \(lst_x\)。其中 \(lst_x\) 表示 \(x\) 最后出現(xiàn)的位置。
666，結(jié)論對(duì)了。
CF1801B && P13532 *1800
想到的：應(yīng)該是 dp 了。主要是因?yàn)槊看伪仨氋I一個(gè)禮物，所以是由后效性的，不能貪心。注意到最后必然有一個(gè)人取到 \(a\) 和 \(b\) 中的最大值，所以接下來該怎么辦？不對(duì)，不一定是全部的最大值，而是取到的最大值。此時(shí)便有 \(n^2\) 做法了。即枚舉每一個(gè) \(a_i\) 是否成為第一個(gè)人的最大值，然后把所有的滿足 \(a_j\le a_i\) 和 \(b_j\) 取一個(gè)與 \(a_i\) 最接近的數(shù)即可。如何優(yōu)化？可以排序然后搞一下嗎？不用 dp 啊，這不是排序加二分嗎？先搞出每一個(gè) \(a_j\ge a_i\) 的最大 \(b_j\) 然后再按 \(b\) 排序，二分一下就行了。不用按 \(b\) 排序，只需要用一個(gè) multiset 維護(hù)一下，同時(shí)記錄一下當(dāng)前的最大 \(b_i\) 然后如果 \(maxn>a_i\) 就直接算貢獻(xiàn)，否則在 multiset 中二分即可。
細(xì)節(jié)較多，洛谷數(shù)據(jù)好水啊！
CF2151C *1400
想到的：反悔貪心嗎？貪心的考慮，每次都積攢夠 \(k\) 個(gè)人再釋放人。即 \(ans = \sum_{i=1}^{n} a_{i+k}-a_i\)。但可能會(huì)出現(xiàn)下面這種情況，就比如：
式子有一定問題，但不影響理解。或者換一種角度想，題目就是要求兩兩配對(duì) \(a_i\) 使得差值最大，同時(shí)這個(gè)配對(duì)有一定的依賴性，具體來說就是不能連續(xù)選 \(\ge k\) 個(gè)同樣的匹配。哦，轉(zhuǎn)換成染色，就是指黑白染色然后不能有\(\ge k\) 個(gè) \(a_i\) 染相同的顏色，求黑色與白色的差值的最大值，即令黑色最小。
能 dp 嗎？但有 \(n\) 次詢問，怎么辦呢？第一個(gè)詢問是好處理的，現(xiàn)在看怎樣 \(O(1)\) 轉(zhuǎn)移詢問。考慮每次詢問本質(zhì)，即為將一些點(diǎn)顏色互換。完了，成廢物了。貪心的考慮可以把最小的黑色點(diǎn)權(quán)找出，然后優(yōu)化一下便 ok 了。
CF1054D *1900
想到的：考慮異或運(yùn)算的本質(zhì)，即為當(dāng)該位出現(xiàn)的 \(1\) 的個(gè)數(shù)為奇數(shù)時(shí)便不為 \(0\)。能不能 01 trie 呢？貪心的考慮，每次能否令最高位 \(k\) 都變成 \(0\)，然后留幾個(gè) \(1\) 下來？套路的，考慮枚舉每個(gè)子串的右端點(diǎn)，然后進(jìn)行一些判斷。感覺比較想，因?yàn)榭梢蚤_一個(gè)桶記錄前 \(i\) 個(gè)數(shù)的第 \(k\) 位的 \(1\) 的個(gè)數(shù)，然后枚舉到 \(j\) 的第 \(k'\) 位時(shí)只要判斷前面有多少個(gè) \(i'\) 滿足奇偶性相同即可。但怎樣去重以及處理翻轉(zhuǎn)操作呢？
考慮將區(qū)間異或?yàn)?\(0\) 數(shù)量最小化。即區(qū)間內(nèi)所有數(shù)位上的 \(1\) 的個(gè)數(shù)都為偶數(shù)。通過前綴和轉(zhuǎn)換，變成讓每個(gè)前綴相同的數(shù)最少。于是大膽猜結(jié)論，每次都去較少的。
沒想到的：又是正難則反！
ds
CF2138B *1900
想到的：注意到僅使用操作一來達(dá)到目的的操作次數(shù)其實(shí)等同于 \(l\sim r\) 之間逆序?qū)Φ膫€(gè)數(shù)，所以如果使用了操作二后能夠使操作次數(shù)更少僅可能是使逆序?qū)€(gè)數(shù)一次減少一個(gè)以上。手玩發(fā)現(xiàn)，只要出現(xiàn)形如 \(a\cdots b\cdots c\) 且滿足 \(a>b>c\) 的子序列，答案就不會(huì)是 YES。怎么維護(hù)這個(gè)東西呢？考慮先用單調(diào)棧預(yù)處理出對(duì)于每一個(gè) \(b\) 的 \(\min\{c - a + 1\}\)。然后把這些區(qū)間丟到一個(gè) vector 里面去按左端點(diǎn)排序，接著用 \(\operatorname{ST}\) 表去維護(hù)區(qū)間最小右端點(diǎn)。每次查詢時(shí)就是先二分出哪一段區(qū)間滿足 \(l\le a\le r\)，接著在 \(\operatorname{ST}\) 表中查詢最小 \(c\)，如果有 \(c\le r\)，那么顯然滿足上述子序列。
dp
CF2167F *?
CSP 考前最后一天寫的題，帶給我 RP 吧！
想到的：應(yīng)該就是樹形換根 dp 了。先考慮求出以 \(1\) 為根的樹的答案。從 \(1\) 開始 dfs，然后判斷一下 dfs 到的點(diǎn)的子樹大小 \(sz\) 是否滿足 \(sz\ge k\)，如果滿足，就說明可以產(chǎn)生貢獻(xiàn)。現(xiàn)在考慮如何計(jì)算以其它點(diǎn)為根的答案。似乎都不用 dp，直接先欽定 \(1\) 為根，然后 dfs 一遍算出每一個(gè)點(diǎn)的 \(sz\)。接下來直接拆貢獻(xiàn)，考慮每一個(gè)點(diǎn)的父親為誰，然后算一下剩下的節(jié)點(diǎn)數(shù)量是否 \(\ge k\)。注意每一個(gè)點(diǎn)都可以為根。
草，看錯(cuò)題了。哦，只需要再乘上有多少個(gè)點(diǎn)可以為根即可。
CF2153D *1800~~~~
想到的：套路的考慮，斷環(huán)為鏈，然后考慮一些性質(zhì)。發(fā)現(xiàn)操作一定會(huì)把一些連續(xù)的數(shù)變得相同，然后注意到把連續(xù)四個(gè)數(shù)變得相同一定不會(huì)優(yōu)于把連續(xù)三個(gè)數(shù)或兩個(gè)數(shù)變得相同。在此時(shí)考慮線性 dp，轉(zhuǎn)移只有兩種可能，即從前兩個(gè)或前三個(gè)轉(zhuǎn)移而來。設(shè) \(f_i\) 表示考慮完前 \(i\) 個(gè)的最小花費(fèi)，則轉(zhuǎn)移為：
答案有三種可能，即第一個(gè)數(shù)可以從倒數(shù)第二個(gè)、倒數(shù)第一個(gè)和它本身轉(zhuǎn)移而來，取 \(\min\) 即可。不對(duì)，需要二維，記錄一個(gè)從哪里轉(zhuǎn)移而來的即可。
不對(duì)，答案的處理略顯麻煩。怎么搞呢？只有四種情況，都跑一遍即可，大力分討。
沒想到的：可以把分討過程轉(zhuǎn)換成簡單的循環(huán)，然后每次讓 \(a\) 向后移一位。
CF2138C1 *1800
想到的：感覺是讓每一層都放相同的，然后如果放不了了就停止，輸出答案。但為什么 tag 是背包 dp？個(gè)人感覺一個(gè)比較對(duì)的結(jié)論是在前面幾層都放相同的，知道不能放或到達(dá)較淺的層數(shù)后就停止。此時(shí)，就會(huì)出現(xiàn)每一層究竟使用 \(0\) 還是 \(1\) 的問題。這涉及到剩余的 \(0\) 和 \(1\) 的數(shù)量，所以類似一個(gè)背包 dp。
狀態(tài)定義為 \(f_{i, j}\) 表示 dp 完前 \(i\) 層，還剩 \(j\) 個(gè) \(0\) 的可行性，\(sz_i\) 表示第 \(i\) 層的節(jié)點(diǎn)個(gè)數(shù)。
轉(zhuǎn)移為：\(f_{i,j}=\operatorname{OR}f_{i-1,j},f_{i-1, j - sz_i}\)
Luogu
P10842 \(\textcolor{green}{綠}\)
想到的：看到的換根 dp。考慮一個(gè)點(diǎn)為根時(shí)會(huì)和那些鏈產(chǎn)生貢獻(xiàn)，對(duì)于不同的貢獻(xiàn)，記錄一下鏈的個(gè)數(shù)。狀態(tài)的設(shè)計(jì)是何？\(f_u\) 表示以 \(u\) 為根的距離之和，\(g_u\) 表示在以 \(u\) 為根的子樹中有多少條鏈。
第一遍 dfs 的轉(zhuǎn)移如下：
第二遍 dfs（即換根）的轉(zhuǎn)移如下：
AT
abc
427e *?
想到的：套路的，考慮把所有垃圾的移動(dòng)轉(zhuǎn)換成高橋的移動(dòng)。然后這樣就只需要將原來的矩陣擴(kuò)大 9 倍，然后去 bfs 即可。司馬了，還是得正向 bfs，因?yàn)榫哂泻笮浴?/p>
427f *1600
想到的：打表發(fā)現(xiàn)當(dāng) \(n=30\) 時(shí)的狀態(tài)數(shù)大約為 \(2\times 10^6\)，所以考慮 meet in the middle。用四個(gè) map 存一下前一半的狀態(tài)和后一半的狀態(tài)，然后處理一下前一半狀態(tài)的最后一個(gè)數(shù)和后一半狀態(tài)的第一個(gè)數(shù)的情況即可。需要卡一下常，用 unordered_map 過了。
arc
206b *1100
想到的：應(yīng)該要往逆序?qū)Φ姆较蛏先ハ耄紤]一個(gè)數(shù)要往前移，那么必然會(huì)和所有在它前面的并且大于它的數(shù)有互換操作（在這里我們假定每次都從小到大把數(shù)擺好，這樣就避免討論往后操作的情況）。然后就可以這樣建圖，然后考慮把所有邊都刪掉，求最少刪掉的點(diǎn)數(shù)。可是為什么 tag 是二分？現(xiàn)在有一個(gè)線段樹做法，但后面刪點(diǎn)的部分怎么搞。可是這樣建出來的圖的邊數(shù)是 \(n^2\) 的級(jí)別的啊！這樣似乎不是很行。考慮一個(gè)數(shù)在圖里的度數(shù)為前面比它大的數(shù)的個(gè)數(shù)以及后面比它小的數(shù)的個(gè)數(shù)，然后從大到小貪心似乎就有正確性了。怎樣判斷圖完全不連通了？權(quán)值線段樹！勢(shì)能分析復(fù)雜度為 \(O(n\log n)\)，應(yīng)該是對(duì)的吧……第二部分假了……這是一個(gè)二位偏序！666，最長上升子序列是什么鬼。
沒想到的：一個(gè)顯然的結(jié)論，只需要令每一個(gè)顏色的史萊姆都遞增即可。然后因?yàn)橹匦氯旧蟛粫?huì)與其它任何一種顏色有沖突，所以可以不在考慮。接著又是正難則反！！！因?yàn)閷?duì)于每一個(gè)顏色要改變最少一些數(shù)使剩下的為上升序列所以考慮留下最多的。于是變成了最長上升子序列……【我是傻逼】
206c *1500
想到的：容易注意到構(gòu)造出來的數(shù)組中必然不出現(xiàn)兩個(gè)及以上的 \(a_i=i\)。連續(xù)兩個(gè)數(shù)之中必然存在一個(gè) \(a_i \in \{i-1, i+1\}\)，并且如果 \(a_i\notin \{i-1,i+1\}\)，則必然 \(a_{i+1}=a_{i-1}=i\)。Moreover，\(|a_i-i|\le 2\)，且如果出現(xiàn)了一個(gè) \(|a_i-i|=2\)，則其它的數(shù)都必然被確定了。如果全是 -1，則每個(gè)數(shù)都可以 \(|a_i-i|=1 \operatorname{OR} 2\)。那如果有 -1 呢？先判斷一下是否無解，然后進(jìn)行一些計(jì)算。之前的 \(|a_i-i|\le 2\) 是假的，但其它的都是對(duì)的。
接著就是考慮形如 RRRRXLLLL 的構(gòu)造了。但還是腦殘了，總是差一點(diǎn)……
agc
010f
想到的：觀察到如果一個(gè)節(jié)點(diǎn)的點(diǎn)權(quán)比其周圍點(diǎn)權(quán)的和都要小或相等，那么這個(gè)點(diǎn)必然就會(huì)成為必?cái)↑c(diǎn)，因?yàn)橄仁肿卟怀鋈ァＫ韵让杜e每一個(gè)點(diǎn)是否可能成為必勝點(diǎn)，然后 dfs 去遞歸的判斷其周圍的點(diǎn)是否全是比敗點(diǎn)或它自己就是必?cái)↑c(diǎn)，時(shí)間復(fù)雜度 \(O(n^2)\)。哦，需要可行性 dp，典的。有一個(gè)問題，只有如果一個(gè)節(jié)點(diǎn)的點(diǎn)權(quán)比其周圍點(diǎn)權(quán)都要小或相等才行。
成弱智了，剛剛的發(fā)現(xiàn)沒錯(cuò)，所以說每一個(gè)人便只能像比它小的點(diǎn)走，然后每次狀態(tài)都會(huì)翻轉(zhuǎn)，dfs 即可。
::::success[Code]
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using i128 = __int128;
using PII = pair<int, int>;
using PLL = pair<ll, ll>;
constexpr ll inf = (1ll << 62);
constexpr int N = 3000;
int n;
vector<int> a(N), b(N);
vector<vector<int>> G(N);
bool dfs(int u, int fa, int step) {
bool ok = false;
for (auto v : G[u]) {
if (v == fa) continue;
if (b[v] < b[u]) {
bool flag = dfs(v, u, step ^ 1);
ok |= (flag ^ 1);
}
}
return ok;
}
void solve() {
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
u--;
v--;
G[u].push_back(v);
G[v].push_back(u);
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
b[j] = a[j];
}
if (dfs(i, -1, 1)) {
cout << i + 1 << " \n"[i == n - 1];
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
while (t--) {
solve();
}
return 0;
}
::::
模擬賽
s
提高級(jí)
27
a
思路：雙端隊(duì)列模擬即可。
b
思路：并查集判連通性，然后模擬。
c
思路：暴力 dp 題，似乎并不能優(yōu)化，于是 \(O(nk)\) 過了。
d
思路：設(shè) \(dis_{i,j}\) 表示從 \(i\) 到 \(j\) 的最短路長度。對(duì)于每一個(gè) \(i\)，如果上面的奶牛前往 \(j\) 吃草，那么必須滿足如下不等式（\(val_i\) 表示 \(i\) 上草的價(jià)值）：
簡單移項(xiàng)得到：
于是先正常跑一遍 \(\operatorname{dijkstra}\)，然后建分層圖，第二層表示吃了草后的最短路長度，然后對(duì)于每一個(gè)草加一個(gè)點(diǎn)權(quán)即可。
28
傻逼模擬賽，誰愛補(bǔ)誰補(bǔ)去吧。
初二級(jí)
2
a
思路：模擬題。
b
思路：奇偶最短路跑一下就行了。
c
思路：注意到同一天買進(jìn)的物品可以同一天賣出，所以可以轉(zhuǎn)換成在今天早上買了，然后在晚上賣掉。于是便可以把每個(gè)物品的價(jià)值賦值成相鄰兩個(gè)價(jià)值的差，這樣在跑一邊完全背包就可以搞定了。主要還是需要發(fā)現(xiàn)可以這樣轉(zhuǎn)換。
d
思路：注意到重新定義本質(zhì)不同。定義 \(f_u\) 表示以節(jié)點(diǎn) \(u\) 結(jié)尾的合法括號(hào)串的個(gè)數(shù)，一眼得到方程為：
其中 \(v\) 表示上一個(gè)與 \(u\) 匹配的字符。最后樹上前綴和統(tǒng)計(jì)一遍即可。
noip
7
a
這是要我現(xiàn)場(chǎng)學(xué)高斯消元嗎？
補(bǔ)了一下高斯消元，然后直接暴力枚舉前 \(n+2\) 個(gè)然后排除掉枚舉的那個(gè)數(shù)解方程，接著判斷第 \(n+3\) 個(gè)數(shù)是否符合，如果是就直接輸出枚舉的那個(gè)數(shù)。如果全部都枚舉完了，那就輸出第 \(n+3\) 個(gè)數(shù)。
b
板子，不予評(píng)論。
c
只會(huì)暴力……
怎么是堆加可持久化線段樹大法好！觀察到 \(k\) 的范圍很小，所以可以考慮每次都找到原集合中的最大值，然后將這個(gè)最大值刪掉，如此重復(fù) \(k\) 次即可。現(xiàn)在考慮如何維護(hù)該最大值，套路的，考慮維護(hù)以每個(gè)位置作為左端點(diǎn)連續(xù)子串的最大值，但是如何推廣到每一個(gè)位置上呢？可以使用一個(gè) \(nxt_i\) 表示 \(a_i\) 在 \(i\) 后出現(xiàn)的第一個(gè)位置，然后觀察到，每次往后移動(dòng)一位就相當(dāng)于把 \((i,nxt_i)\) 這段區(qū)間的貢獻(xiàn)都減掉 \(a_i\)，并且把 \(a_i\) 變?yōu)闊o窮小，于是考慮可持久化線段樹維護(hù)。由于需要區(qū)間修改，所以要標(biāo)記永久化。于是拿個(gè)大根堆記錄。
8
a
一眼狀壓，然后怎么讓我 \(4^n\) 過了。還得是跑不滿……
b
確乎是 dsu on tree 了。套路的，考慮維護(hù)每個(gè)節(jié)點(diǎn)到根節(jié)點(diǎn)的距離長度 \(val_u\) 以及每個(gè)點(diǎn)的深度，然后距離為 \(k\) 的點(diǎn)對(duì)便可以直接判 \(val_u+val_v-2*val_{root}\) 是否等于 \(k\) 即可。接著一個(gè)全局的 map 表示在值為 \(x\) 的情況下最小的節(jié)點(diǎn)的深度的編號(hào)。跑完所有輕子節(jié)點(diǎn)的答案后就 map.clear()，重子節(jié)點(diǎn)則直接繼承，最后統(tǒng)計(jì)該子樹的答案即可。放個(gè)代碼吧，想和寫花了兩個(gè)半小時(shí)。
::::success[Code]
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using i128 = __int128;
using PII = pair<int, int>;
using PLL = pair<ll, ll>;
constexpr ll inf = (1ll << 62);
constexpr int N = 2e5 + 10;
int n, k;
ll cnt = 0;
vector<int> depth(N), sz(N), son(N, -1), ans(N, INT_MAX);
vector<ll> val(N);
vector<vector<PII>> G(N);
map<ll, int> tot;
void dfs1(int u, int fa) {
sz[u] = 1;
depth[u] = (fa == -1 ? 0 : depth[fa]) + 1;
for (auto [v, w] : G[u]) {
if (v == fa) continue;
val[v] = val[u] + w;
dfs1(v, u);
sz[u] += sz[v];
if (son[u] == -1 || sz[son[u]] < sz[v]) {
son[u] = v;
}
}
}
int calc(int u, int fa, int root) {
int res = INT_MAX;
if (tot.count(k + 2 * val[root] - val[u])) {
res = min(res, depth[tot[k + 2 * val[root] - val[u]]] + depth[u] - 2 * depth[root]);
}
for (auto [v, w] : G[u]) {
if (v == fa) continue;
res = min(res, calc(v, u, root));
}
return res;
}
void add(int u, int fa) {
if (!tot.count(val[u])) tot[val[u]] = u;
else if (depth[tot[val[u]]] > depth[u]) tot[val[u]] = u;
for (auto [v, w] : G[u]) {
if (v == fa) continue;
add(v, u);
}
}
void dfs2(int u, int fa) {
int res = INT_MAX;
for (auto [v, w] : G[u]) {
if (v == fa || v == son[u]) continue;
dfs2(v, u);
tot.clear();
res = min(res, ans[v]);
}
if (son[u] != -1) {
dfs2(son[u], u);
res = min(res, ans[son[u]]);
}
if (!tot.count(val[u])) tot[val[u]] = u;
else if (depth[tot[val[u]]] > depth[u]) tot[val[u]] = u;
if (tot.count(k + 2 * val[u] - val[u])) {
res = min(res, depth[tot[k + 2 * val[u] - val[u]]] + depth[u] - 2 * depth[u]);
}
for (auto [v, w] : G[u]) {
if (v == fa || v == son[u]) continue;
res = min(res, calc(v, u, u));
add(v, u);
}
ans[u] = res;
}
void solve() {
cin >> n >> k;
for (int i = 1; i < n; i++) {
int u, v, w;
cin >> u >> v >> w;
G[u].push_back({v, w});
G[v].push_back({u, w});
}
dfs1(0, -1);
dfs2(0, -1);
int res = INT_MAX;
for (int i = 0; i < n; i++) {
res = min(res, ans[i]);
// cout << ans[i] << " \n"[i == n - 1];
}
if (res == INT_MAX) {
cout << "-1\n";
} else {
cout << res << "\n";
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
while (t--) {
solve();
}
return 0;
}
::::
c
瞪出來答案具有單調(diào)性，所以可以直接二分答案，check 是好實(shí)現(xiàn)的，只需要哈希加個(gè) map 就行了。
9
a
思路：怒了，耗費(fèi)了一個(gè)小時(shí)，貪心地考慮，讓除了第二個(gè)數(shù)的其它數(shù)都相乘，然后判斷能否整除第二個(gè)數(shù)即可。
b
思路：正解上下界網(wǎng)絡(luò)流，但亂搞可過。每次找到 DAG 中的最長鏈，然后將其刪除，看可以刪除幾次。
c
思路：注意到若:
則：
所以，只需要維護(hù)每個(gè)質(zhì)因數(shù)出現(xiàn)的個(gè)數(shù)即可。
10
a
思路：水題。
b
思路：把所有的 Baka 數(shù)打表打出來并且去掉倍數(shù)關(guān)系后發(fā)現(xiàn)只有 \(466\) 個(gè)。同時(shí)注意到第七個(gè)數(shù)就已經(jīng)超過 \(1000\) 了，所以可以前六個(gè)數(shù)容斥，后面的數(shù)直接類似調(diào)和級(jí)數(shù)暴力碾過去就 ok 了。細(xì)節(jié)是調(diào)和級(jí)數(shù)那里篩出來的數(shù)不能被前六個(gè)整除。
c
思路：旋轉(zhuǎn)卡殼題，不予評(píng)論。
12
a
思路：見到異或想到的第一眼便是 \(01\operatorname{Trie}\) 拆位，但是在經(jīng)過思考以后我們發(fā)現(xiàn)并不可行，不過拆位這個(gè)思想或許仍然用的上。如果不用管 \(x\) 可以怎么做？考慮一個(gè)比較典的貪心，即從高到低去枚舉每一個(gè)數(shù)的二進(jìn)制位，盡可能的滿足該位為 \(1\)，然后可以得到一個(gè)滿足該條件的數(shù)的集合 \(S\)，下一位的枚舉只需在 \(S\) 找滿足的數(shù)即可。但是怎樣把這個(gè) \(S\) 找出來呢？觀察到如果 \(a\) 中的一堆數(shù)的二進(jìn)制中的某一位相同，則這堆數(shù)一定在同一個(gè)區(qū)間內(nèi)，即 \([0, 2^k-1]\) 或者 \([2^k, 2^{k+1}-1]\)。于是我們只需要判斷 \([l,r]\) 中有沒有數(shù)在這段區(qū)間中就行了。如果沒有就說明這一位只能是 \(0\)。
發(fā)現(xiàn)這是好維護(hù)的，因?yàn)?\(a_i\le 10^5\)，所以直接上主席樹就行了。那如果把 \(x\) 考慮在內(nèi)呢？簡單的，只需要把查詢時(shí)的 \([0, 2^k-1]\) 或者 \([2^k, 2^{k+1}-1]\) 改成 \([\max(0, 0 - x), \max(0,2^k-1 - x)]\) 或者 \([\max(0, 2^k), \max(0, 2^{k+1}-1)]\) 就行了。
::::success[Code]
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using i128 = __int128;
using PII = pair<int, int>;
using PLL = pair<ll, ll>;
constexpr int N = 3e5 + 10;
int n, m, tot;
vector<int> a(N), root(N);
struct Node {
int l, r, val;
} tree[N << 5];
void pushup(int p) {
tree[p].val = tree[tree[p].l].val + tree[tree[p].r].val;
}
int build(int l, int r, int k, int p) {
tree[++tot] = tree[p];
p = tot;
if (l == r) {
tree[p].val++;
return p;
}
int mid = l + r >> 1;
if (k <= mid) tree[p].l = build(l, mid, k, tree[p].l);
else tree[p].r = build(mid + 1, r, k, tree[p].r);
pushup(p);
return p;
}
int query(int l, int r, int x, int y, int p1, int p2) {
if (x <= l && r <= y) return tree[p2].val - tree[p1].val;
int mid = l + r >> 1, ans = 0;
if (x <= mid) ans += query(l, mid, x, y, tree[p1].l, tree[p2].l);
if (mid < y) ans += query(mid + 1, r, x, y, tree[p1].r, tree[p2].r);
return ans;
}
void solve() {
tree[0] = {0, 0, 0};
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
for (int i = 1; i <= n; i++) {
root[i] = build(0, 3e5, a[i], root[i - 1]);
}
while (m--) {
int b, x, l, r;
cin >> b >> x >> l >> r;
int ans = 0, cnt = 0;
for (int i = 17; i >= 0; i--) {
if (!((1 << i) & b)) {
int xx = max(0, cnt + (1 << i) - x), yy = max(0, cnt + (1 << i + 1) - 1 - x);
int num = query(0, 3e5, xx, yy, root[l - 1], root[r]);
if (num) {
cnt += 1 << i;
ans += 1 << i;
}
} else {
int xx = max(0, cnt - x), yy = max(0, cnt + (1 << i) - 1 - x);
int num = query(0, 3e5, xx, yy, root[l - 1], root[r]);
if (num) {
ans += 1 << i;
} else {
cnt += 1 << i;
}
}
}
cout << ans << "\n";
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t = 1;
while (t--) {
solve();
}
return 0;
}
::::
b
思路：神秘樹形 dp。考慮在 dfs 過程中枚舉一個(gè)葉子節(jié)點(diǎn)的祖先的狀態(tài)，然后從下往上類似背包的合并。由主定理，這東西不會(huì) TLE……
c
思路：樹鏈剖分，還沒補(bǔ)。
14
a
思路：拼好題，樹的直徑加個(gè)單調(diào)隊(duì)列就行了。
浙公網(wǎng)安備 33010602011771號(hào)