2021“MINIEYE杯”中国大学生算法设计超级联赛（3）-题解1

在2021“MINIEYE杯”中国大学生算法设计超级联赛中，参赛者们面临了涉及算法设计的挑战。以下是三个题目及其解决方案的关键知识点： 1. **Bookshop**： 这道题目主要考察了树的轻重链剖分和最近公共祖先(LCA)的算法。对树进行轻重链剖分可以将树分解为若干个连续的DFS序段，其中重链是具有最多子节点的边，轻链则是其余边。在DFS过程中，先访问重儿子，再访问轻儿子，确保重链在DFS序中连续。对于询问(x, y, z)，找到x和y的LCA(t)，x到t的过程和t到y的过程分别对应DFS序的左右两个O(log n)区间。离线处理询问，将两个过程分开处理，利用平衡树数据结构支持区间插入、删除和批量减操作，以达到O((n + q log n + q log z) log q)的时间复杂度。 2. **Destinations**： 这道题目转化为在树形结构中选择无公共点的链以最小化代价。将每条链的收益转化为106(m+1) - ci,j的形式，这样收益在106m进制下不发生进位。目标是在不进位的前提下最大化收益，从而找到最小代价。然后，采用对偶问题解决，通过深度优先搜索(DFS)和树状数组维护差分，贪心地从深到浅选择节点，保证每条链上至少有收益值数量的点。这样，总时间复杂度为O((n + m) log n)。 3. **Forgiving Matching**： 这是一个字符串匹配问题，考虑了通配符的存在。对于S的每个长度为m的子串，计算其与T匹配的位置数fi。基础情况是无通配符时，通过快速傅里叶变换(FFT)计算匹配数。引入通配符后，匹配数等于子串中通配符数加上T中通配符数，减去两者同时为通配符的个数。通过前缀和可以计算子串中通配符的数量，从而得到匹配位置的总数。 这些题目涉及到的数据结构和算法包括：树的轻重链剖分、DFS、最近公共祖先(LCA)、平衡树、树状数组、差分、快速傅里叶变换(FFT)以及处理通配符的匹配策略。解决这些问题需要深入理解树的遍历方法、区间操作的数据结构以及字符串匹配算法，对参赛者的算法设计能力和问题解决技巧提出了高要求。