3101: N皇后

3101: N皇后

Time Limit: 10 Sec  Memory Limit: 128 MBSec  Special Judge

Submit: 88  Solved: 41

[Submit][Status][Discuss]

Description

n*n的棋盘,在上面摆下n个皇后,使其两两间不能相互攻击…

Input

一个数n

Output

第i行表示在第i行第几列放置皇后

Sample Input

4

Sample Output

2 4 1 3

HINT

100%的数据3<n<1000000。输出任意一种合法解即可

Source

题解:一道神(dou)奇(bi)的题目,传说中貌似有种O(N)构造N皇后解的方法,具体为啥貌似也查不到,求神犇给出证明orzorzorz(引自N皇后的构造解法

一、当n mod 6 != 2 或 n mod 6 != 3时,有一个解为: 2,4,6,8,...,n,1,3,5,7,...,n-1       (n为偶数) 2,4,6,8,...,n-1,1,3,5,7,...,n       (n为奇数) (上面序列第i个数为ai,表示在第i行ai列放一个皇后;... 省略的序列中,相邻两数以2递增。下同) 二、当n mod 6 == 2 或 n mod 6 == 3时, (当n为偶数,k=n/2;当n为奇数,k=(n-1)/2) k,k+2,k+4,...,n,2,4,...,k-2,k+3,k+5,...,n-1,1,3,5,...,k+1         (k为偶数,n为偶数) k,k+2,k+4,...,n-1,2,4,...,k-2,k+3,k+5,...,n-2,1,3,5,...,k+1,n       (k为偶数,n为奇数) k,k+2,k+4,...,n-1,1,3,5,...,k-2,k+3,...,n,2,4,...,k+1               (k为奇数,n为偶数) k,k+2,k+4,...,n-2,1,3,5,...,k-2,k+3,...,n-1,2,4,...,k+1,n           (k为奇数,n为奇数)

然后就是码代码了= = 

 1 /**************************************************************
 2     Problem: 3101
 3     User: HansBug
 4     Language: Pascal
 5     Result: Accepted
 6     Time:1832 ms
 7     Memory:224 kb
 8 ****************************************************************/
 9  
10 var
11    i,j,k,l,m,n:longint;
12 begin
13      readln(n);
14      case n mod 6 of
15           2,3:begin
16                    k:=n div 2;
17                    case (k mod 2)+(n mod 2)*2 of
18                         0:begin
19                                for i:=0 to (n-k) div 2 do writeln(k+i*2);
20                                for i:=0 to (k-4) div 2 do writeln(2+i*2);
21                                for i:=0 to (n-k-4) div 2 do writeln(k+3+i*2);
22                                for i:=0 to k div 2 do writeln(1+2*i);
23                         end;
24                         2:begin
25                                for i:=0 to (n-k-1) div 2 do writeln(k+i*2);
26                                for i:=0 to (k-4) div 2 do writeln(2+i*2);
27                                for i:=0 to (n-k-5) div 2 do writeln(k+3+i*2);
28                                for i:=0 to k div 2 do writeln(1+2*i);
29                                writeln(n);
30                         end;
31                         1:begin
32                                for i:=0 to (n-k-1) div 2 do writeln(k+i*2);
33                                for i:=0 to (k-3) div 2 do writeln(1+i*2);
34                                for i:=0 to (n-k-3) div 2 do writeln(k+3+i*2);
35                                for i:=0 to (k-1) div 2 do writeln(2+2*i);
36                         end;
37                         3:begin
38                                for i:=0 to (n-k-2) div 2 do writeln(k+i*2);
39                                for i:=0 to (k-3) div 2 do writeln(1+i*2);
40                                for i:=0 to (n-k-4) div 2 do writeln(k+3+i*2);
41                                for i:=0 to (k-1) div 2 do writeln(2+2*i);
42                                writeln(n);
43                         end;
44                    end;
45           end;
46           else begin
47                if odd(n) then
48                   begin
49                        for i:=1 to (n-1) div 2 do writeln(i*2);
50                        for i:=1 to (n+1) div 2 do writeln(i*2-1);
51                   end
52                else
53                    begin
54                         for i:=1 to n div 2 do writeln(i*2);
55                         for i:=1 to n div 2 do writeln(i*2-1);
56                    end;
57           end;
58      end;
59      readln;
60 end.

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏HansBug's Lab

1257: [CQOI2007]余数之和sum

1257: [CQOI2007]余数之和sum Time Limit: 5 Sec  Memory Limit: 162 MB Submit: 2001  So...

29480
来自专栏十月梦想

js二维数组遍历

31220
来自专栏算法修养

HOJ 1438 The Tower of Babylon(线性DP)

The Tower of Babylon My Tags Cancel - Seperate tags with commas. Source...

296110
来自专栏数据结构与算法

POJ3683 Priest John's Busiest Day(2-SAT)

Description John is the only priest in his town. September 1st is the John's bu...

34950
来自专栏数据结构与算法

BZOJ3560: DZY Loves Math V(欧拉函数)

$\sum_{i_1 = 0}^{b_1} \sum_{i_2 = 0}^{b_2} \dots \sum_{i_n = 0}^{b_n} \phi( p^{\...

11960
来自专栏JMCui

项目工具类

一、前言     在工作中,难免遇到各种各样的问题,每个人似乎都有一套自己的解决方案。而我,又不想每次解决完问题就把东西扔了,捡了芝麻,丢了西瓜,什么时候才能进...

47860
来自专栏小樱的经验随笔

BZOJ 1257: [CQOI2007]余数之和sum【神奇的做法,思维题】

1257: [CQOI2007]余数之和sum Time Limit: 5 Sec  Memory Limit: 162 MB Submit: 4474  So...

26540
来自专栏JetpropelledSnake

Django学习笔记之Django ORM Aggregation聚合详解

在当今根据需求而不断调整而成的应用程序中,通常不仅需要能依常规的字段,如字母顺序或创建日期,来对项目进行排序,还需要按其他某种动态数据对项目进行排序。Djngo...

10620
来自专栏ml

hdu----(3068)最长回文(manacher)

最长回文 Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 32768/32768 K (Jav...

30350
来自专栏函数式编程语言及工具

SDP(12): MongoDB-Engine - Streaming

   在akka-alpakka工具包里也提供了对MongoDB的stream-connector,能针对MongoDB数据库进行streaming操作。这个M...

493100

扫码关注云+社区

领取腾讯云代金券