NYOJ--關於521

關於521

描述

Acm隊的流年對數學的研究不是很透徹，但是固執的他還是想一頭扎進去。

浏覽網頁的流年忽然看到了網上有人用玫瑰花瓣拼成了521三個數字，頓時覺得好浪漫，因為每個男生都會不經意的成為浪漫的制造者。此後，流年走到哪裡都能看到5、2、1三個數字，他怒了，現在他想知道在連續的數中有多少數全部包含了這三個數字。例如12356就算一個，而5111就不算。特別的，如果他看到了521三個數連續出現，會特別的憤怒。例如35210。

輸入

多組測試數據：
一行給定兩個數a，b（0 輸出

一行顯示他想要知道的數有幾個及顯示有多少個數字令他特別的憤怒。用空格隔開。

樣例輸入

200 500
300 900
1 600

樣例輸出

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

開始一直TLE，後來看了別人的代碼，才發現應該先范圍內的數都判斷一遍，這樣就不用每次都判斷，直接在存儲的數組中找就可以了哈！

超時代碼如下

#include 
using std::endl;
using std::cout;
using std::cin;
int main()
{
	int a , b;
	int cnt = 0;
	while(cin >> a >> b)
	{
		cnt++;
		int s[6];
		int cnt1 = 0 , cnt2 = 0;
		for(int j=a; j<=b;++j)
		{
			int five=0 , two = 0, one = 0;
			s[0] = j % 10;
			s[1] = j / 10 % 10;
			s[2] = j / 100 % 10;
			s[3] = j / 1000 % 10;
			s[4] = j / 10000 % 10;
			s[5] = j / 100000 % 10;
			for(int i=0 ; i<4;++i)
			{
				if(s[i] == 1 && s[i+1] == 2 && s[i+2] == 5)
				{
					cnt2++;
					break;
				}
			}
			for(int i=0 ; i<6; ++i)
			{
				if(s[i] == 5)
				{
					five++;
					continue;
				}
				if(s[i] == 2)
				{
					two++;
					continue;
				}
				if(s[i] == 1)
				{
					one++;
					continue;
				}
			}
			if(five && two && one)
				cnt1++;
		}
		cout << "Case " <
修改後AC的代碼
 
#include 
#include 
using std::endl;
using std::cout;
using std::cin;
int main()
{
	int data1[1000000] , data2[1000000];
	int s[6];
	//把范圍之內的數全都模擬一次，累積符合條件的次數放到數組中
	for(int j=125; j<1000000; ++j)
	{
		int five = 0 , two =0 , one = 0;
		s[0] = j % 10;
		s[1] = j / 10 % 10;
		s[2] = j / 100 % 10;
		s[3] = j / 1000 % 10;
		s[4] = j / 10000 % 10;
		s[5] = j / 100000 % 10;
		int temp;
		for(int i=0; i<4;++i)
		{
			if(s[i] == 1 && s[i+1] == 2 && s[i+2] == 5)
			{
				data2[j] = data2[j-1] +1;
				break;
			}
			//如果不符合條件
			if(i == 3)
			{
				data2[j] = data2[j-1];
			}
		}
	
		for(int i=0; i<6;++i)
		{
			if(s[i] == 5)
			{
				five++;
			}else if(s[i] == 2)
			{
                two++;
			}else if(s[i] == 1)
				one++;
		}
		//判斷是否符合條件
		if(five && two && one)
			data1[j] = data1[j-1]+1;
		else
			data1[j] = data1[j-1];
	}
	int a,b;
	int cnt = 0;
	while(cin >> a >> b)
	{
		cnt++;
		if(a <2)
			a=2;
		//直接在數組中取值，二者相減就是兩個數之間符合條件的個數，注意一定是第一位數的前一位
		cout << "Case " << cnt <<":" << data1[b] - data1[a-1] <<" " <
NYOJ上最優代碼(短小精悍，果然牛逼哈)
#include
struct AC
{
    int x,y;
}a[1000004];
int main()
{
    int i,j,k=0;a[125].x=1,a[521].y=1;
    for(i=0; i<1000003; i++)
    {
        int c[3]={0};
        if(i%10==5||i%100/10==5||i%1000/100==5||i%10000/1000==5||i%100000/10000==5||i%1000000/100000==5)
            c[2]=1;
        if(i%10==2||i%100/10==2||i%1000/100==2||i%10000/1000==2||i%100000/10000==2||i%1000000/100000==2)
            c[1]=1;
        if(i%10==1||i%100/10==1||i%1000/100==1||i%10000/1000==1||i%100000/10000==1||i%1000000/100000==1)
            c[0]=1;
        if(c[0]&&c[1]&&c[2]) a[i].x=a[i-1].x+1;
        else a[i].x=a[i-1].x;
        if(i%1000==521||i%10000/10==521||i%100000/100==521||i%1000000/1000==521) a[i].y=a[i-1].y+1;
        else a[i].y=a[i-1].y;
    }//printf("%d",l);
    while(~scanf("%d %d",&i,&j))
    {int m;
        k++;
        printf("Case %d:%d %d\n",k,a[j].x-a[i-1].x,a[j].y-a[i-1].y);
    }
}