一些自己看的的OI小知識

此文被密碼保護

1. 判斷某個數能否由一些數組成可以先對數進行排序然後使用設 \(f_x\) 表示 \(x\) 是否能被組成，然後對于前 \(i\) 個數就有 \(f_x=f_x | f_{x-a_i}\) ，具體題目是 \(noip2018\) \(day1t2\)
2. 你去删除一個元素的時候可以不用說去真正的移除，你可以用一個并查集來标記像後方，表示被移除。并查集進行打标記是一個很有用的思路。
3. 實在遇到不會做的題，考慮一下 dp，即使不是正解也絕對沒錯，如果是在樹上做 dp ，不要但考慮在鍊上的不如直接考慮樹上 dp。
4. 遇到要求問方案數，沒事就容斥一下，說不定就弄出來了。
5. 求某個節點在某個方向上的直接兒子，改為求方向上節點 \(v\) 的 \(dep_v-dep_u-1\) 級祖先
6. \(\sum_{i=1}^n i^2 = \dfrac{n(n+1)(2n+1)}{6}\)
7. 裴蜀定理同樣适用于多元，\(ax+by+cd=t\) 要求 \(t|(a,b,c)\)
8. 判斷 \(x\) 是否為 \(y\) 的 祖先，可以記錄 dfs 序進行判斷，看一下對于 \(x\) 的 \(dfs\) 序區間是否包含 \(y\) 就行了。

9. 二項式反演：考慮求恰好 \(k\) 個物品的時候，可以按下面兩種方法來做。

   設 \(f_i\) 表示至少 \(i\) 個物品時的答案, \(g_i\) 為恰好 \(i\) 個物品時的答案。

   然後 \(f_k=\sum\limits_{i=k}^n\displaystyle\binom{i}{k}g_i\)

   緊接着 \(g_k=\sum\limits_{i=k}^n(-1)^{i-k}\displaystyle\binom{i}{k}f_i\)

   設 \(f_i\) 表示至多 \(i\) 個物品時的答案, \(g_i\) 為恰好 \(i\) 個物品時的答案。

   然後 \(f_k=\sum\limits_{i=0}^k\displaystyle\binom{k}{i}g_i\)

   緊接着 \(g_k=\sum_{i=0}^k(-1)^{k-i}\displaystyle\binom{k}{i}f_i\)

10. 在使用全排列 \(\text{STL}\) 之前記得将序列從小到大排序。
11. 對于樹鍊剖分上的東西，一個點到他的父親，最多隻會經過 \(\text{log}\) 條輕邊，有時可以根據這個，用資料結構維護重鍊的操作，輕鍊上的進行暴力，複雜度仍然是對的。
12. 多測學會清空。
13. 遇到區間整體加同一個數多次别去想着直接上資料結構，想想差分，如果差分後仍然數量比較多，不妨想想将差分後的序列再差分，最後隻需要做兩次字首和就可以了。
14. 将 \(1 \sim n\) 組成排列考慮分成 \(\sqrt{n}\) 塊， 每一塊分别輸出，不斷減小 \(m\) ，可以證明是對的，也就是 CF1017C 。
15. 異或相關，考慮使用線性基或者 01 trie 。
16. 樹上限制構造次數或者明确周遊次數為 \(n \log n\) 的時候，考慮輕重鍊剖分，保留重兒子答案，單獨處理輕兒子。
17. 哈夫曼樹可以用于平衡一類中增添删除不為 \(O(1)\) 的複雜度平衡，這樣複雜度為 \(n \log n\) 。 詳見問題 stcm，我之前在亂扯對不起！！！！
18. 如果一堆字元串保證 \(\sum len \le n\) 的話，那麼字元串長度不一樣的隻會有 \(\sqrt{n}\) 種，可以根據這個進行根号分治，長度小于根号的存下來後面一起暴力，大于根号的直接暴力。

19. unordered_map

    會對一類特殊的數字被卡，也就是 \(2^{16}\) 。
20. 遇到對每個東西有兩種選擇，選每種選擇有代價，求最小代價，于是考慮拆點之後跑最短路
21. 平面圖轉對偶圖，就是把區域當成一個點，然後建圖，可以看狼抓兔子那道題。
22. 一棵樹隻會有 \(\sqrt{n}\) 種不同的度數
23. 求一些點所構成的極小連通子樹或圖的邊權和，可以将點按 \(dfs\) 序排序，然後為 \(\{a_1, a_2, a_3, \dots ,a_k\}\) 則邊權和的兩倍為 \(dis(a_1,a_2) + dis(a_2, a_3) + \dots + dis(a_n, a_1)\) 。
24. 看到限制條件考慮 2-sat
25. 和距離有關考慮樹分治，也可以考慮長剖進行求解
26. 沒事多考慮建邊，如果建邊數量太多，考慮優化建邊，如果 \(A\), \(B\), \(C\) 中 \(A\) 向 \(B,C\) 建邊，然後 \(B\) 向 \(C\) 建邊，那麼考慮建 \(A->B->C\) 。
27. 對于 \(\max\) 這類不友善直接做的東西，考慮拆開，假設裡面某一個為更大，然後下去做。
28. 一種 \(dp\) 狀态的設立 \(dp_i\) 表示以 \(i\) 結尾的不合法/合法的數量。
29. 在設計一個資料結構時，需要保證：

• 資料組織成嚴格的樹結構：維護資訊的結構有父子關系，在通路子結構時，必須通路父結構。
• 每個節點上維護的資訊不互相包含，父子結構上的标記有嚴格的時間順序。如 sone1 中，設計虛子樹修改标記和實子樹修改标記，而不包括總子樹修改标記；維護虛子樹資訊和和實子樹資訊和，但不維護總子樹資訊和。

不是我說的。

1. 兩個點之間整點數量為 \(\gcd(|x1-x2|,|y1-y2|)\) LOJ1077
2. 在不強制線上情況下分塊一定比莫隊弱。
3. 類似雨天的尾巴這種題線段樹合并的時候，對原樹輕重剖分後合并空間 O(n)。