法一:直接暴力循环取数位求解
简单粗暴不多说直接上代码
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n, x;
cin >> n >> x;
int count = 0;
for (int i = 1; i <= n; i++)
{
int m = i;
while (m != 0)
{
if (m % 10 == x)
{
count++;
}
m /= 10;
}
}
cout << count;
return 0;
}
缺点也很明显就是耗时长,大概18ms,而且n如果更大就更耗时了。
法二:分别对各位进行统计求解
顾名思义,就是从个位开始直接判断存在多少个符合的,然后接着十位,百位……最后累加起来。 写出来总是容易漏情况,所以删删改改了很多次,不过也是改好ac了。
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n, x;
cin >> n >> x;
int N = n;
int C = 0;
int count = 0;
while (N != 0)
{
C++;
N /= 10;
}//C也就是数位长度
if (x != 0)
//这里把x=0和其他分开讨论,因为0比较特殊,不能放在首位,而且其他数都会比他大,且n从1开始所以个位0少一个
{
if (n < 10)//若n是个位数
{
count++;
}
else if (n < 100)//若n是两位数
{
count += n / 10;
if (n % 10 >= x)
{
count++;
}
//上面是判断个位有多少个等于x
//比如n=45,x=5
//那么5,15,25,35这里先计四个,因为40往上需要判断最后一位数与x大小,看是否能取
//45最后一位是5,可以取所以count++,所以个位一共是4+1=5。
if (n / 10 > x)
{
count += 10;
}
if (n / 10 == x)
{
count += n % 10 + 1;
}
//因为是两位数的判断,所以接下来就是十位了
//n=11,x=1来举例
//个位累计1,11所以是2
//n/10==x,所以10,11都符合,这里n%10就是个位,因为从0开始数所以要加1
//现在count就是4了
}
else if (n >= 100)
//若n是三位数及以上,因为最高位和个位需要特判,其他位有规律可循所以接下来可以一套走完。
{
count += n / 10;
if (n % 10 >= x)
{
count++;
}//上面个位判断同理
for (int i = 1; i <= C - 2; i++)//这里是判断个位和最高位中间的数位
{
count += ((n / (int)pow(10, i + 1)) * (int)pow(10, i));
//n=121,x=1举例
//个位一共13个符合,然后这里判断十位因为121是三位数,如果是四位数那这里就判断十位和百位
//那么也就是计算1为十位时有多少种情况
//那就是百位乘上个位的数量,其中百位可以为0也就是从1开始数到100那段
//也就是10,11...19一共十个
//这里乘上10是因为我们求的是十位,如果是百位,那么就是100
//因为比如n=3210,那么3100,3101...3199一共100个都符合所以乘上100
//这里121只乘了一次10是因为我们只能判断百位为0时都能取,如果百位是1,那么十位不一定能取到1
//顺带一提这里pow是小数计算所以必须强转不然会出错。
if (n / (int)pow(10, i) % 10 == x)//所以我们取n的十位进行判断
{
count += n % (int)pow(10, i) + 1;//如果x是111那就是110,111符合,也就是个位1再加1
}
else if (n / (int)pow(10, i) % 10 > x)//如果121来说就是110到119符合,所以加10
{
count +=(int)pow(10, i) ;
}
}
if (n / (int)pow(10, C - 1) > x)//接下来就是判断最高位了,121来说就是百位
{
count += (int)pow(10, C - 1);
}
if (n / (int)pow(10, C - 1) == x)//对于121来说就是100,101...121一共22个符合百位为1
{
count += n % (int)pow(10, C - 1) + 1;
}
}
}
else if (x == 0)
{
if (n < 10)//n从1开始所以n如果是个位数那没有符合情况的
{
count = 0;
}
else if (n < 100)
{
count += n / 10;//因为只能从10开始所以十位多少就有多少
}
else if (n >= 100)
{
count += n / 10;//判断个位,这里和之前x!=0不一样,因为所有个位都>=0而且n从1开始数所以这里个位这么写
for (int i = 1; i <= C - 2; i++)
{
count += ((n / (int)pow(10, i + 1)-1) * (int)pow(10, i));//这里括号里比上面多减1
//这是因为从1开始数到n其中我们取的那个数位如果等于0就相当于最高位为0是错误的
//之前不减1是因为比如n=121,x=1,我从百位为0开始加就是10,11,12...19,然后判断百位为1时十位能不能取到1
//那么这里举例n=101,x=0,那我们从百位为0开始加,那么有00,01这种数吗?所以不对要减去1,我们只能从百位为1的时候开始加,100,101......
if (n / (int)pow(10, i) % 10 == x)
{
count += n % (int)pow(10, i) + 1;
}
else if (n / (int)pow(10, i) % 10 > x)
{
count += (int)pow(10, i);
}//这里和上面x!=0的情况一个意思
//最高位不能为0所以不用判断
}
}
}
cout << count;
return 0;
}
}
//码字真累qwq,所以缺点是比较难想有点烦,优点也显而易见,对于n数据很大的时候速度也快,这里测是2ms。