CQOI2013简单解析.ppt
《CQOI2013简单解析.ppt》由会员分享,可在线阅读,更多相关《CQOI2013简单解析.ppt(16页珍藏版)》请在三一文库上搜索。
1、CQOI2013 CQOI2013 简单解析简单解析 Leqsot t 新Nim游戏 显然没有输出-1的情况,A必胜。(最坏情 况下第一轮只剩一堆) 直接暴力枚举每种第一轮A拿了过后的状态 ,再暴力枚举第一轮B拿了过后的状态,然 后对剩下的进行普通的Nim游戏。 此算法可通过50%的测试点。 若把每堆火柴看作集合S中的元素,每种A 拿后必胜的状态看作集合L中的元素(即L为 集合的集合),据分析及证明,M=S,L 为拟阵。(详见Topcoder) 因M为拟阵,根据拟阵的性质,我们可以把 S中的元素从大到小按顺序贪心考虑加入一 个初始为空的集合T中,若不违背必胜的状 态就加入。 答案即为没有加入集
2、合T中的元素和。 此算法可通过100%的测试点。 棋盘游戏 这题在考场上不容易想到正确思路。 但是同上题一样,此题也没有输出DRAW的 情况(若A不能在第一回合干掉B,则B必胜 ,原理同象棋中的卒与马,B只须把A往角 落中赶即可)。 模拟驱赶的过程?怎么模拟? 考场中有人写模拟得了此题的最高分,通 过了44%的测试点。 此题为博弈论,找N/P态即可。 定义tijxy5维状态,表示A在(i,j) ,B在(x,y),当t=0时表示为A先手,否 则为B先手。 根据状态的转移建图,当i=x且j=y时为最初 的P态,将所有一步操作能进入P态的标 记为N态,如果从某个状态开始的所有一 步操作都只能进入N态
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- CQOI2013 简单 解析
链接地址:https://www.31doc.com/p-2142107.html