11.11考试总结

· · 个人记录

总结

切A题花了一个小时，我做简单题的速度有待提高

今天的B是个单纯的思维题，这是我的弱项之一

二分是个神奇的东西，当单独检查mid值不满足二分性质时还可以将mid值相对于正确答案的大小拿来二分(只有小于等于和大于两种情况)

整体二分nb

详细代码见群体联系1110题目集http://42.247.7.121/zh/Contest/Details/1088

A

给你一个只由字符A,B,C组成的字符串，每次操作可以把ABC这养的子串变为BCA，问这样的变化最多能进行多少次

显然可以发现操作的顺序不会影响结果

然后对于每个A...ABCBC...BC，显然答案是A的个数 * BC的个数，但是这么算会很麻烦因为这样多段连起来后还有可能组成新的。

所以我们可以单独处理前导A，每次将形如A...ABC的子串变为BCA...A，然后变化的次数就是前导A的数量。由于我们每次把A都处理完了，A都会被丢到后面去，不会与其它的BC组合了，所以这样算不会算重也不会少算

B

原题AGC034E

给你一颗树，树上有一些节点上有人。现在每次操作都可以指定两个距离(边数)相差大于等于2的人，让他们沿他们之间的路径靠拢，最后让他们通过这种方法靠拢直到所有人都位于同一个点点上，点数小于等于2000。如果无论如何都走不到一个点上输出-1 。

首先，我们把靠拢说成两人向他们的lca提。

显然，数据范围告诉我们可以O(n)的代价枚举根节点，O(n)或者O(nlogn)来检查当前根节点是否可行，可行的话将答案与(以当前节点为根节点的前提下所有有人的点的深度之和/2)取min。

接下来说如何让判断是否有解。

首先，如果在钦定了根节点的情况下，那么对于一个节点内的有人的点，提不同子树的人和提相同子树的人情况是不一样的。将两个人向非根方向提一定不优(一个向下一个向上)，这样只会使你的答案多加1。然后，假设当前节点所有不同的子树所含的有人节点的深度值和(相对于当前节点)分别为f[1],f[2],...,f[n],那么这个问题就相当于每次取两个数使其-1，问能否将所有数全部变0.解决方法是比较sum-max(a[i])和max(a[i])，如果 sum - max（f[i]） < max(f[i])，那么最后一定会剩下max(a[i])-(sum-max(a[i]))，否则只会剩下0或者1(取决于奇偶性)。然后可以发现，一个子树可以通过它的子树内的点互怼互相提lca实现深度和-2-2-2...-2的操作，所以这里应该把深度和最大的子树自己提了之后的深度和最小值g[i]拿去和sum-max(a[i])比较。所以要递归处理深度和最大的子树，算出实际上的最大深度和的最小值，然后判断。

值得一提的是，提根以及提子树lca的操作的先后顺序并不影响最后计算实际上最大深度和的最小值，这个可以手玩样例发现。

C

给你一个无向连通图，每次询问从两个点x,y出发，在恰好经过z个不同的点后，所经过的边的编号最小值是多少。点数，边数，编号，询问全部1e5级

首先，沿着最小生成树走显然最优，所以可以二分答案，每次验证答案把所有不大于当前答案值的边全部丢到带权并查集里，这样是n^2logn的。然而这题可以整体二分，然后就过了。

还有一种做法是kulskral重构树(平静最小生成树)。对于一个需要check的mid值，从两个节点开始向上倍增，分别找到最大的权值<=mid的"虚点"，这两个找出来的点的子数内的叶子节点总数就是当前答案能去到的最大连通块(详见瓶颈生成树定义与应用)，注意两个倍增出来的点相同和不同的情况。注意二分时只能将l相对于mid调大不能将r相对于mid调小。

D

给你一个长度为(2 * n-1) 的排列，每次操作为依次将相邻的三个数的中位数取出来，最后拿少了两个的中位数序列取代原序列，重复此操作知道只剩一个数为止，问最后一个数是多少。

具体操作过程详见样例：

    1 6 3 7 4 5 2
=>    3 6 4 5 4
=>      4 5 4
=>        4

这道题的思路非常清奇，这是一个二分答案。但是如果直接二分答案值，显然它是没有二分性质的。但是我们可以"半强行"地使它具有二分性质。由于在取中位数地时候只关心大小关系，而且当前尝试地答案值相对于正确答案值之间只有大于和小于等于两种关系(本来是>,<,=三种的，但是二分只能有两种关系所以将<和=合并)，受此启发我们可以二分一个答案值，检查当前答案是不是小于等于正确答案值。

check一个答案是否合法时，使用经典的将小于等于mid值的数全部变为0，大于mid的值的数全部变为1的手段

经过这样的处理后，对于上面那组样例，如果当前mid值为4，那么一路下来的数就变成了

    0 1 0 1 0 1 0
=>    0 1 0 1 0
=>      0 1 0
=>        0

然后开始找规律（

不难发现，如果初始状态下有长度>=2的连续0或者连续1，那么这几列一直到最下面都会和初始状态的0，1保持一致，称其为柱。对于其周围的连续01交替序列， 每向下一层柱就会像两边扩展一格直到碰到其他的柱为止，而且最后的中位数所在的位置一定会被柱扩展到(中间的数两侧各有n-1个数，而取中位数操作最多进行n-1轮)，所以可以直接O(n)扫找到离正中间最近的柱的边界，然后就可以知道中位数相对于mid是什么大小关系了。特别地，如果没有柱，那么最后的中位数将和首/末位相对于mid的大小关系保持一致(见上面那组样例)。

然后附上一张含柱的对"扩展"的说明图

然后我们就可以快乐的二分啦