梦.:如此短暂

SGU109 解题手记
　　样例真不错，实际上，答案的构造跟样例是一样的——每次把最外层的数字剥掉。

1 2 3   3   x 2 x   5   x x x
4 5 6  -->  4 5 6  -->  x 5 x
7 8 9       x 8 x       x x x

　　移动3步，手指不可能落在奇数上，所以最外圈的奇数就可以去掉了，同理，再移动4步，最外圈的偶数就可以去掉了……
　　上面是较为简单的n为奇数的情况，n为偶数稍微复杂一些。

 1  2  3  4        x  2  x  4        x  x  x  x
 5  6  7  8   5    5  6  7  x   7    x  6  7  x
 9 10 11 12  -->   x 10 11 12  -->   x 10 11  x
13 14 15 16       13  x 15  x        x  x  x  x

　　变成只有中间4个数的情况时，应该现移动偶数步，将7去掉，然后移动奇数步，把6 11去掉。
　　总结一下n为奇数和偶数的情况，都是第奇数次移动奇数步时，将最外层行数+列数为偶数的数字去掉，第偶数次移动奇数步时，将最外层行数+列数为奇数的数字去掉。当n为偶数时，最后剩下4个数字要特殊处理。

　　发现一种更简单的构造法：按副对角线去掉数字，最后留下1的位置。
　　Submit 1: AC。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

#include <cstdio>
using namespace std;
 
int main()
{
    int n,i,j,k;
    scanf("%d",&n);
    if (n==2) printf("3 4\n5 2 3\n");
    else
    {
        printf("%d",k=n);
        for (i=2;i<n;i++)
            for (j=n-i+1;j<n;j++) printf(" %d",i*n+j+1);
        printf("\n%d",k+=1+(n&1));
        for (j=0;j<n-1;j++) printf(" %d",n*2+j*(n-1));
        for (k+=2,i=n;k<3*n+1;k+=2,i--)
        {
            printf("\n%d",k);
            for (j=0;j<i;j++) printf(" %d",i+j*(n-1));
        }
    }
    return 0;
}