ACGO 第 12 次排位赛题解 写在前面 本场比赛所有题目经过一轮 ChatGPT−4o\tt{ChatGPT-4o}ChatGPT−4o 测试，测试结果如下： 题目 A B C D E F 分数 100 160 110 14 187 0 测试点通过比例 20/20 20/20 10/25 1/25 11/25 0/35 本场排位赛的所有题目的难度评级为： 题目编号 题目标题 难度 A. 50%AI, 50%Human 入门 B. 统计区间内奇数与偶数的数量 入门 C. 火星背包 II 普及- D. 可分数列 普及/提高- E. 花火大会 普及/提高- F. 剑之试炼 提高+/省选- 非常感谢大家参加本场排位赛！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 直播预告 直播时间：9月14日（周六）16:00 开始 直播地址：B站ACGO官方账号 直播内容：排位赛#12复盘 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 题解简述 以下提供每道题目的思路简述，详细题解的AC代码包括复杂度分析，请点击题目标题查看。 A - 50%AI, 50%HUMAN 我们可以以使用一个变量 M 来统计所有「AI」生成的变量； 每个变量名为一个字符串，一共有 NNN 个变量名，我们可以使用一个执行 NNN 次的循环，每次循环，使用一个 std::string 类型变量 s 读入变量名，并使用 s.size() 来获取字符串的长度，若长度大于 555 则令 m 加 111。 最终就可以得到 NNN 个变量名中「AI」编写的变量的数量 M。 由于需要向上取整，我们可以使用以下方法…… ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ B - 统计区间内奇数与偶数的数量 标签：前缀和；数学 对于每个查询，若直接使用循环暴力统计 [Li,Ri][L_i, R_i][Li ,Ri ] 内的奇数或偶数，时间复杂度为 O(Ri−Li)\mathrm{O}(R_i - L_i)O(Ri −Li )。本题 1≤Li≤Ri≤1091 \le L_i \le R_i \le 10^91≤Li ≤Ri ≤109。暴力统计会超出时间限制。 我们不妨思考一个问题：给定任意正整数 NNN，求 [1,N][1, N][1,N] 中所有「奇数」的数量，如何解决这个问题？ 不妨枚举，打表找找规律，1,3,5,7,9,11,⋯1, 3, 5, 7, 9, 11, \cdots1,3,5,7,9,11,⋯。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ C - 火星背包 II 标签：背包问题 本道题目不难想到套用经典的「01背包问题」，定义 dp[i][j]\tt{dp[i][j]}dp[i][j] 为前 iii 个物品，背包容量为 jjj 可以获取的最大价值，然后使用 dp[i][j]=max⁡(dp[i−1][j],dp[i−1][j−w[i]]+v[i])\tt{dp[i][j] = \max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i])}dp[i][j]=max(dp[i−1][j],dp[i−1][j−w[i]]+v[i]) 进行转移。 此种做法只能够拿到一部分分数（约 40%40\%40%），无法通过本题，原因是本题背包的容量和物品的重量都特别大 (1≤wi≤M≤109)(1 \le w_i \le M \le 10^9)(1≤wi ≤M≤109)。使用上述方式解决这道题目的时间复杂度为 O(NM)\mathrm{O}(NM)O(NM)。 但本题 NNN 以及 viv_ivi 的值都比较小，我们不妨…… ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ D - 可分数列 标签：构造；数学 对于本道题目，不难发现，公差以及首项的值是不重要的，我们需要关注的点主要是如何将这 4N+24N + 24N+2 个元素去掉 222 个元素以后按照题目要求的形式分成 NNN 组。 首先观察样例。 我们将按照『从上到下』，『从左到右』的顺序，除最后一列外，每列 NNN 个元素的方式排列。 将 A2A_2A2 和 A13A_{13}A13 去除掉后，可以将剩余的元素分成 [1,4,7,10][1, 4, 7, 10][1,4,7,10]，[5,8,11,14][5, 8, 11, 14][5,8,11,14]，[3,6,9,12][3, 6, 9, 12][3,6,9,12] 三组。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ E - 花火大会 标签：最短路径；广度优先搜索 本题若只有一处放烟花的地方，那么则为「单源无权最短路问题」。 当有多处放烟花的地方且放烟花的时间相同，则为「多源无权最短路问题」。 以上两个问题都可以使用 BFSBFSBFS 解决。但本题需要解决的是一个「多源不同权的无权最短路问题」。 容易想到的一个策略是使用「优先队列」替换「队列」来实现 BFSBFSBFS。但此种方法的复杂度为 O(NMlog⁡NM)\mathrm{O}(NM\log{NM})O(NMlogNM) 在本题时间复杂度比较大的情况下无法通过本题。 假设队列中的点是按照最短路的大小从小到大排好序的，例如： [1,2,2,2,3,3,3,4,5][1, 2, 2, 2, 3, 3, 3, 4, 5][1,2,2,2,3,3,3,4,5] 第一个点的最短路为 111，当其出队的时候，扩展的到的点的最短路为 222。 我们需要将其放在一个合适的位置，使得每个点第一次出队的时候，一定是未确定最短路的点中，最短路最小的点（DijkstraDijkstraDijkstra 算法的思想）。 那么我们不妨将这些点按照最短路大小进行分组： [[1],[2,2,2],[3,3,3],[4],[5]][[1], [2, 2, 2], [3, 3, 3], [4], [5]][[1],[2,2,2],[3,3,3],[4],[5]] 我们只要能够从小到大依次遍历这些组，并将扩展出的点放入对应的「组」中即可。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ F - 剑之试炼 标签：最短路径；状态压缩动态规划；广度优先搜索； 本道题目包含多个子问题，如果不加以梳理，会非常复杂，并且在梳理完毕后依然编写大量代码，并且需要特别注意实现细节，非常考验「力量」（毅力）,「智慧」与「勇气」。 由于要求必须击败所有的「波克布林」，且从地下 iii 层传送至地下 i+1i + 1i+1 层须花费 111 秒的时间，所以我们可以把击败波克布林需要的时间和传送的时间预处理，后面就可以把所有的「波克布林」当成同一种去处理；把此部分花费的时间记为 cost\tt{cost}cost。 把所有的波克布林当成「特殊点」，并将其在地图中标记为 *，接下来都可以把问题转化成：访问 KKK 层地图上的所有特殊点需要最短时间，将其标记为 mint\tt{mint}mint。 那么本题的答案为 cost+mint\tt{cost + mint}cost+mint。 接下来解决如何计算 mint\tt{mint}mint 的问题。 因为计算 mint\tt{mint}mint 比较复杂，我们可以将其划分成若干个子问题。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

今天我们来讲一元二次函数！ 本文章适合已学习过、接触过函数的同学 注：这里整理的内容网上可找不到哦，是整合内容 注：作者本人7年级小弱弱，自主与高中数学老师的母亲学习，可能不太完善，有错误请提出 好玩爱玩 一元二次函数又称二次函数哦 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 首先我们来了解一元二次函数，即为 Y=AX2+BX+CY=AX^2+BX+CY=AX2+BX+C 其中a不等于零，b，c是实数 这是一个直角坐标系 我们来看个例子： Y=X2+1Y=X^2+1Y=X2+1 这里b=0 会长这样 我们可以看到，一元二次函数的图像是一个抛物线。 那么，抛物线有开口方向、顶点（最低/高点）、与x轴交点（可能为0）、定点与x轴距离等等 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 我们先来观察函数性质： 刚才已经展示了一个函数图像，那么我们再展示一个： Y=−X2+1Y=-X^2+1Y=−X2+1 我们发现，在A>0时，抛物线开口朝上，反之开口朝下 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 我们再来观察图像： Y=X2+2X(C=0)Y=X^2+2X(C=0)Y=X2+2X(C=0) 顶点横坐标（x）为负 Y=X2−2X(C=0)Y=X^2-2X(C=0)Y=X2−2X(C=0) 顶点横坐标为正 Y=−X2+2X(C=0)Y=-X^2+2X(C=0)Y=−X2+2X(C=0) 顶点横坐标为正 Y=−X2−2X(C=0)Y=-X^2-2X(C=0)Y=−X2−2X(C=0) 顶点横坐标为负 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 所以可以得出结论： 当A>0时： 当b>0,顶点在y轴左侧（横坐标为负） 当b<0,顶点在y轴右侧（横坐标为正） 当A<0时： 当b<0,顶点在y轴侧（横坐标为负） 当b>0,顶点在y轴右侧（横坐标为正） 记住，当B=0，顶点在Y轴上（X轴为0） ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 接下来是枯燥无味的顶点公式： 顶点 P(−B2A,4AC−B24A)P(\FRAC{-B}{2A},\FRAC{4AC-B^2}{4A})P(2A−B ,4A4AC−B2 ) 要背，很有用 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 接下来我们来学习函数图像与x轴的交点 函数y=ax2+bx+cy=ax^2+bx+cy=ax2+bx+c可以转换为y=a(x−m)(x−n)y=a(x-m)(x-n)y=a(x−m)(x−n) 其中与x轴交点的坐标分别为： X1(m,0)X_1(m,0)X1 (m,0) X2(n,0)X_2(n,0)X2 (n,0) 其实实质就是am2+bm+c=0am^2+bm+c=0am2+bm+c=0和an2+bn+c=0an^2+bn+c=0an2+bn+c=0 当然，不是所有时候都是2个交点，有时是1个，有时没有。 这里我们需要了解一元二次方程： AX2+BX+C=0AX^2+BX+C=0AX2+BX+C=0 此处有个叫做ΔΔΔ（德尔塔）的东西，即为： Δ=B2−4ACΔ=B^2-4ACΔ=B2−4AC 当ΔΔΔ大于0时，方程有2个不同的解 当ΔΔΔ等于0时，方程有2个相同的解（就是1个解） 当ΔΔΔ小于0时，方程没有解 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 一元二次函数和这里的一元二次方程相似，也有ΔΔΔ，性质相同。 所以当ΔΔΔ大于0时，ax2+bx+c=0ax^2+bx+c=0ax2+bx+c=0有2个解，所以函数图像与x轴有2个交点 当ΔΔΔ等于0时，ax2+bx+c=0ax^2+bx+c=0ax2+bx+c=0有1个解，所以函数图像与x轴有1个交点 当ΔΔΔ小于0时，ax2+bx+c=0ax^2+bx+c=0ax2+bx+c=0没有解，所以函数图像与x轴没有交点 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 一元二次函数，只需要知道3个点，即可确定函数解析式 like this: 已知二次函数 Y=AX2+BX+CY=AX^2+BX+CY=AX2+BX+C 上有3个点，分别为 A(−1,0)A(-1,0)A(−1,0),B(0,1)B(0,1)B(0,1),C(−2,1)C(-2,1)C(−2,1) 先列表（这里只是便于记录，其实不用）： 点 X Y A -1 0 B 0 1 C -2 1 那么逐一带入： A−B+C=0A-B+C=0A−B+C=0 C=1C=1C=1 4A−2B+C=14A-2B+C=14A−2B+C=1 解方程，得： {a=1b=2c=1 \begin{cases} a=1 \\ b=2\\ c=1 \end{cases} ⎩⎨⎧ a=1b=2c=1 所以得出函数：y=x2+2x+1y=x^2+2x+1y=x2+2x+1 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 23/12/28更： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 先讲关于某些题型！ 什么题型呢，就是问你某个函数的函数图像在x轴上/下的部分的定义域是什么 讲个例子，eg.求y=x^2+2-5的函数图像在x轴之下的部分的x坐标范围！ 首先可以画个图辅助： 首先我们前面知道，当a>0时，函数开口朝上，所以在x轴之下的应该是大于m小于n的（这里指前面的y=a(x−m)(x−n)y=a(x-m)(x-n)y=a(x−m)(x−n)顶点式中的m，n) 也就是这一块： 所以我们要求出与x轴相交的两个点坐标，也就是设： x2+2x−5=0x^2+2x-5=0x2+2x−5=0 学过一元二次方程的都会做吧！这里我就不展示了 X=−B±B2−4AC2A=−2±22+202=−1±6X=\FRAC{-B\PM\SQRT{B^2-4AC}}{2A}=\FRAC{-2\PM\SQRT{2^2+20}}{2}=-1\PM\SQRT{6}X=2A−B±B2−4AC =2−2±22+20 =−1±6 X1=−1−6X_1=-1-\SQRT{6}X1 =−1−6 X2=−1+6X_2=-1+\SQRT{6}X2 =−1+6 所以这里m=−1−6m=-1-\sqrt{6}m=−1−6 ,n=−1+6n=-1+\sqrt{6}n=−1+6 所以答案为： −1−6<x<−1+6-1-\sqrt{6}<x<-1+\sqrt{6}−1−6 <x<−1+6 当然，想求在x轴之上也可以，在上面的基础上答案为： x<−1−6x<-1-\sqrt{6}x<−1−6 或者x>−1+6x>-1+\sqrt{6}x>−1+6 注：考试的时候可能在A,B,C中选择几个不告诉你！这里需要结合前面的定理来判断开口方向 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 待更

消灭PYTHON暴政，世界属于C++!!! 1. 高精度计算概述 高精度计算是一种在计算机科学中处理超出标准数据类型范围的大数的计算方法。它广泛应用于密码学、科学计算、金融领域以及任何需要处理极大或极小数值的场合。 1.1 高精度计算的定义 高精度计算通常指的是对超过标准整数或浮点数表示范围的数值进行的算术运算。在C++中，标准整数类型（如int、long）有固定的位数，这意味着它们能够表示的数值范围是有限的。当需要处理的数值超出这个范围时，就需要使用高精度计算方法。 1.1.1 表示方法 高精度数值通常使用数组或字符串来表示，每一位数字作为数组的一个元素或字符串的一个字符。例如，一个非常大的整数可以表示为一个整数数组，其中数组的每个元素存储一个数字位。 1.2 高精度计算的重要性 高精度计算对于需要极高精度的领域至关重要。 1.2.1 科学计算 在物理模拟、天文计算等领域，常常需要非常精确的数值，以确保计算结果的准确性。 1.2.2 密码学 在公钥密码体系中，如RSA加密，涉及到的大整数可能达到数千位，高精度计算是实现这些算法的基础。 1.2.3 金融领域 金融领域中的一些计算，如复利计算，可能需要非常高精度的数值来避免舍入误差。 1.2.4 编程竞赛 在编程竞赛中，高精度计算经常出现在处理大数问题的题目中，掌握高精度计算对于解题至关重要。 1.2.5 实现方式 高精度计算可以通过多种方式实现，包括但不限于： * 字符串操作：将数字以字符串形式存储和操作，适用于加减乘除等基本运算。 * 数组操作：使用数组存储每一位数字，可以高效地进行数值的存储和运算。 * 分数类：对于需要表示有理数的情况，可以使用分数类来存储分子和分母。 提供的BigInt类实现了基本的高精度整数运算，包括加法、减法、乘法以及除法。此外，还实现了一个快速幂函数qpow，用于高效地计算大整数的幂。这些运算是高精度计算的基础，为进一步的复杂计算提供了可能。 2. 高精度计算的实现原理 2.0 作者给的CODE(加了标记，请勿抄袭) 2.1 数字存储方式 高精度计算在处理特别大的数字时，由于这些数字超出了常规数据类型能够表示的范围，因此需要特殊的存储方式。在提供的代码中，BigInt 结构体采用了数组来存储大整数的每一位数字。 * 数组的每一位存储一个整数，通常是一个0到9之间的数字，代表大整数的某一位。 * 数组的长度（MAX_LEN）定义了能够存储的最大数字位数，这里设置为50000，意味着可以存储最多50000位的数字。 * len **变量记录了当前大整数实际使用的位数。 2.2 算术运算的实现 算术运算是高精度计算的核心部分，包括加法、减法、乘法和除法等。以下是对提供的代码中算术运算实现的分析： * 加法 (add 方法)：通过模拟手算加法的过程，从最低位开始逐位相加，同时处理进位（x）。 * 减法 (sub 方法)：模拟手算减法的过程，从最低位开始逐位相减，同时处理借位。需要注意的是，减法前先比较两个数的大小，以确定哪一位需要借位。 * 乘法 (mul 方法)：通过模拟手算乘法的过程，将一个数的每一位与另一个数的每一位相乘，然后按位相加，处理进位。对于单个整数的乘法，则是将数组中的每一位与该整数相乘。 * 除法 (div 方法)：模拟手算除法的过程，从高位开始逐位相除，计算商的每一位，同时更新余数。 代码中还提供了一个快速幂函数 qpow，用于计算大整数的幂次。它采用了递归的方式，通过不断*方底数并乘以剩余的指数来实现。 此外，重载了输出流运算符 <<，使得 BigInt 类型的变量可以方便地输出到标准输出。 以上是对高精度计算实现原理的简要分析，具体的实现细节和优化可能需要根据实际应用场景进一步探讨。 3. 高精度计算的编程实践 3.1 编程语言的选择 在进行高精度计算时，选择合适的编程语言至关重要。C由于其高效的执行速度和对底层内存的控制能力，成为了实现高精度计算的优选语言。在提供的代码示例中，C被用来构建BigInt结构体，该结构体能够存储和操作非常大的整数。 * 执行效率：C++的编译型特性使其在执行时具有很高的效率，这对于处理需要大量计算的高精度算法尤为重要。 * 内存管理：C++允许开发者手动管理内存，这在处理大规模数据时可以优化性能并减少内存使用。 * 类型系统：C++*大的类型系统支持用户自定义类型，如BigInt，可以精确控制数据的存储和操作。 3.2 关键数据结构与算法 高精度计算涉及到的核心数据结构是能够存储任意长度数字的BigInt类。以下是实现高精度计算所需的关键数据结构和算法： * 数据结构：BigInt类通过一个整型数组v来存储数字的每一位，len变量记录数字的长度，sign表示数字的正负。这种设计允许存储的数字大小只受限于可用内存。 * 初始化：构造函数支持从int类型和char*类型初始化BigInt对象，能够处理正负整数和字符串形式的数字。 * 比较操作：compare方法实现了对两个BigInt对象大小的比较，这是许多算术操作的基础。 * 加法：add方法实现了两个BigInt对象的加法操作，通过逐位相加并处理进位来完成。 * 减法：sub方法实现了减法操作，考虑了不同长度和正负号的情况。 * 乘法：mul方法实现了乘法操作，通过逐位乘并以类似手算乘法的方式进行累加。 * 除法：div方法实现了除法操作，通过逐位相除并处理余数来完成。 * 幂运算：qpow函数实现了快速幂算法，通过递归调用实现了指数运算，这对于处理大数次方非常有效。 * 输出重载：重载了<<运算符，使得BigInt对象能够直接输出到标准输出流，方便调试和展示结果。 以上数据结构和算法的实现，为高精度计算提供了坚实的基础，使得程序员能够处理远超常规整数类型的数值计算问题。 4. 代码分析与实现 4.1 代码结构概述 提供的代码实现了一个高精度整数类 BigInt，它能够处理非常大的整数运算，包括加法、减法、乘法、除法以及快速幂运算。代码首先定义了 MAX_LEN 常量，用以设定可以处理的最大位数。BigInt 类包含一个整型数组 v 用于存储数字每一位的值，len 表示当前数字的长度，sign 表示数字的正负。 4.2 构造函数分析 BigInt 类有两个构造函数，第一个接受一个整数 n 并将其转换为高精度表示，第二个接受一个字符串 a 并解析为高精度数字。如果输入是负数或包含负号的字符串，sign 将被设置为 -1。 4.3 比较函数分析 compare **函数用于比较两个 BigInt 对象的大小，返回 -1、0 或 1 分别表示第一个数小于、等于或大于第二个数。 4.4 基本运算实现 * add 函数实现了高精度加法，通过逐位相加并处理进位。 * sub 函数实现了高精度减法，考虑了借位的情况。 * mul 函数实现了高精度乘法，通过每一位的乘积累加，并处理进位。 * div 函数实现了高精度除法，通过逐位相除并处理余数。 4.5 快速幂函数实现 qpow 函数实现了快速幂运算，这是一个递归函数，基于二分幂的思想，当指数为偶数时，通过*方来减少计算次数。 4.6 输出流重载 重载了 std::ostream& 运算符 <<，使得 BigInt 对象可以方便地输出到标准输出流。 这段代码将演示如何使用 BigInt 类进行基本的数**算，并输出结果。 5. 高精度计算的应用场景 5.1 科学计算 高精度计算在科学计算领域扮演着至关重要的角色。由于科学研究往往涉及极其庞大的数值或极其精细的精度要求，传统的浮点数或整数类型无法满足这些需求。 * 数值模拟：在物理学和工程学中，数值模拟经常需要处理非常大的数值，例如天体物理学中的星体质量计算或量子力学中的粒子状态模拟。 * 数据分析：在数据分析中，尤其是大数据处理，可能需要对数据进行精确的统计和分析，高精度计算可以确保分析结果的准确性。 * 算法实现：某些算法，如大整数分解或高精度快速傅里叶变换（FFT），在实现时需要高精度的数据类型来保证结果的正确性。 5.2 商业计算 在商业领域，高精度计算同样发挥着重要作用，尤其是在金融和经济分析中。 * 金融模型：金融领域中的模型，如蒙特卡洛模拟，经常需要处理大量数据和高精度的数值运算来预测市场趋势或评估风险。 * 会计和审计：在会计和审计过程中，确保交易记录的精确性至关重要。高精度计算可以帮助避免因舍入误差引起的财务错误。 * 供应链优化：供应链管理中，对库存水*和需求预测的精确计算可以显著提高效率，减少浪费，这通常需要高精度的数值分析。 高精度计算的应用不仅限于上述场景，它在任何需要极端数值精度或大数处理的领域都有着广泛的应用。随着技术的发展，高精度计算的需求和应用场景将会更加广泛。

矩阵快速幂，听起来很难，模板题也都是绿色的，令人望而却步。我在发呆时突然想起了矩阵快速幂，于是花了一个下午去学习它。于是，就有了这篇文章。 ACGO 主题库上似乎还没有矩阵快速幂的题目，我从洛谷上搬运了几道。数据自造，强度应该是够的，如果搬的题目或数据有什么问题还请联系我。题单：矩阵模板题。原题分别为洛谷 P3390，P1939 和 P1962。 正文从此开始。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 前置知识： * 快速幂 * 矩阵 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 概念 先从矩阵的乘法讲起。矩阵乘法 AB=CAB=CAB=C 的定义为： cij=∑k=1naikbkj,(1≤i≤m, 1≤j≤p).c_{i j} = \sum_{k = 1}^{n} a_{i k} b_{k j} \text{,\qquad($1 \le i \le m$, $1 \le j \le p$).} cij =k=1∑n aik bkj ,(1≤i≤m, 1≤j≤p). 其中 AAA 的大小为 m×nm\times nm×n，BBB 的大小为 n×pn\times pn×p，结果 CCC 的大小为 m×pm\times pm×p。如果 AAA 的列数与 BBB 的行数不同，则他们无法进行矩阵乘法。 是不是有点抽象？举个例子你就明白了。当 AAA 的大小为 2×22\times 22×2，BBB 的大小为 2×32\times 32×3 时，则 C=[a11b11+a12b21a11b12+a12b22a11b13+a12b23a21b11+a22b21a21b12+a22b22a21b13+a22b23]. C = \begin{bmatrix} a_{11}b_{11}+a_{12}b_{21} & a_{11}b_{12}+a_{12}b_{22} & a_{11}b_{13}+a_{12}b_{23}\\ a_{21}b_{11}+a_{22}b_{21} & a_{21}b_{12}+a_{22}b_{22} & a_{21}b_{13}+a_{22}b_{23} \end{bmatrix} \text{.} C=[a11 b11 +a12 b21 a21 b11 +a22 b21 a11 b12 +a12 b22 a21 b12 +a22 b22 a11 b13 +a12 b23 a21 b13 +a22 b23 ]. 同时，我们可以证明矩阵乘法满足结合律，但在一般情况下不满足交换律。 我们立刻写出了这样的矩阵乘法代码： 这个代码的时间复杂度是 O(n3)O(n^3)O(n3) 的，可以接受。事实上，《算法导论》给出了一种时间复杂度 O(nlog⁡27)O(n^{\log_2 7})O(nlog2 7) 的矩阵乘法算法，但似乎并没有在 OI 界得到广泛运用，因此这里暂不介绍。 现在，我们回到正题：矩阵快速幂。由于矩阵乘法满足结合律，我们把它当作一般的快速幂打代码即可，只不过数字变成了矩阵，乘法变成了矩阵乘法。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 实现 先放出 AC 模板题的代码： 整个代码的精髓是这几行： 最令人疑惑的是第三行。按照第三行的定义，我们构造出的矩阵是： Ans=[10⋯001⋯⋮⋮⋮⋱⋮0⋯⋯1]. Ans = \begin{bmatrix} 1 & 0 & \cdots & 0\\ 0 & 1 & \cdots & \vdots\\ \vdots & \vdots & \ddots & \vdots\\ 0 & \cdots & \cdots & 1\\ \end{bmatrix} \text{.} Ans= 10⋮0 01⋮⋯ ⋯⋯⋱⋯ 0⋮⋮1 . 这个矩阵我们称其为单位矩阵。任何矩阵与单位矩阵相乘，得到的依然是原矩阵。 因此，单位矩阵就类似数的乘法中的 111，起到基的作用。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 应用 例题：斐波那契数列（洛谷）或斐波那契数列（ACGO 搬运）。 题面非常简单，就是让你求斐波那契数列的第 nnn 项。但是看到数据范围，1≤n<2631\leq n<2^{63}1≤n<263，显然事情并不是那么简单。现在，我们先从斐波那契数列的本质想起。它的递推式是这样的： fi=fi−1+fi−2f_i=f_{i-1}+f_{i-2} fi =fi−1 +fi−2 发现 fif_ifi 的值只与前两项有关。我们只需要保存两项的值就够了。我们把接下来需要保存的两项 fi,fi−1f_i,f_{i-1}fi ,fi−1 通过现在已知的两项 fi−1,fi−2f_{i-1},f_{i-2}fi−1 ,fi−2 表达出来，形成一个线性方程组： {1×fi−1+1×fi−2=fi1×fi−1+0×fi−2=fi−1\begin{cases} 1\times f_{i-1}+1\times f_{i-2} &= f_i\\ 1\times f_{i-1}+0\times f_{i-2} &= f_{i-1} \end{cases}{1×fi−1 +1×fi−2 1×fi−1 +0×fi−2 =fi =fi−1 根据矩阵乘法，我们可以把这个方程组表达成两个矩阵相乘： [1110][fi−1fi−2]=[fifi−1]\begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix}\begin{bmatrix} f_{i-1}\\ f_{i-2} \end{bmatrix}=\begin{bmatrix} f_i\\ f_{i-1} \end{bmatrix}[11 10 ][fi−1 fi−2 ]=[fi fi−1 ] 这是线性代数中十分常见的变换。是不是非常神奇？别急，还有更神奇的。我们发现矩阵 [fi−1fi−2]\begin{bmatrix}f_{i-1}\\f_{i-2}\end{bmatrix}[fi−1 fi−2 ] 也可以用这个式子求出来。于是，我们可以把它展开： [1110]([1110][fi−2fi−3])=[fifi−1]\begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix}\left(\begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix}\begin{bmatrix} f_{i-2}\\ f_{i-3} \end{bmatrix}\right)=\begin{bmatrix} f_i\\ f_{i-1} \end{bmatrix}[11 10 ]([11 10 ][fi−2 fi−3 ])=[fi fi−1 ] 继续展开直到已知项 [f2f1]\begin{bmatrix}f_2\\f_1\end{bmatrix}[f2 f1 ]： [1110]([1110](⋯[1110][f2f1]⋯ ))=[fifi−1]\begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix}\left(\begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix}\left(\cdots\begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix}\begin{bmatrix} f_2\\ f_1 \end{bmatrix}\cdots\right)\right)=\begin{bmatrix} f_i\\ f_{i-1} \end{bmatrix}[11 10 ]([11 10 ](⋯[11 10 ][f2 f1 ]⋯))=[fi fi−1 ] 又根据矩阵乘法的结合律： [1110]i−2[f2f1]=[fifi−1]\begin{bmatrix} 1 & 1\\ 1 & 0 \end{bmatrix}^{i-2}\begin{bmatrix} f_2\\ f_1 \end{bmatrix}=\begin{bmatrix} f_i\\ f_{i-1} \end{bmatrix}[11 10 ]i−2[f2 f1 ]=[fi fi−1 ] （为什么是 i−2i-2i−2 次？因为乘 iii 次的时候结果矩阵的首项就是 fi+2f_{i+2}fi+2 了，所以乘 i−2i-2i−2 次的时候结果矩阵的首项就刚好是 fif_ifi 了，如果不理解手推一下就明白了。） 现在，你一定发现了：[1110]i−2\begin{bmatrix}1 & 1\\1 & 0\end{bmatrix}^{i-2}[11 10 ]i−2 这一项，直接使用矩阵快速幂即可。最后再乘上 [f2f1]\begin{bmatrix}f_2\\f_1\end{bmatrix}[f2 f1 ] 即 [11]\begin{bmatrix}1\\1\end{bmatrix}[11 ]，得到的结果矩阵首项即为所求的 fif_ifi 。由于矩阵的大小为常数，所以可以把单次矩阵乘法视为 O(1)O(1)O(1)，矩阵快速幂的时间复杂度即为 O(log⁡n)O(\log n)O(logn)，轻松跑过 long long 范围。注意特判 n≤2n\leq 2n≤2 即可（本搬题人好心地加上了这两个极限情况）。AC 代码如下： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 总结 总结一下，用矩阵快速幂优化此类递推（动态规划）的步骤： 1. 确定哪些状态对结果状态或过程状态有贡献。只保留有贡献的状态。 2. 确定上一次得到的状态转移到当前状态使用的递推式（方程组）。 3. 提取方程组的各项系数为转移矩阵。 4. 计算转移矩阵的次数。 5. 写下矩阵快速幂和矩阵乘法模板。 接下来大家可以尝试一下矩阵加速（数列）（洛谷）、矩阵加速（数列）（ACGO 搬运）和广义斐波那契数列（洛谷）。如果你会数论，还可以尝试斐波那契公约数（我不会）。 祝大家暑假快乐！ 看在我搬题，打 LaTeX\LaTeX{}LATE X，写 Markdown 这么努力，可否留个赞支持一下 qwq。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ Upd on 2024/6/30：ACGO主题库已有广义斐波那契数列与斐波那契公约数。

T1 最开始是爱丽丝尽量远离绿，绿去追爱丽丝，如果爱丽丝和绿初始位置距离小于等于 555 （不是 666 是因为爱丽丝先手，等绿出手会远离一格），那么等绿刷出来技能可以直接干掉爱丽丝，否则爱丽丝会干掉绿。 T2 一个区间如果纳入新的数，那么这个数有可能会成为这个区间最大值或最小值，那么肯定是不优的，所以只需要枚举每相邻的两个的差就可以了。 时间复杂度 O(n)O(n)O(n) T3 分块，每个点如果块有标记则颜色为块的标记，没有则是原数组颜色，更新完整块直接给块打标记，非完整先下放标记，再暴力更新。 时间复杂度 O(qn)O(q \sqrt{n})O(qn ) 。 T4 定义状态 dpidp_idpi 为走到 iii 所需最小的步数，每一位可以从上一位走过来，即 dpi=dpi−1+1dp_i=dp_{i-1} + 1 dpi =dpi−1 +1 也可以从之前的位置跳跃而来，设 jjj 为蓄力的时间 dpi=min⁡(dpi−j2+j+1)dp_i=\min(dp_{i-j^2}+j+1) dpi =min(dpi−j2 +j+1) 初始在 111 点 dp1=0dp_1=0 dp1 =0 时间复杂度 O(nn)O(n \sqrt{n})O(nn ) T5 感觉 T5 有问题啊，感觉我做法没啥问题，大家都 20 分，是都忽略啥了吗。 设 dpi,j,kdp_{i,j,k}dpi,j,k 为在第 kkk 秒走到点 (i,j)(i,j)(i,j) 的方案数，你可以从上一秒相邻安全的点转移。其中起点在第 000 秒为 111 ，答案是第 ttt 秒的终点。 时间复杂度 O(nmt)O(nmt)O(nmt) 非AC代码： T6 设 fif_ifi 为以 iii 为根的子树魔法值之和，si,js_{i,j}si,j 为以 iii 为根的子树颜色为 jjj 结点总数，di,jd_{i,j}di,j 为如果 iii 的父亲结点颜色为 jjj，子树中所有颜色为 jjj 的结点与他相连能产生的除去这个父亲节点外能产生的魔法值。 对于每个结点： sss 直接累加所有子树的每种颜色，最后在自己的颜色 +1+1+1。 ddd 也是直接累加，但对于自己的颜色，要额外加上那个子树的 sss，因为上面的点连接下面的点都会穿过他。 fff 先直接累加，对于与自己相连产生的贡献，就是那个子树与自己颜色相同的 d+sd + sd+s ，原因：累加 ddd 请看他的定义， sss 是因为还要算上当前结点产生的贡献。 然后考虑跨过当前结点产生的贡献，在每个子树内，其他子树所有颜色相同的节点都可以和自己的所有结点连接，设当前节点为 uuu，当前子树根结点为 vvv 贡献就是 dv(su−sv)d_v(s_u-s_v)dv (su −sv ) ，对于每种颜色都要统计。还要额外颜色与当前结点相同时跨过当前结点产生的贡献。 时间复杂度 O(nc)O(nc)O(nc)

ACGO 第 8 次挑战赛题解 本场比赛后 333 题在 Acgo\tt{Acgo}Acgo 的 Python 3.6.9\tt{Python\ 3.6.9}Python 3.6.9 下很难通过，但本文给出的代码，在 PyPy 3.10\tt{PyPy\ 3.10}PyPy 3.10 下，保证能够在时限内通过。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 题解简述 以下提供每道题目的思路简述和 Python\tt{Python}Python 代码，详细题解的 AC 代码，请点击题目标题查看。 A - 交集 本题可以使用很多方法解决，这里使用集合的思想来获取两个线段的交集： 1. 令交集的左端点为 LLL，右端点为 RRR。 2. 那么 L=max⁡(L1,L2), R=min⁡(R1,R2)L = \max{(L_1, L_2)},\ R = \min{(R_1, R_2)}L=max(L1 ,L2 ), R=min(R1 ,R2 )。 对于本题，若 L≤RL \leq RL≤R 则交集存在，交集的线段长度为 R−LR - LR−L，否则交集不存在，长度为 000。 语法小课堂 1. 使用 std::max(a, b) 可以获取 a 和 b 中较大的那个；反之使用 std::min(a, b) 可以获取 a 和 b 中较小的那个。 注意：a 和 b 的类型一定要严格一致，并且 int 和 long long 会被认为是两种完全不同的类型。 2. 条件运算符：E1 ? E2 : E3 。若 E1 为 true 则表达式的结果为 E2，否则为 E3。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ B - 比赛结果 我们可以使用一个 std::string 数组 mat 来存储比赛对局的情况。 然后使用一个二重循环遍历这个 std::string 数组 mat，对于每个 (i,j)(i, j)(i,j)，检查 mat[i][j] 和 mat[j][i] 是否存在矛盾； 若根据题目检查发现矛盾则直接输出 incorrect，并使用 return 0 直接退出程序（ Python\tt{Python}Python 可以使用 exit(0)）。 若执行完整个二重循环后，并没有退出程序，则说明比赛结果是正确的，输出 correct 即可。 语法小课堂 1. std::vector 可以当作普通的数组来使用，在效率上几乎与普通数组相当，而且操作和功能更为强大。 2. 基于范围的 for 循环：使用 for (auto x : mat) 可以方便地遍历许多 STL\tt{STL}STL 容器。类似于 Python\tt{Python}Python 中的 for x in mat:。 3. 此处使用的 for (auto &x : arr) 多了一个 & 为 引用，表示可以对 mat 中的元素进行直接修改，而不加 & 则仅为 复制（值传递）。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ C - 新建文件夹（1） 令 L=10L=10L=10 为字符串的最大长度。 如果我们每次都按照题目描述中的的那样去暴力查找统计与 SiS_iSi 相同的字符串的数量，则总共需要花费 Ω(N2)\Omega(N^2)Ω(N2) 时间，从而导致 TLE\tt{TLE}TLE（超时）。 我们可以使用 std::map 来存储“到目前为止 SiS_iSi 出现的次数”（Python\tt{Python}Python 可以使用 defaultdict(int)），这样对于每个字符串 SiS_iSi 可以在 O(Llog⁡N)\mathrm{O}(L\log N)O(LlogN) 的时间内确定要输出的字符串。 通过这种方法，可以在总共 O(NLlog⁡N)\mathrm{O}(NL\log N)O(NLlogN) 的时间内解决问题。 语法小课堂 1. std::map<K, V> 可以创建一个具有 (K:V)(K: V)(K:V) 映射关系的容器，对于本题中，我们希望给出一个字符串，就能够获取其出现的次数，实际上是要建立一个关于 (string:int)(\tt{string: int})(string:int) 的映射关系。那么访问时就可以像数组那样使用 [] 访问。 2. 对于 Python\tt{Python}Python 推荐使用 defaultdict 而非内置的 dict。 defaultdict 会在尝试访问字典中不存在的 键 时，给定一个 默认值，例如使用 defaultdict(int) 创建字典时，若访问到当前字典中不存在的 键 时，就会返回 0，而非直接报错，其行为更接近 C++ 的 std::map。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ D - 投硬币 问题的关键点是对于投完第 iii 枚硬币时，计数器为 jjj 时可以得到的最大金额。 这个状态只和投完第 i−1i - 1i−1 枚硬币时的状态有关。 于是对于投完第 iii 枚硬币，我们可以定义 dp[i][j]dp[i][j]dp[i][j] 为投完第 iii 枚硬币后，计数器为 jjj 可以获得的最大金额。 那么有 dp[i][j]=max⁡(dp[i][j],dp[i−1][j−1]+Xi+wj)dp[i][j] = \max{(dp[i][j], dp[i - 1][j - 1] + X_i + w_j)}dp[i][j]=max(dp[i][j],dp[i−1][j−1]+Xi +wj )，其中 wjw_jwj 为计数器为 jjj 时，获得的额外奖金。 对于无法存在的状态，比如投完第 i−1i - 1i−1 枚硬币后，无法令计数器为 jjj，那么便令 dp[i−1][j]=−∞dp[i - 1][j] = -\inftydp[i−1][j]=−∞。 另外在代码实现上我们只需要保存投 iii 枚硬币后的状态即可，所以只需要保留一维状态。 每次投完硬币后的状态数为 O(N)\mathrm{O}(N)O(N)；进行状态转移的复杂度为 O(N)\mathrm{O}(N)O(N)；总的时间复杂度为 O(N2)\mathrm{O}(N^2)O(N2)。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ E - 宏量运算 对于位运算而言，每一「位」的计算结果都是 相互独立 的，而每次运算后的结果只有 000 和 111 两种可能的结果，所以我们可以单独考虑运算对每一位的影响。 * 令 oneione_ionei 为：前 iii 个运算对 XXX 中二进制位上的 111 产生影响后的结果。 * 令 zeroizero_izeroi 为：前 iii 个运算对 XXX 中二进制位上的 000 产生影响后的结果。 那么对于当前 XXX 施加前 iii 个运算的影响的结果，应为： * 将当前的 XXX 二进制位上的 111 转化为 oneione_ionei 对应二进制位上的状态，位运算操作为 (X and onei)(X\ \mathrm{and}\ one_i)(X and onei )； * 将当前 XXX 二进制位上的 000 转化为 zeroizero_izeroi 对应二进制位上的状态，位运算的操作为 ((X xor M) and zeroi)((X \ \mathrm{xor}\ M) \ \mathrm{and}\ zero_i)((X xor M) and zeroi )，其中 M=230−1M = 2^{30} - 1M=230−1（即有效二进制位上全为 111）； 如何维护 oneione_ionei 和 zeroizero_izeroi ？ 很简单，只需要在每次操作时，将对 XXX 执行的位运算作用到 oneione_ionei 和 zeroizero_izeroi 上即可。 每次位运算的时间复杂度为 O(1)\mathrm{O}(1)O(1)，总的时间复杂度为 O(N)\mathrm{O}(N)O(N)。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ F - 彩球排序 若考虑所有球的颜色都互不相同，那么本题就变为了一道经典的「逆序对」问题。 那么我们可以考虑先求出整个序列 XXX 的「逆序对」的数量，在考虑如何消除相同元素的球进行交换对答案产生的影响即可。 对于颜色同为 CiC_iCi 的 MiM_iMi 个球对应的整数序列为 Xp1,Xp2,⋯ ,XpMX_{p_1}, X_{p_2}, \cdots, X_{p_M}Xp1 ,Xp2 ,⋯,XpM 。 令其排序以后的序列为 Xp1′,Xp2′,⋯ ,XpM′X_{p_1}', X_{p_2}', \cdots, X_{p_M}'Xp1 ′ ,Xp2 ′ ,⋯,XpM ′ 。 那么求出上述序列的「逆序对」数量，并将其在最终的答案中减去即可。 在实现上，我们只需要创建一个「树状数组」，然后将球上的数字按照颜色分组。 对于每组内的数字，球的颜色都是相同的，所以我们对于这个序列求逆序对，在总答案中减去即可； 在结束后，可以再遍历一遍组内的数字，消除求逆序对的过程中对树状数组产生的影响。 然后我们再对整个数组求逆序对，便可得到最终的答案。 以上两个步骤的时间复杂度皆为 O(Nlog⁡N)\mathrm{O}(N\log{N})O(NlogN)。 > 对于 Python\tt{Python}Python 而言一个可以优化的点是，倒序处理，这样每次查找就变成了“小于当前 x 的数量”，这样树状数组可以少做一半的 ask() 运算。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

> 前言：本次挑战赛的难度相较于前面几期有所提升，主要还是因为集训的关系，出题组的成员们没有充裕的时间想原创题目（so，只能原模原样搬运某一场 ABC 的考试了。）Anyway，AK 了就行。 > > 备注：由于 Python 的常数过大，本题解暂不同步更新 Python 版本的题解。 第一题 - INTERSECTION 题目跳转：交集。 这道题可以用暴力的方法，也可以稍微动点脑筋。看在数据量小，直接打暴力就行了，没必要花时间去找两个线段之间的关系。 注意到 0≤L1R1,L2,R2≤1000 \le L_1 R_1, L_2, R_2 \le 1000≤L1 R1 ,L2 ,R2 ≤100，可以新建一个标记数组：如果某个坐标属于某一条线段，那么就将对应索引的标记增加一。最后再遍历一边标记数组，如果存在一个坐标被标记了两遍，那么就证明该坐标被两条线段同时覆盖住了。 最后注意输出的时候要 −1-1−1，表示区间的长度。（如果没有任何重合的区间，即 ans == 0 时，特判直接输出 000 就可以了。 代码时间复杂度：O(N)O(N)O(N)。 本题的 AC 代码如下： 第二题 - TOURNAMENT RESULT 题目跳转：比赛结果。 第二题也是一道纯暴力的模拟题目，双层 for 循环依照题目题干的要求判断点 (i,j)(i, j)(i,j) 和点 (j,i)(j, i)(j,i) 所存的值是否存在冲突就行了。这边我用了一个 check 函数来检查是否存在冲突。如果存在冲突直接返回结果即可。 这边判断冲突的 check 函数我觉得值得讲一下，分类讨论： 1. 如果双方胜负状态相同且不是平局，则返回 false。 2. 如果一方是平局二另一方不是平局，则返回 false。 3. 可以证明其余的情况一定是合法的，直接返回 true 即可，不需要跟其他题解一样大费周章来写条件分支语句。 代码时间复杂度：O(N2)O(N^2)O(N2)。 本题的 AC 代码如下： 第三题 - NEWFOLDER(1) 题目跳转：新建文件夹(1)。 也是一道水题，用 STL 的 unordered_map/ map 存一下某一个字符串出现的次数就可以了。由于 NNN 比较大，因此如果直接用双层循环遍历的话绝对会超时。 但需要注意的是，map 的单次插入/查询的时间复杂度约为 O(log⁡2N)O(\log_2 N)O(log2 N)。因此本题的综合时间复杂度约为 O(Nlog⁡2N)O(N \log_2 N)O(Nlog2 N)。 本题的 AC 代码如下： 第四题 - FLIPPING AND BONUS 题目跳转：投硬币。 接下来来到了本次比赛的重头戏，题目难度也在此有了一个质的飞跃（我也不清楚这次 ABC 的难度为什么这么跳跃）。 考虑使用动态规划，定义状态 dpidp_idpi 表示第 iii 次掷硬币可以获得的最大金额。（其实这道题的状态定义有很多种，用二维的 dp 也可以通过本题，本题解暂是只提供前缀和动态规划的解法） 我们可以枚举在第 jjj 次抛置硬币时选择正面和反面的价值并取最大值。所以，对于每一次投掷硬币有两种可能的决策，分别是： 1. 硬币最终的状态时正面，得到第 iii 次投掷硬币的钱，计数器自增。因此结果就是得到 x1+x2+x3+⋯+xi−1+xix_1 + x_2 + x_3 + \cdots + x_{i-1} + x_ix1 +x2 +x3 +⋯+xi−1 +xi 元钱和 y1+y2+y3+⋯+yk−1+yk (c[k]≤i)y_1 + y_2 + y_3 + \cdots + y_{k-1} + y_k\ (c[k] \le i)y1 +y2 +y3 +⋯+yk−1 +yk  (c[k]≤i) 的奖金。 2. 硬币最终的状态是反面，那么计数器就从头开始计数。因此最终可以获得的结果就为从第 jjj 次投硬币时可以获得的最大金额 dpjdp_jdpj 加上在区间 [j+2,i][j+2, i][j+2,i] 投币全是正面所获的的金额（因为第 j+1j+1j+1 次投币不会获得任何的奖励）(x1+x2+x3+⋯+xi−1+xi)−(x1+x2+x3+⋯+xj+xj+1)(x_1 + x_2 + x_3 + \dots + x_{i-1} + x_i) - (x_1 + x_2 + x_3 + \cdots + x_j + x_{j+1})(x1 +x2 +x3 +⋯+xi−1 +xi )−(x1 +x2 +x3 +⋯+xj +xj+1 ) 再加上前 i−j−1i-j-1i−j−1 次计数器的奖励金额 (y1+y2+y3+⋯+yk−1+yk (c[k]≤i−j−1)(y_1 + y_2 + y_3 + \cdots + y_{k-1} + y_k\ (c[k] \le i-j-1)(y1 +y2 +y3 +⋯+yk−1 +yk  (c[k]≤i−j−1) 。 可以发现，我们可以通过开设两个前缀和数组来优化算法，分别约定 suma,sumb\mathtt{suma, sumb}suma,sumb 分别表示前 iii 次投币全都是正面所获的的金额和计数器的奖励金额。因此最后的状态转移方程时可以写成： dpi=max⁡(dpi,dpj+sumai−sumaj****umbi−j−1)dp_i = \max(dp_i, dp_j + suma_i - suma_{j+1} + sumb_{i-j-1}) dpi =max(dpi ,dpj +sumai −sumaj+1 +sumbi−j−1 ) 备注：十年 OI 一场空，不开 long long 见祖宗。请大家务必开 long long。本题的时间复杂度为 Θ(N+N22)\Theta(\dfrac{N+N^2}{2})Θ(2N+N2 )。 周后，本题的 AC 代码如下： 第五题 - MANY OPERATIONS 题目跳转：宏量运算。 一道位运算的恶心题目，跟上一题一样，可以用前缀和动态规划的思想来解决。因为每一位都是相互独立的，所以只需要按位进行 dp\mathtt{dp}dp 预处理就可以了。定义状态 dpi,j(0/1),kdp_{i, j(0/1), k}dpi,j(0/1),k 表示对于第 iii 位来说，一开始的值为 j(0/1)j(0/1)j(0/1)，经过前 kkk 次操作后这一位的值。而状态转移方程就是 dpi,j,k=dpi,j,k−1dp_{i, j, k} = dp_{i, j, k-1}dpi,j,k =dpi,j,k−1 。之后不断迭代就可以求出最后的解。 本题的主要难点是位运算的一些操作，有些同学对位运算的操作不太熟悉，这里提供一些常见的位运算操作： 1. 获取一个数字的第 jjj 位：(x >> j) & 1。 2. 判断数字是否是奇数：x & 1。 3. 将一个数字乘上 2j2^j2j：(1 << j) * x。 本题的时间复杂度约为 Θ(60N)\Theta(60N)Θ(60N)。 因此，本题的 AC 代码如下： 第六题 - SORTING COLOR BALLS 题目跳转：彩球排序。 > 一道逆序对的题目，因为我懒的使用归并排序来做，所以我用了 树状数组 + map 的方式，荣获运行时长 44.9s 的好成绩。其实这道题应该比第五题简单，Based on my opinion。 一道普普通通的逆序对的题目，在计算逆序对的时候去除相同颜色的逆序对就可以了，类似一道模板题。我用了两个树状数组分别来计算每个数字出现的次数和每个颜色出现的次数。 本题的 AC 代码如下，时间复杂度约为 O(Nlog⁡2N)O(N \log_2 N)O(Nlog2 N)：

前言 这次挑战赛更难了亿点啊。为了精简题解长度，已经去了头文件、部分宏定义和快读快写。 T1 首先是 000 的情况：L1≤R2 or⁡ L2≤R1L_1\leq R_2\ \operatorname{or}\ L_2\leq R_1L1 ≤R2  or L2 ≤R1 ，两条线段不交/只交于一点。 然后暴力分讨。 1. L1≤L2 and⁡ R1≥R2L_1\leq L_2\ \operatorname{and}\ R_1\geq R_2L1 ≤L2  and R1 ≥R2 线段 L2R2L_2R_2L2 R2 被 L1R1L_1R_1L1 R1 包含。直接输出 L2R2L_2R_2L2 R2 的长度即可。 2. L1≤L2 and⁡ R1≤R2L_1\leq L_2\ \operatorname{and}\ R_1\leq R_2L1 ≤L2  and R1 ≤R2 线段 L1R1L_1R_1L1 R1 与 L2R2L_2R_2L2 R2 的交集为 R1L2R_1L_2R1 L2 。输出 R1L2R_1L_2R1 L2 的长度即可。 3. L1≥L2 and⁡ R1≤R2L_1\geq L_2\ \operatorname{and}\ R_1\leq R_2L1 ≥L2  and R1 ≤R2 类似于 1。 4. L1≥L2 and⁡ R1≥R2L_1\geq L_2\ \operatorname{and}\ R_1\geq R_2L1 ≥L2  and R1 ≥R2 类似于 2。 T2 依然是分讨。设 1≤i,j≤n,i≠j1\leq i,j\leq n,i\neq j1≤i,j≤n,i=j： 1. Ai,j=DA_{i,j}=\texttt{D}Ai,j =D：Aj,iA_{j,i}Aj,i 也应该为 D\texttt{D}D。 2. Ai,j=WA_{i,j}=\texttt{W}Ai,j =W：Aj,iA_{j,i}Aj,i 应该为 L\texttt{L}L。 3. Ai,j=LA_{i,j}=\texttt{L}Ai,j =L：Aj,iA_{j,i}Aj,i 应该为 W\texttt{W}W。 枚举判断即可。 T3 使用 map 计数字符串出现的次数即可。如果这个字符串没有出现过，就直接输出；否则要再输出出现的次数。然后在 map 对这个字符串计数。 T4 这题开始上难度了 qwq 首先看数据范围：M,N≤5000M,N\leq 5000M,N≤5000，也许我们可以设计一个时空 O(n2)O(n^2)O(n2) 的 DP。无后效性是满足的，第 iii 次硬币的状态由 i−1i-1i−1 次转移而来。 发现状态只需要硬币和计数器。所以考虑这样设状态：设 f(i,j)f(i,j)f(i,j) 表示第 iii 次掷硬币，计数器为 jjj 时的最大收益。从硬币维开始枚举。每一次枚举有两种可能： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ * 正面 设计数器本次显示 jjj，第 iii 次掷硬币时掷到正面可以获得 X(i)X(i)X(i) 元，计数器为 iii 时可以获得 Y(i)Y(i)Y(i) 元，则容易推得： f(i,j)=f(i−1,j−1)+X(i)+Y(j)(j≥1)f(i,j)=f(i-1,j-1)+X(i)+Y(j)\qquad(j\geq1) f(i,j)=f(i−1,j−1)+X(i)+Y(j)(j≥1) * 反面 计数器本次必然显示 000。可以由上一轮的所有状态取最大值直接转移而来，即 f(i,0)=max⁡j=0i−1f(i−1,j)f(i,0)=\max\limits_{j=0}^{i-1}f(i-1,j)f(i,0)=j=0maxi−1 f(i−1,j)。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 结果为投掷第 nnn 次硬币的最大值，即 max⁡i=0nf(n,i)\max\limits_{i=0}^{n}f(n,i)i=0maxn f(n,i)。 实现还是很简单的。注意开 long long。嫌空间大可以把动态规划数组滚掉一维，是可选的。 T5 前置知识：位运算。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 这道题直接模拟是 O(n2)O(n^2)O(n2) 的，必然超时。 首先位运算很多，发现位与位之间是没有关系的，我们考虑逐位计算，可以简单很多。接下来的讨论都是基于每一位的。 先考虑怎么降时间复杂度。发现每一次依次完成 1−i1-i1−i 操作后，一定是以下两个情况之一： * 反转当位 * 将当位设置为固定值 然后考虑将 1−(i−1)1-(i-1)1−(i−1) 操作的情况拓展至 1−i1-i1−i。设有覆盖标记 t1t1t1，反转标记 t2t2t2。又分为六种情况： * &0 操作。覆盖标记设 000，反转标记清零。 * &1 操作。无需操作。 * |0 操作。无需操作。 * |1 操作。覆盖标记设 111，反转标记清零。 * ^0 操作。无需操作。 * ^1 操作。反转反转标记。 如果存在覆盖标记，则直接将原数赋值为覆盖标记。如果存在反转标记，则对原数进行反转。每一次操作完毕后记录过程性答案，时间复杂度 O(n)O(n)O(n)。细节注释都放在代码里了。 T6 前置知识：归并排序求逆序对 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 首先忽略颜色限制。只能两两交换，把序列排成升序，需要几次操作？显然是逆序对的个数。使用归并排序可以在 O(nlog⁡n)O(n\log n)O(nlogn) 的时间内求逆序对，这里直接贴上代码。 那么加上颜色限制之后，就变得复杂了。先不要急，首先求出原序列的逆序对个数。但是显然有一些逆序对不需要交换。是哪些逆序对呢？当然是同色的逆序对。因此，我们直接将各个颜色的数按序分进桶。（我就是因为没有按序被卡了好久www） 然后对各个桶内的球进行归并排序求逆序对。原序列的逆序对个数，减去同色逆序对个数，就是异序逆序对个数，也就是我们要求的答案了。 实现当然还是轻轻松松。注意一下 long long，然后桶使用 vector 维护就行了。总复杂度 O(nlog⁡n)O(n\log n)O(nlogn)。

如何从0开始用博客记录自己的信奥学习之路 为什么需要写博客 ? 为什么要写博客 ？ 博客的本质就是 「 线上笔记 」。 「 笔记 」是对学习过程的整理以及归纳 , 也方便日后回顾复习 。而为什么需要 「 线上 」 , 是因为 1. 线上可以 随时翻阅 , 方便查看。 2. 与他人评论交流能帮助自己 发现并修改博客的错误 。可以对自己的知识体系进行修正和完善。 3. 能帮助有需要的人 , 分享知识 , 进入 开源世界 。 4. 记录自己的技术成长 , 是未来的简历 。 如何开始写博客 , 我们需要使用 MarkDown 语法 以及 Joplin 编辑器 。 什么是 MARKDOWN ? MarkDown 是有一款轻量级的标记语言 ( 易读、易写、易移植 )。文本格式通过「 标签 」的方式进行定义。与 Word 的所见即所得不同，MarkDown 在写完标签格式 + 内容之后需要在专门的 MarkDown 编辑器或者支持 md 格式转换的网页中才能看的见 「 实际效果 」。 入门 MarkDown 请看 关于MarkDown的简单介绍 MarkDown完全入门 推荐 MarkDown 编辑器 Joplin 一款免费开源的笔记软件 马克飞象在线MarkDown编辑器 MARKDOWN 中文排版规范 为什么需要中文排版规范 ？无规矩不成方圆。就像写信需要相应的格式规范一样 , 如果 MarkDown 不进行格式规范 , 那么对于阅读者来说就是一场 「 灾难 」。 使用舒适的中文排版规范看这里 一篇基础的信奥学习博客应该具有什么 ? 1. 简洁清晰 的表达 , 对知识点的讲解尽量 简单直接 , 对思路的阐述 清晰明了 。 2. 分点阐述 内容 , 对于较长的内容进行分点说明 , 层层剖析。 3. 直接贴出代码 , 并且对代码关键点进行注释。 4. 必要时候配上相关 图片 以及 公式。 课堂笔记应该如何写 ？ 1. 只记录 关键的知识点 , 并对关键知识点用自己的话来解释。 2. 贴上 重点代码 并做好注释。 3. 贴上 相关图片 帮助理解。 4. 对整体内容 总结概括 。 题解笔记应该如何写 ？ 1. 对 题目大意 用自己的话来表述 , 说清楚要解决什么问题。 2. 讲述清楚 分析问题 的思路 , 可以从哪里开始出发开始思考 , 途中遇到了什么错误。如何找到正确的思路等等。可以附上 图片和链接 说明解决该问题需要掌握的额外知识。 3. 列举出 实现代码 中需要注意的点 , 需要用到什么算法 , 可能遇到什么问题等。 4. 直接贴出 代码 , 并对重点部分做出注释。 比赛心得应该如何写 ？ 1. 分点 总结每一道题的解题过程 , 写出比赛当时的 心路历程 。 2. 反思比赛的 失误点 。 总结有哪些地方做的不好 , 有哪些能力不足 , 有哪些算法没有掌握等。 3. 规划下次比赛时需要 提升 的点 。例如算法能力 、代码能力 、debug能力等等。

> 自我反省：确实这次比赛没考好（问题不大，至少排位分没掉）。 博客园链接同步：点此跳转 第一题 - A24630.ASCII 码 题目链接跳转：A24630.ASCII 码 直接用 C++ 内置的类型转换工具就可以了，(char) 可以将任意的数字转换成一个字符（其实字符底层就是用数字存储的）。 本题的 AC 代码如下： 第二题 - A24631.挑食的小码君 题目链接跳转：A24631.挑食的小码君 做题思路：遍历两遍，第一次遍历通过 maxi 变量记录这些食物中最大的美味值。之后遍历小码君所有不喜欢的食物，判断某项食物的美味值是否等于 maxi。 代码很简单，本题的 AC 代码如下： 第三题 - A24632.奇怪的机器 题目链接跳转：A24632.奇怪的机器 数据量不大，直接模拟和暴力枚举就行了。枚举全部数字变成 kkk 所需要花费的最少时间。 在枚举的过程中需要注意的是，由于在一秒之内小码君只能按下一个按钮，因此如果一个数字 aaa 在某一列出现了 xxx 次，那么当枚举 k=ak=ak=a 的时候，需要多经过 (x−1)×10(x - 1) \times 10(x−1)×10 轮才可以把这些转盘（在同一列都出现了 xxx 次）变成相同的数字。 本题的 AC 代码如下： 第四题 - A24633.独特三元组 题目链接跳转：A24633.独特三元组 这道题有很多做法，这里提供一个基于排列组合的算法。 假设有 NNN 个元素，且每个元素各不相同，那么满足题目要求的三元组数量就是这 NNN 个元素中任意取 333 个元素的组合。也就是 (n3)=n×(n−1)×(n−2)/1\binom{n}{3} = n \times (n-1) \times (n-2) / 1(3n )=n×(n−1)×(n−2)/1 。 如果有重复的元素呢？我们只需要把重复的元素再“去除”掉就行。 具体地说，如果某个元素的出现次数 arr[i] 大于等于 333，则可以从这些重复的元素中选出三个元素组成一个三元组 (Ai,Ai,Ai)(A_i,A_i,A_i)(Ai ,Ai ,Ai )，这是不符合条件的，因此再删除掉这些重复元素的组合数即可。即 (arr[i]3)\binom{arr[i]}{3}(3arr[i] )。 如果某个元素的出现次数 arr[i] 大于等于 222，则可以从这些重复的元素中选出两个元素，再从数组中的其他元素中选出一个不同的元素组成三元组 (Ai,Ai,Aj)(A_i,A_i,A_j)(Ai ,Ai ,Aj )，其中 Ai≠AjA_i \neq A_jAi =Aj ，即 (arr[i]2)\binom{arr[i]}{2}(2arr[i] ) 。 最后本题的 AC 代码如下： 第五题 - A24634.道路削减 题目链接跳转：A24634.道路削减 > 前言：刚开始看这道题目的时候看成了最小生成树的模板题目，盲目的 wsq 随手打了一篇最小生成树的代码交上去，荣获满堂红（葬送了好多次提交记录，真是个悲惨的事情）。 最短路树的模板题目，在 Dijkstra 求最短路径的基础上，记录每一个顶点的“前驱边”就行了。更进一步地，如果松弛了某一条边 E(A,B)E(A, B)E(A,B)，可以使得从源点到达 BBB 点的最短距离缩短，那么就保留这一条边（覆盖掉原本通往 BBB 点的前驱边即可，一开始没有可以设置为无穷大或者是一个无意义的数字）。可以证明，如果有 NNN 个顶点，排除源点，当每一个顶点都有一个前驱边时，图上正好只有 N−1N-1N−1 条边。且每一个点到源点的距离都是最小的。 PS：本题的数据量比较大，一定要开 long long 数据类型，同时在计算最短路初始化的时候，切记无穷大要开的大一点。 本题的 AC 代码如下： 第六题 - A24635.分面包 题目链接跳转：A24635.分面包 这道题正着思考比较麻烦，但可以反着思考（选择从小面包逐步拼成大面包，而不是从大面包逐步切割成小面包）。不难发现反着思考后就是一个典型的贪心问题（哈夫曼树）。假设现在有 NNN 块长度不一的小面包，那么将这些小面包合并成稍大一些的面包的最优策略就是选择剩下的小面包中长度最短的两块进行合并。每次合并的代价是两个面包的长度之和。通过这种方式，可以确保每次合并的代价最小，从而最终达到最小的总花费。 为了实现这个过程，我们可以使用一个优先队列（最小堆）来维护当前所有待合并的面包。每次从队列中取出两个长度最小的面包进行合并，并将合并后的新面包重新加入到队列中。如此反复，直到队列中只剩下一个面包。 接下来，考虑如何处理“每个孩子 iii 必须收到一个长度正好为 AiA_iAi 的面包”这个要求。如果原始面包长度 LLL 大于这些长度之和，则将多余的部分 L−∑AiL - \sum A_iL−∑Ai 也加入到队列中。代表“多出来的部分”也需要被单独分割出来。 本题的 AC 代码如下：

ACGO 第9次排位赛题解 写在前面 本次排位赛 EEE 题「隐藏元素」数据已加强。 本次排位赛再次对题目难度进行调整，同时赛后会统计大家的解题情况，以将排位赛的题目难度定在一个合理的档位。 本场排位赛的所有题目的难度评级为： A B C D E F 捉迷藏 最长公共前缀 坏掉的数字键 奇怪的次方 隐藏元素 圣诞礼物 入门 入门 入门 普及- 普及/提高- 普及/提高- 同时本次比赛作为 Acgo\tt{Acgo}Acgo 平台第一场接入 Python\tt{Python}Python 的比赛，鼓励所有使用 Python\tt{Python}Python 的同学参加，调整了时间限制，并增强数据「强度」。 非常感谢大家参加本场排位赛！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 直播预告 直播时间：6月22日（周六）16:00 开始 直播地址：B站ACGO官方账号 直播内容：排位赛#9复盘 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 题解简述 以下提供每道题目的思路简述和 Python\tt{Python}Python 代码，详细题解的AC代码包括复杂度分析，请点击题目标题查看。 A - 捉迷藏 我们可以有很多种方法解决这个问题：可以使用循环枚举 [0,9][0,9][0,9] 之间的所有数字，也可以使用分支语句分类讨论，当然也有比较聪明一些的方法。 观察题目不难发现，A×BA \times BA×B 的结果只有 [0,1,2,3,4,6,8,9][0, 1, 2, 3, 4, 6, 8, 9][0,1,2,3,4,6,8,9] 这几种结果，而 555 和 777 这两个数字是无法得到的。所以我们直接输出 555 或者 777 即可。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ B - 最长公共前缀 我们可以使用一个变量 iii 从 000 开始依次比较两个字符串的当前字符，直到遇到不相等的字符，或者其中一个字符串遍历完毕停下来，此时 iii 就是两个字符串的最长公共前缀的长度。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ C - 坏掉的数字键 对于读入的每个 AiA_iAi 检测其是否含有数字 DDD，有两种方法：1.数位分离判断是否出现 DDD；2. 把 AiA_iAi 当作字符串，在其中查找字符 DDD 是否存在即可。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ D - 奇怪的次方 题目解析 显然 XXX 越大， XNX^NXN 就越大，答案有单调性，所以我们可以使用二分来快速计算 XXX 的值。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ E - 隐藏元素 题目解析 本题需要我们根据各个变量 AiA_iAi 和 A1A_1A1 的关系来推出 AiA_iAi 的值。 我们可以根据给出的 MMM 条信息来构建一个无向图： 对于 Ai⊕Aj=kA_i \oplus A_j = kAi ⊕Aj =k，我们可以构建一条 (i,j)(i, j)(i,j) 的边权为 kkk 的边。 最后使用 DFS/BFS\tt{DFS}/\tt{BFS}DFS/BFS 从 111 开始遍历整个图，对于遍历到的每个点 uuu 其所有的邻接点 viv_ivi ，那么 Avi=Au⊕wu→viA_{v_i} = A_u \oplus w_{u \rightarrow v_i}Avi =Au ⊕wu→vi 。 遍历结束以后没有遍历到的点，说明无法判断其和 A1A_1A1 的关系，输出 −1-1−1 即可。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ F - 圣诞礼物 如果我们直接忽略数据范围，不难发现可以使用完全背包的DP模型来解决这道问题，定义 dp[i][j]dp[i][j]dp[i][j] 为前 iii 个礼物，使用 jjj 个糖果能够获得的最多金币。 但是注意到本题的数据范围 N,M (1≤N,M≤105)N, M\ (1 \le N, M \le 10^5)N,M (1≤N,M≤105) 如果使用上述递推式，时间复杂度为 O(N×M)\mathrm{O}(N \times M)O(N×M)。会超出本题的时间限制。 那么进一步分析题目我们会发现对于每个礼物 AiA_iAi ，制作出礼物需要的糖果为 f(Ai)f(A_i)f(Ai )，其中 1≤Ai≤1091 \le A_i \le 10^91≤Ai ≤109，我们不难发现，2≤f(Ai)≤632 \le f(A_i) \le 632≤f(Ai )≤63； 而对于每个 f(Ai)f(A_i)f(Ai ) 由于可以重复制作同一种礼物，所以只需要取 max⁡Bi\max{B_i}maxBi 即可。 所以我们可以转换 dp[i][j]dp[i][j]dp[i][j] 定义为制作需要糖果数量不超过 iii 的礼物，使用 jjj 个糖果能够获得的最多金币。 那么此时的时间复杂度转化为 O(K×M)\mathrm{O}(K \times M)O(K×M) 其中 K=63K = 63K=63。 > 使用 Python 的同学请不要使用 min/max 函数，非常耗时，建议改用 if 语句。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

本贴为第16次欢乐赛题解 注者:Yuilice 小张张五 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ T1 快乐新年 题目大意 给出一个整数nnn，取值范围为9≤n≤169 \leq n \leq 169≤n≤16,要求根据对应的数字去输出对应的名称。 题意分析 题目描述当中，给出了对应称呼的表格，表格如下。 日期 称呼 9 除夕 10 初一 11 初二 12 初三 13 初四 14 初五 15 初六 16 初七 解题思路 我们只需要使用if语句输出对应内容即可。 时间复杂度解析 只使用到了简单的分支语句，因此时间复杂度为O(1)O(1)O(1) 代码演示 T2 优才生 题目大意 题目共会给出nnn位学生的信息，信息为:姓名、德分、才分。要求你根据给出的德分与才分划分学生的名次。 题意分析 题目描述当中，给出了学生名词排序的优先级顺序，顺序如下 1、 按照德分排序，德分较高者排名靠前。 2、 按照才分排序，才分较高者排名靠前。 3、 如果分数皆相等，最后按照名字的字典序顺序，较小者靠前。 最后根据排名，从上至下输出排名对应的学生姓名即可，需要注意，只有德才分均为60及以上的同学才可输出，每个名字独占一行。 解题思路 本题根据给出的描述，我们可以得知需要按照优先级进行排序，那么我们就可以联想到结构体排序。 根据优先级我们可以编写出一段比较函数的伪代码，其中f与k分别代表德分与才分。 最后只需要在输出的时候根据分数是否都在60分及以上输出名字即可。 时间复杂度解析 需要使用到结构体排序，共有n个元素，所以最后的时间复杂度为O(nlogn)O(nlogn)O(nlogn) 代码演示 T3 答题卡 题目大意 给定一个n×nn \times nn×n的矩阵，矩阵仅由A,B,C,D组成，代表竖着的答题卡。 随后给定一个n×nn \times nn×n的矩阵，矩阵仅由+,-,?所组成,代表用横着的答案去比较竖着的答题卡当中，有哪些格子的答案是正确，错误，与不确定的。 现在，假若你将答题卡横过来，求解最多有几个正确的答案与最少有几个正确的答案。 题意分析 我们可以通过题意得知，竖着的答题卡对应横着的答案，也会有几道题目正确，从而得知正确答案矩阵当中的部分信息，再去进行解题即可。 解题思路 题目最终要求的目的为两个 最多以及最少 ，那么我们就要通过枚举的方式求出不确定答案格子的总数与确定答案格子的总数即可。 首先，我们要明确不确定答案格子的定义: * 原本位置为?的格子一定为不确定答案 * 竖着答题卡原本错误格子-所对应的字符，与旋转变为横着答题卡对应格子的字符不相同，也有可能是正确答案，也为不确定答案。 随后确定答案格子定义就比较简单了: * 竖着的答题卡原本正确+格子对应的字符与翻转过后横着的答题卡对应位置字符一致，则为正确答案。 最终，我们只需要将不确定答案总数累加上确定答案总数则为最多，只保留确定答案则为最小。 时间复杂度解析 本题使用循环对矩阵进行枚举，时间复杂度为O(n2)O(n^2)O(n2) 代码演示 T4 解题赛 题目大意 题目给出nnn个题目(题目编号从1开始)第一次解题的得分aia_iai 与后续解题分数bib_ibi ，并且给出你能够解题的题目总数kkk，要求你计算出最大可以获取的分数总额。 题意分析 我们需要在kkk次的解题机会当中，选择一个积分最大化的方案执行，最后输出答案即可。 但是在题目当中，我们的方案搭配有很多种，比如选择只做第一个题目，做第一个题目之后只做第二个题目等。 解题思路 根据题目意思，我们可以很快总结出两种大致最值的策略。 * 先做完所有的任务，拿取第一次的奖励之后，再将剩下的机会花在重复解题价值最高的题目当中。 * 找到重复做价值最大的谜题，然后一直做它。 这两种策略的取舍和状态具有很多种，但是我们也将答案锁定在了一个较小的范围当中，那么如何进行解题呢？我们还可以再一次进行优化。 我们不妨可以思考一下，我们可以同时枚举出这两种策略所涉及到的所有方案，然后选取出其中总价值最大的答案即可。 我们可以设定一个变量temptemptemp，来保存第一次做过每一个任务的积分，同时设定一个变量maxbimax_{bi}maxbi ，来保存重复做价值最高的任务。 根据kkk,枚举我们做到第iii个任务时，剩下的机会k−ik - ik−i全部兑换bib_ibi 的积分后，所获得的总积分temp+b[i]∗(k−i)temp + b[i] * (k - i)temp+b[i]∗(k−i)。 最终，我们从我们枚举的所有总积分当中选取出一个最大值即可。 时间复杂度解析 本题仅使用for循环对数组进行遍历，因此时间复杂度为O(n)O(n)O(n) 代码演示 T5 井字棋 题目大意 本题为多组样例测试 给出一个3×33 \times 33×3的矩阵，矩阵仅有三个字符.,X,O所组成，代表两个人在3×33 \times 33×3的矩阵上下棋的棋局，X为先手,O为后手,.为未下棋地块。以任意方向放满三个棋子为结束的标志。 请你判断给出的3×33 \times 33×3的矩阵是否可能会在两者对局当中出现，每组样例给出YES与NO的回答。 题意分析 根据给出的棋盘进行判断是否为合法的棋盘即可。 解题思路 矩阵最大为3×33 \times 33×3，我们可以通过枚举所有的情况来判断棋盘是否为合法的。 首先我们需要理清楚，怎样的棋盘为合法的，怎样的棋盘为非合法的。 * X为先手，O为后手，那么在整个合法棋盘当中X的数量必然大于等于O，并且X下过之后O必然会添上一个，那么在整盘的棋局当中，X的数量只会比O多一个或者相等。 * 任意方向三个格子相同字符为结束，那么在一个合法棋盘当中，不可能出现两个人都获胜的情况。 我们还可以根据第二个条件继续衍生出两种不合法情况。 * 假若X获得胜利，那么此时X的数量必然不与O相等。 * 假若O获得胜利，那么此时O的数量必然不可能比X小1个。 整理出以上条件之后，我们只需要判断X与O之间的数量关系，再根据两者的获胜状态判断数量关系即可得出答案。 时间复杂度解析 本题使用循环对矩阵进行枚举，时间复杂度为O(n2)O(n^2)O(n2) 代码演示 T6 挖矿 题目大意 给出nnn件商品的数量与价值，以及背包的体积www，求怎样的装载策略可以在不超过背包体积的情况下让拿取物品到达价值最大化。 题意分析 求价值最大化的物品搭配策略，要求数量总额不超过背包体积。 解题思路 根据题目给出的数据范围，每个物品的最大价值vi≤109v_i \leq 10^9vi ≤109，因此此题用背包去求解是固然求不了的。 我们不妨转换下题意，将每种商品视为si/64s_i / 64si /64个价值总额为vi×64v_i \times 64vi ×64的商品(不足64个的部分分离出来作为一个商品)，那么此题就可以由背包问题转型为贪心类型的问题。 那么当我们从价值最大往最小的去取时，此时的方案一定是最优的。先从最大到最小去取，当取完完整的个体后，再去考虑剩下不够64个的商品。最后判断取与不取哪种方法最优。 在取值的过程当中，我们可以利用优先队列进行维护不足64个的商品，在进行判断时直接取队首即可。 实现的方法很多，只需要将时间复杂度压缩至O(nlogn)O(nlogn)O(nlogn)即可。 时间复杂度解析 利用优先队列进行维护，时间复杂度为O(nlogn)O(nlogn)O(nlogn) 代码演示

都是我自己一个字一个字敲的 :( 链接：点我跳转，查看笔记原文 给大家看一下目录： 备注：其实原本是有插图的，后来因为网络传播原因，就没把插图放上去。

ACGO 第 10 次排位赛题解 本场排位赛的所有题目的难度评级为： A B C D E F ASCII 码 挑食的小码君 奇怪的机器 独特三元组 道路削减 分面包 入门 入门 普及- 普及/提高- 普及/提高- 普及+/提高 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 题解简述 以下提供每道题目的思路简述和 Python\tt{Python}Python 代码，详细题解的 AC 代码与复杂度分析，请点击题目标题查看。 A - ASCII 码 对于任意给定的 ASCII\tt{ASCII}ASCII 值，我们可以使用强制类型转换，获取其字符形式。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ B - 挑食的小码君 可以将问题转化为：“在 B1,B2,…,BKB_1, B_2, \ldots, B_KB1 ,B2 ,…,BK 中，有没有一种食物的美味度是 NNN 个食物中最高的（允许并列）？” 对于这个问题我们可以通过以下流程解决： 1. 找出 NNN 种食物中的最高美味度（假设该值为 MMM）。 2. 对于 j=1,2,…,Kj=1,2,\ldots , Kj=1,2,…,K ，判断是否存在 ABj=MA_{B_j}=MABj =M 。 3. 如果有一个或多个这样的 jjj ，则答案为 Yes；否则，答案为 No。 可以用 for 语句和 if 语句来编写。 注意数组下标的范围。此外，注意不要多次输出 Yes，或在 Yes 后输出 No。 这一点，对于 C++ 程序可以在找到满足条件的 ABj=MA_{B_j} = MABj =M 之后使用 return 0 直接退出程序；对于 Python 程序可以使用 exit(0) 直接退出程序。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ C - 奇怪的机器 每个转轴一共只有 0, 1, …\ldots…, 9 共 101010 个字符； 我们可以尝试枚举最终停下来显示的字符，最终从 101010 个答案中取最小的即可。 对于转轴 iii 若想其显示字符 SjS_jSj ，那么根据题目意思，在每 101010 秒一个周期中只能选择第 jjj 秒按下按钮。即时间 ttt 需要满足 t=10×d+jt = 10 \times d + jt=10×d+j。 又每秒只能按一次按钮，我们可以使用一个数组 st 来标记 ttt 秒是否按过按钮, 然后可以枚举 ddd，找到没有按按钮的最小的 t=10×d+jt = 10 \times d + jt=10×d+j，将 st[t]st[t]st[t] 标记为 111。 对于每个字符 xxx，我们统计让所有的转轴停到 xxx，按下按钮最晚的时间 xtx_{t}xt 即可。最终的答案取所有 xtx_txt 中最小的，即 min⁡xt\min{x_t}minxt 。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ D - 独特三元组 可以将问题转化为：“求满足 Ai<Aj<AkA_i \lt A_j \lt A_kAi <Aj <Ak 的三元组 (i,j,k)(i, j, k)(i,j,k) 的数量”。 > 对于满足题目原条件的三元组 (i,j,k)(i,j,k)(i,j,k)，有且仅有一个 [Ai,Aj,Ak][A_i, A_j, A_k][Ai ,Aj ,Ak ] 的排列 PPP，使得 AP1<AP2<AP3A_{P_1} \lt A_{P_2} \lt A_{P_3}AP1 <AP2 <AP3 。 > 反之，对于有 Ai<Aj<AkA_i\lt A_j\lt A_kAi <Aj <Ak 的三元组 (i,j,k)(i,j,k)(i,j,k)，有且仅有一个 [i,j,k][i,j,k][i,j,k] 的排列 PPP，使得 P1<P2<P3P_1 \lt P_2\lt P_3P1 <P2 <P3 。 考虑枚举 jjj，那么 iii 和 kkk 可以独立选择。 满足条件的 iii 的数量是 AAA 中数值小于 AjA_jAj 的元素个数； 满足条件的 kkk 的数量是 AAA 中数值大于 AjA_jAj 的元素个数。 因此，只要准备一个数组 cnt，令 cnt[x] 为 AAA 中小于等于 xxx 的数量，便可以很容易地计算出满足条件的 iii 和 kkk 的数量。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ E - 道路削减 令 DiD_iDi 为从城市 111 到城市 iii 的最短距离。无论选择哪些道路，显然有 di≥Did_i\geq D_idi ≥Di 。 所以如果有选择道路的方案使得 di=Did_i=D_idi =Di 成立，那么这就是最优解。事实上，这样的选择方法总是存在的。 对于每个 i=2,3,…,Ni=2,3,\ldots,Ni=2,3,…,N，只需保留 “从城市 111 到城市 iii 的最短路径中的最后一条道路” 即可。 答案可以通过记录 Dijkstra\tt{Dijkstra}Dijkstra 算法中到达每个城市前的最后一条道路来找到。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ F - 分面包 1. 首先考虑 L=A1+A2+…+ANL=A_1+A_2+\ldots +A_NL=A1 +A2 +…+AN 的情况： 反转问题为：“使用 x+yx + yx+y 的成本将原本长度为 xxx 和 yyy 的面包拼接在一起，求将面包 A1,…,ANA_1, \ldots, A_NA1 ,…,AN 合并为一个面包的最小费用。” 这个问题和原问题等价。 在这里，原问题的最小费用等于在多重集 S={A1,A2,…,AN}S=\{ A_1,A_2,\ldots,A_N \}S={A1 ,A2 ,…,AN } 上重复以下操作 (N−1)(N-1)(N−1) 次的成本之和： * 令 s1s_1s1 和 s2s_2s2 为 SSS 中最小的两个元素。以 s1+s2s_1+s_2s1 +s2 的成本将长度为 s1s_1s1 和 s2s_2s2 的两条面包拼接在一起。 * 从 SSS 中删除 s1s_1s1 和 s2s_2s2 ，并将 s1+s2s_1+s_2s1 +s2 插入到 SSS 中。 由于每次操作后 SSS 的元素数量减少 111，显然完成以上操作后，SSS 只会剩下一个元素。 2. 考虑 L>A1+A2+…+ANL \gt A_1+A_2+\ldots +A_NL>A1 +A2 +…+AN 的情况： 对于 L>A1+A2+⋯+ANL > A_1+A_2+\cdots+A_NL>A1 +A2 +⋯+AN ，我们可以令 L=A1+A2+⋯+AN+XL = A_1 + A_2 + \cdots + A_N + XL=A1 +A2 +⋯+AN +X。 将剩余的部分当作一条面包，反转问题为：“使用 x+yx + yx+y 的成本将原本长度为 xxx 和 yyy 的面包拼接在一起，求将面包 A1,…,AN,XA_1, \ldots, A_N, XA1 ,…,AN ,X 合并为一条面包的最小费用。” 这个问题同样可以使用上述的方法解决。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

T1 T2 T3 T4 T5 T6 顶上去！

> 两三个星期没有发布新文章了，今天再来讲一个新的数据结构：图。 何为图论 见名知意，图论 (Graph Theory) 就是研究 图 (Graph) 的数学理论和方法。图是一种抽象的数据结构，由 节点 (Node) 和 连接这些节点的 边 (Edge) 组成。图论在计算机科学、网络分析、物流、社会网络分析等领域有广泛的应用。 如下，这就是一个图，可以看到这个图有 555 个顶点，分别编号为 {0,1,2,3,4}\{0, 1, 2, 3, 4\}{0,1,2,3,4} 。同时这个图有 444 条边，例如，在顶点 222 和 顶点 444 之间存在着一条边。 图的基本概念 在详细讲解图论和有关图论算法之前，先来了解一下在图论中的一些基本表述和规范。 1. 图 (Graph)：图是一种由一组顶点和一组边组成的数据结构，记做 G=(V,E)G = (V, E)G=(V,E)，其中 VVV 代表顶点集合，EEE 代表边集合。 2. 顶点 (Vertex)：顶点是图的基本单位，也称为节点。 3. 边 (Edge)：一条边是连接两个顶点的线段或弧。可以是无向的，也可以是有向的。一条边可以记做为 (u,v)(u, v)(u,v)。在无向图中，若存在一条(u,v)(u, v)(u,v)，表示可以从 uuu 点直接走到 vvv 点，反之亦然。但若在有向图中，存在一条边 (u,v)(u, v)(u,v)，表示可以从 uuu 节点直接走向 vvv 节点，如果不存在一条边 v,uv, uv,u，那么 vvv 节点就没有办法直接走向 uuu 节点。 4. 无向图 (Undirected Graph)：图中的边没有方向，即 (u,v)(u, v)(u,v) 和 (v,u)(v, u)(v,u) 是同一条边。 5. 有向图 (Directed Graph/ Digraph)：图中的边有方向，即 (u,v)(u, v)(u,v) 和 (v,u)(v, u)(v,u) 不是同一条边。 6. 简单图 (Simple Graph)：表示含有重边（两个顶点之间的多条边）和自环（顶点到自身的边）的图。 7. 多重图 (Multigraph)：允许有重边和自环的图。 8. 边权 (Weight of an Edge)：一般表示经过这一条边的代价（代价一般是由命题人定义的）。 如下图，就是一个有向的简单图（通常来说，在有向图中边的方向用箭头来表示）： 如下图，就是一个无向的多重图，其中存在两条边可以从顶点 555 到顶点 222： 与此同时，为了方便起见，对于无向图的处理，我们只需要在两个顶点之间建立两个方向相反的无向边就可以表示一个无向图，具体如下： 图的表示方法 在计算机中，图可以通过许多方式来构建和表示。总的可以分成图的邻接矩阵和邻接表两种方法（关于链式前向星本文不过多展开叙述，有兴趣的可以自行查阅相关文档）。 图的邻接矩阵 (Adjacency Matrix) 若一个图中有 NNN 个顶点，那么我们就可以用一个 N×NN \times NN×N 的矩阵来表示这个图。我们一般定义，若矩阵的元素 Ai,j≠−∞A_{i, j} \neq -\inftyAi,j =−∞ 表示从节点 iii 到 jjj 有一条有向边，其中边的权值为 Ai,jA_{i, j}Ai,j 。 假设存在一个有 333 个顶点的图，并且有三条有向边 E={(1,2),(2,3),(3,2)}E = \{(1, 2), (2, 3), (3, 2)\}E={(1,2),(2,3),(3,2)}，那么就可以用邻接矩阵表示为： G=[123101020013010]G = \begin{bmatrix} & \mathtt{1} & \mathtt{2} & \mathtt{3}\\ \mathtt{1} & 0 & 1 & 0 \\ \mathtt{2} & 0 & 0 & 1 \\ \mathtt{3} & 0 & 1 & 0 \end{bmatrix} G= 123 1000 2101 3010 画成可视化的图就长这个样子： 在 C++ 中，我们可以简单地用一个二维数组来表示： 图的邻接表 (Adjacency List) 邻接表本质上就是用链表表示图。数组的每个元素表示一个顶点，元素的值是一个链表，链表中存储该顶点的所有邻接顶点。假设存在一个有 444 个顶点的图，并且有四条有向边 E={(1,2),(2,3),(3,2),(3,4)}E = \{(1, 2), (2, 3), (3, 2), (3, 4)\}E={(1,2),(2,3),(3,2),(3,4)}，那么就可以用邻接表表示为： 画成可视化的图就长这个样子： 在 C++ 中，我们可以使用 STL模板库 中的 vector 来实现： 一般情况下，推荐使用邻接表的方式来存图，因为使用邻接矩阵比较浪费空间。在顶点数量非常多但边非常少的图中，N2N^2N2 的时空复杂度会导致 MLE 或 TLE 等问题。 图的各种性质 1. 度数 (Degree)：一个顶点的度是连接该顶点的边的数量。在有向图中，有 入度 (Indegree) 和 出度 (Outdegree) 之分（具体例子见后文）。 2. 路径 (Path)：从一个顶点到另一个顶点的顶点序列，路径上的边没有重复。 3. 回路 (Cycle)：起点和终点相同的路径。 4. 连通图 (Connected Graph)：任意两个顶点之间都有路径相连的无向图。 5. 强连通图 (Strongly Connected Graph)：任意两个顶点之间都有路径相连的有向图。 对于下面这个无向图不连通图，顶点 111 的度数为 111；顶点 222 的度数为 222；顶点 333 的度数为 111；顶点 444 的度数为 000。同时，由于 444 号顶点没有度数，所以该顶点没有办法到达任何一个其他的顶点，所以这个图是一个不连通图： 如下图，就是一个有向不强连通图。其中，顶点 111 的入度为 000，出度为 222；顶点 222 的入度为 111，出度也为 111；顶点 333 的入度为 222，但出度为 000。由于顶点 111 和顶点 222 可以走到顶点 333，但顶点 333 没有办法走到顶点 111 或顶点 222，因此下面的图不是一个强连通图： 对于下图来说，1→2→3→41\to 2\to 3\to 41→2→3→4 是一条从顶点 111 到顶点 444的路径。2→3→4→2→32\to 3\to 4 \to 2\to 32→3→4→2→3 就不是一个路径，因为相同的边 (2,3)(2, 3)(2,3) 被多次走到了。1→2→3→11\to 2\to 3\to 11→2→3→1 就是一个回路，因为这个路径的起点和终点相同： 图的遍历 图通常采用 深度优先搜索/ 广度优先搜索 这两个算法来遍历。其中深度优先算法是最常见的遍历算法。 对于一个用 邻接矩阵 保存的图，其深度优先搜索遍历的 C++ 代码如下： 对于一个用 邻接表 保存的图，其深度优先搜索遍历的 C++ 代码如下： 广度优先搜索的方式也类似： 对于判断无向图的连通性，我们只需要从任意一个点开始跑一遍深搜或者广搜就行了。如果所有顶点的 vis 都被标记了，则证明图是联通的，否则图就是不连通的。 例题讲解 P3916 图的遍历 模板题目，从每一个顶点开始用深搜遍历一遍就可以了。但从每一个点考虑能走到的最大点比较麻烦，一个更优的解决办法是反向建边，从最大的点开始遍历，这样子就可以一次性计算出多个结果。 P5318 【深基18.例3】查找文献 也是一道模板题目，正常遍历即可。 番外 - 图的常见算法 更多关于图论的算法，请持续关注后续更新。 1. 深度优先搜索 (DFS)：适用于遍历图和检测图中的回路。 2. 广度优先搜索 (BFS)：适用于寻找最短路径（无权图）。 3. Dijkstra 算法：适用于加权图中寻找单源最短路径。 4. Bellman-Ford 算法：适用于有负权边的图中寻找单源最短路径。 5. Floyd-Warshall 算法：适用于寻找所有顶点对之间的最短路径。 6. Kruskal 算法：用于求解最小生成树 (MST - Minimum Spanning Tree)。 7. Prim 算法：另一种求解最小生成树的方法。 8. 拓扑排序 (Topological Sorting)：适用于有向无环图 (DAG)，用于任务调度等应用。 9. Tarjan 算法：用于求解图中的强连通分量、割点、桥。

官方题解｜挑战赛#6 T1、黄金树下的幽影 T2、聪明的莫菲特 T3、魔剑亚托克斯 T4、Drogon T5、Kingdom Game II T6、神庙大冒险 附：挑战赛#5 获奖名单 👉 点击看看

在ACGO社区中，我们鼓励成员们通过提问和分享知识来共同进步。为了帮助大家更有效地交流和学习，我们特别引用了广泛认可的《提问的智慧》一文的核心思想，并针对我们社区的特点进行了适当的改编和优化。希望大家能够提出更清晰、更具体的问题，同时也能够培养出更好的编程习惯和问题解决技巧。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 一、提问指南 1. 阅读社区指南： * 在提问之前，请阅读我们的社区指南，了解如何提出有质量和有建设性的问题。 2. 展示你的努力： * 告诉我们你在尝试解决问题时所做的努力。比如，你已经阅读了哪些文档或尝试过哪些代码片段。 3. 提供详细信息： * 包括你的C++编译器版本、操作系统、完整的错误消息、相关代码段和你的目标。 4. 使用合适的格式： * 如果提问涉及代码，请使用社区支持的代码格式化方式，确保代码清晰可读。 5. 保持礼貌： * 即使你对问题感到沮丧，也要保持尊重和礼貌。记住，他人是在自愿帮助你。 6. 明确的问题： * 避免提问模糊不清的问题。如果你需要帮助解决一个特定问题，请提供完整的问题描述。 7. 耐心等待： * 社区成员都有自己的时间表，他们可能需要一些时间来回复你的问题。 8. 反馈解决方案： * 如果你的问题得到了解决，回来更新你的问题，让其他人知道解决方案。 9. 清晰的主题： * 你的帖子标题应该简洁明了，能够准确反映问题的核心。 10. 接受并学习批评： - 如果你的问题或代码收到批评，请保持开放态度，从中学习。 11. 分享你的知识： - 如果你找到了解决问题的方法，分享它，帮助社区成长。 12. 使用提问模板： - 如果社区提供了提问模板，请使用它来确保你的问题包含所有必要的信息。 13. 鼓励互助： - 社区鼓励成员之间的互助。如果你知道答案，不妨帮助其他成员。 14. 避免重复提问： - 在提问之前，搜索社区，看看是否已经有人提出过类似的问题。 15. 保持问题的相关性： - 确保你的问题与信奥主题相关。 二、示例提问模板 标题：无法通过编译：错误消息“未定义的引用” 正文： 大家好， 我在尝试编译一个C++程序时遇到了问题。我使用的是GCC 9.3.0，在Ubuntu 20.04系统上。 错误消息： 未定义的引用到‘int main()’ 我尝试了以下代码： 我确保了文件名和项目设置都是正确的，但问题仍然存在。 我已经查阅了XX文档和一些在线资源，但没有找到解决方案。 请问有人能帮我理解这个问题吗？非常感谢！ 三、 具体案例 以下是一些具体的案例，展示了如何在不同情况下提出高质量的问题： 案例 1：初学者的编译错误 问题标题：[初学者] 编译时遇到“未定义的引用”错误，求帮助！ 问题正文： 大家好， 我在尝试编译一个简单的C程序时，遇到了一个错误，我不太清楚怎么解决。我用的是Dev C编译器。 错误消息： Linker error: undefined reference to 'void __cdecl ClassName::memberFunction()' 我的代码是这样的： 我试着重新保存和编译了几次，但错误还是存在。 我是新手，对编译过程还不太熟悉。请问有没有人能告诉我这是怎么回事，我该怎么解决呢？非常感谢！ 案例 2：算法问题的求解 问题标题：[算法问题] 二分查找总是超时，如何优化？ 问题正文： 各位编程大佬， 我在解决一个算法题时，使用了二分查找，但是当数据量很大时，程序运行时间就会超时。我用的是C++标准库中的std::binary_search函数。 题目描述： 给定一个已排序的数组和一个目标值，判断目标值是否存在于数组中。 我的代码是这样的： 我在本地测试时效果很好，但是在社区的在线判题系统中就超时了。 请问有没有人能给我一些建议，我应该怎么优化我的算法呢？非常感谢！ 案例 3：初学者的语法问题 问题标题：[C++初学者] 关于循环语句的用法，我哪里做错了？ 问题正文： 大家好， 我在尝试编写一个计算1到100之间所有整数和的程序，但我的循环语句似乎有问题。这是我的代码： 我编译时没有错误，但运行结果却不对。请问我哪里做错了？我应该怎么做才能得到正确的结果呢？ 我是C++的初学者，对循环语句还不太熟悉。非常感谢大家的耐心指导！ 案例 4：算法逻辑的求助 问题标题：[信奥训练] 如何解决“水桶问题”的算法逻辑？ 问题正文： 各位编程高手， 我在训练中遇到了一个难题，被称为“水桶问题”。题目要求计算如何通过有限次操作，将一个水桶填满到恰好指定的水量。 题目描述： 给定一个容量为C的水桶和一个无限数量的小杯，小杯可以盛放任意正整数容量的水量，但每次只能从一个杯子倒水到水桶中。问至少需要倒几次水才能将水桶填满到恰好为W的水量。 我尝试使用贪心算法来解决这个问题，但似乎无法得到正确的答案。 请问有没有人能给我一些解决这个问题的提示或者思路？非常感谢！ 案例 5：代码优化的咨询 问题标题：[代码优化] 如何让我的程序运行得更快？ 问题正文： 大家好， 我在解决一个算法题时，发现自己的程序比其他人的慢很多。题目是关于在一个数组中找到第K大的元素。 我的代码是这样的： 我使用了排序，但听说排序不是最快的方法。请问有没有更高效的算法来解决这个问题？

> 在前几篇文章当中，我们已经讨论了许多有关数论的知识点了，因此 Macw 决定写几篇数据结构的文章缓一缓。（整天写数论相关的内容容易自闭（bushi））。 今天我们将会围绕一个新的数据结构，并查集（Disjoint Set Union）来展开。 集合与集合的常见操作 在谈论到并查集的时候，首先讨论一个前置知识点，即 集合（Set）的概念。集合是一种无序且不重复的元素集，用数学可以表示为 S={a,b,c,… }S = \{a, b, c, \dots\}S={a,b,c,…}，其中 SSS 是这个集合的名字，a,b,ca, b, ca,b,c 等就是这个集合中的元素。 集合的应用非常的广泛。举一个大家生活中都比较熟悉的例子，运动会报名人数统计。假设目前有两个集合，分别表示参加篮球比赛的选手和参加羽毛球比赛的选手，写作： Basketball={Alice,Bob,Cindy,Richard,Tom,Fred}｜参加篮球比赛的选手Basketball = \{\text{Alice}, \text{Bob}, \text{Cindy}, \text{Richard}, \text{Tom}, \text{Fred}\} ｜ \text{参加篮球比赛的选手}Basketball={Alice,Bob,Cindy,Richard,Tom,Fred}｜参加篮球比赛的选手。 Badminton={Vincent,Cindy,Tom,Richard,Selina,Hans}∣参加羽毛球比赛的选手Badminton = \{\text{Vincent}, \text{Cindy}, \text{Tom}, \text{Richard}, \text{Selina}, \text{Hans}\} | \text{参加羽毛球比赛的选手}Badminton={Vincent,Cindy,Tom,Richard,Selina,Hans}∣参加羽毛球比赛的选手。 对于多个集合而言，设 AAA 和 BBB 是两个集合，常见的有以下操作： 1. 交集（Intersection）：求出两个集合中共同包含的元素，写作 A∩BA \cap BA∩B。 2. 并集（Union）：求出两个集合中所有的元素并去重，写作 A∪BA \cup BA∪B。 3. 差集（Difference）：求出在一个集合 AAA 中但不在另一个集合 BBB 中的元素，写作 A∖BA \setminus BA∖B。 举例而言： * 如果我们想要求出既参加了篮球比赛，又参加了羽毛球比赛的同学，可以使用交集操作 Basketball∩Badminton={Cindy,Tom,Richard}Basketball \cap Badminton = \{\text{Cindy}, \text{Tom}, \text{Richard}\}Basketball∩Badminton={Cindy,Tom,Richard}。表示 Cindy, Tom 和 Richard 三个人既参加了羽毛球比赛，又同时参加了篮球比赛。 * 同理，如果我们想要求出所有参赛的同学，可以使用并集的操作 Basketball∪Badminton={Alice,Bob,Cindy,Richard,Tom,Fred,Vincent,Selina,Hans}Basketball \cup Badminton = \{\text{Alice}, \text{Bob}, \text{Cindy}, \text{Richard}, \text{Tom}, \text{Fred}, \text{Vincent}, \text{Selina}, \text{Hans}\}Basketball∪Badminton={Alice,Bob,Cindy,Richard,Tom,Fred,Vincent,Selina,Hans}。表示这些同学是所有参赛的选手。 * 如果我们想要求出参加了篮球比赛，但没有参加羽毛球比赛的同学，可以使用差集的操作 Basketball∖Badminton={Alice,Bob,Fred}Basketball \setminus Badminton = \{\text{Alice}, \text{Bob}, \text{Fred}\}Basketball∖Badminton={Alice,Bob,Fred}。表示 Alice, Bob 和 Fred 三人只参加了篮球比赛，没有参加羽毛球比赛。 在介绍完集合的基本操作后，我们将目光着重放在计算 并集 的过程中，这也是今天所要讲的并查集算法的重要组成部分之一。 并查集算法 并查集是一种树形的数据结构，用于处理一些不相交的集合（指的是两个集合的交集为空，即两个集合没有共同的元素），并支持 合并 和 查询 的操作。 * 查询（Find）：查找某个元素所属的集合。通常通过路径压缩（Path Compression）优化，以加快查找速度。 * 合并（Union）：合并两个集合。通常通过按秩合并（Union by Rank）优化，以保证树的高度较低，提高效率。 并查集广泛应用于解决动态连通性问题，如图的连通分量、网络连接、最小生成树等。 并查集代码的实现 在并查集中，每一个集合都可以被看作成一棵树。而集合的标识符也可以被表示为这一棵树的根节点。与此同时，如果在一个场景当中有许多的树，那么这些树将会构成一个森林。 当我们想要找到某一个节点在哪个集合当中，本质上就是在寻找这个节点的根节点编号。若我们想要合并两个集合，本质上就是将一颗树的根节点指向另一棵树的根节点。这样子两棵树就被合并成了一棵树，集合的合并操作也因此完成了。 推荐算法可视化网站：Visualgo.net，各位可以自行访问网站观看并查集算法逻辑的可视化演示。 第一步：定义变量和初始化。 首先，我们需要定义并初始化以个向量/数组，一个用于存储每个元素的父节点。一开始将所有元素的父节点都设置为该节点本身。 第二步：实现查询操作。 接下来，我们实现并查集的 find 操作，用于查找某个元素所属的集合。在查找元素所属的集合时，本质上就是在查找这个集合的父元素。该方法可以通过递归的方式来实现。其中，递归的终止条件就是某一个节点的父节点是该节点本身，代表这个节点是这个集合（树）的根节点。 在此基础上，我们还可以对算法进行时间上的优化，也就是对搜寻路径进行压缩。路径压缩的基本思想是在执行查找操作时，将路径上的每个节点都直接连接到根节点上，从而降低整个树的高度。 路径压缩可以显著减少树的高度，使得查找操作的时间复杂度接近于常数级别，提高了并查集的效率。 第三步：实现合并操作。 然后，我们实现并查集的 union 操作，用于合并两个集合。如果两个元素所指向的父元素是同一个，那么可以说明这两个元素存在于同一个集合当中，不需要进行合并操作。否则就将一个元素添加到另一个集合之中。 并查集的时间复杂度 并查集的时间复杂度取决于其两个主要操作：查找 和 合并。 查找操作（FIND） 在普通的并查集中，如果不进行路径压缩优化，find 操作的时间复杂度与树的高度成正比。最坏情况下，树的高度可以达到 O(n)O(n)O(n)，其中 nnn 是并查集中元素的数量。 但是，在应用了路径压缩优化的情况下，find 操作的均摊时间复杂度接近于常数级别。具体来说，经过路径压缩的并查集的 find 操作的时间复杂度可以表示为 O(α(n))O(\alpha(n))O(α(n))，其中 α(n)\alpha(n)α(n) 是阿克曼函数的反函数，增长极其缓慢。对于所有实际应用而言，可以将其约等于为常数时间。 合并操作（UNION） 合并操作涉及到查找两个元素所在集合的根节点，并将其中一个根节点连接到另一个根节点上。由于查找过程是常数级别的，而合并两棵树的根节点也是常熟级别的，因此合并操作的时间复杂度也近似于常数时间。 总体复杂度 综上所述，经过路径压缩和按秩合并优化后的并查集，在实际应用中具有非常高效的时间复杂度。对于包含 nnn 个元素的并查集，其 find 和 union 操作的均摊时间复杂度都接近于常数级别，即 O(α(n))O(\alpha(n))O(α(n))。因此，并查集在解决大规模数据集合动态连通性问题时表现非常出色。 相关引用 1. GeeksforGeeks. "Introduction to Disjoint Set Data Structure or Union-Find Algorithm." GeeksforGeeks, 12 May 2023, https://www.geeksforgeeks.org/introduction-to-disjoint-set-data-structure-or-union-find-algorithm/. 2. CP-Algorithms. "Disjoint Set Union." CP-Algorithms, https://cp-algorithms.com/data_structures/disjoint_set_union.html. 3. USA Computing Olympiad. "DSU." USA Computing Olympiad, https://usaco.guide/gold/dsu?lang=cpp. 4. Halim, Steven, et al. "Union-Find Disjoint Sets (UFDS) - VisuAlgo." VisuAlgo.net

博客园链接：https://www.cnblogs.com/Macw07 > 序言，这次排位赛绝对是最轻松的一次排位赛了（打了四次排位赛，终于上了白银组别）。肉眼可见 ACGO 的用户量在慢慢地增长（至少参赛人数变多了，是件好事）[狗头]。 > > PS：在提供 Cpp 标准代码的时候，本文也会同时提供 Python 版本的代码。但 Python 的执行效率不高，同样复杂度的代码 Python 的效率可能是 C++ 代码的十分之一。因此在使用 Python 代码做题的时候，需要时刻注意复杂度和常数，否则有可能出现超时的情况。 第一题 - A23466.捉迷藏 题目链接跳转：A23466.捉迷藏 第一题算是一个签到题，题目要求给定两个数字 A,BA, BA,B 输出在 [0,9][0, 9][0,9] 区间内不是 A×BA \times BA×B 的任意数字。此题非常简单，可以暴力破解，也可以使用玄学算法。 暴力算法很好想，尝试 [0,9][0, 9][0,9] 之间的所有数字即可，找到一个符合标准的结果就输出。 由于我们知道，000 乘上任何数字都为 000，因此对于所有的测试点，只要 A≠0A \neq 0A=0 且 B≠0B \neq 0B=0，那么输出 000 即可（毕竟无论如何答案也都不会是 000）。反之，输出任意一个非零的数字即可。玄学代码如下： 本题的 Python 代码如下（不得不说，用 Python 的代码量确实减少很多）： 两个代码的时间复杂度都是 O(1)O(1)O(1)，但是第二个算法的复杂度可以精确到 Θ(1)\Theta(1)Θ(1)。 第二题 - A23467.最长公共前缀 题目链接跳转：A23467.最长公共前缀 这道题也非常的简单。题目要求求出两个数字的最长公共前缀的长度。例如字符串 interview 和 interrupt 的最长公共前缀就是 inter，所以应该输出 555。 具体地，在遍历的时候判断两个字符串中同一个索引对应的两个字符是否相等，如果相等就将答案长度增加，否则就停止循环就可以了。PS：在遍历的过程中需要注意不要让索引超限。 本题的 AC 代码如下： 本题的 Python 代码如下： 本算法的时间复杂度约为 O(min⁡(lena,lenb))O(\min(\text{lena}, \text{lenb}))O(min(lena,lenb))。其中，lena 与 lenb 分别代表读入进来的两个字符串的长度。 第三题 - A23468.坏掉的数字键 题目链接跳转：A23468.坏掉的数字键 根据题意，我们需要统计在 NNN 个字符串中，有多少个字符串不包括字符 DDD。循环遍历一个一个匹配实在太麻烦了，直接使用 string 类自带的 .find() 函数即可。直接用 Cpp 的内置函数即可（内置函数大法真好用）。 a.find(b) 表示在 a 中寻找 b。如果找到了就返回 b 第一次在 a 中出现的位置，否则就返回 string::npos。 本题的 AC 代码如下： 本题的 Python 代码如下： 本题的每个测试点有多个测试用例，对于每一个测试用例，本算法时间复杂度约为 O(n×d)O(n \times d)O(n×d)，其中 d 表示读入进的字符串长度。更进一步地，a.find(b) 函数的时间复杂度为 O(lena×lenb)O(\text{lena} \times \text{lenb})O(lena×lenb)。其中，lena 与 lenb 分别代表两个字符串的长度。对于本道题而言，lenb 的值永远为 111。 第四题 - A23469.奇怪的次方 题目链接跳转：A23469.奇怪的次方 根据题目要求，我们需要找到一个整数 XXX，满足 XN=YX^N = YXN=Y。根据数学的基本运算法则，我们对等式两遍同时开 NNN 次根即可得到 X=YNX = \sqrt[N]{Y}X=NY 。最后判断再校验一边答案即可。需要注意的是，本题涉及关于小数的运算，因此在实现过程中需要使用 double 数据类型，同时也要关注计算机在处理浮点数存在的误差（使用 round 函数可以将一个数字四舍五入）。 本题的 AC 代码如下： 本题的 Python 代码如下： 本算法的时间复杂度约为 O(1)O(1)O(1) 级别。对于 pow 函数的时间复杂度无法被精确地推算，因为在 C++ 底层中该函数会使用多种不同的算法来实现相同的功能，但一般情况是 log2(n)log_2(n)log2 (n) 级别的。 第五题 - A23470.隐藏元素 题目链接跳转：A23470.隐藏元素 先讲一个运算法则 ，如果 Ai⊕Aj=kA_i \oplus A_j = kAi ⊕Aj =k，那么 Ai⊕k=AjA_i \oplus k = A_jAi ⊕k=Aj 。因此，当我们知道了 A1=1A_1 = 1A1 =1 的时候，我们就可以推出所有有关 A1A_1A1 的线索的另一个数字 AjA_jAj 的值。一旦确定了一个数字，就可以确定所有与之有关联的数字（线索）。 为了方便起见，我们可以建立一个无向图，这样子就可以通过类似拓扑排序的方式按照顺序一个一个地推断出剩余的未知数。如果有一条线索 Ai Aj KA_i\ A_j\ KAi  Aj  K，那么我们就在 AiA_iAi 和 AjA_jAj 直接连接一条无向边，权值为 kkk，最后对这个图从 111 点开始进行拓扑排序就可以了。 需要注意的是，一个点如果已经被访问过的话，就不需要再被访问了，用 vis 数组记录一下就可以了。本题的 AC 代码如下： 本题的 Python 代码如下： 以上算法基于 广度优先搜索/拓扑排序 实现，该算法的时间复杂度约为 O(M)O(M)O(M)。 第六题 - A23471.圣诞礼物 题目链接跳转：A23471.圣诞礼物 一道很明显的完全背包问题，但需要加以优化。如果不优化的话，按照本题的数据量，在极端情况下程序会运行 105×105=101010^5 \times 10^5 = 10^{10}105×105=1010 次，大概需要 222 分钟时间（其实也不是很久）。因此我们需要在原本的完全背包的基础上加以优化： 通过观察可以发现，虽然物品的数量有 10510^5105 种，但是每种物品的花销却极其的少。就算有一个幸运数字为 888888888888888888888888888，那么也只需要 636363 个圣诞糖果就可以。假设有多个幸运数字都需要 101010 个糖果，那按照贪心的思路：如果我们要选支出则 636363 个圣诞糖果的话，我们可以获得的最大收益就是所有需要 101010 个糖果的幸运数字所对应的可以获得的金币数量的最大值。我们可以通过一个数组来记录对于每一种支付的糖果组合，可以获得的最大金币数量。 这样子我们就将原本的物品数量成功压缩成了 636363 种物品，即可通过本题的所有测试点。本题的 AC 代码如下： 本题的 Python 代码如下： 本题的每个测试点有多个测试用例，对于每一个测试用例，本算法时间的多项式时间复杂度约为 O(63M)O(63M)O(63M)，经过化简后的复杂度约为 O(M)O(M)O(M)。其中，数字 636363 代表最多存在 636363 中不同的“物品”。