枚举之万圣节派对

A - 万圣节派对

Time Limit:1000MS     Memory Limit:65535KB     64bit IO Format:%I64d & %I64u

 

Description

万圣节有一个Party，XadillaX显然也要去凑热闹了。因为去凑热闹的人数非常庞大，几十W的数量级吧，自然要进场就需要有门票了。很幸运的，XadillaX竟然拿到了一张真·门票！这真·门票的排列规则有些奇怪：

门票号是由0~6组成的六位数（0~6这几个数字可重用）

每一个门票号的每一位不能有三个连续相同的数字（如123335是不行的）

每一个门票号相邻的两位相差必须在四以下（≤4）（如016245是不行的）

 

Input

第一行一个n，代表数据组数
接下去n行，每行两个数字x,y(x <= y)

Output

对于每一组数据，输出x到y之间的门票编号

Sample Input

2

001001 001002

001011 001012

 

Sample Output

001001

001002

 

001011

001012

第一次的代码如下，结果是时间超限

#include 

#include 

using namespace std; 

int really(int x) //测试x是否满足条件

{ 

    int i; 

    int a[6];    //将x拆分成6个单独的数

    for(i=5;i>=0;i--) 

    { 

        a[i]=x%10; 

        x/=10; 

        if(a[i]>6) 

            return 0; 

    } 

    for(i=0;i<5;i++) 

    { 

        if(i<4) 

        { 

            if(a[i]==a[i+1]&&a[i]==a[i+2]) 

                return 0; 

        } 

        if(i<5) 

        { 

            if(a[i]-a[i+1]>4||a[i]-a[i+1]<-4) 

                return 0; 

        } 

    } 

    return 1; 

} 

int main() 

{ 

    int n,i,j,x,y,t; 

    while(scanf("%d",&n)!=EOF) 

    { 

        while(n--) 

        { 

            int a[6]; 

            cin>>x>>y; 

            for(i=x;i<=y;i++) 

            { 

                if(really(i)==1) 

                { 

                    t=i; 

                    for(j=5;j>=0;j--) 

                    { 

                        a[j]=t%10; t/=10; 

                    } 

                    for(j=0;j<6;j++) 

                    { 

                        cout<<a[j]; 

                    } 

                    cout<<endl; 

                } 

            } 

            cout<<endl; 

        } 

    } 

    return 0; 

}

于是小小改动一下，不判断完再重新拆分输出了，直接在子函数中输出，时间复杂度好像没变QAQ，果然仍是时间超限。
#include
using namespace std;
int really(int x)
{
    int i;
    int a[6];
    for(i=5;i>=0;i--)
    {
        a[i]=x%10;
        x/=10;
        if(a[i]>6)
            return 0;
    }
    for(i=0;i<5;i++)
    {
        if(i<4)
        {
            if(a[i]==a[i+1]&&a[i]==a[i+2])
                return 0;
        }
        if(a[i]-a[i+1]>4||a[i]-a[i+1]<-4)
            return 0;
    }
    for(i=0;i<6;i++)
    {
        cout<
    }
    cout<
    return 1;
}


int main()
{
    int n,i,j,x,y,t;
    cin>>n;
    while(n--)
    {
        int a[6];
        cin>>x>>y;
        for(i=x;i<=y;i++)
        {
            really(i);
        }
        if(n!=0)
            cout<
    }
    return 0;
}
注意：正确结果只是将下列的cin,cout输入输出改为scanf和平日printf，实践证明scanf比cin快很多，大约10倍左右。
但是为什么呢？上网搜索得：

比较合理的解释：默认情况，cin与stdin总是保持同步的，也就是说这两种方法可以混用，而不必担心文件指针混乱，同时cout和stdout也一样，两者混用不会输 出顺序错乱。正因为这个兼容性的特性，导致cin有许多额外的开销，如何禁用这个特性呢？只需一个语句 std::ios::sync_with_stdio(false);，这样就可以取消cin于stdin的同步了，此时的cin就与scanf差不多 了。

另一种解释： cout在输出时总是要先将输出的存入缓存区。而printf直接调用系统进行IO，它是非缓存的。所以cout比printf慢。

stdin(Standardinput)标准输入
stdout(Standardoutput)标准输出
stderr(Standarderror)标准错误
第一种解释表示难以理解，第二种解释感觉更容易理解些。可能是对于第一种解释没有准确理解，我感觉两种解释是一样的，先存入缓存区即是额外的开销。

经过多次改动，想令程序更快些，代码如下，结果WA了，尚未找到原因。。。
#include
int really(int x)
{
    int i;
    int a[6];
    for(i=5;i>=0;i--)
    {
        a[i]=x%10;
        x/=10;
        if(a[i]>6)
            return i+2;//返回值没有什么特别的意义，只是将不满足条件的位数区分出来。
    }
    for(i=0;i<5;i++)
    {
        if(i<4)
        {
            if(a[i]==a[i+1]&&a[i]==a[i+2])
                return i+10;
        }
        if(a[i]-a[i+1]>4||a[i]-a[i+1]<-4)
            return i+9;
    }
    for(i=0;i<6;i++)
    {
        printf("%d",a[i]);
    }
    printf("\n");
    return 100;
}


int main()
{
    int n,i,j,x,y,t;
    scanf("%d",&n);
    while(n--)
    {
        int a[6];
        scanf("%d%d",&x,&y);
        for(i=x;i<=y;i++)
        {
            switch(really(i))
            {
            //默认x,y小于700000；所以没考虑第一位大于6的情况。可见该程序仍可优化。
            case 3:i+=29999;break;  //最初想的是返回值为3说明第二位大于6，从小往大扫的话最先出现的一定是*70000，i+=29999再经过i++相当于i+=30000即跳过该第二位，直接判别(*+1)00000
            case 4:i+=2999;break;//第三位大于6
            case 5:i+=299;break;//第四位大于6
            case 6:i+=29;break;//第五位大于6
            case 7:i+=2;break;//第六位大于6
            case 9:i+=9999;break;//第一位和第二位相差>4，最先出现的应该是ab0000,跳到直接判别a(b+1)0000
            case 10:i+=999;break;//第二位和第三位相差>4或第一二三位相等，最先出现的应该是abc000,跳到直接判别ab(c+1)000（实践证明，该步之前都没问题，加入该条件就WA了。）
            case 11:i+=99;break;//第三四位相差>4或二三四位相等
            case 12:i+=9;break;//第四五位相差>4或三四五位相等
            default:break;
            }
        }
        if(n!=0)
            printf("\n");
    }
    return 0;
}

我承认这题是一道水题，但这题花费了我3个多小时的时间，无论什么题，多思总能学到东西，哪怕什么都没学到也多少锻炼了脑袋（》v《）。