K 题解

· · 个人记录

题目大意：一个L位的十六进制数N，求从1到N这N个数（十六进制表示时）中有多少个数字K。

直接讲AC做法。要求1~N有多少个K，我们对问题进行分解，实际上就是求每一位上K能够出现多少次。我们发现，显然可以直接看成十进制意义下进行计算，等统计答案再转为十六进制即可，以N=31245,K=2为例，无非就分几种情况：小于K、等于K和大于K。

小于K的情况，我们看千位数1，那么这个位置上2能出现多少次，也就是锁定这一位是2，共有多少种可能的数字。由于最大值为1，先看万位最高位，可以发现能够取0,1,2，这样无论后面三位数取多少，都不会大于31245。而由于锁定了千位为2，且实际最大值千位是1小于2，那么最高位不能取3，所以这样就有 3\times16^3 种可能。我们设这一个数的前缀 pre 代表这一位前面的数，也就是千位1的 pre=3 ，同样地也有后缀 suf=245 ，答案即为 pre \times 10^{suf_{len}}，suf_len 为后缀的位数，也就是后边三位取什么都可以。

大于K的情况，我们看十位数4，这个位置上2能出现多少次，也就是锁定这一位是2，共有多少种可能的数字。我们看前三位，取0~312都是可以的，因为这位最大值4大于2，所以3122x一定也是满足题意的，那么最后一位不管取多少都是可以满足的，也就是313 \times 10^1 种，答案的形式是 (pre+1) \times 10^{suf_{len}}。

最后看等于K的情况，我们看百位数2，这个位置上2出现多少次，就需要分两部分讨论。首先肯定0~30是没有问题的，因为309xx也小于31245，这部分的答案就是 pre \times 10^{suf_{len}} 。但31就特殊，因为百位严格为2，所以后缀只能取0~45共suf+1个数，则等于K的情况总答案为pre \times 10^{suf_{len}}+suf+1。

最后统计的时候我们把每位的答案累加即可。注意原题为16进制，过程中随时取模，不要乘爆ll 。

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int N,k,ans,a[333],base[333]={1};
char K;
const int p=99999989;
string s;
int calc(char c){
    if(c>='A'&&c<='F'){
        return c-'A'+10;
    }
    return c-'0';
}
signed main(){
    cin>>N>>K>>s;
    k=calc(K);
    for(int i=1;i<=N;++i){
        base[i]=base[i-1]*16%p;
    }
    for(int i=0;i<N;++i){
        a[i]=calc(s[i]);
    }
    for(int i=0;i<N;++i){
        int pre=0,suf=0;
        for(int j=0;j<=i-1;++j)
            pre=(pre*16+a[j])%p;
        for(int j=i+1;j<N;++j)
            suf=(suf*16+a[j])%p;
        if(a[i]>k){
            ans=(ans+(pre+1)*base[N-i-1]%p)%p;
        }
        else if(a[i]==k){
            ans=(ans+suf+1+pre*base[N-i-1]%p)%p;
        }
        else 
            ans=(ans+pre*base[N-i-1]%p)%p;
    }
    cout<<ans;  
    return 0;
}

这份代码其实只有50pts。在某个月黑风高的夜晚，这本该被当作std的代码被神@LYYY爆杀掉了，经过熬夜奋战后菜只因出题人找到了更优方法，写下了下面这份货真价实的std。其实仅仅是给pre和suf加了个显然得不能再显然的预处理。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MAX=1e6+7;
int N,k,ans,a[MAX],base[MAX]={1}, pre[MAX]={0}, suf[MAX]={0};
char K;
const int p=99999989;
string s;
int calc(char c){
    if(c>='A'&&c<='F'){
        return c-'A'+10;
    }
    return c-'0';
}
signed main(){
    cin>>N>>K>>s;
    k=calc(K);
    for(int i=1;i<=N;++i){
        base[i]=base[i-1]*16%p;
    }
    for(int i=0;i<N;++i){
        a[i]=calc(s[i]);
    }
    for(int i=1;i<N;++i){
        pre[i]=(pre[i-1]*16+a[i-1])%p;
    }
    for(int i=N-2;i>=0;--i){
        suf[i]=(suf[i+1]+base[N-i-2]*a[i+1]%p)%p;
    }
    for(int i=0;i<N;++i){
        if(a[i]>k){
            ans=(ans+(pre[i]+1)*base[N-i-1]%p)%p;
        }
        else if(a[i]==k){
            ans=(ans+suf[i]+1+pre[i]*base[N-i-1]%p)%p;
        }
        else 
            ans=(ans+pre[i]*base[N-i-1]%p)%p;
    }
    cout<<ans;  
    return 0;
}

应神@LYYY要求，把他的读入16进制超级大暴力放上，以备参考（

int main()
{
    int n,c,x,ans=0;
    cin>>n;
    cin>>hex>>c>>x;
    for(int i=1;i<=x;++i)
    {
        int nw=i;
        while(nw)
        {
            if(nw%16==c) ++ans;
            nw/=16;
        }
    }
    cout<<ans<<endl;
    return 0;
}