题目链接:
http://acm.hdu.edu.cn/showproblem.php?pid=4734
题意：就是给一个函数 <nobr aria-hidden="true"> f(x) </nobr> <math xmlns="http://www.w3.org/1998/Math/MathML"> <mi> f </mi> <mo stretchy="false"> ( </mo> <mi> x </mi> <mo stretchy="false"> ) </mo> </math> 原来的十进制变成二进制，但是系数不变，最后得到的十进制数
数位 <nobr aria-hidden="true"> dp </nobr> <math xmlns="http://www.w3.org/1998/Math/MathML"> <mi> d </mi> <mi> p </mi> </math>是上次寒假集训学的，没怎么学会。。。现在才来补
这道题的记录的状态有点特别，是记录枚举到这一位的和与 <nobr aria-hidden="true"> f(A) </nobr> <math xmlns="http://www.w3.org/1998/Math/MathML"> <mi> f </mi> <mo stretchy="false"> ( </mo> <mi> A </mi> <mo stretchy="false"> ) </mo> </math> 的差值，大于 <nobr aria-hidden="true"> f(A) </nobr> <math xmlns="http://www.w3.org/1998/Math/MathML"> <mi> f </mi> <mo stretchy="false"> ( </mo> <mi> A </mi> <mo stretchy="false"> ) </mo> </math> 的直接就不要了
按照哪位大佬的说法，我们正常来写的话，就应该是记录现在的 <nobr aria-hidden="true"> sum </nobr> <math xmlns="http://www.w3.org/1998/Math/MathML"> <mi> s </mi> <mi> u </mi> <mi> m </mi> </math>，以及每次的 <nobr aria-hidden="true"> f(A) </nobr> <math xmlns="http://www.w3.org/1998/Math/MathML"> <mi> f </mi> <mo stretchy="false"> ( </mo> <mi> A </mi> <mo stretchy="false"> ) </mo> </math>，然后来比较进行取舍，但是每个 <nobr aria-hidden="true"> pos </nobr> <math xmlns="http://www.w3.org/1998/Math/MathML"> <mi> p </mi> <mi> o </mi> <mi> s </mi> </math> 的 <nobr aria-hidden="true"> sum </nobr> <math xmlns="http://www.w3.org/1998/Math/MathML"> <mi> s </mi> <mi> u </mi> <mi> m </mi> </math>不同吧，而且每次询问的 <nobr aria-hidden="true"> f(A) </nobr> <math xmlns="http://www.w3.org/1998/Math/MathML"> <mi> f </mi> <mo stretchy="false"> ( </mo> <mi> A </mi> <mo stretchy="false"> ) </mo> </math> 也不同，哇~那就要把这两种状态都记录下来，内存根本装不下，然后就想到记录两个的差值，真是太 <nobr aria-hidden="true"> TM </nobr> <math xmlns="http://www.w3.org/1998/Math/MathML"> <mi> T </mi> <mi> M </mi> </math> 的机智了~
#include"bits/stdc++.h"
#define out(x) cout<<#x<<"="<<x
#define C(n,m) ((long long)fac[(n)]*inv[(m)]%MOD*inv[(n)-(m)]%MOD)
using namespace std;
typedef long long LL;
const int maxn=1e5+5;
const int MOD=1e9+7;
int tot,a[20];
map<int,int>dp[20];
LL f(LL x)
{
if(x==0)return 0;
LL ans=f(x/10);
return (ans<<1)+x%10;
}
LL dfs(int pos,int sum,bool lim)
{
if(sum>tot)return 0; //大于f(A)的直接就不要了
if(pos==-1)return 1;
if(lim==0&&dp[pos][tot-sum])return dp[pos][tot-sum];
int up=lim?a[pos]:9;
LL cnt=0;
for(int i=0;i<=up;i++)
{
cnt+=dfs(pos-1,sum+i*(1<<pos),lim&&i==up);
}
if(lim==0)dp[pos][tot-sum]=cnt; //以差值作为记录的状态
return cnt;
}
LL solve(LL n)
{
int pos=-1;
while(n)
{
a[++pos]=n%10;
n/=10;
}
return dfs(pos,0,true);
}
int main()
{
int T;
cin>>T;
for(int Case=1;Case<=T;Case++)
{
int A,B;
cin>>A>>B;
tot=f(A);
cout<<"Case #"<<Case<<": "<<solve(B)<<endl;
}
}
京公网安备 11010502036488号