cqoi201秒3简单解析.pptVIP

CQOI2013 简单解析 Leqsott 新Nim游戏 显然没有输出-1的情况，A必胜。（最坏情况下第一轮只剩一堆） 直接暴力枚举每种第一轮A拿了过后的状态，再暴力枚举第一轮B拿了过后的状态，然后对剩下的进行普通的Nim游戏。 此算法可通过50%的测试点。 若把每堆火柴看作集合S中的元素，每种A拿后必胜的状态看作集合L中的元素（即L为集合的集合），据分析及证明，M=｛S，L｝为拟阵。（详见Topcoder） 因M为拟阵，根据拟阵的性质，我们可以把S中的元素从大到小按顺序贪心考虑加入一个初始为空的集合T中，若不违背必胜的状态就加入。 答案即为没有加入集合T中的元素和。 此算法可通过100%的测试点。 棋盘游戏 这题在考场上不容易想到正确思路。 但是同上题一样，此题也没有输出DRAW的情况（若A不能在第一回合干掉B，则B必胜，原理同象棋中的卒与马，B只须把A往角落中赶即可）。 模拟驱赶的过程？怎么模拟？ 考场中有人写模拟得了此题的最高分，通过了44%的测试点。 此题为博弈论，找N/P态即可。 定义[t][i][j][x][y]5维状态，表示A在（i，j），B在（x，y），当t=0时表示为A先手，否则为B先手。 根据状态的转移建图，当i=x且j=y时为最初的P态，Ⅰ将所有一步操作能进入P态的标记为N态，Ⅱ如果从某个状态开始的所有一步操作都只能进入N态，则标记为P态。 用F表示此状态为N/P，G表示达到此状态所需的步数（倒推的）。 当为Ⅰ时，当前状态的G取能到达的状态中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。 定义 [t][i][j][k][p]5维状态，F为此状态下的最小C’值，从低位枚举，表示枚举到第t位，A已放i个1，B已放j个1，C已放k个1，若p=0，表示该状态无进位；否则表示有进位。 同时枚举第t位时A’和B’放0还是1，结合上一位的进位，算出该位是否有进位与C’该位上为0还是1。 设该位上A’、B’与上次进位之和为res，则有f[t][i+x][j+y][k+(res1)][res1] = Min(f[t-1][i][j][k][p]+((res1)(t-1)))，x，y为0或1。 此算法可通过100%的测试点。 图的逆变换 此题为本次省选中最简单的一题，但是AC率却很低，可能是大家把模型想复杂了。 原图中的一条边为新图中的一个点，原图中两条相接的边为新图中的一条边，即a→b为点ab，a→b→c为ab→bc。 题目要求根据新图判断是否存在一个原图。 设新图中ab出发可达bc(1)、bc(2)、、bc(i)、、bc(n)。则对于bc(i)和bc(j)，若其它任意一个点对于这两个点都是可达或不可达，则存在原图；若存在一个点对于这两个点一个可达一个不可达，则不存在原图。 此算法可通过100%的测试点。 新数独 有哪些信誉好的足球投注网站题。 仔细处理输入。 可先对3*3的小9宫格搜，再对3*3的大9宫格搜，hash判下重即可。 因题目保证只有一种目标答案，搜到后快速退出DFS。 此算法可通过100%的测试点。