算法合集之《从《parity》的解法谈程序优化》

《算法合集之《从《parity》的解法谈程序优化》》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、让我们做得更好——从《parity》的解法谈程序优化福州第三中学高三（3）孙林春Parity题意描述一个序列全部由0和1构成。你将知道其中某些连续的区间段中（例如，从第三位到第五位）含有的1的个数是奇数还是偶数，这些信息按照给出顺序编号。然而，这些信息有可能是自相矛盾的。你的任务是编程求出一个最大编号，使得存在一个序列，满足此编号及此编号之前的所有信息。样例输入：10{序列的长度L，1<=L<=1000000000}5{信息总数N,1<=N<=5000}12even{表示从第一位到第二位中含有偶数个1}34odd{表示从第三位到第四位中含有

2、奇数个1}56even16even710odd样例输出：3{即可以找到一个序列，使之满足前三条信息，但找不到一个序列，使之满足前四条信息}是否与已知条件矛盾中止并输出读入是否结束读入一个新区间算法框架是是否否原始的考虑——算法一预备：两个区间之间的关系具体做法是：将当前的区间与已知区间逐个进行比较：如果存在某个已知区间与之重合，则直接判断是否出现矛盾；否则，如果有左端点或右端点与其相同的区间，则对区间进行删截，同时修改区间信息，并将得到的新区间重新与已知区间比较，直至与所有已知区间的左右端点都不相同为止；最后将剩下的区间插入已知区间的队列中

3、。将当前区间的信息分别与每个已知的区间的信息进行比较，判断是否出现矛盾。两个区间之间的关系1相离区间1区间22重合区间1区间2相交区间1区间2包含区间1区间1区间2区间2两个区间之间的关系深入分析——算法二改进点：保留部分重复的区间及信息，而把注意力集中到其中一些能够直接导出矛盾信息的区间上来。做法：当读入一个新的区间并进行判断时：若已知区间队列中有与其具有共同的左端点的区间，我们只需留下它们之中右端点小的一个，较长区间长出的部分则可以看成是一个新的区间，并重新与其他已知区间进行比较；若没有一个已知区间与当前区间有相同的左端点，则将当前区间

4、作为一个新的左端点的代表区间插入队列中。局部优化——算法三改进：将原有的端点值离散化后对端点重新编号。我们将所有出现过的端点值放入另一个数组中，并对该数组进行快速排序，然后把用二分法在该数组中查找一个端点值所得到下标作为该端点的新编号。最简单的办法：开一个数组，将左端点的值作为数组的下标，数组中的值表示该左端点的代表区间的右端点的值，若这样的区间不存在，则值记为0。离散化端点值，提高查找效率挖掘本质——算法四区间奇偶性描述法：以某个区间段中所含的1的个数的奇偶性来描述01序列P[i,j]=前缀奇偶性描述法：以前i位中所含1的个数的奇偶性来描

5、述01序列Parity[i]=两种描述法的对应关系若p[i，j]=true，则parity[i-1]xorparity[j]=true；若p[i，j]=false，则parity[i-1]xorparity[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决

6、定了parity[i-1]的值与parity[j]的值是否相同；实际上也就决定了i－1和j是否属于同一个等价类。这样，原来对每个区间[i，j]进行约束的条件就转化成了元素i-1，j是否属于同一个等价类的判断条件。定义集合same[i]表示已知与i在同一个等价类中的元素集合集合opp[i]表示已知与i不在同一个等价类中的元素集合根据已知条件，若有：parity[j]＝parity[i]，则j∈same[i]；parity[j]≠parity[i]，则j∈opp[i]；初始时，same[i]={i}，opp[i]=Ф。具体做法是if与已知条件不

7、矛盾thenifp[i,j]=truethenbegin合并(same[i],same[j])；合并(opp[i],opp[j])；endelsebegin合并(same[i],opp[j])；合并(same[j],opp[i])；endelse中止判断；依次处理每条区间信息：具体实现时，我们可以应用并查集来完成所需的操作。理论上已经证明，如果利用按秩合并与路径压缩等技巧对程序进行充分优化，并查集这种数据结构的时间复杂度是O（N*α(N))的。其中，α(N)是单变量阿克曼函数的逆，它是一个增长速度比logN慢的多但又不是常数的函数。同时，我

8、们已经将算法主体部分的时间复杂度降为O（N*α(N))的，查找部分再用O（logN）的二分查找就显得不合适了，因此我们考虑用更加高效的哈希表来实现查找。哈希表的查找时间是O（1）