Magic of David Copperfield II
Problem's Link
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();
}
}
}
}
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();
}
}
}
}
![P2853 [USACO06DEC]Cow Picnic S](https://ucc.alicdn.com/pic/developer-ecology/0d9b09beae414acda2667932fc530d7b.png?x-oss-process=image/resize,h_160,m_lfit)
![[USACO 2012 Feb G]Cow Coupons----贪心&带悔(看完稳AC)](https://ucc.alicdn.com/pic/developer-ecology/e2524b2d3a88406789bd6de3c915e0c5.png?x-oss-process=image/resize,h_160,m_lfit)
