不要62

小咪咪 2024-02-18 21:57 3阅读 0赞

## 不要62 ##

**Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)  
Total Submission(s): 55413 Accepted Submission(s): 21347**

**Problem Description**

杭州人称那些傻乎乎粘嗒嗒的人为62（音：laoer）。  
杭州交通管理局经常会扩充一些的士车牌照，新近出来一个好消息，以后上牌照，不再含有不吉利的数字了，这样一来，就可以消除个别的士司机和乘客的心理障碍，更安全地服务大众。  
不吉利的数字为所有含有4或62的号码。例如：  
62315 73418 88914  
都属于不吉利号码。但是，61152虽然含有6和2，但不是62连号，所以不属于不吉利数字之列。  
你的任务是，对于每次给出的一个牌照区间号，推断出交管局今次又要实际上给多少辆新的士车上牌照了。

**Input**

输入的都是整数对n、m（0<n≤m<1000000），如果遇到都是0的整数对，则输入结束。

**Output**

对于每个整数对，输出一个不含有不吉利数字的统计个数，该数值占一行位置。

**Sample Input**

1 100 0 0

**Sample Output**

**Author**

qianneng

**Source**

[迎接新学期——超级Easy版热身赛][Easy]

**Recommend**

先上一个超时的代码：

#include<stdio.h>
    #include<math.h>
    
    int main()
    {
         
        int n,m;
        int a[8];
        while(~scanf("%d %d",&n,&m),m||n)
        {
         
            int i,j=0,t,p,f=0,k=0;
            for(i=n;i<=m;i++)
            {
         
                t=i;f=0;
                j=0;
                while(t!=0)
                {
         
                    a[j]=t%10;
                    //printf("a[%d]:%d\n",j,a[j]);   需要电脑在线判断，感觉比较麻烦，遂卒
                    t/=10;
                    j++;
                }
                
                for(p=0;p<j;p++)
                {
         
                    if(a[p]==4||(a[p]==2&&a[p+1]==6))
                    {
         
                        f=1;
                        break;
                    }
                }
                //printf("%d\n\n",f);
                if(f==1)
                continue;
                else
                k++;
                
                
            }
            printf("%d\n",k);
        }
        return 0;
    }

最朴素的算法就是枚举n-m之间的所有数字进行在线判断。
    判断可以利用itoa把数字转化成字符串，利用字符串函数strstr快速判断之后输出答案，再继续搜索下一个n-m
    
    
    但是我们考虑一个问题。由于本题目没有提问组数的范围，考虑一个极端情况，询问100000次1-1000000
    
    很显然，肯定是会超时的。
    
    
    
    因此我们考虑来离线回答这个问题，也就是预处理。我们知道，如果在线回答100000次1-1000000就意味着要做100000次1-1000000的循环，那么我们提前在回答前就算好并记录好答案，然后询问的话只要直接输出就行了。
    
    
    那么怎么预先算好呢？很简单，读入前先做一次1-1000000的循环，建立一个数组a，记录前i个数有几个是不符合的。也就是利用了前缀和。这样的话后面读入n与m后，我们只需要a[m]-a[n]能在o（1）的复杂度内就知道n-m内不符合的数字，同时计算出答案。这样就绝对不会超时了。
    
    
    
    可能有萌新不知道前缀和。我一开始也不知道，但是其实自己一直在用，后来才被告知这叫前缀和= =
    
    举个例子，1 2 3 4 5 6 7 8 9我想知道任意区间[n,m]的值，我们读入的时候不要存一个数，而是把前I项存起来。
    
    存完是这样的1 3 6 10 15 21 28 36 45，如果我想知道[2,10]内数字的和，就直接a[10]-a[2-1]即可，不需要循环了。

\#include<stdio.h>  
\#include<stdlib.h>  
\#include<string.h>  
int a\[1000010\];  
char str\[1000010\];  
int main()  
\{  
  
  
int n,m;  
int i,j;  
memset(a,0,sizeof(a\[0\]));  
for(i=1;i<1000001;i++) //用数组统计从1到下标之间的含不符合条件的个数  
\{  
itoa(i,str,10);  
if(strstr(str,"4")!=NULL)  
\{  
a\[i\]=a\[i-1\]+1;  
continue;  
\}  
if(strstr(str,"62")!=NULL)  
\{  
a\[i\]=a\[i-1\]+1;  
continue;  
\}  
a\[i\]=a\[i-1\];//如果没有出现62和4，则跟前一个一样。  
\}//统计完毕  
while(~scanf("%d %d",&n,&m),m||n)  
\{  
printf("%d\\n",m-n+1-(a\[m\]-a\[n-1\]));  
\}  
return 0;  
\}

[Easy]: http://acm.hdu.edu.cn/search.php?field=problem&key=%D3%AD%BD%D3%D0%C2%D1%A7%C6%DA%A1%AA%A1%AA%B3%AC%BC%B6Easy%B0%E6%C8%C8%C9%ED%C8%FC&source=1&searchmode=source