计数问题

定义

给定一个整数$x$，求$0 - x$的整数中数字$i$（可取0~9）出现的次数，记为 $count(x,i)$

例如，$count(10,0)=2，count(11,1)=4$

链接：https://www.acwing.com/problem/content/340/

算法思路

• 对于$x和i$，计算$i$在$x$的每一位出现的次数，相加即为结果
  • 设$x=abcdefg，i=5，计算5在x的第4位(d的位置)出现的次数$
  • 这种情况下数字的形式为$xxx5yyy$
  • 接下来进行分类讨论
    • $000=<xxx<abc，此时xxx5yyy一定小于adcdefg，所以方案数为（abc-1-0+1）*1000$
    • $xxx==abc,此时需要再次分类讨论$
      · $ d<5，此时xxx5yyy一定大于abcdefg，所以方案数为0 $
      · $ d=5，此时要使xxx5yyy<=abcdefg，yyy应该取000-efg，方案数为efg+1 $
      · $d>5，此时xxx5yyy一定小于abcdefg，yyy可取000-999，方案数为1000$
  • 累加次数即为结果
• 注意特判，即当$i==0$时，$xxx是不能取000的，只能取1，因为若xxx取000，yyy也取000，那么xxxiyyy就是0000000，$$当i在不同的位置时，0000000会被多次计算，这样0这个数就被重复计算了很多次，$$所以xxx不能从0开始，而应该从1开始$
• 当$i==0$时，应该从第二位开始计算，第一位为0没有合法数字
• 因为把000去掉了，所以最后记得加上0，也就是$ans++$

代码

int count(int x,int c)
{
    string s=convert<string>(x);
    int ans=0;
    int len=s.size();
    for(int i=0;i<len;i++)
    {
        if(!i&&c==0) continue;
        string t=s.substr(0,i);
        if(t!="") 
        {
            int pre=convert<int>(t);
            if(c==0)
            {
                ans+=(pre-1)*pow(10,len-i-1);
            }
            else
            {
                ans+=pre*pow(10,len-i-1);
            }
        }
        if(s[i]-'0'==c)
        {
            int end=1;
            string p=s.substr(i+1);
            if(p!="") end=convert<int>(s.substr(i+1))+1;
            ans+=end;
        }
        else if(s[i]-'0'>c)
        {
            ans+=pow(10,len-i-1);
        }
    }
    if(c==0) ans++;
    return ans;
}