usaco_4_4_1_shuttle.cpp

usaco自己做的1到5章的代码

/*
PROB: shuttle
LANG: C++
*/
/*
这道题乍看之下是用搜索来解决，不过既要不超时不超空间，用能保证搜出来的是正确解，即按照字典序，需要很强大的搜索技巧，只少我是没搜出来。
参考了网上的方法，原来这道题主要是找规律来解决的。
看下面的三个数据的解：
3

(4) 3 5 6 4 2 1 3 5 7 6 4 2 3 5 4
(-1) 2 1 -2 -2 -1 2 2 2 -1 -2 -2 1 2 -1

4

(5) 4 6 7 5 3 2 4 6 8 9 7 5 3 1 2 4 6 8 7 5 3 4 6 5
(-1) 2 1 -2 -2 -1 2 2 2 1 -2 -2 -2 -2 1 2 2 2 -1 -2 -2 1 2 -1

5

(6) 5 7 8 6 4 3 5 7 9 10 8 6 4 2 1 3 5 7 9 11 10 8 6 4 2 3 5 7 9 8 6 4 5 7 6
(-1) 2 1 -2 -2 -1 2 2 2 1 -2 -2 -2 -2 -1 2 2 2 2 2 -1 -2 -2 -2 -2 1 2 2 2 -1 -2 -2 1 2 -1

第一行是输出的答案，第一行的数字通过加上对应位置的第二行的数就可以得到第一行后面一个数、
发现，原来是空格的位置是按照1和2通过符号位的变化和连续的2的三角形变化得到的序列。
比如3，空格最初在4的位置，那么后来空格就是4-1=3，3+2=5，5+1=6……
这样只要求出这个序列，然后对n+1执行这个序列的和就行了。
*/
#include<stdio.h>
int main()
{
    int i,j,k,ptr,n;
    int s[200];
    freopen("shuttle.in","r",stdin);
    freopen("shuttle.out","w",stdout);
    scanf("%d",&n);
    int sign=-1;
    ptr=0;
    for(i=1;i<=n;i++){
        s[ptr++]=sign;
        sign=0-sign;
        for(j=1;j<=i;j++)
           s[ptr++]=sign*2;
    }
    sign=0-sign;
    s[ptr++]=sign;
    for(i=n-1;i>0;i--){

        for(j=1;j<=i;j++)
           s[ptr++]=sign*2;
        sign=0-sign;
        s[ptr++]=sign;
    }
    k=n+1;
    for(i=0;i<ptr-1;i++)
    {
        k+=s[i];
        if((i+1)%20==0) printf("%d\n",k);
        else printf("%d ",k);
    }
    printf("%d\n",k+s[i]);
}