位运算
常用运算符
- 按位与
& - 按位或
| - 按位异或
^ - 取反
~ - 左移
<< - 右移
>> - 非负整数原码反码补码都一样！
- 运算符优先级不清楚就打括号！
- C++运算符优先级
应用场景
- 用二进制位表示元素的存在情况
- 题目要求进行位运算
- 获取二进制的某一位
int getBit(int a, int b) {
return (a >> b) & 1;
}
- 将一个数二进制某一位设为 0/1/取反
int unsetBit(int a, int b) {
return a & ~(1 << b);
}
int setBit(int a, int b) {
return a | (1 << b);
}
int flapBit(int a, int b) {
return a * (1 << b);
}
std::bitset
- 存储 \(0/1\) 的大小不可变的容器
bitset<SIZE> bs; bs.count()返回 \(1\) 的个数bs.size()返回bs的位数bs.any()返回是否有 \(1\)bs.none()返回是否全部为 \(0\)bs.all()返回是否全部为 \(1\)bs.reset(x)x为 \(0\) 或 \(1\)，将bs中元素全部设为xoperator：[]，==，!=（支持位运算！）
位运算例题
- P1100 高低位交换
- 注意读入数据的类型为
unsigned int - 左移右移的巧妙应用
- AC记录
- 注意读入数据的类型为
- B3632 集合运算1
- 交集 \(∩\) 相当于位运算的
&按位与 - 并集 \(∪\) 相当于位运算的
|按位或 - AC记录
- 交集 \(∩\) 相当于位运算的
搜索
暴力枚举所有方案（深度优先搜索）
void dfs(int n, ...) {
if (所有状态均枚举完成) {
...
return; // 一定要返回
}
for (遍历当前状态所有扩展可能性) {
if (判断扩展状态是否合法) {
调整状态
dfs(n + 1, ...); // 向深层递归搜索
复原状态（一定要回溯！！）
}
}
}
图上的深度优先遍历（用 vis 数组跳过已经走过的点）
void dfs(int u) { // 当前的位置（节点）
vis[u] = 1;
for (与 u 相邻的节点 v) {
if (!vis[v]) dfs(v);
}
}
dfs(s); // 从起点开始
图上的广度优先遍历（使用队列）
void bfs() {
queue<T> q;
q.push(s); // 起点入队
vis[s] = 1;
while (!q.empty()) {
T u = q.front();
q.pop();
for (与 u 相邻的节点 v) {
if (!vis[v]) {
q.push(v);
vis[v] = 1; // 必须在此处标记，避免某节点多次入队
}
}
}
}
暴力搜索例题
图上的深度、广度遍历例题
- P5318 查找文献
- 图上遍历模板题，无任何思维难度。
- AC记录
搜索拓展-记忆化搜索
搜索拓展-剪枝
- 最优性剪枝：如果当前方案已经比目前最优解更差，直接停止
- 可行性剪枝：如果当前方案不可用，直接停止
- 例题：B3624 猫粮规划
贪心
- 注意：一定要满足无后效性且能大概证明其正确性！！
- 大胆假设，小心求证！！
- 证明贪心正确性
- 反证法（交换元素）
- 归纳法
- 证伪贪心正确性
- 反例法
- 例题：P1208 混合牛奶 Mixing Milk
- 参考：P2240 部分背包问题
- 例题：P4995 跳跳！
二分
二分查找
- 在一个 有序！！ 序列中查找某一元素的算法（\(O(logn)\)），每次将搜索范围缩小一半
- 例题：P1947 猜数（交互题）
二分答案模板
题目答案特点：具有有界性、单调性！！
直接求解难，但是判定某解是否符合题意相对容易！
int binary_search(int L, int R, int k) {
int l = L, r = R, ans = -1;
while (l <= r) { // 必须写 l <= r！！！
int mid = (l + r) >> 1;
if (check(mid)) { // 自己写 check 函数
把 mid 以某种方式赋值给 ans
l = mid + 1; 或 r = mid - 1;
} else {
l = mid + 1; 或 r = mid - 1;
}
}
return ans;
}
- 例题：P2678 跳石头
- 例题：P9455 塔台超频
- 例题：P1824 进击的奶牛
前缀和
- 一种重要的预处理方式，大大降低查询的时间复杂度
- 一维前缀和：\(f_i = f_{i-1} + a_i\)
- 二维前缀和：\(f[i][j] = f[i-1][j] + f[i][j-1] - f[i-1][j-1] + a[i][j]\)
- 多维前缀和：使用容斥原理解决
- 查询 \([i,j]\) 的区间和：\(f_j - f_{i-1}\)
差分
- 前缀和的逆运算
- 主要作用：多次修改、一次查询（单点修改，区间查询）
- 使用差分：
f[l] += x，f[r += 1] - x：把区间 \([l,r]\) 内所有的数字都加上 \(x\)
双指针
- 同时使用两个指针
- 利用区间有序性
- 维护区间信息
- 快慢指针：在单链表中找环
- 跑步套圈，一个指针一次走一步，一个指针一次走两步
- 两个指针相遇后，将其中一个移到表头，让两者都一步一步走，再度相遇的位置就是环的起点
- 例题：P1102 A-B数对
- 例题：P1147 连续自然数和