7.13动规测试题目习题讲解

1、习题讲解清华大学张瑞喆Cant stop得分情况：Cant stop【题目大意】给一个长度为 10w 的序列,每个位置有 4 个元素。需要选出 k(k=2或 3)个关键字,使得包含至少一个关键字的连续段最长,求最长的连续段中起始位置最靠前的。算法0对于n=1000部分选哪些数作为关键字？先枚举起点在哪里在起点处选择起点位置的某个元素作为第一个关键字算法0第二个关键字选择什么？选第二个元素的某个值？如果第二个元素的某个值已经和第一个关键字相同，则不必如此做。向后拓展至某个元素，其不包含第一个关键字。算法0选择了第二关键字后，继续向后拓展，跳过所有已经包含第一关键字或第二关键字的。如果k=3，则枚

2、举第三关键字，方法同上。算法0复杂度分析：时间复杂度O(Tdk*n2)期望得分：45算法1算法0时间复杂度过高是因为，单个元素被扫描的次数达到了O(n)级别。要想通过全部数据，必须减少单个元素的扫描次数自由吐槽（Free talk）单调维护？数据结构？算法1实际上可以用分治的做法来实现分治：取出序列的中间点，答案就有两种可能性：A：目标序列完全在左边/右边B：目标序列跨越该中间点算法1对于A部分，递归求解。对于B部分，枚举该中间点的哪个元素被选为关键字。像算法0一样，向左右两边拓展。拓展至极大后，枚举接下来向左or向右，然后枚举左边/右边那个元素的某个值做关键字，重复此过程。算法1复杂度分析：

3、时间复杂度O(Tnlogn*dk*2(k-1)这能过？算法1实际测试，std最大点时间在1s内原因：若答案很大，则递归到小区间时可以直接剪枝，若答案很小，则每次扫描范围不大。减肥食品给出一个长度为n的序列s，其中元素为非负整数且两两不相等要求构造两个序列a,b，长度均为n,满足以下条件：1、ai+bi=si 0=ai,bi=si（1=i=n）2、a,b中至少各有（2*n）/3（向下取整）种元素【题目大意】【数据规模】对于20%的数据,n=10对于40%的数据，n=200对于50%的数据,n=1000对于100%的数据n=5000，0=si=106自由吐槽（Free talk）随机数据好像解很多

4、？如何构造无解？如何获得各种奇怪的分数？我们在认真研究了题面后可以发现：我们需要满足两个序列中分别有(2*n)/3（向下取整）个不同元素，则必然有n/3个si被分成ai,bi，且ai,bi都可计入不同元素总数，其余n/3个满足ai,bi。于是我们设法对这n个元素构造两个序列满足条件用如下图片说明（红色线为满足a的数，蓝色为b）前n/3个ai=i-1中间n/3个bi=i-1最后n/3个bi=n-i由此，构造出整个数列因为s序列元素是两两不同的，所以不会有无解前n/3个ai满足条件，计入总数接着n/3个bi满足条件，计入总数最后n/3个ai,bi同时满足条件，计入总数最优决策【题目大意】给n个bo

5、ol变量赋值，使得m个bool表达式中为真的个数尽量多数据1、2N十分小，2N枚举所有可能的取值进行判断即可数据3、4所有的表达式都是a|b的类型的，符合2-SAT形式，最优解可以满足所有表达式补充知识:经典问题2-SAT2-SAT用于解决的模型即为3,4两点的模型，有若干形如xi|xj的表达式需要为真，求给所有x赋值的一种方案。拆点：先将每个点拆成xi0和xi1两个点，若xi0被标记，则xi为假，若xi1被标记则xi为真。补充知识:经典问题2-SAT约束条件：每个表达式都约束了xi和xj不能同时为假。即xi为假可以推出xj为真，xj为假可以推出xi为真。那么，对这些推理关系连单向边。求解，从

6、小到大枚举每个变量，若没有被标记则枚举其真假，并标记。一个点被标记后会导致其所有出边连的点被标记，并重复该过程补充知识:经典问题2-SAT若一个节点标记为真或假均会引起矛盾，则无解（也无法通过调整之前的决策求解）。否则，全部点都被标记后得到解。数据5、6所有的表达式都是(a&b&c.)|(d&e&f.)组成的等价于(a|d)&(a|e)&(a|f)&.也可以用2-SAT解决，Data6有3个表达式，不能满足数据7观察数据可知：每个表达式都是一些标号接近的变量组成的状压DP数据8有一些连续位必然一起出现，由于都是&，将连续的几位视为1位。这样转化后，每个表达式都只有两个变量，且每组变量都只能满足一个表达式的一半，二分图匹配即可数据10前99个变量没有在表达式中出现每个表达式都是类似x100&x101&x102&112的L型或者10个的(x10