构造 - SGU 109 Magic of David Copperfield II-白红宇

Magic of David Copperfield II

Mean:

略

analyse:

若i+j为奇数则称(i,j)为奇格，否则称(i+j)为偶格，显然每一次报数后，所有的观众要不同是指向奇格，要不同时指向偶格，这一点很容易启发我们利用奇偶性构造：

1 2 3 2 1

2 3 4 3 2
3 4 5 4 3
2 3 4 3 2
1 2 3 2 1

如上图所示，设n为奇数（若为偶数则可以加宽一列加高一行，并且标记最右边一列最下边一行都已经被删除了），最开始观众指向偶格(1,1)，第一次报一个奇数后观众的手只能指向奇格，此时就可以把标号为1的格子都删掉；第二次再报另一个奇数，则观众的手只能指向偶格，此时又可以把标号为2的格子都删掉；以此类推，最后只剩下中央的一个格子，游戏在n-1步类完成。101~299有足够的奇数可以选择用来报数，而且次删掉部分格子后剩下的格子都是连通的，也就不存在孤立的格子。

Time complexity: O(N)

view code

import
java
.
util
.
*; 
public
class
Solution
{ 
public
static
void
main( 
String
[]
args) 
{ 
Scanner
in
=
new
Scanner( 
System
.
in); 
int n 
=
in
.
nextInt(); 
if (n 
==
2) 
{ 
System
.
out
.
println( 
"3 1"); 
System
.
out
.
println( 
"5 2 3"); 
}
else
{ 
System
.
out
.
print(n); 
for ( 
int
i
=
0; 
i
< n; 
++
i) 
{ 
for ( 
int
j
=
Math
.
max( 
0
, n 
+
1
-
i); 
j
< n; 
++
j) 
{ 
System
.
out
.
print( 
" "
+ ( 
i
* n 
+
j
+
1)); 
}
}
System
.
out
.
println(); 
for ( 
int
k
=
0; 
k
< n; 
++
k) 
{ 
System
.
out
.
print(((n 
+
1) 
/
2
+
k) 
*
2
+
1); 
for ( 
int
i
=
Math
.
max( 
0
,
1
-
k); 
i
<
Math
.
min(n 
, n 
+
1
-
k); 
++
i) 
{ 
System
.
out
.
print( 
" "
+ ( 
i
* n 
+ (n 
-
k
-
i) 
+
1)); 
}
System
.
out
.
println(); 
}
}
}
}