信息学试题cqoi2013简单解析

1、CQOI2013 简单解析Leqsott新Nim游戏显然没有输出-1的情况，A必胜。（最坏情况下第一轮只剩一堆）直接暴力枚举每种第一轮A拿了过后的状态，再暴力枚举第一轮B拿了过后的状态，然后对剩下的进行普通的Nim游戏。此算法可通过50%的测试点。若把每堆火柴看作集合S中的元素，每种A拿后必胜的状态看作集合L中的元素（即L为集合的集合），据分析及证明，M=S，L为拟阵。（详见Topcoder）因M为拟阵，根据拟阵的性质，我们可以把S中的元素从大到小按顺序贪心考虑加入一个初始为空的集合T中，若不违背必胜的状态就加入。答案即为没有加入集合T中的元素和。此算法可通过100%的测试点。棋盘游戏这题在考

2、场上不容易想到正确思路。但是同上题一样，此题也没有输出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态，则标记为P态。用F表示此状态为N/P，G表示达到此状态所需的步数（倒推的）。当为时，当前状态的G

3、取能到达的状态中G的最小值+1。（尽快获胜）当为时，当前状态的G取能到达的状态中G的最大值+1。（拖延时间）最后看初始状态的F判断输赢，G判断步数。此算法可通过100%的测试点。二进制A+B统计A中有多少1，B中有多少1，C中有多少1，暴力枚举A中1放的位置，B中1放的位置，相加计算C是否1刚好有那么多。若刚好有那么多1且位数不超过最大位数，比较出最小的C，即为答案。此算法可通过44%的测试点。数位DP。定义 tijkp5维状态，F为此状态下的最小C值，从低位枚举，表示枚举到第t位，A已放i个1，B已放j个1，C已放k个1，若p=0，表示该状态无进位；否则表示有进位。同时枚举第t位时A和B放0

4、还是1，结合上一位的进位，算出该位是否有进位与C该位上为0还是1。设该位上A、B与上次进位之和为res，则有fti+xj+yk+(res&1)res1 = Min(ft-1ijkp+(res&1)(t-1)，x，y为0或1。此算法可通过100%的测试点。图的逆变换此题为本次省选中最简单的一题，但是AC率却很低，可能是大家把模型想复杂了。原图中的一条边为新图中的一个点，原图中两条相接的边为新图中的一条边，即ab为点ab，abc为abbc。题目要求根据新图判断是否存在一个原图。设新图中ab出发可达bc(1)、bc(2)、bc(i)、bc(n)。则对于bc(i)和bc(j)，若其它任意一个点对于这两个点都是可达或不可达，则存在原图；若存在一个点对于这两个点一个可达一个不可达，则不存在原图。此算法可通过100%的测试点。新数独搜索题。仔细处理输入。可先对3*3的小