第七届北航程序设计大赛现场决赛解题报告.doc

第七届北航程序设计大赛现场决赛解题报告a. 大囧这题应该还算简单吧，写个递归函数对一个字符矩阵作画就行了，比如：void draw(const int n, char mapmapsize, const int r, const int c) int size = (1 (n + 2); maprc = mapr + size - 1c + size - 1 = +; maprc + size - 1 = mapr + size - 1c = +; for (int i = 1; i size - 1; i+) maprc + i = mapr + size - 1c + i = -; mapr + ic = mapr + ic + size - 1 = |; if (n = 0) return; for (int i = 2; i size / 2 - 1; i+) mapr + ic + size / 2 - i = /; mapr + ic + size / 2 + i - 1 = ; draw(n - 1, map, r + size / 2, c + size / 4);一个关键的问题其实是：这个字符矩阵应该全部初始化为32号字符（空格）而不是0号字符（虽然这种情况，你的ide在屏幕上输出的内容可能“看起来”是正确的）。很多人都是错在这一点上。b. 切棍棍这是一个需要一点分析的博弈问题。关键的策略是“模仿”，假设现在有偶数根等长的棍子，无论先手做什么动作（选哪一根切成多少段），后手总是可以完美“模仿”先手的动作。扩展一下，如果所有棍子长度不同，但每种长度的棍子都是偶数根，那么后手依然可以使用“模仿”策略，并且还能保证动作后先手依然面对“每种长度的棍子都是偶数根”的局面。于是：（1） 如果m已经没法切了，那么先手就已经输了。（2） 如果m可以切：（1） 如果n为偶数，那么先手必败（因为后手可以使用“模仿”策略）。（2） 如果n为奇数，那么就选一根将其切得尽可能碎，以至于切成的每段都没法再切，于是后手就面对偶数根等长的棍子了，先手就可以使用“模仿”策略保持不败，即先手必胜。其实这一题题面忘记说明切成的棍子长度必须仍旧是整数了。这样的话判断m是否可以切，只需要一个o(sqrt(m)的循环判断m是否有大于k且小于m的约数即可。如果允许切成的棍子长度为任意实数，那么能不能切就取决于m是否大于k*2。不过数据没卡这个问题，两种理解都可以过c. 马后这一题最讨厌的就是有“象”这么个奇怪的东西混再里面了，还不准拆它的路径，搞得计数的时候好像还挺麻烦。其实你把“象”看做每次只能斜着走一步的“士”就好了，因为不准拆的跨越式的“象步”和每次走一步的“士步”在计数时其实是完全一样的发现这个坑以后，这一题就是个单纯的递推：fi,j = fi-1j-2 + fi-2j-1 + fi-1j-1记得判断下标超界以及取模就行。做好预处理之后，每组数据只要直接输出结果就行了。时间复杂度为o(n*m+t)。d. 最大路劲值方法是动态规划（记忆化搜索其实是一回事）。假设所有边的权重保存在对称矩阵w中。可以用fij表示从起点s走j步走到i号点，路径上所有边的权重的最小值最大是多少（有点拗口哈，即从起点s有很多条长度为j的路径能够到达i，每条路径肯定都有权重最小的边，而各条路径的权重最小的边的最大值就是fij）。那么考虑fij对应的路径，其肯定有倒数第二个节点，假设是k，那么根据fij的定义就有：fij = min(fkj-1, wki)依据这一点，可以得到fij的状态转移方程：fij = max min(fkj-1, wki) | k = 1.n 且 k != i 初始也很简单，就是：fs0 = +，fi0 = 0（i != s）于是，最后的结果就是：answer = max ftj / j | 0 j = n则必定有环，有环就必定不会最优，所以j应该小于n）关键就是将路径长度作为状态函数的参数。e. n以内约数最多的数假设n分解质因数以后的结果是：那么n的约数就有这么多个：即与其质因子其实没有关系，而只是与质因子的指数有关。因为我们想要找到约数最多且尽可能小的数。所以p1、p2、pk肯定是最小的那些质数。考虑到前16小的质数之积已经超过109了。于是就只需要枚举最小的16个质数的指数分配情况，就可以求得要求的数。可以考虑用一个递归函数来处理枚举和求解，比如：const int pcount = 16;const long long p = 2,3,5,7,11,13,17,19,23,29,31,37,41,43,53,59;void find(int i, long long n, int maxe, long long &w, long long &y) / 现在前 i 小的质数都不能用，要找到不超过 n 且各质因子指数不超过 maxe 的数 / 将这个数和其约数的个数用 w 和 y 返回 w = y = 1; if (i = pcount) return; int e = 0; / pi 的指数 long long pe = 1, we, ye; while (pe = n & e y | (ye * (e + 1) = y & we * pe b - 1e-13才能等价于数学上的a = b，a b + 1e-13才能等价于数学上的a b。h. 简单的序列操作这一题的策略是“分段”。和预赛的gg的小金库一样，首先还是需要进行坐标离散化（具体请参考网络预赛的解题报告）。最终得到不超过100000个块，每个块里的元素总是会有相同的值，且总是同时被一个操作所覆盖。将所有的块分成若干段，使得每段都有blocklen个块，那么段数blockcount就应该是：块数/blocklen+1。对于每个段，保存：（1） 包含的所有的块的“标记值”（初始全为0）：int valueblocklen;（2） 包含的所有的块的长度（离散化时得到）：int lenblocklen;（3） 整段的乘法系数（初始为1）：int mu;（4） 整段的加法系数（初始为0）：int ad;（5） 整段的所有块的“实际值”与块长乘积之和，即包含的所有元素之和（初始为0）：int sum;（6） 整段包含的所有块的长度之和，即包含的元素个数（根据len得到）：int totallen;（7） “标记值”为指定值的元素的个数（初始时只有cnt0为totallen其他都是0）：int cnt10001;可以发现上面强调了“标记值”和“实际值”，即段中各块的标记值并不是其实际值，而是：标记值 * mu + ad = 实际值于是：（1） 对一个完整的段做加c的操作，那么其实各块的“标记值”是不需要改变的，只需要ad += c再sum += c*totallen即可。（2） 对一个完整的段做乘c的操作，则是mu *= c再ad *= c再sum *= c即可。（3） 求这个完整的段的和最简单，返回sum即可。（4） 求此完整的段中值等于c的元素个数，则会稍微麻烦些：a) 如果mu = 0i. 如果ad = c，那么返回 totallenii. 否则返回0b) 如果mu 0i. 如果c=ad且c-ad是mu的倍数，则返回cnt(c-ad)/mu，ii. 否则返回0即对于完整的块做四种操作中的任意一个，都不会改变标记值序列value和标记值计数器cnt。时间复杂度都是o(1)的。如果不是对完整的段而是对段的一部分施加操作，那么就先对全段做一遍扫描，将各个块的标记值还原为实际值（在改变某个块的标记值时可以o(1)维护好标记值计数器cnt）。然后再对被施加操作的那一部分进行相应的操作就可以了。时间复杂度是o(blocklen)的