timus 1180. Stone Game 解题报告

Input

Output

Sample

8

1
2

2.解题思路

这种博弈问题，都是从最简单的情况考虑，递推到复杂情况的。但是这道题有一些有趣的技巧~

基本的递推：

N　　win?

1　　y

2　　y

3　　n

嗯。分析到这里，思路大概是这样的：

bool suc[maxN+1];

suc[1] = suc[2] = true;

for (i = 3; i <= n; i++) {

　　for (b = 1; b < n; b *= 2) {

　　　　if (suc[i-b] == false) {

　　　　　　suc[i] = true;

　　　　　　break;

　　　　}

　　}

}

然而再回头看一下题目规模，发现n的取值范围是n <= 10^250。这是要高精度的节奏啊。

不急，回去再看一下有没有优化的方法。通过找规律，

发现：N = 3*n， suc[n] = n

　　　N = 3*n + 1 || N = 3*n + 2， suc[n] = y

这样问题转换为求n%3。

而一个十进制数N = sum(ai*10^i) = sum(ai) + sum(ai*(10^i-1))(i>=0)

而10^i-1 = 0 (mod3)

故N = sum(ai) (mod3)

3.代码：

#include <iostream>
using namespace std;
int main()
{
    int s = 0;
    char tmp;
    while (cin >> tmp) s += tmp - ‘0‘;
    if (s % 3 == 0) cout << 2;
    else cout << 1 << ‘\n‘ << s % 3;
    //return 0;
}