【每日一题】【枚举】【估计时间复杂度】[蓝桥杯 2024 省 B] 好数 C++
P10424 [蓝桥杯 2024 省 B] 好数
[蓝桥杯 2024 省 B] 好数
题目描述
一个整数如果按从低位到高位的顺序，奇数位（个位、百位、万位……）上的数字是奇数，偶数位（十位、千位、十万位……）上的数字是偶数，我们就称之为“好数”。
给定一个正整数 N N N，请计算从 1 1 1 到 N N N 一共有多少个好数。
输入格式
一个整数 N N N。
输出格式
一个整数代表答案。
样例 #1
样例输入 #1
24
样例输出 #1
7
样例 #2
样例输入 #2
2024
样例输出 #2
150
提示
样例 1 解释
24 24 24 以内的好数有 1 , 3 , 5 , 7 , 9 , 21 , 23 1,3,5,7,9,21,23 1,3,5,7,9,21,23，一共 7 7 7 个。
数据规模与约定
- 对于 10 % 10\% 10% 的测试数据， 1 ≤ N ≤ 100 1 \leq N \le 100 1≤N≤100。
- 对于全部的测试数据， 1 ≤ N ≤ 1 0 7 1 \le N \leq 10^7 1≤N≤107。
做题思路
做蓝桥杯的题首先要看数据规模和运行时间，第二看时间复杂度。
这道题最暴力的做法就是从1到 n n n枚举，然后每一个数字都判断一下是否为好数即可。
从时间复杂度来看
粗略估计:
从1到n每次最多内循环7次,总共 O ( 7 N ) O(7N) O(7N)
因为 1 ≤ N ≤ 1 0 7 1 \le N \leq 10^7 1≤N≤107。
所以不会超时。
顺便说说如何判断是否为好数。
一个数按位且1后是判断最后一位(最低位)是为奇数，如果按位且1后答案为1那么最低位就是奇数；否则为偶数。
这里还用到了按位异或判断是否一致，也就说奇数位（个位、百位、万位……）上的数字是不是奇数的判断。
if((x&1) ^ k)return false;
如果不看数据规模和运行时间、时间复杂度，首先想着优化就完蛋了。
时间复杂度分析
粗略估计:
从1到n每次最多内循环7次,总共 O ( 7 n ) O(7n) O(7n)
代码
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
bool check(int x){bool k = true;while(x){if((x&1) ^ k)return false;k^=true;x/=10;}return true;
}
int main(){int n,cnt = 0;cin >> n;for(int i=1;i<=n;i++)if(check(i))cnt++;cout << cnt;return 0;
}