找小“3”
序号：#40难度：困难时间限制：1000ms内存限制：10M
描述
给定一个奇数n，可得到一个由从1到n的所有奇数所组成的数列，求这一数列中数字3所出现的总次数。例如当n=3时，可得到奇数列：1,3，其中有一个数字3，故可得1
输入
一个奇数。表示n，0<n<9999999999。
输出
一个整数，表示从 1 到 n 的奇数列中，数字 3 出现的次数。
输入样例
1
3
35
复制样例
输出样例
0
1
7
#include<iostream>
#include<string.h>
#include<stdio.h>
#include<algorithm>
using namespace std;
typedef long long ll;
int bit[15];
ll n;
ll ans;
ll dp[15];
ll mypow(ll a,ll b)
{
if(b==0)return 2;
ll ret=1;
while(b--)ret*=a;
return ret;
}
ll get(ll p)
{
if(p==0)return 1;
ll tmp=1;ll res=0;
for(ll i=1;i<=p;i++)
{
res+=bit[i]*tmp;
tmp*=10;
}
return res;
}
ll dfs(ll pos,bool flag)
{
if(flag&&dp[pos]!=-1)return dp[pos];
if(pos==0)return 0;
ll x=flag?9:bit[pos];
ll res=0;
for(ll i=0;i<=x;i++)
{
if(i==3){
if(flag||i<x){res+=mypow(10,pos-1)/2;}
else {
res+=(get(pos-1)+1)/2;
}
res+=dfs(pos-1,flag||i<x);
}
else {
res+=dfs(pos-1,flag||i<x);
}
}
if(flag)dp[pos]=res;
return res;
}
int main()
{
//freopen("in.txt","r",stdin);
while(~scanf("%lld",&n))
{
memset(dp,-1,sizeof(dp));
int cnt=0;
while(n)
{
bit[++cnt]=n%10;
n/=10;
}
ans=dfs(cnt,0);
printf("%lld\n",ans);
}
return 0;
}