2021.7 月月赛题解

Once edited 3 年，4 月前

本次 EOJ 月赛由华东师范大学 ACM 团队与华东师大二附中信息学竞赛组联合举办。首先，感谢以下同学为本次月赛命题做出的贡献：

命题人：孙诺舟

验题：Once、bingoier、MorphLing

感谢华东师范大学肖春芸老师、华东师范大学第二附属中学金靖老师的组织策划，使得 EOJ 月赛能够圆满完成。此外，感谢 EOJ 运维团队为月赛提供了重要的技术支持。

最后，祝各位 ACMer 和 OIer 们暑假快乐，学业有成。

扫描二维码关注我们的微信公众号，获得更多信息。本次月赛的获奖名单和后续竞赛通知将通过公众号发布。

构建

先判断是不是可以构成四边形，如果不行再枚举去掉的边判三角形。

判断方法为判断最长边是否大于其他边长之和。

时间复杂度 $O(1)$。

球场

求出一每个位置为比赛区域、观众席的左侧、右侧端点时，最长多长。枚举比赛区域和观众席的分界线，那以此为分界线的最长长度就是一侧观众席长度和另一侧比赛区域长度的min，对所有分界线的最长长度取max即可。

求比赛区域的最长长度可以用单调栈维护，求观众席最长长度可以直接递推。

时间复杂度 $O(n)$。

渡渡鸟

对于一组询问，如果 $s,t$ 完全相同，那么答案是固定的，可以直接算出；否则如果 $s,t$ 的01个数均相同，答案也固定，可以用容斥原理预处理出来。

否则如果01的数量不是一个1多一个0多，答案就是0。

假设 $s$ 比 $t$ 多 $x$ 个0，少 $y$ 个1，那么就有 $x\times len_A=y\times len_B$。令 $x’=\frac{x}{\gcd(x,y)},y’=\frac{y}{\gcd(x,y)}$，那么 $A,B$ 分别是同一个串复制 $x’$ 遍和复制 $y’$ 遍。 用等比数列求和求出满足长度要求的串的数量即可。

$O(n\log n+Q\log k)$

购置土地

考虑搜索购买的土地的形状，固定1号点为最左的点中最上的，从1号点开始搜索。假设目前搜索到 $x$ 号点，一共拓展了 $y$ 个，遍历其4相连的位置中，没有被拓展的点，如果该位置不与某个编号小于 $x$ 的点相连，就枚举是否拓展它，如果是，就将它标为 $y+1$。枚举了所有相连的点后，搜索第 $x+1$ 号点，直到拓展到 $k$ 个点为止。

拓展到 $k$ 点后，遍历该形状来检查是否满足题面要求，再计算出在 $n\times m$ 的平面中可以放入的位置数。

树

先考虑链上的情况：

考虑分块，假设分了 $k$ 块，每块长 $L$，对于每个块，统计中间元素在块内的情况，在开始统计前，对块两边的元素建立哈希表。

三个元素都在块内：先枚举中间位置的元素，对一侧的块内元素建立哈希表，枚举另一侧的元素，然后在哈希表示查询对应元素有多少个。

两个元素在块内：枚举这两个元素，在预处理的哈希表中查询。

可以发现，这两中情况的时间复杂度都是 $O(L^2)$ 的。

如果只有一个元素在块内，可以使用FFT将块两边的哈希表卷积，然后就可以快速查询了。

这种情况的时间复杂度是 $O(L+m\log m)$ 的。

总复杂度是 $O(\frac{n^2}k+km\log m)$ 的。

接着考虑树上的情况：

尝试将链上的做法拓展到树上，考虑树分块，可以发现，树分块的结果具有树结构。

在开始对一个块统计前，前处理好祖先链，以及每个子树块的哈希表。

前两种情况依然可以暴力。

对于只有一个元素在块内的情况，可以前将每个子树块的哈希表和祖先链的哈希表卷积一次，然后对每个点统计是在所有这个点是子树块祖先的哈希表上查询即可。

复杂度依然是 $O(\frac{n^2}k+km\log m)$ 的。

Comments

zqy1018

3 年，4 月前

根据数据 D 题这种情况也算只围成了一块地，有点奇怪

..........
...###....
...#.##...
...##.#...
....###...
..........

回复 2 1