【题解】2023年第六届传智杯复赛第一场题解_牛客网

　　补题链接：https://ac.nowcoder.com/acm/contest/72647#question

　　作为复赛，本场比赛难度略高于初赛，且都是原创题，总体比赛强度还是比初赛高一个档次的。复赛第一场一共8题，其中A组使用6题：BDEFGH；B组使用6题：ACDEFG

　　比赛通过率：87.79%

　　知识点：字符串，模拟

　　思路：签到题。只需要判断字符串长度是否是3的倍数即可。如果是3的倍数，则在的地方添加一个空格；否则无解。

　　参考代码：

　　比赛通过率：82.33%

　　知识点：数组、哈希、模拟

　　思路：建议使用map等哈希容器（java为HashMap，python为dict），这样可以比较方便统计每个元素的次数。另外也可以通过排序等方式来达成目的。

　　参考代码：

　　比赛通过率：36.61%

　　知识点：数论、贪心

　　思路：一个比较显然的结论是，最终需要将数组的元素变成所有元素的gcd（最大公约数）。因此每个元素需要分裂的次数可以直接求出来。这个结论的证明可以结合辗转相除法的性质，请大家自行思考。

　　参考代码：

　　比赛通过率：26.21%

　　知识点：组合数学

　　思路：我们可以先计算出满足第一个条件的字符串数量：用乘法原理计算，答案为。

　　然后我们需要减去和原字符串同构的情况，答案为最大的字符减去最小的字符这么多。

　　参考代码：

　　比赛通过率：4.53%

　　知识点：树形dp

　　思路：我们记录dp[u][i][j]代表以u节点的子树，当u节点赋值为的时候，该子树权值和模3等于的方案数。在dfs的时候转移即可。

　　参考代码：

　　比赛通过率：5.03%

　　知识点：线段树、离散化

　　思路：直接维护区间的相交情况比较困难。我们可以首先进行离散化，然后在值域上开线段树进行维护区间和。当添加一个区间时，我们进行区间加1；删除一个区间时，我们进行区间减1。这样，问题可以转化为，如果存在一个大于1的值，则意味着存在两个区间相交。这样我们可以通过询问全局最大值解决。

　　参考代码：

　　比赛通过率：1.26%

　　知识点：博弈，数论，哈希

　　思路：首先我们将该博弈问题进行抽象，可以比较轻松得出以下结论：如果初始所有元素乘积为完全平方数，那么小紫获胜；否则小红获胜。

　　因此我们可以先用的根号分解，对于次数和为奇数的素因子，我们需要使得该素因子的次数变成偶数即可。那么这道题等价为：给定一个数组，询问有多少个连续子数组满足子数组所有元素中，出现次数为奇数素因子的乘积恰好等于。（为初始给定的数的奇数次数因子乘积）。

　　要解决这个问题，我们可以首先使用筛法，预处理出每个元素的素因子次数。然后使用哈希批量维护区间信息。在处理过程中，我们可以对初始的因子进行特殊标记，减少哈希中需要处理的不同因子数论，避免出现tle或者mle。

　　参考代码：

　　比赛通过率：5.48%

　　知识点：启发式合并

　　思路：本题其实只需要求出每个节点染红后，最终排列中“红色段”数量是多少即可。该方案可以用树上启发式合并来解决：首先使用set维护子树节点信息，当添加/删除节点时，需要同时在set中查询红色段的数量影响。随后将小的子树的set合并到大的上面即可。

　　参考代码：