「hdu3555」Bomb

2014年12月12日3,5920

Problem Description

The counter-terrorists found a time bomb in the dust. But this time the terrorists improve on the time bomb. The number sequence of the time bomb counts from 1 to N. If the current number sequence includes the sub-sequence “49”, the power of the blast would add one point.
Now the counter-terrorist knows the number N. They want to know the final points of the power. Can you help them?

Input

The first line of input consists of an integer T (1 <= T <= 10000), indicating the number of test cases. For each test case, there will be an integer N (1 <= N <= 2^63-1) as the description.
The input terminates by end of file marker.

Output

For each test case, output an integer indicating the final points of the power.

Sample Input

3 1 50 500

Sample Output

0 1 15

Hint

From 1 to 500, the numbers that include the sub-sequence “49” are “49”,”149″,”249″,”349″,”449″,”490″,”491″,”492″,”493″,”494″,”495″,”496″,”497″,”498″,”499″, so the answer is 15.

题解

复习数位dp。。。

好像我的写法和网上都不太一样

预处理f[i][j]表示长度为i开头为j的不满足条件的数字个数

ans=n-dp(n)

然后就可以dp了。。。诶好像是废话

顺便说下dp过程

比如78915 L=5

首先算出 1-9999

for(int i=1;i<L;i++)
for(int j=1;j<=9;j++)
ans+=f[i][j];

然后是10000-69999

for(int i=1;i<cur;i++)ans+=f[L][i];

现在限定第一位为7，算70000-77999

。。。。第二位位8，算78000-78899

以此类推

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<cmath>
#define inf 0x7fffffff
#define ll long long
using namespace std;
inline ll read()
{
	ll x=0;char ch=getchar();
	while(ch>'9'||ch<'0')ch=getchar();
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x;
}
ll base[20];
int T;
ll n,f[20][10];
void pre()
{
	base[1]=1;for(int i=2;i<=19;i++)base[i]=base[i-1]*10;
	for(int i=0;i<=9;i++)f[1][i]=1;
	for(int i=2;i<=19;i++)
		for(int j=0;j<=9;j++)
			for(int k=0;k<=9;k++)
				if(j!=4||k!=9)
					f[i][j]+=f[i-1][k];
}
ll dp(ll x)
{
	int L=19,cur,pre;
	ll ans=0;
	while(base[L]>x)L--;
	for(int i=1;i<L;i++)
		for(int j=1;j<=9;j++)
			ans+=f[i][j];
	cur=x/base[L];x%=base[L];
	for(int i=1;i<cur;i++)ans+=f[L][i];
	if(L==1)ans++;
	pre=cur;
	for(int i=L-1;i;i--)
	{
		cur=x/base[i];x%=base[i];
		if(i==1)
		{
			for(int j=0;j<=cur;j++)
				if(pre!=4||j!=9)ans+=f[i][j];
		}
		else 
		{
			for(int j=0;j<cur;j++)
				if(pre!=4||j!=9)ans+=f[i][j];
		}
		if(pre==4&&cur==9)break;
		pre=cur;
	}
	return ans;
}
int main()
{
	pre();
	T=read();
	while(T--)
	{
		n=read();
		cout<<n-dp(n)<<endl;
	}
	return 0;
}

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<algorithm>

#include<cstring>

#include<cmath>

#define inf 0x7fffffff

#define ll long long

using namespace std;

inline ll read()

{

ll x=0;char ch=getchar();

while(ch>'9'||ch<'0')ch=getchar();

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x;

}

ll base[20];

int T;

ll n,f[20][10];

void pre()

{

base[1]=1;for(int i=2;i<=19;i++)base[i]=base[i-1]*10;

for(int i=0;i<=9;i++)f[1][i]=1;

for(int i=2;i<=19;i++)

for(int j=0;j<=9;j++)

for(int k=0;k<=9;k++)

if(j!=4||k!=9)

f[i][j]+=f[i-1][k];

}

ll dp(ll x)

{

int L=19,cur,pre;

ll ans=0;

while(base[L]>x)L--;

for(int i=1;i<L;i++)

for(int j=1;j<=9;j++)

ans+=f[i][j];

cur=x/base[L];x%=base[L];

for(int i=1;i<cur;i++)ans+=f[L][i];

if(L==1)ans++;

pre=cur;

for(int i=L-1;i;i--)

{

cur=x/base[i];x%=base[i];

if(i==1)

{

for(int j=0;j<=cur;j++)

if(pre!=4||j!=9)ans+=f[i][j];

}

else

{

for(int j=0;j<cur;j++)

if(pre!=4||j!=9)ans+=f[i][j];

}

if(pre==4&&cur==9)break;

pre=cur;

}

return ans;

}

int main()

{

pre();

T=read();

while(T--)

{

n=read();

cout<<n-dp(n)<<endl;

}

return 0;

}

« 「BZOJ1833」[ZJOI2010] count 数字计数「数位动规练习」准考证 »

hzwer.com _ Home | http://hzwer.com

「hdu3555」Bomb

分类目录

热门文章

Myfriends

近期评论