「vijos1655」萌萌的糖果博弈
背景
用糖果来引诱小朋友学习是最常用的手法，绵羊爸爸就是用糖果来引诱萌萌学习博弈的。
描述
他把糖果分成了两堆，一堆有A粒，另一堆有B粒。他让萌萌和他一起按照下面的规则取糖果：每次可以任意拿走其中一堆糖果；如果这时候另一堆糖果数目多于1粒，就把它任意分成两堆，否则就把剩下的一粒糖果取走并获得这次博弈的胜利。胜利者将获得所有的糖果。萌萌想要得到所有的糖果，而绵羊爸爸想把糖果留下以便下一次利用。现在由萌萌先取糖果，旁观的小朋友们想知道萌萌是否有必胜策略。
输入格式
本题有多组测试数据（不超过100组）。每组数据包括两行，第一行为A，第二行为B。1 ≤ A,B ≤ 2^127。输入数据以一个 -1 结束。
输出格式
每组数据对应一行输出。如果萌萌获胜则输出”MengMeng”，否则输出”SheepDaddy”（不包括引号）。
代码
找规律….想想:那个叫XX67的怎么有必胜策略?..必胜策略是”所谓有必胜策略是指，无论对方如何操作，自己总有办法取胜。”就是说:我一操作保证剩下的一堆无论你怎么分你都赢不了!那我必胜.否则我不必胜…)(就是把剩下的堆分成两个XX67{先手}必输得堆)…(注意注意”不必胜”<>”必输”…呀呀..我为什么看了那么久才发现?….补语文呀..
想想看:如果有一堆糖果个数>=10.那它就能分出任意的0 1 2 3 4 5 6 7 8 9 个的堆…没有探讨的意义….知推0~9的规律..呵呵..0没有用的…假设有 两堆:x y..先吃x..(先加上约束..好推)
x 1的情况–>XX67胜
x 2的情况–>XX67负
x 3的情况–>XX67负 {这些小的幼稚园小朋友都推的出..毫无技巧可言..}
…….. 接下来:只要XX67有一种操作使剩下的一堆无论S..怎么分都赢不了!
then XX67 win
else S… win…
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
#include<iostream> using namespace std; int main() { string a,b; char m,n; while(cin>>a) { if(a=="-1")break; cin>>b; m=a[a.size()-1]; n=b[b.size()-1]; if((m=='2'||m =='3'||m=='7'||m=='8')&&(n=='2'||n=='3'||n=='7'||n=='8')) cout<<"SheepDaddy"<<endl; else cout<<"MengMeng"<<endl; } return 0; } |
OI 课件=>
