题意略.
思路:
我们总是假设 a> b, 那么现在有两种情况:
1.a - b <b 2.a - b>= b
在处于第一种情况下, 我们只有一种选择, 也即把 a 变成 b, 而原有的 b 变成 a - b.
在第二种情况时, 我们分类考虑一下:
1. 当 (b,a % b) 为必败态时, 我们直接从当前状态转移过去, 可以使我们当前状态为必胜态.
2. 当 (b,a % b) 为必胜态时, 我们直接从当前状态转移到 (a % b + b,b) , 逼迫对手将我们推向必胜态.
也就是说, 当 a / b>= 2 时, 当前操作的人必胜.
详见代码:
- #include<bits/stdc++.h>
- using namespace std;
- int main(){
- int a,b;
- while(scanf("%d%d",&a,&b) == 2 && (a + b)){
- bool jud = true;
- if(a <b) swap(a,b);
- while(true){
- if(a / b>= 2 || a % b == 0) break;
- else{
- int temp = a % b;
- a = b,b = temp;
- }
- jud = !jud;
- }
- printf("%s\n",jud ? "Stan wins" : "Ollie wins");
- }
- return 0;
- }
- HDU 1525
来源: http://www.bubuko.com/infodetail-2696565.html