信息与未来 2024真题解析- 幸运数字

B3978 [信息与未来 2024] 幸运数字

题目描述

如果一个正整数的二进制表示中，每个比特（

或

）的左边或右边都至少有一个相同的比特，Dr. X 就认为它是一个“幸运数字”。例如:

有落单的

，它不是幸运数字。

有落单的

，它不是幸运数字。

是幸运数字。

是幸运数字。

对于给定的

和

，Dr. X 希望你求出

中幸运数字的数量。

输入格式

输入空格分隔的整数

和

。

输出格式

输出一行一个整数，代表

和

之间幸运数字的数量。

输入输出样例 #1

输入 #1

1 100

输出 #1

14

输入输出样例 #2

输入 #2

4096 65535

输出 #2

1364

说明/提示

对于

的数据,满足

。

本题原始满分为

。

参考题解

#include <bits/stdc++.h>

using namespace std;

/**

* 将十进制整数转换为二进制字符串

* @param n 需要转换的正整数

* @return 二进制表示的字符串（无前导零）

*/

string to_binary(int n) {

  string s;

  while (n > 0) {

      // 每次取余得到最低位，并将字符插入到字符串最前面

      // 例如：6%2=0 3%2=1 1%2=1 最终得到"110"

      s = char((n % 2) + '0') + s;

      n /= 2;  // 右移一位

  }

  return s;  // 根据题目n≥1，所以s不会为空

}

/**

* 判断数字是否为幸运数字

* @param n 需要判断的正整数

* @return true: 满足幸运数字条件, false: 不满足

*/

bool is_lucky(int n) {

  string s = to_binary(n);

  int len = s.length();

  // 单比特情况直接排除（如1的二进制"1"）

  if (len == 1) return false;

  // 遍历每个二进制位（从高位到低位）

  for (int i = 0; i < len; ++i) {

      if (i == 0) {  // 最高位只需检查右侧

          if (s[i+1] != s[i]) {

              return false;  // 例: "10..." 最高位1右侧是0，不满足

          }

      } elseif (i == len-1) {  // 最低位只需检查左侧

          if (s[i-1] != s[i]) {

              return false;  // 例: "...01" 最低位1左侧是0，不满足

          }

      } else {  // 中间位需检查左右任意一侧

          if (s[i-1] != s[i] && s[i+1] != s[i]) {

              return false;  // 例: "...010..." 中间的1两侧都是0，不满足

          }

      }

  }

  return true;  // 所有位都通过检查

}

int main() {

  // 输入处理

  int a, b;

  cin >> a >> b;

  int count = 0;

  // 遍历区间内所有数字

  for (int num = a; num <= b; ++num) {

      if (is_lucky(num)) {

          ++count;

      }

  }

  // 输出结果

  cout << count << endl;

  return 0;

}