当前位置 : 主页 > 手机开发 > harmonyos >

HDU 2147

来源:互联网 收集:自由互联 发布时间:2023-10-08
/* * 博弈论:组合博弈 * 必败点(P点) :前一个选手(Previous player)将取胜的位置称为必败点。 * 必胜点(N点) :下一个选手(Next player)将取胜的位置称为必胜点。 * 必败(必胜)点的属性: *
/*
 * 博弈论:组合博弈
 * 必败点(P点) :前一个选手(Previous player)将取胜的位置称为必败点。
 * 必胜点(N点) :下一个选手(Next player)将取胜的位置称为必胜点。
 * 必败(必胜)点的属性:
 * (1) 所有终结点是必败点(P点);
 * (2) 从任何必胜点(N点)操作,至少有一种方法可以进入必败点(P点);
 * (3)无论如何操作, 从必败点(P点)都只能进入必胜点(N点).
 * 由上面的属性得到该题的算法:
 * 步骤1:将所有终结位置标记为必败点(P点);
 * 步骤2: 将所有一步操作能进入必败点(P点)的位置标记为必胜点(N点)
 * 步骤3:如果从某个点开始的所有一步操作都只能进入必胜点(N点) ,则将该点标记为必败点(P点) ;
 * 步骤4: 如果在步骤3未能找到新的必败(P点),则算法终止;否则,返回到步骤2。
 * 由上面的算法计算一个例子:
 * 我们可以把问题转换成从(1,1)走到(n,m) (方便等下得出结论)
 * 但n=8,m=9的情况
 *  NNNNNNNNN
 *  PNPNPNPNP
 *  NNNNNNNNN
 *  PNPNPNPNP
 *  NNNNNNNNN
 *  PNPNPNPNP
 *  NNNNNNNNN
 *  PNPNPNPNP
 *初始点(1,1)为N所以输出Wonderful!
 *从这里例子就可以很清楚得看出当n和m都为奇数时,初始点(1,1)才会是P。
 *因此该题只需判断n,m是否同时为奇数即可。
 */
上一篇:FZU 2079 最大获利
下一篇:没有了
网友评论