NYOJ975关于521

古城微笑少年丶 2022-05-29 07:49 82阅读 0赞

## 关于521 ##

时间限制： 1000 ms | 内存限制： 65535 KB

难度： 2

描述

Acm队的流年对数学的研究不是很透彻，但是固执的他还是想一头扎进去。

浏览网页的流年忽然看到了网上有人用玫瑰花瓣拼成了521三个数字，顿时觉得好浪漫，因为每个男生都会不经意的成为浪漫的制造者。此后，流年走到哪里都能看到5、2、1三个数字，他怒了，现在他想知道在连续的数中有多少数全部包含了这三个数字。例如12356就算一个，而5111就不算。特别的，如果他看到了521三个数连续出现，会特别的愤怒。例如35210。

输入

多组测试数据：  
一行给定两个数a，b（0<a，b<1000000），表示数字的开始和结束。

输出

一行显示他想要知道的数有几个及显示有多少个数字令他特别的愤怒。用空格隔开。

样例输入

200 500
    300 900
    1 600

样例输出

Case 1:2 0
    Case 2:2 1
    Case 3:6 1

来源

[流年][Link 1]

上传者

[ACM\_安鹏程][ACM]

题目链接： [http://acm.nyist.edu.cn/JudgeOnline/problem.php?pid=975][http_acm.nyist.edu.cn_JudgeOnline_problem.php_pid_975]

/*
    	刚开始直接暴力去做，超时了
    	后来想到了打表
    */
    #include<cstdio> 
    #include<cstring>
    const int MAXN=1000000+5;
    int ans[MAXN],sum[MAXN];
    int s[10];
    int a,b;
    void solve()
    {
    	memset(s,0,sizeof(s));
    	sum[124]=0;
    	ans[124]=0;
    	for(int i=125;i<=1000000;i++)
    	{
    		int num=i,k=0;
    		while(num)
    		{
    			if(num%1000==521)	k=1;
    			if(num%10==5)		s[5]++;	
    			if(num%10==2)		s[2]++;	
    			if(num%10==1)		s[1]++;	
    			num/=10;
    		}
    		if(s[5]&&s[2]&&s[1])	sum[i]=sum[i-1]+1;
    		else					sum[i]=sum[i-1];
    		s[5]=s[2]=s[1]=0;
    		if(k)	ans[i]=ans[i-1]+1;
    		else	ans[i]=ans[i-1];
    	}
    }
    int main()
    {
    	int t=0;
    	solve();
    	while(scanf("%d %d",&a,&b)!=EOF)
    	{
    //		printf("Case %d:%d %d\n",++t,sum[b]-sum[a],ans[b]-ans[a]); 
    		printf("Case %d:%d %d\n",++t,sum[b]-sum[a-1],ans[b]-ans[a-1]);//一定要减去a-1 
    	}
    	return 0;
    }

[Link 1]: http://acm.nyist.edu.cn/JudgeOnline/search_result.php?source=%E6%B5%81%E5%B9%B4
[ACM]: http://acm.nyist.edu.cn/JudgeOnline/profile.php?userid=ACM_%E5%AE%89%E9%B9%8F%E7%A8%8B
[http_acm.nyist.edu.cn_JudgeOnline_problem.php_pid_975]: http://acm.nyist.edu.cn/JudgeOnline/problem.php?pid=975