HDU - 6253——Knightmare - lose__way的博客 - CSDN博客

原题链接:Knightmare(hdoj/hdu6253) ?
文章价值(3) ?
阅读数(632) ?

Knightmare

Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 346????Accepted Submission(s): 144


Problem Description
A knight jumps around an infinite chessboard. The chessboard is an unexplored territory. In the spirit of explorers, whoever stands on a square for the first time claims the ownership of this square. The knight initially owns the square he stands, and jumps?N?times before he gets bored.
Recall that a knight can jump in 8 directions. Each direction consists of two squares forward and then one squaure sidways.

After?N?jumps, how many squares can possibly be claimed as territory of the knight? As?N?can be really large, this becomes a nightmare to the knight who is not very good at math. Can you help to answer this question?
?

Input
The first line of the input gives the number of test cases,?T.?T?test cases follow.
Each test case contains only one number?N, indicating how many times the knight jumps.
1T105
0N109
?

Output
For each test case, output one line containing “Case #x: y”, where?x?is the test case number (starting from 1) and?y?is the number of squares that can possibly be claimed by the knight.
?

Sample Input
3 0 1 7
?

Sample Output
Case #1: 1 Case #2: 9 Case #3: 649
?
代码中注释的部分是,计算前30个数据,用于查找规律
(在大部分情况下,a,b,c三个连续结果,有如下规律:(c-b)-(b-a)==28 )。

#include
#include
#include
#include
#include
using namespace std;
int main() {
    /*  const int com[16] = { -2, -1, -2, 1, -1, 2, -1, -2, 1, 2, 1, -2, 2, 1, 2, -1};
      set<> >se1;
      se1.insert ( pair ( 0, 0 ) );
      int T = 20;
      while ( T-- ) {
          set<> >se2;
          set<> >::iterator it;
          for ( it = se1.begin(); it != se1.end(); it++ )
              for ( int i = 0; i < 8; i++ )
                  se2.insert ( pair ( ( *it ).first + com[i * 2], ( *it ).second + com[i * 2 + 1] ) );
          for ( it = se2.begin(); it != se2.end(); it++ )
              se1.insert ( ( *it ) );
          cout << se1.size() << endl;
      }*/
    int T;
    unsigned long long n;
    cin >> T;
    const int com[6] = {1, 9, 41,109,205,325};
    for ( int i = 1; i <= T; i++ ) {
        scanf ( "%llu", &n );
        if ( n <= 5 ) printf ( "Case #%d: %d\n", i, com[n] );
        else printf ( "Case #%d: %llu\n", i, 205 + ( n - 4 ) * 120 + ( n * ( n + 1 ) / 2 - 5*n + 10 ) * 28 );
    }
    return 0;
}









(注:此网站文章大都来自公开的博客,如有原作者发现有侵权问题,请在此留言,我们会立刻删除相关文章。)

我的评价: