- 6737151's blog
杂项汇总
-
6737151
LV 8
@
2023-10-22 13:14:07
- 正难则反，不仅包括转换合法与不合法，还有 将逆等价的过程倒转（尤其是不太容易立刻看出来的）！！！
- 要求判定 关于各元素关联对象出现次数性质 的题目，可以用元素随机赋权哈希解决。
- 相同出现次数元素归一类，类型总数是 的。
- 对于逐增类构造方案的计数，应优先考虑 每步递增方案是否导致相同的本质。
- 即使 全为整数，计算 的范围时不应转化为 ，因为除法的向下取整机制。
- 对于逐步逼近或答案与理论限接近的单调界限问题，应该用 步长逐增的倍增 而非二分解决。
- 求解 ， 最值时，将 子集全部标记后即可贪心。
- Dijkstra 的 zkw 线段树上传退出条件不是节点值无变化，而是 节点值不等于更新值。
- 线性 STL 容器的内存最多会比静态数组多一倍。
lower_bound找的是 大于等于特定值的最小位置，upper_bound则是 大于。- 避免用
bitset的无赋值运算符，会带来额外时空消耗。 - 真正涉及到的状态数可能远小于预期，但要注意构造数据情况。
- 根据端点信息和贪心策略可简化 DP 状态数。同时可以通过打表最优转移来源找规律。
- 有些题目中可 对小规模子问题和大规模子问题分别取更合适的做法，如根号分治。
- 某些 总体期望值 可以拆成 各个小部分期望 的和。
- 遍历树形结构过程中遇到需随当前点更新值的情况，如果无法撤回，需要分层存当前层被修改位置修改前的内容。
- 维护须增删元素集合的乘法积时，需要记录其中 零的个数。
- 某些多维限制（如元素双向奔赴）问题可以用 扫描线优化掉第一维。
- 对于计数问题，考虑 一些有序元素是否完全平等，可以简化问题。
- 对于字符串算法的填充字符，如果字符集不确定，可以哟 到 的控制符填充，但不要把它们输出。
- 区间取最值操作线段树只用记录到区间的 次最值。
- 二分图不重状态公平游走博弈中先手必胜当且仅当 所有最大匹配包括起始点。
- 前几个自然数 次方（包括逆元）可以用 线性筛 求解。
- 静态数组传进函数，函数外的值也会被函数改变。用 STL 容器可避免问题。
- 多组数据 / 多次判定 只清空上组数据涉及到的内容。如果涉及内容离散分布在整个数组中，可以记录 上次用到特定下标的数据编号。
- 动态有根树中若保持 ，优先用 欧拉序列 而不是 LCT。
- 最多同色段路径问题中每条边可以压成 最多三种颜色。
- DAG 计数问题考虑枚举 无出度点 剥离，然后容斥。
- 最值状压中牢记 min-max 容斥，亦可应用于期望。
- 对于特定类元素 / 操作数量有限制的最优方案求解，可以 对限定操作一个惩罚值加入总代价，然后二分。
- 增减两侧都非严格 的单峰函数不能用三分或倍增斜率求解。但证明斜率非严格单调的函数可以。
- 一维或区间为状态的 DP 优先考虑决策单调性和四边形不等式。
- 一些操作路径中特定值的 凹陷部分可以被翻成凸起，最后变成单峰简化问题。
- 无左右区分的括号匹配中栈高的一段凹陷可以被翻转过来，当且仅当 两侧栈内容相同。
- 在一般数据结构题的数据范围中， 和 的时间开销差不了多少。
- 基于
fread的快读在某些环境中需要特判避免遇到EOF后还会不断读进最后几个字符。 - 序列的某些关系位置可能只产生 极少的等差数列，可以利用该性质加速求解。典型例子是字符串的
border。 - 底数对 取模，则指数对 取模。 不是质数时还要判断指数是否超过了 。
- 长链剖分中内容从后往前存，一定要注意数组越界的问题，包括前后。
- 如果为了调试中间变量注释掉某些原本代码中的语句或缩小了某些枚举的范围，在前面打个
#pragma warning防止调试后被忽略。 - 线段树有多种标记时，一定要注意 各种标记的优先级以及一种标记对其它标记的影响。只保持每个节点只有一种标记会导致 TLE。
- 值为 的时候需要避免与未初始化的默认值混淆。
- 强制转换用 C++ 的构造函数风格 而不是 C 风格，同时 每处转换都要加（避免无
long long变量运算的问题，尤其是移位符号），防止语法判定不符合预期。 - 无标号类自然溢出不视作未定义行为。如果不是为了自然溢出，其风险可能不会被编译选项查到。
- 需要用到较多高精度数或多项式时，用 STL 封装。
- 调试 最优先查越界。有些数组开小了看不出来，可以先把
MAXN开十倍。 - 在编写过程中需要增加某些变量时，不要把它随意加到
char或bool类型后面，数据小了查不出来。 - 冒险修改代码时先拷一份备份，免得麻烦的撤回，而且 Dev-C++ 的撤销会把自动补全的括号弄没。
- 构造题可以合理严格化其性质使其更容易判定，有时这不会影响答案存在性。最值类构造可以增量法。
- 先右后下的行走时间问题（红绿灯模型）预处理 每个障碍在当前回合失效 后还要多少路程。
- DP 套 DP 中不要将内外两层混淆，尤其是可行性和计数之间。
- 树直径问题考虑枚举 直径的中点或中边。
- 斯特林分解别忘了
- 组合数的维护定式 ，还可以用于 组合数定列前缀和。
- 对于 DP，打表找（决策点）单调性、凸性，以及状压包含状态的关系。
- 总体要求选 min/max 方案，小部分同样是在某些不相干的值中求 min/max，那么小部分可以看作在这些值中做出一个选择。
- 树上分块 按需选方案（实在不行随机撒点摆烂，个数可以多一点）。比如路径问题一般只要求深度。
- 二维数组的合法子矩形问题，可以用扫描线、单调数据结构、悬线、并查集之类解决。找最简单实用的。
- 累赘而对总代价没影响的方案部分，可以在求解时忽略，先注重关键点。
- 数列操作问题前缀和和差分一定都要考虑，不要否决了一个忘了另一个。
- 贪心拿不稳的要数据分治。