ZOJ 3798--解题报告

题目相关:
  3798相关链接: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=5330
  Alice和Bob玩数字游戏, 这次Alice和Bob玩的是绝对值游戏. (Alice和Bob以前只玩博弈类游戏, 现在开始玩数列了...)
  Alice有n个数(分别是1~n), 然后Alice随机从N个数中取数, 组成一个数列{A(i)}.
  Bob来构建{B(i)}数列, 满足如下规则:

{	B(1) = A(1)	
{	B(i) = | A(i) - B(i-1) |	 (i>=2 && i<=n)

  目标是:
    所有序列中B(n)的最小值和最大值, 并且构造它们的一种可能序列.

思路分析:
  可以猜测该题是规律题, 那么我们来找找规律, 看看其满足什么样的规律?
  枚举2, 3, 4的情况
  1). 当n=2时, (1, 2)的最小值为1(2, 1), 最大值为1(2, 1)
  2). 当n=3时, (1, 2, 3)的最小值为0(3, 2, 1), 最大值为2(1, 2, 3)
  3). 当n=4时, (1, 2, 3, 4)的最小值为0(4, 3, 2, 1), 最大值为4(3, 2, 1, 4)
  B(n)的最小值, 可以构造序列{n, n-1, ..., 4, 3, 2, 1}, 观察得这必然是最小的序列之一.
  再由奇偶性分析, 最后的差值由奇数个数决定, 奇数个时B(n)最小值为1, 偶数个时B(n)最小值为0, 验证和满足猜测.
  同时我们可以大胆猜测, B(n)最大取值 = n - B(n - 1)<最小值>, 即 序列{ B(n) }={ 最小值 B(n -1 )序列, n }

AC代码:

#include <cstdio>

// *) 找规律问题
class game_t {
public:
  int min_score(int n) {
    if ( ((n + 1) >> 1) & 0x01 ) {
      return 1;
    }	
    return 0;
  }
  void solve(int n) {
    // *) 处理最小值/最大值
    printf("%d %d
", min_score(n), 
          n - min_score(n - 1));

    // *) 简单构造最小值
    for ( int i = n; i > 1; i-- ) {
      printf("%d ", i);
    }	
    printf("1
");

    // *) 简单构造最大值	
    for ( int i = n - 1; i > 0; i-- ) {
      printf("%d ", i);
    }	
    printf("%d
", n);
  }
};

int main()
{
  int n;
  game_t game;
  while ( scanf("%d", &n) != EOF ) {
    game.solve(n);	
  }
  return 0;
}
原文地址:https://www.cnblogs.com/mumuxinfei/p/3953492.html