五個題目池
由于看了某些學長的學習策略視頻，某些人也要開始放仿造了qwq
五大題目池
1. 好題但還未篩選
2. 篩選完適合我，但是未看題解+按自己的想法來描述題解
- CF53E Dead Ends
- CF351C Jeff and Brackets
- CF442D Adam and Tree
- CF258D Little Elephant and Broken Sorting
- CF115E Linear Kingdom Races
3. 不想啃了，過
- Tree Decorations
- 基礎寄術練習題
- 建造軍營II
- Biconnected Graph
- 清明
- Mizuyokan 2
- Card Collection
- Security Guard
- Organizing a Race
- Mind Bloom
- Lisa's Sequences
- 三染色
- Bugaboo
- Colorful Star
- Attraction on Tree
- All the Same
4. 寫完題解準備來打代碼
-
-
考慮枚舉 \(x,y\) 的 LCA，計算所有 \(LCA(x,y)=z\) 的 \(dist(x,y)\) 之和。不妨設 \(x\) 在 \(z\) 的左子樹內，\(y\) 在 \(z\) 的右子樹內\(（y\not=z）\)，則 \(x→y\) 的路徑一定形如 \(x?a→b?y\)，其中 \(a\) 是 \(z\) 的祖先，\(b\) 在 \(y\) 的子樹內，三段路徑的形態分別形如：
- \(x?a\) 是一條由 \(x\) 只經過第一類邊到達 \(a\) 的路徑。顯然此時一定不會去走第二類邊。
- \(a→b\) 是一條二類邊。
- \(b?y\) 是若干條一類邊和二類邊。
-
進一步發現，對于一個確定的 \(y\)，左側的每個 \(x\) 到他要選擇的這一條二類邊 \(a→b\) 都是一樣的。因此只需要在右側跑 \(dijkstra\)，算出 \(a→b?y\) 這部分的貢獻，再直接累加上 \(x?a\) 部分的貢獻即可。
-
-
- 無窮條邊，暴力 Kruskal 肯定不行。 每兩點之間的邊都取個 min 值，但是還是 \(O(n^2)\) 的，如果我們能把一些沒用用的邊去掉或者是把一些邊改一下兩端的點，那么復雜度就降低了。開始考慮改邊，如果 \(x\) 和 \(y\) 已經聯通，那么現在有一條邊 \(x\) 和 \(z\)，可以改成 \(y\) 和 \(z\)。因為 \(a_i\) 和 \(b_i\) 在 \(a_i\) 和 \(b_{i+1}\) 前面已經出現過了, 那么 \(a_i\) 和 \(b_{i+1}\) 就可以改成 \(b_i\) 和 \(b_{i+1}\) 了！所以這變成了一條鏈,那么就可以用一個前綴和來做,然后跑 \(Kruskal\) 就好了
-
- 顯然一個數如果被操作多次，只有最后一次有用。那么每個元素有三種情況：最后一次在放在開頭，最后一次放到末尾，未操作過。前兩種操作對應 a 的前綴后綴，中間剩余的元素必須是升序的。假設前綴有 x 個元素，后綴有 y 個元素，計數時先給每個操作劃分到元素中，非最后一次的操作可以選方向，前綴操作和后綴操作內部有序，總的方案數就是：
然后就結束了qwq,預處理完之后 \(O(1)\) 即可
- 顯然一個數如果被操作多次，只有最后一次有用。那么每個元素有三種情況：最后一次在放在開頭，最后一次放到末尾，未操作過。前兩種操作對應 a 的前綴后綴，中間剩余的元素必須是升序的。假設前綴有 x 個元素，后綴有 y 個元素，計數時先給每個操作劃分到元素中，非最后一次的操作可以選方向，前綴操作和后綴操作內部有序，總的方案數就是：
-
- 為了簡易，我們想辦法使得最后只需要考慮取 \(w\) 體積的情況，這個可以通過對每一位加一些無價值節點實現?？紤]從低位往高位依次計算。先考慮這一位內，若 \(w\) 這一位為 \(1\)，那么能取，直接取最大的即可。否則這一次是不能取的。剩下沒用過的節點需要轉移到更高一位，由于更高一位的一體積相當于當前位的兩體積，因此我們需要給當前位所有元素兩兩打包。顯然從大到小依次打包最優。于是這道題就貪心完了。
-
- 我們設 \(sum_i\) 表示 \(a_1⊕a_2⊕?⊕a_i\) ，則在 \(i\) 時刻 \(P⊕Q⊕R=sum_i\) ，且 \(P,Q,R\) 中有兩個一樣。那么一定是一個 \(sum_i\) 與兩個相同的數，無序情況下形如 \((x,x,sum_i)\)。那么 \((x,x,sum_i)\) 由什么轉移而來的？\((x,x,sum_i)←(sum_{i?1},sum_{i?1},sum_{i?1}⊕a_i),x=sum_{i?1}\) 。系數為
\(3\)。\((x,x,sum_i)←(sum_i,sum_i⊕a_i,sum_{i?1}),x=sum_{i?1}\)。系數為 \(2\)。那么用 \(map\) 來維護 \(dp_{i,j}\) 表示考慮了前 \(i\) 個數，\(x=j\) 的方案數。然后就 \(ok\) 了。
- 我們設 \(sum_i\) 表示 \(a_1⊕a_2⊕?⊕a_i\) ，則在 \(i\) 時刻 \(P⊕Q⊕R=sum_i\) ，且 \(P,Q,R\) 中有兩個一樣。那么一定是一個 \(sum_i\) 與兩個相同的數，無序情況下形如 \((x,x,sum_i)\)。那么 \((x,x,sum_i)\) 由什么轉移而來的？\((x,x,sum_i)←(sum_{i?1},sum_{i?1},sum_{i?1}⊕a_i),x=sum_{i?1}\) 。系數為
-
- 對于每個生成樹是難以計算的，考慮計算當前的 \(a_i\) 會成為多少個邊權。\(a_i\) 按 \(p\) 重新排列后，\(i\) 需要在前面選擇一個父親，則選擇父親的這條邊的權值為 \(a_i\) 當且僅當前面的 \(k\) 個 \(a\) 中存在一個 \(a_j\) 使得 \(a_j≤a_j\)，其余的隨便排。而 \(i\) 向兒子的全部連邊中，邊權為 \(a_i\) 當且僅當兒子 \(j\) 前面的 \(k\) 個 \(a\) 均比 \(a_j\) 大且 \(a_i\) 為最小的一個。則我們選出 \(k\) 個比 \(a_i\) 大的數進行排列并欽定這個排列右邊的第一個數比 \(a_i\) 小即可。然后就做完了。
-
-
把 \(3^n\) 個兒子見到 \(3\) 叉 \(trie\) 上， 對于兩個操作分討
- \(Salasa\) ： 交換 \(1\), \(2\) 打懶標記
- \(Rumba\) : 輪換 \(0, 1, 2\)， \(0\), \(1\) 就直接換，\(2\) 要進位所以遞歸一下就好了
-
-
- 不太能數據結構維護，注意到值域小，對值域所有數處理對應的答案。發現如果 \(x,y\) 在某時刻的位置互為相反數，則它們此后的位置必為相反數。每次只維護符號相同區間 \([l,r]\)，若在當前操作后符號不完全相同了，則將符號不同的兩邊中元素數量較少的一邊扔了——反正后面可以通過對稱性得出；并對恰好可以取到 \(0\) 的位置打上標記。最后 \(dfs\) 一遍推出被扔掉的點的信息。
-
Guessing Permutation for as Long as Possible
- 限制等價于三點誘導子圖有 \(\max(x→y, y→z) > x→z\) 。所以枚舉有序三元組 \((x,y,z)\)，如果 \(\max((x,y), (x,z)) < (y,z)\)，則 \((x,y), (x,z)\) 定向時有且僅有一條是指向 $x￥ 的。發現順便滿足了 DAG，就是 \(2-sat\) 問題了。只要考慮個數，所以帶權并查集即可。
-
- 二分答案，即要求每一段和小等 \(mid\), 能證明區間的數量是連續的。用樹狀數組優化 \(dp\) 求最多最少分幾段就好了，這個東西你場上不會證明但是也不要心虛，一些貪心如果是比較經典的，就別證明了qwq
-
- 讓?雷不動我們動，不能向下所以只能向左?格，向左上?格，由于狀態是循環的，統計出以 12 為周期的?雷狀態的?案數，?與?之間暴力就好了
-
- 首先 \([i/2^j]\ mod\ 2\) 表示子集 i 的二進制表示中第 j 位（從低到高）是否為 1。我們考慮數位dp，從?位到低位確定每個 \(x_i\)，然后四維背包記?下剩余容量，即還需滿足的數值?？梢园l現的是，這個背包容量每維的容量不需要超過15，因為否則剩余的所有?集加起來也不夠。進?步我們發現這個15是不緊的，?如對于?層，如果集合 1, 1234, 12, 134 都被?到了那么這兩種?定能互相調整成更?的?？梢?抽屜原理，簡單證明這層最多? 5 個，所以容量不會超過 9。
所以直接背包時間復雜度?概是 \(30 \times 10^4 \times 2^4\)，而實際上可以通過更仔細的分析，發現背包上界開到 7 也是?夠的，但更?就不?了。
- 首先 \([i/2^j]\ mod\ 2\) 表示子集 i 的二進制表示中第 j 位（從低到高）是否為 1。我們考慮數位dp，從?位到低位確定每個 \(x_i\)，然后四維背包記?下剩余容量，即還需滿足的數值?？梢园l現的是，這個背包容量每維的容量不需要超過15，因為否則剩余的所有?集加起來也不夠。進?步我們發現這個15是不緊的，?如對于?層，如果集合 1, 1234, 12, 134 都被?到了那么這兩種?定能互相調整成更?的?？梢?抽屜原理，簡單證明這層最多? 5 個，所以容量不會超過 9。
-
- 暴力并查集顯然不行，將下邊界拓展到 b + 1，我們不用知道 1..b-1 的連通性，只需要知道第 b 行的就好了qwq，只維護第 b 行的并查集，發現維護的是后綴，所以就啟迪我們去把等價的區間一塊維護了，用分治解決就好了。
-
- 由于對稱只看 \(a < b\), 對于長度為 \(len\) 的黑色長條， 前面的 \(len - (len mod k)\) 一定被經過，長度均為 \(k\), 把 \(len\) 看成 \(len mod k\) 即可，剩下的就能用特殊性質 \(c\) 來做了
-
- 只管父親，兒子遇到就打標記，但是這樣好像還是不行，因為這個的時間復雜度是 \(O(n \times d ^ 2)\), 發現只要讓 \(\le d\) 的點最多被標記一次就好了，這樣子的時間復雜度就降到了 \(O(n \times d)\).
-
- 度數小等 4， 把 i,i-1 去掉就最多剩下 7 個聯通塊,設 \(f_(i,p_1,p_2,S)\) 為 \(p_1\) 為 \(i-1\), \(p_2\) 為 \(i\), \(\le i\) 集合為 \(s\), 發現狀態只有 \(n^2 \times 2^7\) 種，所以能過
-
-
記 \(f_{i,l,r}\) 為考慮值為 i 區間為 [l,r] 的方案，則
- $f_{i,l,r} ← I_{l,r} \times f_{i+1,l,r} 。
- $f_{i,l,r} ← \sum_{k∈[l,r]}I_{l,k?1} \times f_{i+1,l,k?1} \times f_{i,k+1,r} 。
-
-
- 等價于詢問向量 (a,b)，對于前若干個向量，每個向量都要取偶數個，問能不能加起來得到向量 (c,d) 使得 c≤a,d≥b。（a,c 代表 \(\sqrt2\) 的系數，b,d 代表 ?1 的系數）， 這個時候有一個偶數的限制就很煩，怎么辦，全除掉就好了，猜：設最后一個向量是 (p,q)，只需要滿足 \(p \div q \le a \div b\) 就行了。
-
-就是推柿子沒什么好說的了，就是毒瘤推柿子題.....
-
- \(f_i=min(f_j+∑^{k=p_{j??1}}_j(c_k?i+1))\), 其中，其中 \(c_i\) 為第 i 個 A 前面有多少個 B,\(p_i\) 為最小的 \(k\) 使得 \(c_k?i\) 不為 0, 發現能夠單調隊列優化加斜率優化，就做完了
-
-
設 \(f_{l,r}\) 表示 \((l,r]\) 是原 \(a\) 序列，當前先手在 \(l\) 堆至少取多少石子能贏。設 \(g_{l,r}\) 表示 \([l,r)\) 是原 \(a\) 序列，當前后手在 \(r\) 堆至少取多少石子能贏。
- 當 \(l = l, f_{l, l} = 1\)
- 當 \(g_{l+1,r} > a_r, f_{l, r} = 1\)
- 當 \(g_{l+1,r} \le a_r, f_{l, r} = a_r - g_{l+1,r} + 1\)
- 當 \(l = l, g_{l, l} = 1\)
- 當 \(f_{l, r - 1} > a_l, g_{l, r}\)
- 當 \(f_{l, r - 1} \le a_l， g_{l,r} = a_l - f_{l, r - 1} + 1 + g_{l + 1, r}\)
-
-
- 只要正反兩下就能只考慮周圍的點qwq,設 \(c(u)\) 為 x 周圍的點的個數，然后分討
- topo內有一個數，中途記錄出現在隊列中的點的個數cnt,f[x]+=n?cnt
- topo內有兩個數，記錄隊列中的兩點x,y,對于y,如果y存在y?>z且z的入度為1,那么x顯然不能到z,標記一下x即可
-
- 把上限鎖死，要不然時間復雜度不穩定，因為一次一定就可以，但是答案一定是最大的，其實 \(|c_0, c_1|\) 不劃算，不如拆開：\(∣c_0?c_1| =d\)調整為至多 \(d+1\) 次 \(c_0=c_1\), 想把 1 盡可能往后放，所以每次操作一個前綴是最優的。
-
- 首先，縮小范圍，下界是不能都小于 0，否則答案肯定不超過 2n, 就考慮取正填負的策略就好了，為了更小，所以就不能重復走，我們分討，如果我們走完這一段的前后綴，如果和 >0 我們就一定能夠直接填完，否則要找前綴和大等 0的位置在分段操作，所以答案就是最大子段和，但是有參數不能直接維護，我們要用線段樹來維護前綴和，這樣子才能在合法時間內完成
-
- 把 \([l, r]\) 區間拆開，拆成 \([1, l]\), \([1, r]\)兩塊和跨 \(l, l-1\)的區間，前綴就建立 \(s_i\) 的 ACAM 以后把 t 拉上去跑，每走一步記錄 fail 樹上終止節點祖先的個數。至于跨越，就是建反串的 ACAM,然后放 fail 樹上就好了
-
- wqs二分是我們看到題目的第一個想法，但是我們這個時間復雜度是 \(mnlog_w\) 再乘上阿爾法的這顯然時間復雜度不對。。。。我們發現斜率有且僅且改變黑邊。直接一起二分就好了，但是我們如果是偶數的話必定有一條不確定，我們就直接不管，去做 \(n-2\) 條邊的最小生成樹就好了qwq
-
， 就是求， 
，然后能用線段樹維護
，這樣子的一個鬼東東，區間內左右端點是否選擇時的答案，這就是pushup，螞蟻就單點修改，方糖就區間修改，
，對于選法的影響即 kx(k是區間個數)，\(x_r -x_l \le 2L\) ,所以在K=0的時候特判掉，時間復雜度 \(O(n\log_n)\)
-
- 考慮判斷一個終止態是否可達,單個棋子必定可以到達，多個的話會產生多個連續段，把棋子看做成刪除，要求是顏色要異于其他連續段的兩邊棋子的顏色。設第一個被刪的段（最后一個放棋子的段）的最后一個棋子顏色為 c，必須在兩邊的是他的補色，所以把所有c的都刪了，剩下只剩補集 c' , 所以含 c 的段就只有一個，所以這個段就是最后被刪除的段（第一個放棋子的段），刪棋子和放棋子的方案是一一對應的，所以合法刪就是合法放，暴力dp,設 \(f_{i,0/1,0/1}\) 表示欽定 i 不放棋子，當前是否存在 第一個被刪的段，當前是否存在 最后被刪的段，放棋子數量的最小值。轉移大概是如果 i?1 不放棋子就是 $f_{i,x,y}←f_{i?1,x,y}否則枚舉 i?1 所在段的左端點，考慮這一段是第一個被刪的段、最后被刪的段還是其他段。時間復雜度是 \(O(n^2)\) ， 容易通過子序列自動機找到以 i?1 為右端點的第一個合法的左端點，并且發現能轉移的點是一段前綴，這個前綴隨著 i 增大而增大。分三類記一下前綴最小值即可,這樣時間復雜度就降成 \(O(n)\) 了
-
AT_arc067_c [ARC067E] Grouping
- 設 \(f_{i,j}\) 代表分人數為 i 的組，當前有 j 個人的方案數，\(g_{i,k}\) 代表將 ki 個人分成 k 組，一組 i 個人的方案數。
,
,遞推分子，枚舉的是調和級數，所以是 \(O(n^2\long_n)\) 的時間復雜度.
- 設 \(f_{i,j}\) 代表分人數為 i 的組，當前有 j 個人的方案數，\(g_{i,k}\) 代表將 ki 個人分成 k 組，一組 i 個人的方案數。
-
AT_agc008_e [AGC008E] Next or Nextnext
- 全是相同的你就別管，可以證明一定是一個連通塊，是顆內向基環樹，考慮對于一個基環內向樹如何還原 \(p_i\)，考慮記 i 點延長的鏈長為 L，i 點到前一個有延長鏈的環上節點距離為 L'，若 L>L′顯然無解，若 L<L′則鏈頂可以選擇放在 \(i?1→i\) 或 \(i?2→i?1\) 上，否則選擇唯一。
剩下的就模擬討論就好了qwq,時間復雜度 \(O(n\log_n)\)
- 全是相同的你就別管，可以證明一定是一個連通塊，是顆內向基環樹，考慮對于一個基環內向樹如何還原 \(p_i\)，考慮記 i 點延長的鏈長為 L，i 點到前一個有延長鏈的環上節點距離為 L'，若 L>L′顯然無解，若 L<L′則鏈頂可以選擇放在 \(i?1→i\) 或 \(i?2→i?1\) 上，否則選擇唯一。
-
- \(k_i = a_i - b_i\), \(x_i\) 為從 i 位置運送到 i+1 位置的壁的數量， 那么就有
，這可以用slope trick 解決啊
- \(k_i = a_i - b_i\), \(x_i\) 為從 i 位置運送到 i+1 位置的壁的數量， 那么就有
-
，有后效性就把他二分出來（指 \(f_{1,H}\), H), 然后在二分，如果 \(f_{1,H} = mid\) 移動 l, 否則就移動 r. \(O(n^2)\) 的記憶化就結束了qwq
-
- 本來想著很復雜，一看題解，秒懂。。。。 記 \(f_{i, j}\) 示敲擊了鍵盤 i 次，匹配了 j 個字符的方案數。有 \(f_{i,j}=(f_{i-1,max(j-1,0)}+f_{i-1,j+1} \times 2)\) ， 然后注意一下邊界就好了哇
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 3010;
const int mod = 1e9 + 7;
int n;
string str;
int f[N][N];
signed main()
{
cin >> n >> str;
f[0][0] = 1;
for (int i = 1 ; i <= n ; i ++ )
for (int j = 0 ; j <= i ; j ++ )
f[i][j] = (f[i - 1][max(j - 1, 0ll)] + f[i - 1][j + 1] * 2 % mod) % mod;
cout << f[n][str.size()]<<endl;
return 0;
}
-
AT_agc043_d [AGC043D] Merge Triplets
- 最終的排列中，按照前綴 max 的位置劃分，每一段的長度不超過 3，這是必要條件但是好像不充分，長度為 2 的段個數不超過長度為 1 的段個數。好像充要。所以設 \(f_{i,j}\) 表示考慮前 i 個數，長度為 1 的段個數減去長度為 2 的段個數為 j 的方案數。枚舉的時候枚舉長度就好了，時間復雜度 \(O(n^2)\)
-
AT_agc041_d [AGC041D] Problem Scores
- 這不就等價于，有 n 種物品，每一種都有無限個，第 i 種物品重量為 \(w_i\)，現在要選出一些物品使得總重不超過 n?1，求方案數。很簡單的無限背包
-
AT_agc040_e [AGC040E] Prefix Suffix Addition
- 記 \(dp_{i,j}\) 表示我們在第 i 個數令了 \(q_i=j\)。容易發現 DP 轉移：
- 把 \(a_i?a_{i?1}\) 按正負分討就好了
?
-
AT_agc022_e [AGC022E] Median Replace
- 維護一個從棧底到棧頂由一段連續的 1 和一段連續的 0 組成的棧。
- 若 c = 0 著必定賺翻了，三個成一個 0 他不香嗎
- 若 c = 1 ， 是 0 就抵消了（指棧頂，兩個1就忽略掉就好了啊，否則就要多加一個1
-
P4931 [MtOI2018] 情侶？給我燒了?。訌姲妫?/a>
- 這就是一個簡單的母函數模板，推出來就是 \((i+1) \times f_{i+1}=4 \times i \times f_i + 8 \times f_{i?1}\)， 然后預處理就好了
-
- 這道題目還是生成函數，只不過推完之后還有一點的求通項，然后直接帶入就好了
- \(a_n≡485071604×940286408^n+514928404×59713601^n(mod10^9+7)\)
-
- 這不就是板子嗎，就是有點卡常，這個預處理的長度最好是 \(2 \times 10^7\)
-
[P6860 象棋與馬](https://www.luogu.com.cn/problem/P6860）
，沒掉的是求和，這個的話有意思，推的過程有億點點長，放不下，然后再把這個套杜教篩就好了呢
-
- 這還要講嗎，狄利克雷板子，做一下類似埃篩就好了
-
P12939 [NERC 2019] Foolprüf Security
- 黑白染色，最終 Prüfer 序列里一定有 n?1 個白點（刪了這么多黑點）和 m?1 個黑點（刪了這么多白點）。， 所以無解的一個充分條件：\(k_a≥m\) 或 \(k_b≥n\), 剩下的就按模板構造就好了
-
- 把 \(L, K\) 閑著沒事除個 \(K\), 這不就成了選數N次使選出的數最大公約數為1的方案數。f[i]實際上是含有公約數i的方案數，然后用一下容斥，f[i]分別減去f[2i],f[3i] ， 倒著推一遍就好了，\(L = 1\) 的時候要特判
- 就是先Dfs染一遍色, 黑節點的兒子是白點，白點的兒子是黑點, 然后用 f[i][j] 來表示i這個點為j方贏時最少控制的關鍵節點,數
- 若是黑點，如果該點是白點，則只有其所有的兒子都是黑節點，如果該點是黑點，則只需要有一個兒子是黑點，白點亦然
- 再Dfs一遍，合并了就好了
-
5. 答案代碼了（由于啥也沒用，所以不算題目池qwq
浙公網安備 33010602011771號