解题报告范例

IOI2010 国家集训队第二次作业 GCJ09 Final 解题报告 江苏省常州高级中学 吴翼 第 1 页 共 4 页 Doubly sorted Grid GCJ09 Final Problem C 简要描述简要描述 给出一个 N M 的方格纸 在方格内可以任意填写字母 a 到 z 但是必须保证 任意一 行从左到右字母的字典序必须保证不降 同时任意一列也必须保证字典序不降 现在一些格子已经填上了一些字母 现在要求将剩余没有填写的空格子填满 同时要 使得整个方格纸上满足双调不降的要求 问总的方案数取模 10007 的值 Small dataset N M 4 Large dataset N M 10 分析与算法设计分析与算法设计 看到这个问题当然最简单的想法就是搜索了 不过 注意到每一个格子可以填 26 种不同的字母 所以简单考虑就可以发现 对于即 使单独 1 M 的方格纸 可能填写的数目也将达到 O 26M 的规模 所以简单的搜索是绝不 可行的 但是 同时我们也可以注意到 其实我们在进行搜索的时候进行了很多的重复搜索 所以我们需要尝试确立一些搜索的状态来进行记忆化搜索 或者进行递推 算法算法 1 注意到在 Small 中 虽然总的方案数很多 但是注意到行数和列数都不是很大 因此 我们可以尝试进行状态压缩的动态规划 沿用状态压缩动态规划的一般方法 我们记录扫描线上的状态进行转移 如有图所示 其实我们需要记录的状态仅仅是紫色格子 中的字母填写情况 蓝色格子中的已经填写过的字母情况我 们其实就不用知道了 通过紫色格子已经可以反映出蓝色 格子的字母状况了 然后我们只要枚举橘红色格子填写什么字母然后进行状 态的转移即可 那么考虑紫色扫描线上的点只有 O M 相应的 状态 数即为 O 26M 这在 Small 中 是完全可以接受的 至于一些格子已经填写了一些字母 我们只需要在转移 到具体的格子然后再进行判断即可 算法并没有什么关键的转变 时间复杂度 时间复杂度 O NM26M ace e bdfg bf IOI2010 国家集训队第二次作业 GCJ09 Final 解题报告 江苏省常州高级中学 吴翼 第 2 页 共 4 页 空间复杂度 空间复杂度 O NM 26M 期望得分 期望得分 Small 通过通过 观察到在 Large 中 虽然 N 和 M 仍然不大 仅仅 10 而已 但是 考虑到 26 个字母的 可能填写方案 显然的 仍和关于字母具体信息的扫描线记录方式都是完全行不通的 我们知道 记录一个位置到底是什么字母 就需要花费 26 的记录代价 这是导致我们 无法记录信息的关键问题 那么 我们能不能分离这一问题 并不去记录某一个位置是什么字母 而去记录每一 种字母到底占了哪些位置呢 显然的 算法算法 2 这里我们就需要利用到双调有序这一重要性质了 如果在格子 x1 y1 内的字母比 x2 y2 内的字母字典序小 那么则必然有这样的限制条件 x1 x2 y1 y2 所以 对于字母 c1 以及恰好比其大一个字典序位置的字母 c2 其分界线一定是一个 从左下角到右上角的连续折线 并且任意一点只会向上 或者向右 如右图所示 我们这里标出了字母 a b c 下方的分 界线 注意这里字母 c 所在的格子并不是连通的 所以 字母 c 的分界线是存在一部分与 b 的分界线是重合的 而其实字母 d 的分界线是完全和字母 c 重合的 字母 e 的分界线就是整个方格的下拐折线 并且任意字典序大于 e 的字母的分界线都是与字母 e 重合的 我们不妨称这样的一条从左下角到右上角的折线为一 条路径 对于两条路径 P1和 P2 如果满足两条路径不严格相交 并且路径 P1存在一部分严格 的处在在 P2的上方 则我们称 P1 P2 同样的 我们也可以定义 P1 P2所需要满足的情况 比如在上面这个例子中 a 的分界线 也就是路径 Pa满足 Pa Pb 而 Pc Pd 容易发现 在一种合法的填写方式中 我们设第 k 小的字母的分界线为路径 Pk 则一 定有 Pk Pk 1 我们惊奇大发现 我们又挖掘出了一种数据之间的有序性 而这也正是由 于字母填写的双调有序性导致的 我们可以发现 这样的从左下角到右上角的分界线一共有种 在 Large 中 这 M N M C 个数字也不过是 184756 而已 完全是我们可以接受的状态数量 于是我们可以基于上述的路径描述的方法 设立动态规划的状态 我们设 f P k 表示字母当前填写到路径 P 上方的所有格子 并且当前路径 P 是第 k 小 的字母的分界线 于是我们可以有如下转移 1 f P kf PkPP 由于路径总数是 O 2N M 级别的 每次我们需要枚举上一条分界线在哪里 因此 这样 我们就得到了一个复杂度为 O C4N M 的动态规划算法 aaabbb aaabbc aabbce bbbbce bbbeee bbceee e IOI2010 国家集训队第二次作业 GCJ09 Final 解题报告 江苏省常州高级中学 吴翼 第 3 页 共 4 页 但是 路径数达到了 105级别 如果我们这样暴力枚举分界线 显然是无法通过测试 的 那么 我们改如何优化转移呢 首先 对于状态 f P k 如果路径 P 上方任意格子都不 包含第 k 小的字母 显然这种情况下 可行方案的总数就是 f P k 1 于是现在我们即可以假设在路径 P 上方一定存在第 k 小 的字母 由于路径 P 是第 k 小字母的分界线 也就是说 所 有 P 上方的格子都是用字典序前 k 小的字母填充的 而又 由于存在第 k 小的字母 因此其一定有一些位置紧邻路径 P 那么是哪些位置呢 观察右图中黄色的路径 不妨设其为我们之前讨论的路径 P 如果路径上方仅适用前 k 小的字母并且至少使用了一个第 k 小的字母 则我们用橘红色颜色标出的这些下凸的格 子中 至少存在一个格子其中填写的字母是第 k 小的字母 那么到底是哪一个呢 填写了几个格子呢 我们并不知道 不过我们可以通过枚举来 确定 情况 1 格子 A 中填写了 情况 2 格子 A 和格子 B 中填写了 等等 对于格子 A 中填写的情况中 已经包含了格子 A 和格子 B 都填写了第 k 小字母的情况 可见 我们 的枚举使得总的方案数的计数出现了重复 如何提出重复呢 容斥原理 因此 转移的时候 对于状态 f P k 我们首先找图上图中橘红色的可行拐点 然后 对于这些拐点可能的情况进行枚举 并利用容斥原理进行计算 容易发现 由于任意一条路径上拐角数量是不超过 O M 的 因此 容斥的计算复杂度 为 O 2M 并且其实是远远达不到这个数量的 至于已经填写的一些格子 仍然是只需要在转移的时候进行特判即可 至此 Large 也被我们解决 时间复杂度 时间复杂度 O C2N M M 空间复杂度 空间复杂度 O 2N M 期望得分 期望得分 Large 通过通过 其实 算法算法 2 还可以进行一些优化得到更好的时间复杂度 算法算法 3 可以发现 容斥原理将我们的转移变得很慢 而实际上 我们也的确做了一些重复的 容斥 很多时候反复的容斥原理都是可以加速的 这里也是一样的 我们将状态稍作修改 f P c k 表示当前利用前 c 个字母填写了路径 P 以上的所有格子 并且第 c 小的字母 全部位于前 k 列中 这样 我们在转移的时候 只需要枚举第 k 列是否存在第 c 小的字母就可以了 我 们将容斥的复杂度转移到了状态上 并且将其大大降低 这样一来 虽然我们使得状态数增加到了 O CM2N M 但是却使得决策复杂度降低到 了 O 1 其实从本质上来说 这就是进行了一个容斥原理的加速 时间复杂度 时间复杂度 O CM2N M 空间复杂度 空间复杂度 O M2N M 期望得分 期望得分 Large 通过通过 C B A IOI2010 国家集训队第二次作业 GCJ09 Final 解题报告 江苏省常州高级中学 吴翼 第 4 页 共 4 页 实现与细节实现与细节 我们首先来说一下关于路径的表示问题 对于一条从左下角出发的路径 我们可以认为其存在 N M 个拐点 每一个拐点其要 么向上 要么向右 并且其中恰好向上 N 次 这其实和 2 进制形成了一个一一对应 向上对应 2 进制中的 0 向右对应 2 进制中的 1 那么 我们之前在容斥中所描述的下凸点 其实就对应二进制位中的 10 这样的 2 进制表示其实和路径的组合意义也是对应的 因为有 N M 个 2 进制位 要保证恰好 M 个 1 其方案总数就是 M N M C 而且 我们可以利用 2 进制将所有路径和一个整数对应起来 不妨设路径 P 所对应的 2 进制整数表示为 ID P 则容易发现 如果 P1 P2 则一定有 ID P1 ID P2 这里在 2 进 制中我们也从左往右依次表示从左下角到右上角的各个拐点的前进方向 这样的好处在于 我们将路径的序与整数的序相联系起来 注