2187944 2007-01-01 19:14:20 Accepted 1893 C++ 00:00.00 388K Crux.D     这题好X难。     题目大概意思是：两人轮流乘一个2－9的数，从1开始乘，求谁的乘积先大于N。     如果是加法就好做了。凑到剩下的数能整除11，然后对称着加。问题是乘法。     所以寻找必胜点（段）。以1000为例。     1000 | 999 ... 112 |    若占住999到112，则对手必胜。必须让对手占领此段。     1000 | 999 ... 112 | 111 ... 56 |   因此必占段是 111 －? 。如果56被对手占住，则56×2＝112，入必败段。问题转化成为占56。     如此循环。如下 1000 | 999 ... 112 | 111 ... 56 | 55 ... 7 | 6 ... 4 | 3 ... 1    仔细考虑端点，我在处理端点情况时想了好久。     这是牛人的代码。 #include <stdio.h> unsigned int N; bool StanWins (){// printf ( "%u\n" , N ); if ( N == 1 ) return true; int step; for ( step = 1; N > 1; step ++ )  if ( step & 1 ) N = ( N - 1 ) / 9 + 1;   else N = ( N + 1 ) / 2; return ( step & 1 ) == 0;} int main(){// freopen ( "p.in" , "r" , stdin );  while ( scanf ( "%u" , &N ) != EOF )  if ( StanWins () ) printf ( "Stan wins.\n" );   else printf ( "Ollie wins.\n" ); return 0;}     这是我的代码。 #include <cstdio> unsigned int n; int main(){ //freopen("in.txt", "r", stdin); while(scanf("%u", &n) != EOF) {  int step = 0;  //printf("%u\n", n);  if(n == 1)  {   printf("Stan wins.\n");   continue;  }  while(n > 1)  {   n = (n - 1) / 9 + 1;   step ++;   if(n <= 1) break;   n = (n + 1) / 2;   step --;  }  if(step)   printf("Stan wins.\n");  else   printf("Ollie wins.\n"); } return 0;}

评论