解题报告范例.docVIP

Doubly-sorted Grid GCJ09 Final Problem C 【简要描述】 ≤4 Large dataset N,M≤10 【分析与算法设计】 如有图所示，其实我们需要记录的状态仅仅是紫色格子中的字母填写情况，蓝色格子中的已经填写过的字母情况我们其实就不用知道了——通过紫色格子已经可以反映出蓝色格子的字母状况了。 然后我们只要枚举橘红色格子填写什么字母然后进行状态的转移即可。 那么考虑紫色扫描线上的点只有O(M)，相应的，状态数即为O(26M)，这在Small中，是完全可以接受的。 至于一些格子已经填写了一些字母，我们只需要在转移到具体的格子然后再进行判断即可，算法并没有什么关键的转变。 时间复杂度：O(NM26M) 空间复杂度：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的上方，则我们称P1P2，同样的，我们也可以定义P1≤P2所需要满足的情况。 比如在上面这个例子中，a的分界线，也就是路径Pa满足PaPb，而Pc=Pd。 容易发现，在一种合法的填写方式中，我们设第k小的字母的分界线为路径Pk，则一定有Pk≤Pk+1——我们惊奇大发现，我们又挖掘出了一种数据之间的有序性，而这也正是由于字母填写的双调有序性导致的！ 我们可以发现，这样的从左下角到右上角的分界线一共有种，在Large中，这个数字也不过是184756而已——完全是我们可以接受的状态数量。 于是我们可以基于上述的路径描述的方法，设立动态规划的状态。 我们设f[P][k]表示字母当前填写到路径P上方的所有格子，并且当前路径P是第k小的字母的分界线。 于是我们可以有如下转移： 由于路径总数是O(2N+M)级别的，每次我们需要枚举上一条分界线在哪里，因此，这样我们就得到了一个复杂度为O(C4N+M)的动态规划算法。 但是，路径数达到了105级别，如果我们这样暴力枚举分界线，显然是无法通过测试的。那么，我们改如何优化转移呢？ 首先，对于状态f[P][k]，如果路径P上方任意格子都不包含第k小的字母，显然这种情况下，可行方案的总数就是f[P][k-1]。 于是现在我们即可以假设在路径P上方一定存在第k小的字母，由于路径P是第k小字母的分界线，也就是说，所有P上方的格子都是用字典序前k 小的字母填充的，而又由于存在第k小的字母，因此其一定有一些位置紧邻路径P。 那么是哪些位置呢？ 观察右图中黄色的路径。不妨设其为我们之前讨论的路径P，【实现与细节】 。 而且，我们可以利用2进制将所有路径和一个整数对应起来，不妨设路径P所对应的2进制整数表示为ID(P)，则容易发现，如果P1P2，则一定有ID(P1)ID(P2)（这里在2进制中我们也从左往右依次表示从左下角到右上角的各个拐点的前进方向），这样的好处在于，我们将路径的序与整数的序相联系起来（注意，这种对应是不可逆的），所以我们在进行动态规划的转移过程中，只要按照整数的序来进行即可——同样对于路径的记录和转移时路径的修改也可以利用数组和位运算来大大简化我们程序的书写并加快程序运行速度。 详细请参加C.cpp。 【小结】 IOI2010国家集训队第二次作业 GCJ09 Final解题报告 江苏省常州高级中学 吴翼 第4页 共4页 a c e e b d f g b f a a a b b b a a a b b c a a