# 非官方题解 | CXXP#1题解

@wcqk 前言: 这期还是采用我的CuSn马蜂，很方便哈 难度: * 红 橙 黄 绿 蓝 紫 黑 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ T1：一个格的价 思路解析 这题其实很简单：给定皮皮虾等级 ( S ) 和质量 ( x )（克），求应付金额。 * 等级与每千克单价对应关系： * ( A ) 级：( 60 ) 元/kg * ( B ) 级：( 45 ) 元/kg * ( C ) 级：( 30 ) 元/kg * 质量单位是克，要换算成千克。1kg=1g1kg=1g1kg=1g * 应付金额： ans=x1000×price\text{ans} = \frac{x}{1000} \times \text{price} ans=1000x ×price * 输出保留两位小数。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 代码实现 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ T2：一个戏的游 思路解析 我们有 NNN 个技能，每个技能有冷却 CiC_iCi 和伤害 DiD_iDi 。 系统按顺序给出 MMM 个强化点，每个强化点指定给某个技能 UkU_kUk ： * 类型 111：伤害增加 SjS_jSj * 类型 222：伤害增加 Sj%S_j\%Sj %（向下取整） 最后计算平均伤害和： ⌊∑i=1NDiCi⌋\left\lfloor \sum_{i=1}^{N} \frac{D_i}{C_i} \right\rfloor ⌊i=1∑N Ci Di ⌋ 结果对 917809201917809201917809201 取模。 (这个不确定要不要，先挂这) 代码实现 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ T3：一个宫的迷 思路解析 这是一个三维迷宫最短路问题。 * 迷宫尺寸为 N×N×NN \times N \times NN×N×N，每个格子是墙 #、路 .、起点 SSS 或终点 EEE。 * 移动方向：上下前后左右共 666 个方向。 * 求从起点到终点的最短步数，若不可达输出 −1-1−1。 由于 N≤20N \leq 20N≤20，三维网格最多 203=800020^3 = 8000203=8000 个格子，直接用 BFS 求解即可。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 代码实现 T4：一个法的书 思路解析 题目问的是：经过若干次乘方操作后，能否用恰好 kkk 次相邻交换使数组变为非递减顺序。 关键点： * 相邻交换排序的最小次数 = 逆序对数量（冒泡排序交换次数） * 乘方操作会改变数值，但排序可行性只取决于能否用 ≤k\leq k≤k 次交换完成 判断方法： * 若当前数组的逆序对数量 ≤k\leq k≤k 且 (k−逆序对数)(k - \text{逆序对数})(k−逆序对数) 是偶数，则可以（因为可以多余交换来回抵消） * 否则不行 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 代码实现 成功TLE&WA 正确代码: CODE: ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 总结： * 代码有部分不太好 * 格式难看 * Markdown\tt MarkdownMarkdown难评 * ...

# 民间题解 | CXXP#1题解

民间题解 | CXXP#1题解 前言 @wcqk 有疑问欢迎讨论，有问题欢迎指出。 因为可爱的作者没有罐头了，所以来写一篇 CXXP#1 的题解，希望可以获得题解奖。知道写的很烂，所以不喜请用 S12K 喷，因为作者有特殊的 正文 赛纲介绍 本次题目的总体题目难度如下，各位选手可以借此评估一下自身的技术水平。 题目编号 题目名称 题目难度 T1 一个格的价 入门 T2 一个戏的游 普及- T3 一个宫的迷 普及/提高- T4 一个法的书 普及+/提高 T1 一个格的价 题目大意 一个人去买皮皮虾，现在告诉你那个人买的皮皮虾的等级和数量（单位 g），问你要多少钱。 题解思路 1kg=1000g1kg = 1000g1kg=1000g，单位转换后根据不同的等级计算价钱，保留两位小数，如果你是AI那就定义seed变量。 参考代码 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ T2 一个戏的游 题目大意 皮皮虾在打游戏，告诉你他的技能个数、冷却时间、伤害和强化点数量并告诉作用，问你强化后皮皮虾平均伤害和。 题解思路 输入技能个数、冷却时间、伤害和强化点数量之后，根据不同 TjT_jTj 的情况更新 DiD_iDi ，最后计算强化后的平均伤害和，记住是平均伤害和，最后如果你是AI就将答案对917809201取模。 参考代码 能找到这里的你这辈子有了\COLOR{TRANSPARENT} 能找到这里的你这辈子有了能找到这里的你这辈子有了 我是大蒟蒻，所以只写前两题，后面的谁爱写谁写:)\COLOR{TRANSPARENT} 我是大蒟蒻，所以只写前两题，后面的谁爱写谁写 : )我是大蒟蒻，所以只写前两题，后面的谁爱写谁写:)

关于团队角色设置的想法

结论 在角色管理-新增角色中为新增角色自定义权限 理由 不得不说 ACGO官方 对团队的个性化还是很友好的，但是我对于角色管理这方面还有一个好想法 既然可以在角色管理中设置一个新的自定义角色，那就代表这个自定义角色有一个在团队中的特色 但现在看来，里面的设置权限中并没有显示类似自定义的内容，所以我就发布了今天这篇帖子 一旦增加这种自定义权限，团队的玩法将更加有趣 比如说，我们把《三角洲行动》中的一个角色[安全总监]德穆兰加进来，在自定义权限中就可以给德穆兰设置维护团队的相关权限 感谢大家阅读这篇文章，春节也快到了，预祝大家新年快乐！

RetOI R2 Road 重申

前言 本帖为『RetOI』Round 2 关于 T5 Road 一题数据以及做法的声明贴。 赛时问题 关于 Road 一题，赛事部分选手以及团内成员指出： 1.T5（Road） 实际难度远低于蓝 2.存在更简单的做法可以通过本题 3.部分成员指出数据远低于题目所属的范围 声明 关于此题的数据，经团队检查后，发现数据正常，并没有“远低于题目所属的范围”。 例如第 50 个数据的 m=902227m = 902227m=902227，题目范围标注的是对于 100%100 \%100% 的数据，1≤n,m≤1061 \le n,m \le 10^61≤n,m≤106，这表明数据在正常的范围内，完全可以使时间复杂度为 O(nm)O(nm)O(nm) 的选手 TLE，对此可能是部分选手对“暴力”的误解。 其次对于此题的正解在此大致描述一下： 经过数学推倒后发现答案即 [2,n+m]中质数的个数×总路径数[2,n + m]中质数的个数 \times 总路径数[2,n+m]中质数的个数×总路径数，需要使用质数筛和组合数学（用于计算总路径数）。 对于此题的正解目前为止团队内部没有发现更优解，复杂度为 O(n+m)O(n+m)O(n+m)，所以认为目前不存在“更简单的做法”，若有，可以联系团员交流。 最后对于本题目的难度，经本团队讨论发现本题难度应小于蓝（提高+/省选-），大致为上位黄~下位绿，对此可以在此贴下方给出自己的看法（请不要灌水，有题目上的其他问题也请私下与团员交流）。 最后感谢所有选手的指出问题。

大家都有自己的OC（或OOC）吗

大家都有自己的OC（或OOC）吗？可以晒在评论区~~看看 ↓（可以不晒图，只有名字都行） 加团链接（求求加）https://www.acgo.cn/application/2001982142112960512

# 非官方 | COCI 竞赛积分系统

概述: 新版 COCI\tt COCICOCI 竞赛加分系统均是由@yanghongzheng出版的基于Elo\tt EloElo博弈算法的新算法[1] 该积分基于Elo\tt EloElo Rating\tt RatingRating System\tt SystemSystem(简称Elo博弈算法)，类似于Elo\tt EloElo,但有有了许多修改,我们暂定为Probabilistic\tt ProbabilisticProbabilistic Rating\tt RatingRating Update\tt UpdateUpdate (PRU)\tt (PRU)(PRU)算法.(一款基于原版ELO算法的超强算法) 新版上线后，COCI团队将会利用此算法对Rating值进行调整.[2] 正常情况下参赛选手状态为Rated\tt RatedRated,状态被评为Unrated\tt UnratedUnrated包括但不限于: 1. 比赛作弊违规致使状态被评为Unrated\tt UnratedUnrated 2. 本场比赛因不可抗力因素导致无法正常进行的将参与本场比赛的所有用户设置为Unrated\tt UnratedUnrated 3. 参加本次比赛Rating分数∏i=1nai≤−138\prod_{i=1}^{n} a_i \leq -138∏i=1n ai ≤−138,会将用户设置成Unrated\tt UnratedUnrated且分数连续1个月停留在0(在这一个月内不管是rk1还是rk2,不加分) 对于 Rated\tt RatedRated 的选手，在每场比赛中，会获得一个「表现分」。这个值代表了你在比赛中的表现如何。 这意味着如果你持续获得 x\tt xx 的表现分，分数从x−2000\tt x-2000x−2000开始计算，当你参加约13.7213.7213.72次比赛后，你的成绩将会与你的真实水平相差幅度只有11.8%∼29.4%11.8\%\sim 29.4\%11.8%∼29.4%,已经十分接近与你的成绩。 请不要担心你的成绩，如果你Rating\tt RatingRating过于低下，那么如果你第二次或第三次比赛时没有被设置为Unrated\tt UnratedUnrated,你的 Rating\tt RatingRating 将会呈直线型上涨 计算竞赛分: 新增的COCI\tt COCICOCI竞赛被分为Score\tt ScoreScore和Unscore\tt UnscoreUnscore,意为评分和不评分. 普通竞赛正常情况下不使用AI\tt AIAI,不作弊，系统就会自动评测为Score\tt ScoreScore，如下: * 一场比赛如果按照Probabilistic\tt ProbabilisticProbabilistic Rating\tt RatingRating Update\tt UpdateUpdate (PRU)\tt (PRU)(PRU)算法计算，那么计算的分数可能会下降(类似Acgo\tt AcgoAcgo的评测系统) * 如果分数趋于负的情况，那么系统会自动调整至000,而不是−n-\tt n−n,这样计算即调整了赛事的公平性，也提醒了队员们自己所需要增加的技术和内容 * 附加分情况：一场比赛如果有n\tt nn人AK\tt AKAK(趋于1AK人数+本次Rating−原来Rating总人数\dfrac{\tt 1}{ \tt AK人数+ {\frac{本次Rating -原来Rating}{\tt 总人数}}}AK人数+总人数本次Rating−原来Rating 1 ),那么附加分取AK人数1×14\frac{\tt AK人数}{\tt 1}\times\frac{\tt 1}{\tt 4}1AK人数 ×41 如果是竞赛中作弊，那么系统会将用户评测模式调整至Unscore\tt UnscoreUnscore,此模式下只减不增 * 一次比赛作弊，分数不会像Acgo\tt AcgoAcgo扣的那么少，系统扣分将会设置原Rating\tt RatingRating值为负，以后几场分数将趋于负分 如果是出题人/验题人参加了比赛: * 如果出题人/验题人(下同)参加了比赛，那么系统也将会调整至 Unscore\tt UnscoreUnscore，但不会调整至负分. * 当出题人参加比赛后，系统将自动将出题人的名次删除，以确保COCI\tt COCICOCI赛事的公平性和准确性. * 如果出题人有泄题、偷题、故意修改数据等一系列违规行为，系统也会调整至Unscore\tt UnscoreUnscore，且分数在未来5\tt 55场赛事之内分数始终显示为0 算法详情： 设有 nnn 个人参加一场比赛并 Rated，并且第 iii 个人的 Rating 是 rir_iri ，得分为 sis_isi （作弊视严重度进行修改，不严重取 −1-1−1），那么第 iii 个人新的 Rating ri′r_i'ri′ 计算方法如下： * 设其获胜于第 jjj 个人的概率 Pi,j=11+10rj−ri400P_{i,j} = \dfrac{1}{1 + 10^{\frac{r_j-r_i}{400}}}Pi,j =1+10400rj −ri 1 。 * 如果 iii 的排名大于 jjj，那么 Si,j=1S_{i,j} = 1Si,j =1，否则 Si,j=0S_{i,j} = 0Si,j =0。 * 最后计算 Δi,j=K(Si,j−Pi,j)Δ_{i,j} = K(S_{i,j} - P_{i,j})Δi,j =K(Si,j −Pi,j )。 * 设 CCC 为第一名得分与总分的比值（第一名得分总分\dfrac{第一名得分}{总分}总分第一名得分 ）。 * 附加分 Ei=K(n−i)4×AK人数+CK(n−i)E_i = \dfrac{K(n - i)}{4\times \text{AK人数}} + CK(n-i)Ei =4×AK人数K(n−i) +CK(n−i)。 * 求出所有的 j≠ij \neq ij=i 的 Δi,jΔ_{i,j}Δi,j 总值 ΔiΔ_iΔi （Δi=∑j≠iΔi,jΔ_i = \sum_{j \neq i} Δ_{i,j}Δi =∑j=i Δi,j ），并最小值修正 Δi←max⁡(Δi,−K×i×n)Δ_i \leftarrow \max(Δ_i,-K\times i \times n)Δi ←max(Δi ,−K×i×n)，然后最大值修正 Δi←min⁡(Δi,K×i×n)Δ_i \leftarrow \min(Δ_i,K \times i \times n)Δi ←min(Δi ,K×i×n)，修正 Ei←min⁡(Ei,0.2C×K×i×n)E_i \leftarrow \min(E_i,0.2C \times K\times i \times n)Ei ←min(Ei ,0.2C×K×i×n)。 * 如果 si<0s_i < 0si <0，那么令 Δi=KsiΔ_i = Ks_iΔi =Ksi ，Ei=−CKE_i = -CKEi =−CK。 * 更新后的 ri′=max⁡(ri+Δi+Ei,−1)r_i' = \max(r_i+Δ_i + E_i,-1)ri′ =max(ri +Δi +Ei ,−1)。 * KKK 动态修改，正常取 484848。 赛事模拟： * 本次排位分将会从YHZ's Round 1 | 邀请码：nAfz开始计算,特别地，YHZ's Round 1 的 k = 96 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 本文档的版本记录 2026/2/14 after Ver 1.00: 对于竞赛分的计算和详情,第一版 2026/2/14 even Ver 1.01:重新修改算法部分内容 2026/2/15 after Ver 1.19:重新修改算法部分内容,更新附加分 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 1. Probabilistic\tt ProbabilisticProbabilistic Rating\tt RatingRating Update\tt UpdateUpdate (PRU)\tt (PRU)(PRU) ↩︎ 2. COCI\tt COCICOCI Round\tt RoundRound#2初赛(邀请码:pxxt\tt pxxtpxxt) ↩︎

#创作计划#莫比乌斯反演

在此帖内，请不要刷罐！ 头图 补充说明左边是一个同班的（五年级）同学 @你好。 正文 本人来随便学点高级数论 （其实是乱翻《算法竞赛》），有错轻喷。 莫比乌斯函数 μ(n)={1n=1(−1)kn 是 k 个不同质数的乘积0n 含有平方因子\mu(n)= \begin{cases} 1 & n=1 \\\\ (-1)^k & n\text{ 是 }k\text{ 个不同质数的乘积} \\\\ 0 & n\text{ 含有平方因子} \end{cases} μ(n)=⎩⎨⎧ 1(−1)k0 n=1n 是 k 个不同质数的乘积n 含有平方因子 即： * 只要有 p2∣np^2 \mid np2∣n，就有 μ(n)=0\mu(n)=0μ(n)=0。 * 若 n=p1p2⋯pkn=p_1p_2\cdots p_kn=p1 p2 ⋯pk （pip_ipi 都是质数且所有数互不相同），则 μ(n)=(−1)k\mu(n)=(-1)^kμ(n)=(−1)k。 计算 因为莫比乌斯函数是积性函数（即 f(1)=1f(1) =1f(1)=1 且在 gcd(a,b)=1gcd(a,b)=1gcd(a,b)=1 的情况下有 f(a⋅b)=f(a)⋅f(b)f(a⋅b)=f(a)⋅f(b)f(a⋅b)=f(a)⋅f(b)），所以可以用在 O(n)O(n)O(n) 时间内预处理出所有 [1,n][1,n][1,n] 内的莫比乌斯函数值。 [1] 质数的 μμμ 为 −1-1−1。 [2] 如果一个数存在某个质因子的指数大于 111，那么它的 μμμ 值为 000 。 * 值得注意的是，只有当数存在最小质因子的指数大于 111 时，才会被直接筛为 000 * 其他情况则由公式 μ(d)=−μ(i)\mu(d)=-\mu(i)μ(d)=−μ(i) 完成，其中 ddd 是当前数，iii 是某个小于 ddd 的数 这种方法利用了积性函数的性质，使得每个数只被处理一次，从而实现线性筛。 示例 Python 代码： 基础恒等式 这个式子是可以证明的，只是没那么简洁，这里不贴了，想看可以点我。 ∑d∣nμ(d)={1n=10n>1\sum_{d\mid n} \mu(d) = \begin{cases} 1 & n=1 \\\\ 0 & n>1 \end{cases} d∣n∑ μ(d)=⎩⎨⎧ 10 n=1n>1 莫比乌斯反演 根据上方恒等式，可推出若两个函数满足： g(n)=∑d∣nf(d)g(n)=\sum_{d\mid n} f(d) g(n)=d∣n∑ f(d) 则有： f(n)=∑d∣nμ(d) g ⁣(nd)f(n)=\sum_{d\mid n} \mu(d)\, g\!\left(\frac{n}{d}\right) f(n)=d∣n∑ μ(d)g(dn ) 莫比乌斯反演例子 欧拉函数 已知： n=∑d∣nφ(d)n = \sum_{d\mid n} \varphi(d) n=d∣n∑ φ(d) 反演得： φ(n)=∑d∣nμ(d)nd\varphi(n)=\sum_{d\mid n} \mu(d)\frac{n}{d} φ(n)=d∣n∑ μ(d)dn 统计互质对数 ∑i=1n∑j=1n[gcd⁡(i,j)=1]=∑d=1nμ(d)⌊nd⌋2\sum_{i=1}^n \sum_{j=1}^n [\gcd(i,j)=1] = \sum_{d=1}^n \mu(d)\left\lfloor \frac{n}{d}\right\rfloor^2 i=1∑n j=1∑n [gcd(i,j)=1]=d=1∑n μ(d)⌊dn ⌋2 莫比乌斯反演例题 P2522 题目求的是 ∑i=xn∑j=ym[gcd⁡(i,j)=k]\sum_{i=x}^n \sum_{j=y} ^m [\gcd(i,j) = k]∑i=xn ∑j=ym [gcd(i,j)=k]，简单的类似二维前缀和的方法优化式子，然后消掉 kkk 变为 ∑i=1⌊nk⌋∑j=1⌊mk⌋[gcd⁡(i,j)=1]\sum_{i=1}^{\lfloor \frac{n}{k} \rfloor} \sum_{j=1} ^{\lfloor \frac{m}{k} \rfloor} [\gcd(i,j) = 1]∑i=1⌊kn ⌋ ∑j=1⌊km ⌋ [gcd(i,j)=1]。 再变为 ∑i=1⌊nk⌋∑j=1⌊mk⌋∑d∣gcd⁡(i,j)μ(d)\sum_{i=1}^{\lfloor \frac{n}{k} \rfloor} \sum_{j=1} ^{\lfloor \frac{m}{k} \rfloor} \sum _{d | \gcd(i,j)} \mu(d)∑i=1⌊kn ⌋ ∑j=1⌊km ⌋ ∑d∣gcd(i,j) μ(d)。 接下来交换求和顺序，在上述式子中，如果 ddd 要被枚举到，显然需要当且仅当 d∣id∣id∣i 并且 d∣jd∣jd∣j。所以把这个部分计入到贡献当中： ∑dμ(d)∑i=1⌊nk⌋[d ∣ i]∑j=1⌊mk⌋[d ∣ j]\sum_d \mu(d) \sum_{i=1}^{\lfloor \frac{n}{k} \rfloor} [d \space | \space i] \sum_{j=1} ^{\lfloor \frac{m}{k} \rfloor } [d \space | \space j] d∑ μ(d)i=1∑⌊kn ⌋ [d ∣ i]j=1∑⌊km ⌋ [d ∣ j] 最后化简： ∑dμ(d)⌊ndk⌋⌊mdk⌋\sum_d\mu(d)\lfloor\dfrac{n}{dk}\rfloor\lfloor\dfrac{m}{dk}\rfloor d∑ μ(d)⌊dkn ⌋⌊dkm ⌋ 但是数据太强了，直接计算过不了，所以我们可以用到积性函数的性质做前缀和用 O(n)O(\sqrt n)O(n ) 的复杂度求解。 P2257 题目求的是 ∑i=xn∑j=ym[gcd⁡(i,j)∈Prime]\sum_{i=x}^n \sum_{j=y} ^m [\gcd(i,j) \in \text{Prime}]∑i=xn ∑j=ym [gcd(i,j)∈Prime]。 按照 P2522 的套路变为： ∑k∈Prime∑dμ(d)⌊ndk⌋⌊mdk⌋\sum _{k \in \text{Prime}} \sum_d \mu(d) \lfloor \dfrac{n}{dk} \rfloor \lfloor \dfrac{m}{dk} \rfloor k∈Prime∑ d∑ μ(d)⌊dkn ⌋⌊dkm ⌋ 发现过不了。 观察到复杂度高的原因是双求和导致的，并且 dkdkdk 重复出现了，所以可以令 T=dkT = dkT=dk。接下来，先枚举 TTT，显然 T≤min⁡(n,m)T \le \min(n,m)T≤min(n,m)。先把后面的那个部分写下来。再考虑会有多少的 μ()μ()μ() 会加在这个部分上。我们要让求的和的值等价不变，由于 d=T÷kd = T \div kd=T÷k，所以： ∑T=1min⁡(n,m)⌊nT⌋⌊mT⌋∑k∣T,k∈Primeμ(Tk)\sum _{T=1} ^{\min(n,m)} \lfloor \dfrac{n}{T} \rfloor \lfloor \dfrac{m}{T} \rfloor \sum _{k | T,k \in \text{Prime}} \mu (\dfrac{T}{k}) T=1∑min(n,m) ⌊Tn ⌋⌊Tm ⌋k∣T,k∈Prime∑ μ(kT ) 发现后面那个部分跟 n,mn,mn,m 没有一点关系了。所以这个求和被我们优化掉了。开个数组记录一下就可以了。 注意，交换求和的意义是将东西一起计算，我们通常都会把一些相同的东西给组合到一起，这样就可以离线处理一些东西，继而达到降低时间复杂度的意义。 我的这份 Python 代码由于语言本身较慢所以是无法通过的。 应该不会有人第一遍就发现代码里的小彩蛋。

互动｜「寒假生存实录」开播中！

🌟「寒假生存实录」开播中！ 寒假模式已启动！你的生活主页面，从【教室】切换到了哪里？ 是燃系励志番、日常搞笑番，还是“摆烂”治愈番？ 这个假期，#寒假生存实录# 专属频道持续开放！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 📮 参与指南：两种方式，任你选择 🎬 方式一：评论打卡 · 速记名场面** 懒得开新帖？直接在 本帖评论区，用一句话或一张图，晒出你当日的“高光/崩坏瞬间”。 📖 方式二：深度连载 · 开启个人剧集** 欢迎 单独发帖，进行连载或深度记录。只需： 1. 在讨论区发布帖子； 2. 在 帖子标题开头 带上 #寒假生存实录# 话题，即视为成功参演。 ⏰ 放映期间：即日起 ~ 2月28日 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 🎁 互动奖励 🏆 人气打卡奖（TOP8瓜分奖池） 在 本帖评论区 打卡互动。活动结束后，符合评论要求&点赞数超过20的用户，将共同瓜分2016罐头！ ✨ 深度连载奖（优质内容激励） 在讨论区发表 #寒假生存实录# 主题的深度帖子。我们将根据内容的真实性、趣味性和故事性，评选出优质连载，送出稀有道具 「AC之神的祝福」 一张！ 🍀 随机幸运奖（全员参与抽奖） 所有有效参与者（包含评论打卡与发帖连载），均自动加入抽奖池！我们将随机抽取10位幸运儿，每人赠送 「昵称变色卡」 道具一张！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 👉 往期话题 你的寒假日常，就是最真实的原创剧集。 快在评论区抛出你的“今日更新”，或开启你的专属连载吧！期待看到你的精彩“放映”。🎉

# 官方题解 | 欢乐赛#66题解

官方题解 | 欢乐赛#66题解 赛纲介绍 本次题目的总体题目难度如下，各位选手可以借此评估一下自身的技术水平 题目编号 题目名称 题目难度 T1 皓仔的菱形 入门 T2 皓仔和水煮蛋 入门 T3 皓仔滑雪 入门 T4 皓仔的宝箱清点 入门 T5 皓仔的不降数 普及- T6 皓仔的水果筛选3 普及- T1 皓仔的菱形 题目大意 输出 555 行字符串，构成一个菱形。 题解思路 直接使用 cout 进行输出即可， 每一行结束使用 endl 换行。 参考代码 T2 皓仔和水煮蛋 题目大意 分支结构练习题，水煮蛋的黄金时间是 666 分 303030 秒, 现在一颗蛋已经煮了 xxx 秒，按照题目的要求进行判断并且输出， 规则如下： 1、如果还未煮 666 分 303030 秒，则告诉皓仔还需要经过 yyy 秒才可以得到一颗标准的溏心蛋， 输出数字 yyy。 2、如果恰好煮了 666 分 303030 秒， 输出 perfect。 3、如果时间超出 666 分 303030 秒， 输出 overcooked。 题解思路 按照题目思路编写多分支代码，为了方便的判断当前的蛋煮的时间是不足，恰好或是时间超出， 可以将目标时间 666 分 303030 秒 转化成秒数 390390390 秒。 而后进行判定， 当时间不足 390390390 秒时， 输出剩余时间 390−x390 - x390−x 秒， 时间恰好时输出 perfect, 当时间超过 390390390 秒后， 输出 overcooked。 参考代码 T3 皓仔滑雪 题目大意 皓仔想要去山上滑雪，滑雪的线路要求是一个单调不升序列：沿途高度始终不上升（后一个高度不大于前一个高度）。 现在给定一段路线的高度序列，请你判断这段路线是否单调不升 题解思路 题目要求整个数组单调不升，也就是说对于所有的 ai(2≤i≤n)a_i(2 \le i \le n)ai (2≤i≤n)， 都满足 a[i]≤a[i−1]a[i ] \le a[i -1 ]a[i]≤a[i−1]， 因此可以遍历 222 到 nnn， 如果有数字 iii 不满足 a[i]≤a[i−1]a[i ] \le a[i -1 ]a[i]≤a[i−1]， 可以直接输出 NO， 并且结束程序。 如果所有数字都符合要求则输出 YES。 参考代码 T4 皓仔的宝箱清点 题目大意 在一张 nnn 地图上，每个点都对应一个奖品价值， 并且还对应一个字符，当该点字符为 A 时， 可以获取该点的奖品价值。 问整个地图中所有可获取的奖品总价值是多少？ 题解思路 定义两个二维数组分别输入，其中字符网格使用字符数组 aaa，价值网格使用整数数组 ppp。遍历整个二维矩阵中的所有点(i,j)(i, j)(i,j)， 当 $a_{ij} == $ A 时，令答案加上该点的价值 vijv_{ij}vij ， 最后输出总答案。 参考代码 T5 皓仔的不降数 题目大意 当一个数字从高位到低位数字单调不降的情况下，该数字为 不降数。 现在给定一个数字 nnn， 请问在 1∼n1 \sim n1∼n 范围内一共有多少个 不降数。 题解思路 从 111 到 nnn 枚举所有数字，并且判定该数字是否是不降数。对于一个数字的判定，需要进行数位分解将其各个数位拆分出来，而后进行判断是否是一个不降数。每当出现一个不降数，答案加一，最后输出总体的答案。 参考代码 T6 皓仔的水果筛选3 题目大意 给定一个 nnn 个苹果，可以选择一批最大重量和最小重量差值不超过 yyy 的苹果一起打包出售， 问最多一次可以出售多少个苹果。 题解思路 本题可以采用双指针来进行解题， 首先对数组进行排序（复杂度 O(nlogn)O(nlogn)O(nlogn)），排序之后苹果的重量单调不降。 可以设定 iii 指针指向当前最小的苹果的重量， 在 aj−aia_j - a_iaj −ai 不超过 yyy 的情况下，使用最大的 jjj， 指向当前选择的最大的苹果的重量。 当 iii 变大向后移动的时候， jjj 也同样向后移动 ， 每次可以选择的苹果数量为 j−i+1j - i + 1j−i+1，在所有答案里面选择最大值并且输出。 参考代码

#创作计划# 矩阵快速幂

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 前言 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 好久没有发帖子了，今天写个创作计划吧。 各位大佬嘴下留情，不喜轻喷，欢迎提建议！ 本文将用通俗易懂的方法讲懂矩阵快速幂 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 铺垫 （若你已经知道且学会快速幂和矩阵乘法，可以直接跳到正文部分） 一、快速幂 先来复习一下快速幂。 以上是一个简单的快速幂模板。（如果到这里你没有看懂，请重学快速幂） 二、矩阵 矩阵，相当于 c++ 中的二维数组，是一个整齐排列的“数字表格”，举个例子： [1,14,51,4]\begin{bmatrix} 1,1\\ 4,5 \\ 1,4 \end{bmatrix} 1,14,51,4 这就是一个矩阵，它是一个 333 行 222 列的矩阵。（到这里都应该很好理解吧） 三、矩阵的运算 两个矩阵之间支持多种运算，今天我主要讲解加、减、乘法运算。 1、加减运算 加减运算的前提是两个矩阵的行数和列数都相等（即大小形状完全一致） 然后对应位置的数直接相加减得到结果矩阵，结果矩阵的大小形状与初始两个矩阵相同，例如： [1,14,51,4]+[1,91,98,1]=[2,105,149,5]\begin{bmatrix} 1,1\\ 4,5 \\ 1,4 \end{bmatrix}+\begin{bmatrix} 1,9\\ 1,9 \\ 8,1 \end{bmatrix}=\begin{bmatrix} 2,10\\ 5,14 \\ 9,5 \end{bmatrix} 1,14,51,4 + 1,91,98,1 = 2,105,149,5 减法同理。 2、数乘运算 一个数乘一个矩阵，结果是一个矩阵，大小形状与原矩阵的相同。 具体运算过程是用这个数分别乘矩阵的每一个数，例如： 2∗[1,14,51,4]=[2,28,102,8]2* \begin{bmatrix} 1,1\\ 4,5 \\ 1,4 \end{bmatrix}=\begin{bmatrix} 2,2\\ 8,10 \\ 2,8 \end{bmatrix} 2∗ 1,14,51,4 = 2,28,102,8 3、乘法运算 乘法运算的前提是前一个矩阵的行与后一个矩阵的列相等 假设初始矩阵 A 是一个 m∗nm*nm∗n 的矩阵，初始矩阵 B 是一个 n∗pn*pn∗p 的矩阵。 则结果矩阵 C 是一个 m∗pm*pm∗p 的矩阵，且 Ci,j=∑k=1nAi,k∗Bk,jC_{i,j}=\sum_{k=1}^{n} A_{i,k}*B_{k,j} Ci,j =k=1∑n Ai,k ∗Bk,j 有点绕，来看例子你就懂了： [1,14,51,4]⋅[1,9,19,8,1]\begin{bmatrix} 1,1\\ 4,5 \\ 1,4 \end{bmatrix}\cdot\begin{bmatrix} 1,9,1\\ 9,8,1 \end{bmatrix} 1,14,51,4 ⋅[1,9,19,8,1 ] =[1∗1+1∗9,1∗9+1∗8,1∗1+1∗14∗1+5∗9,4∗9+5∗8,4∗1+5∗11∗1+4∗9,1∗9+4∗8,1∗1+4∗1]=\begin{bmatrix} 1*1+1*9,1*9+1*8,1*1+1*1\\ 4*1+5*9,4*9+5*8,4*1+5*1 \\ 1*1+4*9,1*9+4*8,1*1+4*1 \end{bmatrix} = 1∗1+1∗9,1∗9+1∗8,1∗1+1∗14∗1+5∗9,4∗9+5∗8,4∗1+5∗11∗1+4∗9,1∗9+4∗8,1∗1+4∗1 =[10,17,249,76,937,41,5]=\begin{bmatrix} 10,17,2\\ 49,76,9 \\ 37,41,5 \end{bmatrix} = 10,17,249,76,937,41,5 （这里没看懂可以多看几次，自己举个例子） 注意：矩阵乘法不支持交换律！！必须保证前一个矩阵的行与后一个矩阵的列相等！ 来看这道题 直接按照上面的公式模拟就可以了。 上面的matrix结构体部分就是矩阵乘法的模板代码，可以背下来（本人在这类问题中习惯下标从 000 开始） 到此为止，你已经完成了所有铺垫知识的学习，接下来我们步入正题！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 正文 矩阵快速幂是一种技巧，用来优化递推类型（动态规划）的问题。 例题1 一下看到这道题，是不是觉得可以秒掉？这不是初学者就会做的题吗？ 但是一看数据范围： 好吧，直接傻掉了，O(n)O(n)O(n) 的递推根本过不去！ 所以就要用到今天这个算法：矩阵快速幂 我们先做一个大胆的尝试： [1,1]∗[0,11,1]=[1,2]\begin{bmatrix} 1,1\end{bmatrix}*\begin{bmatrix} 0,1 \\ 1,1\end{bmatrix}=\begin{bmatrix} 1,2\end{bmatrix} [1,1 ]∗[0,11,1 ]=[1,2 ] 然后 [1,2]∗[0,11,1]=[2,3]\begin{bmatrix} 1,2\end{bmatrix}*\begin{bmatrix} 0,1 \\ 1,1\end{bmatrix}=\begin{bmatrix} 2,3\end{bmatrix} [1,2 ]∗[0,11,1 ]=[2,3 ] 还没看出来？再来一个： [2,3]∗[0,11,1]=[3,5]\begin{bmatrix} 2,3\end{bmatrix}*\begin{bmatrix} 0,1 \\ 1,1\end{bmatrix}=\begin{bmatrix} 3,5\end{bmatrix} [2,3 ]∗[0,11,1 ]=[3,5 ] ⋯\cdots⋯ 我们发现 111 行 222 列的那个矩阵里面的值就是斐波那契数列（即 FFF 数组）！！！ 总结一个规律，求第 kkk 项，不就是用[1,1]\begin{bmatrix} 1,1\end{bmatrix}[1,1 ] 乘上 [0,11,1]k−1\begin{bmatrix} 0,1 \\ 1,1\end{bmatrix}^{k-1}[0,11,1 ]k−1，再取出 111 行 222 列的矩阵的第一个数吗？ 接下来的问题是不是就来到了如何求 [0,11,1]k−1\begin{bmatrix} 0,1 \\ 1,1\end{bmatrix}^{k-1}[0,11,1 ]k−1 吗？ 可以使用快速幂！！！ 矩阵快速幂！！！ 看模板代码之前，还要引入一个概念：单位矩阵（相当于累乘器初始化的 111） 它的主对角线为 111，其余地方为 000。（可以自己举几个例子，发现不管它乘什么矩阵，结果都是原来的矩阵） 和正常快速幂没什么区别，就是做运算的底数是矩阵而已。 那么我们就可以解决上面那道例题了，主函数部分： 复杂度：O(k3logn)O(k^3log n)O(k3logn) kkk 为矩阵的行/列数，可忽略。 是不是特别简单？ 可能有读者看到这里会问了，如何知道那个放到快速幂中的 MMM 矩阵是什么呢？每道题的这个矩阵都一样吗？ 别急，通过接下来的这道例题，你会明白如何得到这个 mmm 矩阵。 例题2 这道题看起来和刚刚那道题很像，只是多了个系数。 还是按照刚刚的思路，我们一起来推理一下 mmm 矩阵。 首先我们要先有一个矩阵（向量），里面存储了我们想要的信息。 这道题我们想知道什么呢？ 首先肯定是当前这一项 aka_kak ， 然后还有什么？ 我们需要知道下一项，是不是要知道它前面的两项？所以还要存储一个上一项 ak−1a_{k-1}ak−1 [ak−1,ak]\begin{bmatrix} a_{k-1},a_k\end{bmatrix} [ak−1 ,ak ] 这个向量的初始数据是 [x,y]\begin{bmatrix} x,y\end{bmatrix}[x,y ]（kkk 从 222 开始） 这样就定义好了，就像定义一个状态。接下来要推理 mmm 矩阵。 mmm 矩阵一定是一个行数等于列数的矩阵。 因为它要能和这个向量相乘，需要满足行数和列数都等于这个向量的数据个数（在这里为 222） 因此 mmm 矩阵长这样： [?,??,?]\begin{bmatrix} ?,?\\ ?,? \end{bmatrix} [?,??,? ] 接下来我们看看如何设定 mmm 矩阵使得数据能递推下去，即满足下面这个式子： [ak−1,ak]∗[?,??,?]=[ak,ak+1=p∗an−1+q∗an−2]\begin{bmatrix} a_{k-1},a_k\end{bmatrix}*\begin{bmatrix} ?,?\\ ?,? \end{bmatrix}=\begin{bmatrix} a_k,a_{k+1}=p*a_{n-1}+q*a_{n-2}\end{bmatrix} [ak−1 ,ak ]∗[?,??,? ]=[ak ,ak+1 =p∗an−1 +q∗an−2 ] 不难发现左上角填 000，左下角填 111，右上角填 qqq，右下角填 ppp： [0,q1,p]\begin{bmatrix} 0,q\\ 1,p \end{bmatrix} [0,q1,p ] 这道题基本就做完了。 读者可以尝试自己推导例题一的矩阵。 掌握较熟练后，还可以思考如何求斐波那契前 nnn 项和，前 nnn 项平方和。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 拓展例题 最后来看例题3 这道题看上去非常吓人，有读者可能会考虑高精度，但发现 nnn 最大有 101810^{18}1018，不可行。 考虑 dp。 设 dp[i]dp[i]dp[i] 表示考虑加到第 iii 个数的结果对 mmm 取模，不难得到状态转移方程： dpi=dpi−1∗10x+idp_i=dp_{i-1}*10^x+i dpi =dpi−1 ∗10x+i 其中 xxx 表示 iii 是几位数。 考虑矩阵快速幂优化。 在这里直接给出递推式，请读者自行推演： [dpi,i+1,1]∗[10x,0,01,1,00,1,1]\begin{bmatrix} dp_i,i+1,1 \end{bmatrix}*\begin{bmatrix} 10^x,0,0\\ 1,1,0 \\ 0,1,1 \end{bmatrix} [dpi ,i+1,1 ]∗ 10x,0,01,1,00,1,1 发现 10x10^x10x 会变化，考虑做多次矩阵快速幂，每次做同样位数的范围。 细节比较多，具体看代码： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 结语 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 终于肝完了，矩阵快速幂还是挺实用的。 其实它类似于一类构造题，需要自己多多练习和领悟。 本文可能有许多没讲懂或没讲全的内容，深感抱歉，但实在是能力有限欢迎提出修改建议。