算法合集之〔从〔parity〕的解法谈程序优化〕.ppt

让我们做得更好 ——从《parity》的解法 谈程序优化 Parity题意描述 一个序列全部由0和1构成。你将知道其中某些连续的区间段中（例如，从第三位到第五位）含有的1的个数是奇数还是偶数，这些信息按照给出顺序编号。然而，这些信息有可能是自相矛盾的。你的任务是编程求出一个最大编号，使得存在一个序列，满足此编号及此编号之前的所有信息。 原始的考虑——算法一 预备：两个区间之间的关系 两个区间之间的关系 1 相离 区间1 区间2 深入分析——算法二 局部优化——算法三 最简单的办法：开一个数组，将左端点的值作为数组的下标，数组中的值表示该左端点的代表区间的右端点的值，若这样的区间不存在，则值记为0。 挖掘本质——算法四 区间奇偶性描述法：以某个区间段中所含的1的个数的奇偶性来描述01序列 两种描述法的对应关系 若p[i，j]=true， 则parity[i-1] xor parity[j]=true； 若p[i，j]=false， 则parity[i-1] xor parity[j]=false； parity数组的所有下标构成了集合 A＝{1，2，…，L}。 这个集合根据元素i所对应的parity[i]的值是True还是False被划分成了两个等价类A1和A2， 所有parity[i]=True的i归入A1中， 所有parity[i]＝False的i则归入A2中。 根据对应关系，p[i，j]的值是True还是False决定了parity[i-1]的值与parity[j]的值是否相同；实 际上也就决定了i－1和j是否属于同一个等价类。 这样，原来对每个区间[i，j]进行约束的条件就转化成了元素i-1，j是否属于同一个等价类的判断条件。 运行时间比较 总 结 通过解决这道题，我们看到了充分优化算法的重要作用，并从中总结出优化算法的一些一般规律： 1 从问题出发，深入挖掘题目本质； 2 针对当前算法的不足加以改进。 但归根到底，这些优化都是建立在对问题本身及数据结构深刻理解的基础上的。只有充分认识问题，理解问题，并熟练掌握各种数据结构，才能针对问题设计出高效而实用的算法并加以实现。 * * 福州第三中学高三（3） 孙林春 样例输入： 10{序列的长度L，1=L=1 000 000 000} 5 {信息总数N,1=N=5000} 1 2 even {表示从第一位到第二位中含有偶数个1} 3 4 odd {表示从第三位到第四位中含有奇数个1} 5 6 even 1 6 even 7 10 odd 样例输出： 3? {即可以找到一个序列，使之满足前三条信息，但找不到一个序列，使之满足前四条信息} 是否与已知条件矛盾 中止并输出 读入是否结束 读入一个新区间 算法框架 是 是 否 否 具体做法是：将当前的区间与已知区间逐个进行比较：如果存在某个已知区间与之重合，则直接判断是否出现矛盾；否则，如果有左端点或右端点与其相同的区间，则对区间进行删截，同时修改区间信息，并将得到的新区间重新与已知区间比较，直至与所有已知区间的左右端点都不相同为止；最后将剩下的区间插入已知区间的队列中。 将当前区间的信息分别与每个已知的区间的信息进行比较，判断是否出现矛盾。 2 重合 区间1 区间2 相交 区间1 区间2 包含 区间1 区间1 区间2 区间2 两个区间之间的关系 改进点：保留部分重复的区间及信息，而把注意力集中到其中一些能够直接导出矛盾信息的区间上来。 做法：当读入一个新的区间并进行判断时：若已知区间队列中有与其具有共同的左端点的区间，我们只需留下它们之中右端点小的一个，较长区间长出的部分则可以看成是一个新的区间，并重新与其他已知区间进行比较；若没有一个已知区间与当前区间有相同的左端点，则将当前区间作为一个新的左端点的代表区间插入队列中。 改进：将原有的端点值离散化后对端点重新编号。我们将所有出现过的端点值放入另一个数组中，并对该数组进行快速排序，然后把用二分法在该数组中查找一个端点值所得到下标作为该端点的新编号。 离散