bzoj 3101 N 皇后

线性构造出一个解。

#include <cstdio>
#include <iostream>
void solve(int n)
{
    if ((n >> 1) % 2 == 0)
    {
        for (int i = 2; i <= n; i += 2)
            printf("%d ", i);
        for (int i = 1; i <= n; i += 4)
            printf("%d %d ", i + 2, i);
    }
    else
    {
        printf("%d ", n - 1);
        for (int i = 2; i <= n; i += 2)
            printf("%d ", i);
        for (int i = 1; i <= n - 2; i += 4)
            printf("%d %d ", i + 2, i);
    }
}
int main()
{
    int n = read();
 //   int st = clock();
    if (n == 2 || n == 3)
        printf("no solution");
    else if (n % 6 == 2)
        solve(n);
    else if (n % 6 == 3)
    {
        if ((n >> 1) % 2 == 1)
        {
            printf("%d ", n);
            solve(n - 1);
        }
        else
        {
            printf("%d ", n);
            for (int i = 4; i <= n; i += 2)
                printf("%d ", i);
            for (int i = 1; i <= n - 2; i += 4)
                printf("%d %d ", i + 2, i);
            printf("2 ");
        }
    }
    else
    {
        for (int i = 2; i <= n; i += 2)
            printf("%d ", i);
        for (int i = 1; i <= n; i += 2)
            printf("%d ", i);
    }
   // std::cerr << "Total time: " << (double)(clock() - st) / CLOCKS_PER_SEC << "s" << std::endl;
    return 0;
}