传送门:http://acm.hdu.edu.cn/showproblem.php?pid=4734
数位DP。
用dp[i][j][k] 表示第i位用j时f(x)=k的时候的个数,然后需要预处理下小于k的和,然后就很容易想了
dp[i+1][j][k+(1<<i)]=dp[i][j1][k];(0<=j1<=j1)
AC代码:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cstdlib>
#include <cmath>
#include <vector>
#include <list>
#include <deque>
#include <queue>
#include <iterator>
#include <stack>
#include <map>
#include <set>
#include <algorithm>
#include <cctype>
using namespace std;
typedef __int64 xiaohao;
typedef long long LL;
const int N=7000;
const int INF=0x3f3f3f3f;
const double PI=acos(-1.0);
const double eps=1e-7;
int dp[12][12][N];
int tsum[12][12][N];
int w[20];
void init()
{
memset(dp,0,sizeof(dp));
dp[0][0][0]=1;
int n=10;
for(int i=0;i<12;i++)
{
for(int j=0;j<n;j++)
{
for(int k=0;k<N-1;k++)
{
for(int k1=0;k1<n;k1++)
{
int t1=k+k1*(1<<i);
dp[i+1][k1][t1]+=dp[i][j][k];
}
}
}
}
memset(tsum,0,sizeof(tsum));
for(int i=1;i<12;i++)
{
for(int j=0;j<n;j++)
{
for(int k=0;k<N-1;k++)
{
tsum[i][j][k]=tsum[i][j][k-1]+dp[i][j][k];
}
}
}
}
int f(int x,int fa)
{
if(x==0) return 0;
int len=0;
int flag=0;
while(x)
{
w[++len]=x%10;
x/=10;
}
int tsum1=0;
for(int i=len;i>=1;i--)
{
for(int k=0;k<w[i];k++)
{
tsum1+=tsum[i][k][fa-flag];
}
flag+=(w[i])*(1<<(i-1));
if(fa<flag)
break;
}
return tsum1;
}
int main()
{
init();
int cas;
while(~scanf("%d",&cas))
{
for(int q=1;q<=cas;q++)
{
int a,b;scanf("%d%d",&a,&b);
int len=0;
int fa=0;
while(a)
{
int t1=a%10;
fa+=(1<<(len))*t1;
len++;
a/=10;
}
int ans=f(b+1,fa);
printf("Case #%d: %d\n",q,ans);
}
}
return 0;
}
分享到:
相关推荐
ACM/ICPC 2010年多校联合第十场第九题的解题报告及代码,AC代码有三个,最好的是src
浙江大学在线论坛,衡阳市第八中学信息学奥赛论坛,杭州电子科技大学在线论坛,浙江师范大学ACM/ICPC论坛。 浙江大学在线题库:http://acm.zju.edu.cn/problems.php 浙江工业大学在线题库:http://acm.zjut.edu.cn ...
几个程序设计的训练网站给大家,供大家参考! http://poj.org/ 北大的,比较难 http://acm.hdu.edu.cn/ 杭电的,相对容易 http://cm2prod.baylor.edu/welcome.icpc ACM/ICPC官方网站
思路:这个题和HDU - 5703类似,其实就是拆数问题,一个数的拆法其实就是2^(N-1),具体证明过程可以直接搜刚才杭电那道题的题解,所以这道题其实就是让你算2^(N-1),但是题目给的N特别大, 可以达到10^100000,我们...
ACM-ICPC OJ 解决方案代码 介绍 我的解决方案代码适用于流行的在线裁判系统,例如 POJ、HDOJ、SGU 和 ACM-ICPC Live Archive。 但是,我忘记了我用来解决这些问题的算法! 我将通过竞赛来组织代码和解决方案。 一些...
Offline Judge1.00 Beta 简单的离线ACM/ICPC测试内核 使用WindowsAPI和C++开发 支持多文件Case的测试,获取测试时间,内存和输出文件大小 Powered by Wiskey mail:huangwei@stu.hdu.edu.cn
ACM ICPC HDOJ 1005
杭电的组合博弈课件与oj题目详解,ACM国际大学生程序设计竞赛(英文全称:ACM International Collegiate ProgrammingContest(ACM-ICPC或ICPC)是由美国计算机协会(ACM)主办的,一项旨在展示大学生创新能力、团队...
ACM ICPC HDOJ1000
ACM ICPC HDOJ1004
此回购包含OJ Hunt的源代码 简体中文版: 建造状态 产品特点 查询oj的ac / submissions 存储查询历史 正在开发中 电子邮件支持 等级 …… ...搜寻器:搜寻器来查询OJ。...crawler-api-backend:提供查询api的微服务 ...
利用vjudge源码改造爬虫抓取vjudge全局共享答案资源。 ACMer,请用于参考思路,对拍代码,不要直接提交。
E-Olymp-ECNU在线法官-Facebook黑客杯-FZU在线法官-Google Code Jam(新)-Google Kick Start-HackerEarth-HackerRank-HDU在线法官-HIT在线法官-hihoCoder-Hrbust Online法官-ICPC实时存档-Jutge-Kattis-LightOJ-MSK...
刚性裁判专为 RigidOJ 设计的强大而稳定的判断系统。...OnlineJudges 并发任务自动重试远程在线裁判支持: UVa POJ HDU ZOJ UVaLive SGU SPOJ AIZU Ural Codeforces Codeforces::Gym要求JRE 7 RabbitMQ 3.4支持访问。