BaiBaiShaFeng's Blog :D

摘要： 之前寫過一篇介紹同余最短路的文章，其實寫的蠻爛得，鴿了這道題好久，今天中午好不容易算是做出來了。 題意 給定一個 \(K\)，求出來 \(V=xk\)(\(x\) 為正整數)，使得這個 \(V\) 的各數位和是最小的。 這個 \(K\) 的級別是 1e5 的。 做法 我們發現直接去具體搞明白到底是哪 閱讀全文

摘要： 一道很有意思的貪心題，似乎noi導刊上有？記不太清了，反正是做出來了。 題意 有一個橋，一個火把，一堆人。 這對人要過橋，過橋有一些條件。 需要過橋的人有火把 不可同時過兩個以上 每次過橋的花費時間是兩人中花費最高的那位。 詢問最小的過橋花費。 注意，火把是必須有人帶回的，這個火把不能憑空傳送。 解 閱讀全文

摘要： 題意 給定一個 \(n\), 構造長度為 \(n\) 的序列，使得和為 0，乘積為 \(n\)。 解答 我們考慮 \(n\) 的性質，發現 \(0\) 是一個偶數，如果序列中沒有偶數，作為一對奇數乘積的 \(n\) 自然也會是奇數，奇數個奇數整不出來偶數。 所以肯定是有偶數的。 抓著這一點下手，我們 閱讀全文

摘要： 巳時，閑來無事，學分數規劃至正午，忽覺無用，遂大悲，閱洛谷題庫以尋題，欽四五題以切，遇此好題。 題意。 一棵 \(N\) 個點的樹，點權不是 0 就是 1。 我們有一個神秘的操作，我們先選擇一個點，把它和所有的相鄰點權都取反。 詢問最小的操作次數，使得所有的點權最后都為 0。 \(N\) 是 \(1 閱讀全文

摘要： 關于這個技巧我甚至都記不清是什么時候學的了，反正就是很早很早之前，當時學了之后看什么子樹查詢都想上 Dsu On Tree，后來也沒怎么寫過了，不過這個東西確確實實很強勁。 今天寫了一上午教練的題單，大概獲得了三天的時間來寫自己想寫的，就去寫寫各種莫隊吧。 結果寫到一個樹上莫隊，突然想使用這個東西， 閱讀全文

摘要： 今天又一次碰到了這個問題，上一次是 [ZJOI2008] 騎士，這一次是 城市環路。 記錄一下這個問題怎么搞。 我們選擇把這個問題轉化為在一棵正常的樹上邊做正常的最大獨立集，同時有環上的兩個相鄰點 \(S,T\) 被規定不能選擇相同的。 我們斷掉 \(S,T\) 之間這一條邊，選擇在 \(S,T\) 閱讀全文

摘要： Rope 真的是一個非常好用的東西，在非常多的平衡樹的題目中可以起到意想不到的作用。 聲明 對于 pbds 里邊的很多神秘東西我總是忘記怎么定義。 這個東西并沒有被包含到萬能頭里邊，我們需要再加上萬能 Stl 擴展庫 #include <bits/extc++.h> 這個東西同樣需要 using n 閱讀全文

摘要： 講個笑話，這道題目我本來是在掃描線的題目里邊找到的，但我的方法跟掃描線沒有任何關系。 題意不多說了。 發現題目諧音單調棧，但是并沒有什么幫助，因為題干在描述的不就是一個單調棧嘛？ 不可否定的，對于 \([L,R]\)，一個個位置 \(A[L]\) 一定是成功的。 我們只需要判斷什么時候會把 \(A[ 閱讀全文

摘要： P4857 [PA 2013] Konduktorzy 一道浪費了我半個下午的題，我否認這是一道綠題，看了題解還是一知半解，最后瘋狂思考想明白了。 題意略，以后都不放了。 我們該怎么做呢。 加入這個 \(n\) 小一些的話用一個優先隊列模擬就可以，但是這個 \(n\) 出奇的大，讓我們不知道該怎么辦 閱讀全文

摘要： 題意 給定正整數 \(N, L\) 和一個長度為 \(N\) 的正整數序列 \(A = (A_1, A_2, \dots, A_N)\)。 對于 \(i = 1, 2, \dots, N\)，請回答以下問題： 是否存在一個長度為 \(L\) 的非負整數序列 \(B = (B_1, B_2, \dot 閱讀全文