2020牛客暑期多校第一场讲课笔记版本题解1

这篇内容主要涵盖了一些计算机科学和算法竞赛中的关键知识点，包括后缀数组、无限树、二次型、矩阵求逆、有向图的生成树计数、无穷字符串比较、快速幂运算以及最小费用流。 1. 后缀数组(B-Suffix Array): 后缀数组是一种数据结构，用于高效地处理字符串的子串查询。B-Suffix Array是基于字符间的最小距离构建的，它等价于由字符间最小距离数组构成的后缀数组。在文本搜索和字符串处理问题中非常有用，可以用于构建LCP阵列，解决模式匹配等问题。 2. 无限树计算: 在这里提到的是用虚拟树来表示阶乘序列{1!, 2!, ..., n!}，然后使用线段树或 Fenwick 树来计算实际成本。这种方法适用于动态维护区间加权操作的问题，时间复杂度为O(m log^2 m)。 3. 有向图的生成树计数(Domino Flip Graphs): 提到了Domino翻转图中的距离计算，可以通过"Lagrange Duality"证明，答案是b的转置乘以矩阵A的逆再乘以b。这在图论和网络流问题中常见。 4. 二次型(Quadratic Form): 提供了求解二次型的方法，即利用拉格朗日对偶性，通过计算矩阵A的逆来得到最优解。 5. 无穷字符串比较: 通过周期性引理，比较两个无穷字符串a^∞和b^∞，如果前a+b-gcd(a,b)个字符没有不匹配，那么两个字符串是相同的。这在处理字符串的无限模式时非常有用。 6. 快速幂运算(Brute Force and Exponentiation): 题目中提到了用加法表示乘法，乘法表示指数运算，并预计算B_{i,j} = 2^{W*j} * v_i，然后利用快速幂优化计算，复杂度为O(nm/W + 2^W)，其中W通常取16，可以得到足够快的解决方案。 7. 最小费用流(Minimum-cost Flow): 这是网络流问题的一种，目标是在满足容量限制的情况下，找到使得总费用最小的流。在运筹学和图论中有广泛应用，通常采用Ford-Fulkerson算法或Edmonds-Karp算法等方法求解。 这些知识点在算法竞赛和实际编程问题中都非常关键，掌握它们对于提升编程能力、解决复杂问题具有重要意义。