错误总结、套路集锦
加粗表示很有用
错误总结
- cmp函数不能在结构体内部
- 对于一道题意不裸的题，都应该手玩样例检验没有看错题、想出来算法的基本正确性，再去code
- 标准差是方差的算术平方根，所以说所谓方差是不需要开根的
- 不等式的移项 一定要分析正负性
- stl的比较重载不能随便搞，一定要满足传递性和大小情况单一性（stl用<和>推导出=）
- fft得答案时要round
- 带取模计数，判无解不能用答案=0，因为答案可能是模数的倍数
- 注意！
multiset的count复杂度和对应元素数量相关 - 注意！
set等非随机访问结构的lower_bound，必须调用结构内部的，用stl的那个函数会线性 - 注意 s&bin[i] 和 (s&bin[i])>0 的不同（惯犯
- 用指针a[]表示数组的时候，sizeof a只会得到单位大小，而不是整个数组的大小
- 取模题最后转正很容易忘记，养成中途转正的习惯
- map等stl在结构体内的时候memset会gg
- 在无c++11的时候，queue系列的swap是o(n)的
- 如果一个东西的插入复杂度是通过势能分析保证的
那么通常不能支持删除操作，因为可以多次进行高复杂度的操作 - 在CF上，任何自选模数的题都应该rand或者双模数，例如路径关键点、hash
- 线段树如果值域int，求mid的时候可能爆int……
奇妙结论
- 一个1到n的集合，选若干个不互质的数，要求和最大
结论：每个数最多两个不同的质因子，且一个在根号内，一个在根号n外
bzoj3308 - 让拓扑序的逆字典序最小，应建反向边跑大根堆；只会感性理解正确性
- 随机序列的笛卡尔树深度为log（每次期望为分成两半），即上升序列长度为log；笛卡尔树的子树大小也是log级别的
搜索
- 搜索去掉次序性的套路：强行限制大小关系
举例：POJ1011 Sticks - 常见优化：优化搜索顺序、排除等效的决策和物体、可行性、最优性、记忆化
- 对于一个序列，拆分成多个序列的问题，有两种不同的方向：给每个元素分配组、通过组找元素
最好能仔细根据题目斟酌一下策略，本人多次用2各种剪枝，也比不过裸的1……
举例：Sticks、Missile Defence System、Zebras
数学
- 数论分块
当出现连续的$\lfloor \frac{n}{i} \rfloor$时，值一定是单调不递增的，同值的区间可以合起来计算
复杂度：$O(\sqrt n)$
① 当$i \leq \sqrt n$,分母只有$\sqrt n$种
② 当$i > \sqrt n$,$\lfloor \frac{n}{i} \rfloor < \sqrt n$
$last=\lfloor \frac{n}{ \lfloor \frac{n}{i} \rfloor } \rfloor$
举例：CQOI2007 余数求和、非常多数论题 - 由调和级数，1+1/2+1/3…1/n=O(logn)
- 对于一个素数P，任何P以内的x，其倍数在模P意义下可以表示出所有P以内的数
- x不断对【<x】的数取模，只会进行 $O(logn)$ 次，讨论一下就知道了
- 【任意模数下存在逆元的数，其逆元互不相同】的证明： $ax=1(\%p)$，那么把其一作为未知数，根据裴蜀定理另一个与p互质
- $\sum_{i=1}^n d(i)^2约为nlog^2n$
- 期望有个套路的转化，恰好到达的状态的概率*步数之和，等价于所有未到达的状态的概率之和，这个你可以通过【把当前概率推到上面的步数个祖先上】理解
- 若$H*W且gcd(H,W)=1$的网格左下角射出$(0,0)\to(1,1)$的光线，则$\forall x,y \in N,(x+y)\%2=0,(x,y)会被经过$，其中不在边框上的点会被经过多次，且上述结论是充要的
树
点分树上，点对的LCA一定也在原树两点路径上
在一棵边权非负的树上，与该点最远的一定是直径的某个端点
两棵树合并起来，新的直径端点一定在两边直径端点中产生
直径的中心唯一
每个点的最远点，都一定经过直径的中心
改一条边，端点最多变化一个一棵树上点集的连通块个数=点-边
很多模型能转化为树形：
互不重叠只包含的区间（最近一个包含作为fa），例如析合树、一些性质题
某个变量只有单一指向（作为fa），这个其实是最常见的就不举例了
入栈出栈序列是可以表示为树形结构的，节点x的子树大小为k，则表示x先入栈，然后子树内的元素为$[x,x+k-1]$且都更晚入栈更早出栈，举例：HDU5181 numbers
其他，举例：跳跳棋
图的dfs树不会有横叉边
虚树上如何找到原树某个点的第一个祖先（强制在线）：
$dfn_A \leq dfn_B \leq dfn_A+siz-1$
我们先找到$dfn_A \leq dfn_B$的区间，然后就是这段区间能覆盖B的最右边的点
这个可以在线段树上二分实现用可重路径覆盖一棵树，最小数量：$\lceil \frac{度=1的点数量}{2} \rceil$
用路径并可以判断是否存在一条路径包含某节点
给定一棵树结构，每个点标号，要求每个点的编号比子树其他点小,合法方案个数=$\frac{n!}{\prod siz_i}$
除了树的图论
- 对于无向图，一个点双内如果有奇环，那么内部每条边都至少在一个奇环中；点双内有奇环的充要条件是在dfs搜索树上存在一个【一条非树边+若干树边】组成的奇环
字符串
- 串的计数，枚举长度，建立间隔为长度的关键点（调和级数），然后每个串会经过一个关键点，枚举关键点算贡献
举例：【NOI2016】优秀的拆分、股市的预测 - 如果一个串是双回文串，一定存在一种分割，满足前面是最长回文前缀或者后面是最长回文后缀
- 一个串重复多次的最长回文子串，如果不是无限长，则最多是两个合并起来
决策算法
- 找前k优的区间，固定一个点后，左边的优秀情况是极值问题
可以用堆维护左边，取出一个位置后把左边区间拆成两半放回去
举例：超级钢琴、树上的路径
当然非区间一般也是用堆维护
做法：堆维护，堆顶为最差元素
举例：K远点对、Supermarket - max n个数的环上相邻差；最小化这个，可以递增奇数+递减偶数
- 对于一些求大小为k最优集合的题目，不妨尝试猜测k一定为k-1的增量，感觉一般都不太好证明，不过可以画一画有没有反例:D
解题思路
- 有些题可以从简单情况着手、然后拓展到复杂情况（数学归纳法或者总结经验、模仿）
或者先考虑普通情况，再考虑改进来解决特殊情况
举例：noi2015 荷马史诗、POJ2442 Sequence - 对于比较陌生的题目操作形式，可以多造几组数据来模拟，找到一些性质，用这些性质转化题目
- 目前碰到处理棘手的删除问题的方法主要有两个，基本都需要离线
一个是倒着做，这个对题目的要求较高；
另一个是贪心，离线后按出现时间处理，然后按结束时间贪心
举例：【bzoj4644】经典傻逼题【集训队互测2015】最大异或和、【bzoj5040】航线规划【bzoj4229】选择 - 平方形式，可以转为为数点对，或者是进行两次然后相同的情况
又或者可以处理其差分1,3,5,7,9,11……
举例：NOI2009 管道取珠. 蔬菜. 学习小组 - 有关区间问题并用到区间最值，求出l[i]和r[i]表示第一个比a[i]大的位置，则l[i]+1~r[i]-1中间，用到的最大值都是a[i]
不过要小心最大值相等而重复的情况，可以强行把左边界改严格来限制
举例：洛谷18年7月月赛T4 - 很多计数问题要求排列，可以时刻保证排列性，然后插入一个数，将比它大的数+1
举例：51nod1296 有限制的排列、以及一些比较经典的树上dp - 跟极值有关的区间问题，考虑一下已知某个极值贴着区间所带来的影响（笛卡尔树dp之类的）
举例：hnoi2016序列、hnoi2017影魔、ioi2018会议、noi2019机器人的50分部分分（都有题解） - 问从状态A操作到B，考虑倒着操作
比赛技巧
- 取模题对拍时可以改小模数检验
经典问题
- 权值总和为S的背包，可以 $O(S \sqrt S)$ 完成，即考虑大块小块有根号级别的不同权值，每种权值单调队列优化多组背包即可
- 若干个不同的集合，要求选最多对数满足来自不同的集合；当$mx>sum-mx$，显然答案为$sum-mx$，否则考虑在一个优先队列中每次取最大的两个集合拿出一对数再塞回去，答案为$\lfloor \frac{sum}{2} \rfloor$；如果对数为更多，那应该只能用堆模拟了
其他
- 设cnt(x)为x二进制下1的数量，$cnt(a \oplus b)$ 为奇，当且仅当一个cnt为奇，另一个是偶
因为两个1在一起是偶，不在一起也是偶 - 有时候矩乘的矩阵有特殊性，可以舍弃许多可推导信息来减少规模；举例：弱题