首页 > 代码库 > BZOJ 2063: 我爸是李刚

BZOJ 2063: 我爸是李刚

2024-09-13 22:04:43   214人阅读

2063: 我爸是李刚

Time Limit: 10 Sec  Memory Limit: 64 MB
Submit: 155  Solved: 82
[Submit][Status][Discuss]

Description

背景： LC同学在2011年的浙江省选中轻松虐爆了WJMZBMR，无压力进入省队并参加了NOI 2011，在1个小时之后，A光了所有题目的LC同学轻松的喝着茶，哼着小曲。 由于在信息学方面的杰出表现以及LC同学的父亲是伟大的LG同志。 LC同学轻松获得了2012年诺亚方舟的船票。并且得到了卖票员这一肥差。 题目描述： 卖票员这一工作十分简单，世界上有很多卖票员。LC同学分到了第L号票到第R号票。 因为一些神奇的东西，第I号票对应的船舱能坐的人恰好是I的各位数字之和。 地球上有很多大家族，每个家族都有M个人，同时每个家族都想买一些连续的票位使他们家族的人都能坐的上船。 大家族都很排外，不肯跟别人共享一张票对应的船舱。 LC同学想知道他在把票都卖光的情况下，能 服务几个大家族呢？

Input

一行三个数L,R,M

Output

一行一个数表示结果。

Sample Input

40 218 57

Sample Output

29

HINT

100%的数据 l,r<=10^18 ,M<=1000 50%的数据，r-l<=10^6

Source

和谐社会模拟赛 Sgu390

分析：

这题目名字很NB，思想也很NB...我们一起来膜拜论文~~~

技术分享

技术分享

技术分享

这个论文里面的思想大概都是用多叉树来实现的数位DP...

代码：

#include<algorithm>#include<iostream>#include<cstring>#include<cstdio>//by NeighThornusing namespace std;long long l,r,m;int cntl,cntr,nol[18+5],nor[18+5];struct M{		long long x,y;		M(long long a=0,long long b=0){		x=a,y=b;	}		inline void init(void){		x=-1,y=0;	}		friend M operator + (M a,M b){		M res;		res.x=a.x+b.x;		res.y=b.y;		return res;	}	}f[19][201][1001];inline M dfs(int dep,long long sum,long long rem,bool lf,bool rf){	if(!dep)		return sum+rem>=m?M(1,0):M(0,sum+rem);	if(!lf&&!rf&&f[dep][sum][rem].x!=-1)		return f[dep][sum][rem];	M ans=M(0,rem);	for(int i=(lf?nol[dep]:0);i<=(rf?nor[dep]:9);i++)		ans=ans+dfs(dep-1,sum+i,ans.y,lf&&i==nol[dep],rf&&i==nor[dep]);	if(!lf&&!rf)		f[dep][sum][rem]=ans;	return ans;}signed main(void){#ifndef ONLINE_JUDGE	freopen("in.txt","r",stdin);#endif	scanf("%lld%lld%lld",&l,&r,&m);	while(l) nol[++cntl]=l%10,l/=10;	while(r) nor[++cntr]=r%10,r/=10;	for(int i=0;i<=18;i++)		for(int j=0;j<=200;j++)			for(int k=0;k<=1000;k++)				f[i][j][k].init();	printf("%lld\n",dfs(cntr,0,0,1,1).x);	return 0;}

　　

By NeighThorn

BZOJ 2063: 我爸是李刚


联系
我们