【题解】2020牛客暑期多校训练营（第四场）

A-Finding the Order

•大致题意
有两条平行的直线AB 和CD。
给出AC, AD, BC, BD 四个距离，问是AB//CD 还是AB//DC。

•一个比较简单的做法
找到这四个距离的最大值。如果最大值来自AD 或BC，则AB//CD，否则AB//DC。

B-Basic Gcd Problem

•大致题意

•做法
观察公式，fc(x) 其实是c 的若干次方，且指数要尽量大。最好的情况下，每次只消掉一个质因子。所以fc(x)=cx的质因子个数

C-Harder Gcd Problem

•做法
p2>n 的p 必然不能匹配，将它们除去。倒序枚举所有质因子p，考虑所有是p 的倍数、且未被匹配的数，任意将它们进行匹配。如果个数是奇数就留下p2。最后把剩下的偶数都随意匹配一下。

D-Count New String

•大致题意

•定义字符串函数 ，返回一个长度为y-x+1的字符串，第i位是

•设集合 

•N<=100000

•字符集大小<=10

•核心点1

这题等价于f(S,i,n) 这n 个串的不同子串的个数

•核心点2

假设当前字符的位置是i，最近的大于等于它的字符的位置是j，那么新增的代价是j-i。f(S,i,n) 翻转后构成的字典树的大小不超过10N,所以我们要考虑这个字典树本质不同的子串

•最暴力的方法：在构成的字典树上建广义后缀自动机即可，设k 为字符集大小，复杂度O(Nk2),也可以用一些哈希或序列自动机的方法求一求。

E-Investigating Legions

•大致题意

•大致想法

•从一个点出发先把所有1 的的连通块构出来。如果其中混入了错误点，那么他和其他点之间的1 肯定偏少。难点在于m 没有给出，所以偏少的这个阈值需要进行构造一下。这个可以在本地自行生成数据测试。还可以用团与团之间0 比较多的特性去纠正一些例子。

•标算的做法

标算采用了一个迭代的形式化解法。我们的期望：对于图中的一个三元环(i, j, k)，我们总是希望他们之间的边要不全相等要不是(0, 0, 1)，却不能是(1, 1, 0)。因为后者代表了不合法情况。我们试图用迭代的方法去纠正少量的错误，使得图中不存在(1, 1, 0) 的Case。具体迭代方法详见https://arxiv.org/pdf/1706.05067.pdf

•另一个做法

F-Dividing Strings

•大致题意

把一个数字串划成若干段（至少两段），使得最大值和最小值的差尽量的小。注意不能有前导0。

•N<=100000

•一个显然而重要的性质

答案必然。因为我们总能把每一段都划成一位数。

•分类讨论

我们已经有一个全划成个位数的解了，该如何优化？

有两种可能的情况：

1.划成的每一段长度相等

2.划成的段里最大段和最小段的长度差为1。

•对于第一种情况

因为N 只有105，我们可以枚举N 的所有约数。对于给定约数，线性扫一遍判断答案、复杂度O(N√N)（而且远远不到）

•对于第二种情况

因为我们要验证答案是否能小于9，形式只可能是99…9x 和100…0y，其中x=2..9, y=0..7,因为x 不能是1，y 不能是9，容易发现，满足这种构型的方案只有O(1) 种，稍微特判一下即可。复杂度O(N)

•一些细节的说明

G-Ancient Distance

•大致题意

给一个有根树，在树上选择k 个关键点(根必须选),最小化点到最近关键祖先距离的最大值,求出k 分别为1,2,…,n 时答案的和

•基础暴力

当k 固定时，可以二分答案x,每次选择当前深度最深的点，将它的第x 个祖先设为关键点，并且删除这个关键点的子树,直到整棵树被删完，然后比较关键点数量和k 的大小关系，来改变二分的范围

•结论

有一个显然的结论，当答案为x 时，关键点数量≤n/((x+1) )+1,因为按照上面的贪心，每次挑选一个关键点时，至少能删除x+1 个节点。所以对于一个k，二分上界是O(n/k)。

•做法

我们按顺序枚举1~k，争取每次验证二分时，把复杂度和N 剥离开来，搞成和关键点数量有关。如果每次验证的复杂度是 关键点数量*log，那么容易证明总复杂度是N〖〖(log〗⁡〖N)〗〗^2 的（还有一个log 是调和级数）。

•如何验证二分的答案x

我们要使复杂度和最终放置的关键点个数有关。容易想到，我们用一颗线段树去维护整棵树的DFS 序。

•我们每次的操作是：

1.找到最深的还未被染色的节点p。

2.将p 向上x 步的节点q 置为关键点，把q 的子树区间染色。

H-Eliminate++

•大致题意

黑板上有N 个互不相同的数，且N 是奇数。每次选取连续的三个数，只将它们的中位数保留。重复上述操作直到剩下一个数字。对于原来的每一个数字x 都询问：是否存在一种擦除方法，使得最终剩下的数是x。N<1000000

•先考虑暴力

我们依次枚举一个数x，判断是否能将它保留。一个有用的转化,对于枚举的x，把大于它的数看成1，小于它的数看成0。我们的目的是把所有01 都消掉最终剩下x。

000à0, 010à0, 011à1, 111à1, 01xàx, 00xà0, 11xà1

•一个重要的引理：x 左右的01 无关。即如果原问题有解，一定存在一个方案是：把左右单独做一遍消除（只剩下一个或者两个数字）,最后左右和中间的x 再合并消除剩下x。

•引理证明

•我们可以认为，在左右各自消了一会的某个时间点后都是跨x 的消除（我们总能把之后的左右单独消这一步提前做）,注意：左边提供2 个数结合x 的消法也可以看做是左右单独的消除（而不是跨x 的消除），因为这样只能是01x 或者10x，可以在一开始就结合那一侧的数消掉这对01。由于0x0 和1x1 会使x 消失，跨区间的只能形如0x1 或1x0（然后01同时消失）。所以在最后跨区间消的时候，左右01的个数一样且互补。如果跨区间消出现了至少三次，我们可以单独把左边的三个和右边的三个在之前单独消,所以在最后的互补状态里，左右最多两个数字。基于引理和跨区间消除的性质，我们可以把原问题转化成一些左右独立的询问（每次问消到这种状态是否可行）：

1. 左0/00 右1/11

2. 左1/11 右0/00

3. 左01/10 右01/10

如果能满足以上的某一条（左右都能消成对应状态），就有解。先考虑如何判断一侧是否能留下全0 (全1 也一样)

•核心想法：尽量凑三个1 进行消除，使得0 剩下的更多。

•如果原来就有连续三个1 相邻，直接消除肯定没问题。存在一种情况类似于11011，这时候是两段1 要合并再一起消除。这样损耗了3 个1 和1 个0。从左到右贪心做，维护前缀0 的个数zero（0我们都留着不消）以及紧接着一段连续1 的个数one（one 的值最多只会是2，一旦大于等于3 就立刻消除）。如果新来的数是0 且one 有值，带来的效果就是one--（这组01被消掉，以利于one这段1和后面的1合并）。做到最后如果one > zero，那么能留下全0。

•如何判断能否留下01（或10）呢？

•重要性质：如果0 和1 的个数一样，一定能消除成01/10。

证明：因为我们每次可以选择相邻的01，再随便加一个数就可以把他们成对地消除。

1.如果onei-1=2，则oneionen 不变，zeroizeron 不变。

2.如果onei-1=0，则oneionen 不变，zeroizeron 加一。

3.如果onei-1=1，则要不zeroi+1zeron 加一（如果ai+1=0）要不onei+1onen 不变，zeroi+1~zeron 不变（如果ai+1=1）

•复杂度分析

当第i 位从1 变成0 后，我们从第i 位开始重新修改。由以上分析，要不(zero, one) 的值迅速收敛（和上一次保持一致），那我们就直接break；要不zero 的值全都集体+1，这样这次更新的确可能影响O(N) 个位置。第一种贪心算法要求判断zero > one 是否可行。所以当zeroi >=3 后，i 以及i 之后的点必然合法。每个点的zero 最多增加三次，由均摊分析复杂度是线性的。对于第二种贪心算法，我们只需在1 比0 多的时候调用zero >= one，0 比1 多时反一下。出题人在这里偷懒用了一个树状数组，总复杂度是O(N log⁡N)

I-Jumping on the Graph

•基础暴力

不妨枚举次大边的权重，此时我们考虑将大于次大边的边权重赋值为1，其他边赋值为0。此时若(i,j) 之间的最短路径则说明i,j 的次大值当前枚举权值，否则必然大于。记Ans[k] 表示最短路的点对数,每次通过Floyd O(N^3 ) 直接跑，作差之后统计，总复杂度O(MN^3)

•暴力优化

•上述问题可以这样转化：当我加入一些边之后，所有的点会由权值为0 的边联通成一些连通块。此时，对于所有权值为1 的边，他所能带来的点对数量是其两边连通块的size 和。那我们不妨枚举每条当前权值为1 的边，然后将每条边的答案合并起来。当然要注意去重，也就是如果两条边连接两个相同的连通块，只能被计算一次。这样就可以做到O(NM log⁡N)。更进一步，我们只需要计算每次新增的点对数，假设这一步新增的边将接通连通块x 和y，新增的点对数量应该是size[x] * (y的出边size 和) + size[y] * (x的出边size 和) -(size[x] + size[y]) * (x 与y 的出边交集)。

•出边和统计

•为了统计每个连通块的出边和，对于点x，我们定义其权值为出边的数量，一个连通块的权值为所有点的权值之和。对于每个连通块，我们维护其所有出边，这个出边直接表明了另一个连通块的代表标号。当我们将y 合并到x 上时，需要将y 中所有边对应修改成以x 为顶点的边。方便点，使用启发式合并和set 来维护，复杂度为O(〖M(log⁡M)〗^2)，对于每个连通块，若其权值第一次大于√M，则扫描所有边，并且累加对应的size 之和，注意到上述情况一共只会发生√M 次。对于权值不超过√M 的点，我们扫描所有边直接询问。否则，我们直接调用已经得到的值.当然我们需要维护所有“大”点的值。为此，每个点需要维护一个其所有连出的“大”点列表。每次发生修改时，需要同步修改所有会发生改变的权值。维护该列表的方法与维护出边表相同，复杂度也不会劣于之前的复杂度。据此，复杂度为O(M√M+〖M(log⁡M)〗^2)。算法中某些部分需要一些简单的分类讨论，留给选手自己思考

J-Geometry Challenge

•题意

给出若干个符合一定规则的几何题条件。要求出某个角或者某条边或未知数x 的值。

•核心点

注意题目保证了每一步的结果依然是expressions。核心思路：我们不断用已知的条件和定理扩展我们知道的量，直到找到答案。中途可能需要构方程和解方程。整个过程有点像迭代加深搜索。

•一些注意点

同一个角的表示有很多种，注意要对它们建立Equal 关系。对于所有PointLiesOnLine，要构建边长相加的Equal 关系和角度相加的Equal 关系。对于平行线，同位角可能不存在，所以可以只用内错角和同旁内角建立关系。可以先不断地用“基本定理”传播expression，到最后再用勾股定理、相似定理等复杂的定理解方程。要能检测出图中的三角形（只要三点不共线就算），并积极寻找全等和相似的三角形对。在运用一些定理时，所用的条件可能不是“完全”的。比如我们知道两条边的长度都是2x+3，我们依然可以利用它们相等来构建对角相等或者三角形全等的关系。可以用Find 导向去优化搜索方向。不过这道题是不必要的，你把所有可以求的量求出来也是OK 的。在解出x 后，要把之前所有用x 表示的表达式都带入一遍。复杂度为 所有状态量* 定理数量* 步数上限（4）。