题解：B4516 [四川青少年 C++ 算法设计大赛 2025] 醒来的统计

Mayuteng20121224 · 2026-04-25 10:07:12 · 题解

题目传送门

先浅浅看一下标签：二分和数学。

二分想到二分答案，数学则想到数位拆分。

所以本题的核心思想是二分答案和数位统计。

因为数字越大，1 至 n 内指定数字出现次数只会增加或不变，答案具有严格单调性，满足二分条件。

通用拆分方式

对当前位 p（个位、十位、百位……），将 n 拆分为：

注意事项：

1. 不开 long long 见祖宗。

2. 在拆位时，假如 x=0，那么就要处理一下前导零，避免统计前导零。

时间复杂度：O(\log^2 n)。

AC Code:

#include<bits/stdc++.h>
using namespace std;
using ll=long long;//必须要有，否则炸了别怪我
ll x,y;
//计算1~n中数字x出现的总次数
ll count(ll n)
{
    if(n<0)return 0;
    ll r=0,p=1;
    for(;p<=n;p*=10)//数位拆分
    {
        ll h=n/(p*10);
        ll c=(n/p)%10;
        ll l=n%p;
        if(x==0)//判断前导零
        {
            if(h==0)continue;//避免统计前导零
            if(c>x)r+=h*p;
            else if(c==x)r+=(h-1)*p+l+1;
            else r+=(h-1)*p;
        }
        else
        {
            if(c>x)r+=(h+1)*p;
            else if(c==x)r+=h*p+l+1;
            else r+=h*p;
        }
    }
    return r;
}
int main(){
    cin>>x>>y;
    //二分答案
    ll l=0,r=1e18,ans=0;
    while(l<=r)
    {
        ll m=l+r>>1;
        if(count(m)<=y)ans=m,l=m+1;
        else r=m-1;
    }
    cout<<ans;
    return 0;
}