数位dp-Bomb

难受啊!!越做题是越感觉菜,这个又被几个坑给卡住了(只有我这个学渣才会卡)

坑点:1.考虑n是否已包含49,有的话还要再+1.

2, 注意从最高开始考虑时,再判断时要考虑它本身为0的情况,.比如n=5701,在考虑最高位时,其实是在考虑0~5000所能组成的含49的数的个数,这个是包含f[i][2]中的前导0并且千位最高位也可为0

#include<bits/stdc++.h>
using namespace std;
//#define LL long long
typedef __int64 LL;
LL f[][];
int n[];
void init()
{
// f[1][9]=1;
// f[1][0]=10;
memset(f,,sizeof(f));
f[][]=;
for(int i=; i<=; i++)
{
f[i][]=f[i-][]*+f[i-][];
f[i][]=f[i-][];
f[i][]=f[i-][]*-f[i-][];
}
}
int main()
{
int t;
scanf("%d",&t);
init();
// for(int i=1;i<=20;i++)
// printf("%lld\n",f[i][1]+f[i][0]);
while(t--)
{
// string s;
// cin>>s;
// for(int i=0; i<s.size(); i++)
// n[s.size()-i]=s[i]-'0';
LL a;
scanf("%I64d",&a);
int len=;
LL ans=;
int flag=;
a++;
while(a)
{
n[++len]=a%;
a/=;
}
n[len+]=;
for(int i=len; i>=; i--)
{
ans+=n[i]*f[i-][];
if(flag)
ans+=n[i]*f[i-][];
else if(n[i]>)
ans+=f[i-][];
if(n[i+]==&&n[i]==)
flag=;
}
printf("%I64d\n",ans);
}
return ;
}
上一篇:关于 Android 进程保活,你所需要知道的一切


下一篇:edge.js架起node.js和.net互操作桥梁