算法设计策略杂谈(二)
算法设计中,二进制和状态压缩
是很常见的处理dp问题,搜索问题的关键
二分,序列问题,单调性也常常一起出现
二进制状态压缩
- 取出 在二进制下的第 位:
- 取出 在二进制下的第 位(后 位):
- 把整数 在二进制表示下的第 位取反:
- 对整数 在二进制表示下的第 位赋值:
- 对整数 在二进制表示下的第 位赋值:
位运算每一位都是相对独立的
一般来说,需要从高位到低位每个 bit 依次检查
决定该位填 0 或者填 1
如果这一位填的是 0,那么对于这个数,该位无贡献
否则的话,应该要将
1 | val += (1 << bit) |
1 | const int maxn = 1e5 + 10; |
状态压缩二维矩阵
1 | typedef pair<int, int> PII; |
状态依赖与递推
1 | const int inf = 0x3f3f3f3f; |
计算几何问题中的精度处理
在解决计算几何问题的时候,常常涉及到四舍五入相关的输出
在处理此类问题, 特别是比如距离 dist 结果时
可以用以下代码
1 | ll dx = ans1.first - ans2.first, dy = ans1.second - ans2.second; |
序列问题
无长度限制的最大子段和
1 | const int maxn = 100 + 10; |
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 算法小站!
评论