！！（╯' - ')╯︵ ┻━┻ | ┬─┬ ノ( ' - 'ノ) | (╯°Д°)╯︵ ┻━┻！！

原标题：一些不难但是关键时刻能搞死人的（我可能想不到的）技巧/思路/方法（开坑慢慢填）
实际上开始脱离标题，几乎变成了不会做题目大全
然后很多时候关键部分都想出了，偏偏最简单的一步想不出来
然后看题解的时候就很窒息了
！！（╯’ - ')╯︵ ┻━┻ （掀桌子） ┬─┬ ノ( ’ - 'ノ) （摆好摆好） (╯°Д°)╯︵ ┻━┻(再他妈的掀一次）

https://www.luogu.org/problemnew/show/CF1168B

把黑看成黑，把白看成没，然后换进换出？ [CQOI2012]交换棋子
前缀后缀搞一搞就可以搞出删一个的效果 CF1028C
博弈论：大胆猜想，胡乱验证。

一道不会的构造

不会诶

正难则反 考虑差分
多人背包 懒得新开一篇，就告诉我自己有这道题

这题的标算，一个小trick，不过我感觉我的做法也很好（光速逃）

递推构造矩阵一个trick？

一个转化

有相同元素的排列复位，用dsu。。明明以前想到过，怎么又想不到了。。
也不一定要并查集，暴力跳也是办法。。

曼哈顿转切比雪夫

=k <=k <=k-1

O(n)第K大：nth_element

permutation 记住这个拼写

有些暴力只要考虑启发式合并就行惹……
QAQ QAQ QAQAQQQ

Simpson积分 ，懒得打前面的，我突然发现这个其实Simpleson，为什么以前一直不会……
$\frac{R-L}{6}\left(f\right(L)+4f(\frac{L+R}{2})+f(R\left)\right)$6R−L​(f(L)+4f(2L+R​)+f(R))

树形结构的限制，可以考虑合并结点

• 2018 Multi-University Training Contest 3 H
• [HNOI/AHOI2018]排列

环形考虑倍长

• https://atcoder.jp/contests/agc039/tasks/agc039_c

树状数组也阔以二分

• https://www.luogu.org/problem/CF1208D 就是砍掉右儿子的线段树嘛

vis数组不用清空的trick

• 每次判断 vis==tot ， tot 表示使用次数

森林连通块数=点数-边数

• http://codeforces.com/contest/1151/problem/E

有时候只用考虑个数

• https://dev.xjoi.net/contest/1237/problem/2
• https://dev.xjoi.net/contest/1235/problem/2
• https://www.luogu.org/problem/CF1151F

min-max容斥

• $min\left(S\right)={\sum }_{T\subseteq S}(-1{)}^{\mid T\mid -1}min(T)$min(S)=∑T⊆S​(−1)∣T∣−1min(T)
• 感性证还是很好理解的
• 期望意义下也成立
• [HAOI2015]按位或 还要SOSDP+压空间。。不会FWT和FMT。。

线性基的某个性质

• 假设 $n$n 个数的线性基中有 $k$k 个数，那么显然共有 $2^k$2k 个不同的异或和，而其中每一个异或和的出现次数都是 $2^{n-k}$2n−k
• 感性理解一下的话……就是不在线性基中的每一个数字都可以被线性基中的数字表示出来从而异或之后为 $0$0，那么这些数字都可以看做 $0$0
• P4869 albus就是要第一个出场

背包，删除一个物品其实可以直接减

• 大概就把dp倒过来？？可能别的dp也可以这么搞？

根号分治？

• CF1039D You Are Given a Tree

如果要多次计算矩阵快速幂，一个有用的trick

• 题 $O\left(n^{3}logm\right)$O(n3logm) 预处理，然后单次就可以做到 $O\left(n^{2}logm\right)$O(n2logm)

把区间按模数分类

• CF1197D Yet Another Subarray Problem

性质

• $abs\left(a\right)=max(a,-a)$abs(a)=max(a,−a)
• G. The Awesomest Vertex 勉强能算用到？

神奇格雷码

• CF 1163E

关于第一个的特判

• CF 1168A

xor和最大

• 记得搞个trie哈

模拟费用流

• CF 280D k-Maximum Subsequence Sum
• 一般来说可能是个看起来像贪心的东西，证明用费用流。先咕着。

限制思路

• 有时候是被DP限制思路，有时是被组合限制思路。

期望可加性

• CF 280C Game on Tree 一道神仙题，好像是WJMZBMR出的吧

如果求出现次数可以只考虑第一次出现

• luogu2664 树上游戏

有些期望题可以把每个质因子的贡献分开考虑

• CF1097D Makoto and a Blackboard

带反悔的贪心

• CF1091F New Year and the Mallard Expedition

看起来十分有关的两个东西其实可以分开考虑

• CF1076F Summer Practice Report（其实也不是完全分开）

把差不多的东西弄一起？？（我也不知道这叫啥了）

• CF1065F Up and Down the Tree

拓扑排序后边的重定向&&关于反向和删边的性质

• CF 1100E Andrew and Taxi

计算有多少个相同的可以用trie

• 【THUWC2019模拟2019.1.16】Square

倍增

• CF 1078D Chattering 这题还套了线段树，但是线段树的部分很好想，倍增则不太熟悉。这题还卡了很久的常= =

归并排序的奇葩本质

• CF 1081G Mergesort Strikes Back

gcd其实就是各个质因子指数取min的过程

• 反正有道TC，找到了补。

树上链修改，单点查询，不用树剖

• 希望不要数据结构学傻

可以记有几个三元组，减少状态量，卡常必备

• CF 1110D Jongmah

最长回文可以原串和reverse后求LCS

• CF 1114D Flood Fill （虽然总觉得此题关键并不在此）

欧拉路径就是欧拉回路减一条路

• 牛客练习赛40 C-小A与欧拉路

基环树可以把环上的点考虑到树里

• CF 1109D Sasha and Interesting Fact from Graph Theory 这题是个链的数数题，结果就没想到这个= = 真见鬼= =

点对可以转化到平面上

• 牛客OI周赛7-提高组 C-小睿睿的方案
• CF1137E Train Car Selection 无比巧妙，竟然变成了凸包。。。

滑动窗口最值问题当然是单调栈

• 数据结构真的会学傻呜呜数据结构学傻是真的没救呜呜呜

分块

• 暴力会T，log数据结构又用不上，于是就要考虑优雅的暴力……
• CF 1129D Isolation 几乎完全不会分块= =
• G. The Awesomest Vertex

树恰好可以每个结点管一条边（除根外）

• 这是个很智障的性质对吧，蠢得不行对吧，谁都懂是吧
• 但在题里就想不到呢CF 1120D Power Tree