解题报告范例

《解题报告范例》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、IOI2010国家集训队第二次作业GCJ09Final解题报告江苏省常州高级中学吴翼Doubly-sortedGridGCJ09FinalProblemC【简要描述】给出一个N*M的方格纸，在方格内可以任意填写字母a到z，但是必须保证，任意一行从左到右字母的字典序必须保证不降，同时任意一列也必须保证字典序不降。现在一些格子已经填上了一些字母，现在要求将剩余没有填写的空格子填满，同时要使得整个方格纸上满足双调不降的要求。问总的方案数取模10007的值。SmalldatasetN,M≤4LargedatasetN,M≤10【分析与算法设计】看到这个问题当然最简

2、单的想法就是搜索了。不过，注意到每一个格子可以填26种不同的字母，所以简单考虑就可以发现，对于即使单独1*M的方格纸，可能填写的数目也将达到O(26M)的规模——所以简单的搜索是绝不可行的。但是，同时我们也可以注意到，其实我们在进行搜索的时候进行了很多的重复搜索，所以我们需要尝试确立一些搜索的状态来进行记忆化搜索，或者进行递推。算法1：注意到在Small中，虽然总的方案数很多，但是注意到行数和列数都不是很大，因此我们可以尝试进行状态压缩的动态规划。沿用状态压缩动态规划的一般方法，我们记录扫描线上的状态进行转移。aceebdfgbf如有图所示，其实我们需要记

3、录的状态仅仅是紫色格子中的字母填写情况，蓝色格子中的已经填写过的字母情况我们其实就不用知道了——通过紫色格子已经可以反映出蓝色格子的字母状况了。然后我们只要枚举橘红色格子填写什么字母然后进行状态的转移即可。那么考虑紫色扫描线上的点只有O(M)，相应的，状态数即为O(26M)，这在Small中，是完全可以接受的。至于一些格子已经填写了一些字母，我们只需要在转移到具体的格子然后再进行判断即可，算法并没有什么关键的转变。时间复杂度：O(NM26M)第4页共4页IOI2010国家集训队第二次作业GCJ09Final解题报告江苏省常州高级中学吴翼空间复杂度：O(NM

4、+26M)期望得分：Small通过观察到在Large中，虽然N和M仍然不大，仅仅10而已，但是，考虑到26个字母的可能填写方案，显然的，仍和关于字母具体信息的扫描线记录方式都是完全行不通的。我们知道，记录一个位置到底是什么字母，就需要花费26的记录代价，这是导致我们无法记录信息的关键问题。那么，我们能不能分离这一问题，并不去记录某一个位置是什么字母，而去记录每一种字母到底占了哪些位置呢？显然的！算法2：这里我们就需要利用到双调有序这一重要性质了。如果在格子(x1,y1)内的字母比(x2,y2)内的字母字典序小，那么则必然有这样的限制条件：x1≤x2，y1≤

5、y2。所以，对于字母c1，以及恰好比其大一个字典序位置的字母c2，其分界线一定是一个从左下角到右上角的连续折线，并且任意一点只会向上，或者向右：aaabbbaaabbcaabbcebbbbcebbbeeebbceeee如右图所示，我们这里标出了字母a，b，c下方的分界线，注意这里字母c所在的格子并不是连通的，所以，字母c的分界线是存在一部分与b的分界线是重合的。而其实字母d的分界线是完全和字母c重合的。字母e的分界线就是整个方格的下拐折线。并且任意字典序大于e的字母的分界线都是与字母e重合的。我们不妨称这样的一条从左下角到右上角的折线为一条路径。对于两条路

6、径P1和P2，如果满足两条路径不严格相交，并且路径P1存在一部分严格的处在在P2的上方，则我们称P1

7、。于是我们可以基于上述的路径描述的方法，设立动态规划的状态。我们设f[P][k]表示字母当前填写到路径P上方的所有格子，并且当前路径P是第k小的字母的分界线。于是我们可以有如下转移：由于路径总数是O(2N+M)级别的，每次我们需要枚举上一条分界线在哪里，因此，这样我们就得到了一个复杂度为O(C4N+M)的动态规划算法。但是，路径数达到了105第4页共4页IOI2010国家集训队第二次作业GCJ09Final解题报告江苏省常州高级中学吴翼级别，如果我们这样暴力枚举分界线，显然是无法通过测试的。那么，我们改如何优化转移呢？CBA首先，对于状态f[P][k]，如

8、果路径P上方任意格子都不包含第k小的字母，显然这种情况下，可行方案