小米oj-找小“3” 模拟+思维

题目
思路：由于数位最大为10，所以我们可以分出所有3出现位置和个数的所有情况，最多也就 $2^{10}$210种情况，然后对每种可行情况进行 $dfs$dfs.
$dfs$dfs进行的每一层说明，前面 $0-now$0−now都是跟给定的数字相同的，那么当前这一位就有两种取法，一个是小于给定的数字，一个是等于给定的数字。
$1.$1.小于给定的数字我们好解决，后面的位置没有被3放的位置我们可以放任意的数字，但是最后一位不能放偶数。
$2.$2.直接递归下一位即可。
$3.$3.若当前已经递归完成，若最后没有放三且是偶数则贡献为0，否则为1.
详细细节见代码

#include<iostream>
#include <cstring>
#define LL long long
#define fi first
#define se second
#define mp make_pair
#define pb push_back
 
using namespace std;
 
LL gcd(LL a,LL b){return b?gcd(b,a%b):a;}
LL lcm(LL a,LL b){return a/gcd(a,b)*b;}
LL powmod(LL a,LL b,LL MOD){if(b<=0)return 1;LL ans=1;while(b){if(b%2)ans=ans*a%MOD;a=a*a%MOD;b/=2;}return ans;}
const int N = 2e5 +11;
char a[33];
int res[333],cnt,n,q[11];
LL ans;
LL f(int x,int now){
 	int mid=0;
 	if(now==n)return ((res[n-1]==0&&(a[n-1]-'0')%2==0)?0:1);
 	for(int i=now+1;i<n;i++)mid+=res[i];
 	if(res[now]){
 		if(a[now]-'0'<3)return 0;
 		if(a[now]-'0'==3)return f(x,now+1);
 		if(now==n-1)return 1;
 		return (res[n-1]?powmod(9,n-now-mid-1,1e18):(powmod(9,n-now-mid-1,1e18)/9*4));
 	}
 	if(a[now]=='0')return f(x,now+1);
 	if(now==n-1){
 		return a[n-1]-'0'+1-q[a[n-1]-'0']-(a[n-1]-'0'>=3);
 	}
 	return max(0,a[now]-'0'-(a[now]-'0'>3))*(res[n-1]?powmod(9,n-now-mid-1,1e18):(powmod(9,n-now-mid-1,1e18)/9*4))+(a[now]!='3'?f(x,now+1):0);
}
int main(){
 	ios::sync_with_stdio(false);
 	cin>>a;
 	n=strlen(a);
 	q[0]=1;q[1]=1;q[2]=2;q[3]=2;q[4]=3;q[5]=3;
 	q[6]=4;q[7]=4;q[8]=5;q[9]=5;
 	for(int i=0;i<(1<<n);i++){
 		memset(res,0,sizeof res);
 		cnt=0;
 		for(int j=0;j<n;j++){
 			if((1<<j)&i)res[j]=1,cnt++;
 		}
 		if(res[0]&&a[0]-'0'<3)continue;
 		if(cnt>n)continue;
 		ans+=1ll*cnt*f(i,0);
 	}
 	cout<<ans<<endl;
 	return 0;
} 

看了大佬们的另一种写法，感觉智商压制了。。。。。。。。

#include <cstdio>
#include <iostream>
using namespace std;
typedef long long ll;
int main(){
    ll n;
    while(~scanf("%lld",&n)){
        ll ans=0,t1=1,k=0,no;
        while(n){
            ll t=t1;
            if(t1==1)t*=2;
            ans+=n/10*t/2;//这一位是3，前不为0
            cout<<n/10*t/2<<endl;
            no=n%10;
            if(no>3)ans+=t/2;//前面都是0
            else if(no==3)ans+=(t1==1?1:(k+1)/2);
            k+=no*t1;
            t1*=10;
            n/=10;
        }
        printf("%lld\n",ans);
    }
    return 0;
}

这种做法直接考虑每一位，两种情况，这一位是3前面不是0，这一位是3前面是0，然后对3出现的次数直接累加即可。。，复杂度
$O\left(数位\right)$O(数位)…