【CF/其他 經驗總結貼】Key&Mind篇（一）
食用說明 \（‘ - ‘）/
個人訓練總結用，主要是關鍵詞聯想豐富自己腦洞
Key&Mind
| 關鍵詞 | 聯想 |
|---|---|
| 小于x的最大可用 | 二分，set |
| 配對分組 | 統計每組數量；小于一半防重復索引配對；先配數量最多的，堆動態維護；先配完，然后剩下的和其他配；一個個配，別著急；自己配自己，單獨配對的，無法配對的等特殊情況 |
| 數論構造 | 分奇數偶數；不等式嘗試構造貼近邊界的；0，1，2； |
| 完全平方數 | 完全平方數=完全平方數（A）*完全平方數（B）；分解質因數后質因子指數%2為0 |
| 序列整除 | 整除轉化為取模 |
| Mex函式 | 單調遞增 |
| 不能對相鄰元素進行某一操作 | 思考相鄰的情況，無法相鄰操作后會剩下什么，然后思考把剩下的作為判斷結果的特征依據 |
| 能不能轉化為某一排序 | 思考不能轉化，某一元素是否不能再另外元素之前 |
| 列舉 | 列舉分界線（左邊都進行一個操作，右邊都進行一個操作），從兩邊向中間列舉，雙指標 |
| 二維方格 | 二維轉一維獨立，分操作第幾次是奇還是偶 |
| 數論符合等式解對數 | 轉化為整除式子變為求因子數，有可能還要討論因子種類數 |
| gcd ，lcm | 分解質因數，設為兩個互質的，lcm轉gcd,lcm=npq,pq=lcm/n |
| 線性篩分解質因數預處理 | 可用直接預處理出每個數最小質因子，每個數質因子種類數量 |
| 如果確定答案為非負 | 加max(0,ans)或者加絕對值 |
| 取模 | 如果a+c，c<m那么可以把取模操作轉化為是否減去m |
| 二維陣列爆空間 | vector |
| 多個組選元素，每個元素有使用次數限制 | 按組的人數排序先選限制大的，然后每組選可使用最多的 |
| 兩字串操作后相等 | 公共子串，公共子序列，最短編輯距離，BFS |
| 字串，相鄰元素距離限制，最少修改次數 | 距離限制內找最遠可以修改的 |
| 乘法除法 | 分解質因子，相應質因子次數加減 |
| 找n個數滿足一個等式 | 雙指標，二分，map（看沖突），鴿巢原理(時間復雜度） |
| 差分 | 邊界特殊處理 |
| 互質乘積 | 求約數 l o g N logN logN,分解質因子 |
| 求方案數 | DP，組合計數，樣例湊數遞推 ，遞回+記憶化（思考引數） |
| BFS擴展 | 佇列實作；直接掃整個集合已經出現過的就擴展 |
| 多重背包 | 物品抽象為操作 |
| 時間復雜度 | bool陣列雙重回圈時間復雜度分析需要注意 |
| 貪心優先佇列 | 先把寬容度大的加入堆，然后逐個遍歷，比較當前元素與堆頂或堆的資料 |
| 不相鄰染色 | 預處理黑白二分圖，如果多種顏色則多次黑白二分染色 |
| 平衡（合法）括號串 | (和）各占一半；首尾分別為(和)；對于任意前綴(一定比）數量多，堆疊 |
| 某一操作打破合法性 | 思考如何抵消這次操作，可能是再進行一次這種操作，奇偶性 |
| 前綴操作 | 反向操作，從后向前遍歷，使得后半部分以后不會被重復修改 |
| shuffled（打亂） | 順序無關的話變成組合選數問題 |
| 判斷是否能選n個數使他們的和為某個值 | 可以先根據公式推出這個值的可能的范圍，然后如果超過范圍就直接不成立，如果范圍內再暴力嘗試 |
| 如果自己想的不能覆寫某些特殊情況 | 分類討論/while暴力微調（很爽）直到符合條件 |
| 構造題 | 把樣例模擬一遍 |
| 涉及排列的構造 | 嘗試從1~n自然排列開始，斐波那契，逆序排列，然后做微調修改 |
| 問經過m次操作后結果相關的東西 | 遞回+記憶化（DP，遞推）,記憶化注意負數 |
| 給比較少的操作種類問最值(一般2種） | 設每個操作進行次數，然后線性規劃找約束->消元->二分三分（或者想貪心打表） |
| 按位與性質 | a & b = b & a ; a & a = a ; a & b < = m i n ( a , b ) a\&b=b\&a;a\&a=a;a\&b<=min(a,b) a&b=b&a;a&a=a;a&b<=min(a,b)前兩個用來式子轉化補充完整 ， 第三個常用來證相等 |
| 下標相關的式子 | 將其完全展開列出來，觀察其中不變的項，尋找規律，區分下標是定值還是變化的 |
| 區間擴展 | 從左到右，右到做，中間向兩邊，兩邊向中間 ，前綴，后綴 |
| 區間性質 | 對于一個區間對于某個性質成立，觀察一下區間擴展程序中，是否也是成立的，不然容易只看到最終區間符合操作條件，忽略了區間內部也是符合的，造成操作的遺漏 |
相關解題報告
【解題報告】CF DIV2 #ROUND 707 A~C
【解題報告】CF DIV2 #ROUND 708 A~C,E1
【解題報告】CF DIV2 #ROUND 709 A~C
【解題報告】CF DIV3 #ROUND 710 A~E
【解題報告】CF DIV2 #ROUND 711 A~D
【解題報告】CF DIV2 #ROUND 712 A~D
【解題報告】CF DIV3 #ROUND 713 A~E
【解題報告】CF DIV2 #ROUND 714 A~D
【解題報告】CF EDU #ROUND 107A~D
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/277132.html
標籤：其他