一点点递推与二分

本文最后更新于:7 个月前

AcWing116. 飞行员兄弟

特性

  1. 每个开关只按一次
  2. 顺序无关紧要
  3. 数据范围很小,16个位置
  4. 要求步数和字典序最小

    拓展:高斯消元法,T208

    流程

  5. 枚举所有方案,0-2^16-1
  6. 按该方案对所有灯泡进行操作
  7. 判断灯泡是否全亮
    1. 若全亮,记录方案

      注意

      vector每次定义时都会初始化为空
      位运算方法的实用性

二分

思想(具有普适性)

  1. 确定一个区间,使得答案一定在区间内
  2. 找一个性质,满足
    1. 性质具有二段性
    2. 答案是二段性的分界点
  3. 判断终点M在该判断条件下是否成立
  4. 若更新方式写的是R = M则不做任何处理
  5. 若更新方式是L = M,则在计算M时+1
  6. 注意当两个端点非常接近时的合理性判断

整数二分具有离散性,需要考虑边界条件,而实数二分具有稠密性,因此边界条件可以不考虑,有单调性一定可以二分,没有单调性也有二分的可能

红色区间右端点

代码方面L和R的中间值计算时分子要补1(解决计算小区间情况)

1
2
3
4
5
6
while(L < R)
{
M = L+R+1/2;
if(M 红)L = M;
else R = M-1;
}

绿色区间左端点

1
2
3
4
5
6
while( L < R)
{
M = L+R/2;
if(M 绿) R = M;
else L = M + 1;
}

eg.数的范围

  • 特性
  1. 数组长度决定了数的范围
  2. 相同数字是分布在同一区间的位置
  3. 需要建立标号(位置)与值之间的对应关系
  • 步骤
  1. 先确定左右端点中的某个端点此处以左端点为例
  2. 目标为寻找首个大于等于x的q[mid]
  3. 构建二分查找
  4. 进行结果判断结果