来，挑战评论最多的帖子

# 非官方题解 | 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} 我是大蒟蒻，所以只写前两题，后面的谁爱写谁写 : )我是大蒟蒻，所以只写前两题，后面的谁爱写谁写:)

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)，所以认为目前不存在“更简单的做法”，若有，可以联系团员交流。 最后对于本题目的难度，经本团队讨论发现本题难度应小于蓝（提高+/省选-），大致为上位黄~下位绿，对此可以在此贴下方给出自己的看法（请不要灌水，有题目上的其他问题也请私下与团员交流）。 最后感谢所有选手的指出问题。

#创作计划# 矩阵快速幂

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 前言 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 好久没有发帖子了，今天写个创作计划吧。 各位大佬嘴下留情，不喜轻喷，欢迎提建议！ 本文将用通俗易懂的方法讲懂矩阵快速幂 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 铺垫 （若你已经知道且学会快速幂和矩阵乘法，可以直接跳到正文部分） 一、快速幂 先来复习一下快速幂。 以上是一个简单的快速幂模板。（如果到这里你没有看懂，请重学快速幂） 二、矩阵 矩阵，相当于 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 会变化，考虑做多次矩阵快速幂，每次做同样位数的范围。 细节比较多，具体看代码： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 结语 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 终于肝完了，矩阵快速幂还是挺实用的。 其实它类似于一类构造题，需要自己多多练习和领悟。 本文可能有许多没讲懂或没讲全的内容，深感抱歉，但实在是能力有限欢迎提出修改建议。

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

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

关于团队角色设置的想法

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

# 非官方 | 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 代码由于语言本身较慢所以是无法通过的。 应该不会有人第一遍就发现代码里的小彩蛋。

#寒假生存实录#寒假日记

如果您是来刷罐头的\HUGE{\COLOR{RED}如果您是来刷罐头的}如果您是来刷罐头的： 如果您还在刷\HUGE{\COLOR{RED}如果您还在刷}如果您还在刷： 真正好看的部分等春节过完的三天。我会写个特辑的捏。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 广子： 我与秋裤等人办的公开赛开始啦，欢迎大家参赛。链接描述 同时也欢迎各位加入出题团，具体内容看链接所指的帖子。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 特爱写日记。 其实我本来就想写的，然后看见了AC君的那个活动，虽然奖品不咋样但是还是参与了。 本文与秋裤的文章同步更新。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ DAY -3 DAY -2 好的第一门语文。两个小时。前面水题，不过等交卷了突然感觉作文有点跑，不管了随缘吧。预估分数 95 考完语文立刻吃饭，后面在楼下玩了半个小时。中午没午睡，开始复习科学（临时抱佛脚这一块），做的是科学老师塞给我的一张卷子。 第二门科学，一小时四十分。题目难度不高，还行，不过写完感觉还是有点炸。预估分数 140，对完答案目前没有错的。 好的考完了，去吃饭。 然后听数学老师讲试卷。。。 我去阴死我了，晚自习下课没铃声导致晚回了五分钟，幸好老师不在 下半截晚自习做作业，不过主要是复习。然后看见俩哥们打起来了（桌子大残，椅子大残，空气大残），给我们班人都笑抽了（我去老师来了这俩娃都没事）。 回家水了一下犇犇，之后认真复习道法。 DAY -1 不是洛谷怎么大凶啊。 早自习直接复习数学。（不过数学老师呢 好的好的，数学考试，两个小时。嗯，水题……不是最后一题是个啥，咋还是原题的。倒数第二题又是个啥，本以为分类讨论结果只有一种情况（我还在答题卡划了重写一遍你知道吗）。看了一下至少五题是我做过的。居然原题大战有点意思。下课对完答案感觉良好。预估分数 118，对完答案目前没有错的。 原题大战原题大战。 依旧考完立刻恰饭，食堂也是个人物，关东煮美其名曰“麻辣烫”，骇死我里。 中午背道法背到冒烟你知道吗，还有英语老师突击检查你知道吗，还要写英语卷子你知道吗（我的 English 非常的 good ） eee，社会比我想象中简单，是我们社会老师监考。考试的时候老师一直在看我卷子知道吗，我心理压力多大知道吗，老师还翻来覆去的看知道吗。最后一道题实在不知道讲了啥知识点，干脆把已知的所有知识点默一遍吧，后面老师说看了我的答题卡，觉得我做的还行，感觉良好。预估分数 93（我们的卷子有个神秘的东西，想知道的私信我） 英语也还行，不过当我 20s 做完一个题目发现这题是听力的时候：。预估分数 115，没对答案、、（昨天晚上在南开的贴子里说英语来着）。 笑点解析：英语试卷的所有插图都是 AI 生成的，AI 味比@（坤泰）的代码还浓。后来我笔试部分都做完了听力都没放。做完听力+检查之后干坐一个小时%%% 关于这次期末考，列了张表大家可以看看（这里的预估分数是以最低的为准） 语文 数学 英语 科学 社政 总分 预估分数 95 118 115 145 93 568 实际分数 107 113 115.5 141 95 571.5 满分 120 120 120 150 100 610 完了怎么感觉考的跟shi一样（不管了相信玄学） 关于期末考，推荐更权威的渠道：去找滚蛋吧c++，同一张卷子他比我做的好。 我去我去，消失了一天的数学老师限时返场，送了我一袋子零食，开心死我了。 好的放假了。走之前和同学打了一会球，结果被数学老师狙了、 误闯天家劝余放下手中沙。现在罐头币两千多了，大赚。 准备闭关了，发现秋裤他们都红名了，就我和 Stars 还是橙名。而且 Stars 分还比我高。 笑点解析：猜猜撤回的消息是什么（ DAY 0 嗯？ return false DAY 1 嗯。 不是怎么起的比上学还早。 早饭一碗泡面，还是汤达人的。 今天和同学去玩，笑点解析：同学现在还在睡觉。十一点钟出发，去商场玩。一共八个同学。 今天开盲盒小亏。亏了 100。 在出去玩之前，出了一道题，和秋裤聊了一会天。 本来打算坐地铁的，结果我爸叫了个车给我送过去，在一个商场（上面有提到过）玩。八位同学来了六位。一个打王者一个打洲，其中跑刀哥跑了个显卡。跑刀子的那位给我们买了 KFC 大餐。吃完之后和其他人一起逛街去了。 一位同学（就是那位跑刀哥）拿着他的板去转转上估价，结果估出来 790。平还是加上了 91 元的补贴的。给那同学干红温了。 简单的解决了中饭，因为实在无聊买了个狼人杀。赢了两把输了一把 后来又完了猫鼠游戏，我太菜了就没玩。后面他们被俩女生干掉了，是我们班正副班长。 他们要吃晚饭走，我就算了，先行回来了。刚到家。 晚上搞了两口面对付对付。 一进书房看见我那堆积如山的课本/教辅陷入了沉思。话了 40min 的时间收拾完了。现在整洁多了（其他练习册都撇了）。我还特意留了两个没做过的教辅给我堂妹，我真是太善良了。 DAY 2 气死我了闹钟没关。 不过睡了一个回笼觉，七点四十分起床。第一件事就是回复秋裤的消息。 后来开了个盲盒， 的 BUG 给我卡掉了一个，但是记ACGO录里有一个 399，大概率我那个开了 399。今天盲盒小赚。 老妈给我做好了早饭，是排骨汤，很好喝。加上我爸前几天给我们卤味，味道挺好的。 成绩还没出 突然想起老师给我们布置的寒假作业还有一点点没写，明天就要交了，花了 5min 写完了（ 好的欢乐赛开始，赶紧水一波。 T1 我直接python三引号大法秒了，T2简单分支秒了，T3把单调不升序列的意思理解错了，吃了两发罚时，红温了，不打了。（最草率的一集） 好的成绩出了 语文 数学 英语 科学 社政 总分 预估分数 95 118 115 145 93 568 实际分数 107 113 115.5 141 95 571.5 满分 120 120 120 150 100 610 总结一下 * 语文：我去咋改的，可以可以很满意。班级 rk1 * 数学：我去咋改的，过程分我恨你啊。班级 rk3 * 英语：有点点差，申请加入义和团。班级 rk5 * 科学：也还可以，不过为啥扣这么多呢？班级 rk2 * 社会：可以的，正常发挥。班级 rk1 * 总分：比预料之中高，但是还是很可惜的，我感觉年级 rk1 拿不到了 555。班级 rk1…………我就知道，年级 rk2。555555 综上所述：数学过程分我恨你 555 彻底红温了。 为了缓解心情，和秋裤哥一起做了一些水题。比谁卡常卡的好。好消息：我卡到了 8ms；坏消息：是错的；更坏的消息：加上一个 if，代码能过但是复杂度瞬间增加 30ms——有人知道什么原因吗QAQ。 滚蛋吧c++限时返场 细节秋裤找了1h 的题目。 和秋裤比赛切题，最终战绩： * 我：三道橙题（AC）+一道黄题（50pts）+一道绿题（在时间结束前拼死跳出的暴力，25pts） * 秋裤：一道橙题（AC）+ 一道黄题（50pts）+一道绿题（20pts）。他策略失误了，我现切三个橙，然后拿部分分。他先做黄去了。 简单洗了个澡，明天要返校，早点睡觉吧。 今日做题战绩（参考秋裤的）：P5266 P14635 P1190 P11908 P1028 P3114（50pts） P7074（25pts） DAY 3 误闯天家，三个 888，两个 99，大赚！！！！！ 今天要返校了，一天安排都很紧，只有等晚上来写了QAQ。 好的返校回来了，中午午饭简单凑活了一下。 下午回了一趟小学，见了一下曾经的班主任。当时正值雨季，漫步在园中的校园，让我想起了过往的许多美好回忆。所以…… > 我常常追忆过去。 > > 生命瞬间定格在脑海。我将背后的时间裁剪、折叠、蜷曲，揉捻成天上朵朵白云。 > > 云朵之间亦有分别：积云厚重，而卷云飘渺。生命里震撼的场景掠过我的思绪便一生无法忘怀，而更为普通平常的记忆在时间的冲刷下只留下些许残骸。追忆宛如入梦，太过清楚则无法愉悦自己>的幻想，过分模糊却又坠入虚无。只有薄雾间的山水，面纱下的女子，那恰到好处的朦胧，才能满足我对美的苛求。 > > 追忆总在不经意间将我裹进泛黄的纸页里。分别又重聚的朋友，推倒又重建的街道，种种线索协助着我从一个具体的时刻出发沿时间的河逆流而上。曾经的日子无法重来，我只不过是一个过客。>但我仍然渴望在每一次追忆之旅中留下闲暇时间，在一个场景前驻足，在岁月的朦胧里瞭望过去的自己，感受尽可能多的甜蜜。美好的时光曾流过我的身体，我便心满意足。 > > 过去已经凝固，我带着回忆向前，只是时常疏于保管，回忆也在改变着各自的形态。这给我的追忆旅程带来些许挑战。 > > 我该在哪里停留？我问我自己。 （（（ 和许多曾经的同学聊了会天，之后我们聚在一起拍了一张合照。再然后，我们和老师聊了。但是因为个人原因，我不得不提前离开。走之前回望校园，想起了在小学的时光。 我常常追忆过去。说句实话还是有点挂念，下次再回来看看吧。 好的来和秋裤比赛了。 上来两个水体，一个打表一个二分答案板子。后来看见一个黑题，想尝试部分分。结果死磕半小时， O(t×n)O(t\times n)O(t×n) 的算法一分都不给，气死我了气死我了。 最后力竭了先行下场。 和 Xy，秋裤讨论了一下关于公开赛的事 因为 smart luogu 不适配新版洛谷界面，下了氧洛谷，再稍微配了一下。效果挺不错的。 晚上吃了一锅纯素的火锅。 不是今天怎么就有打卡了啊，不管了看见地理的填图量很少直接 5min 写完上交。666 还有读英语、体育。 简单看了一会电视，准备来水讨论拉 今日刷题记录：P2063：0pts P2440:100pts P8738：100pts DAY 4 不是不觉已经放假 4 天了，再过二十多天就要上学了（ 今天自然醒 每日开罐头，小亏 100 罐头币 早饭没饭吃，依旧吃泡面。 上午一直在上课+写作业 到小码王了 上课了，今天上的内容是图的遍历，难度还行。 气死我了调了半天是我思路错了、、、 买了五个盲盒，一次买五个，明天直接梭哈。对了，注意到码豆商城也有冰箱贴了，而且价格还相等。 It's been a long day,without you my friend. 《一天一篇作文》555 今晚 ABC 真毒瘤，感觉要掉分了。 DAY 5 坏了坏了，今天盲盒开完亏了 500 多。 中午的饭还可以的捏。 去小码王的路上碰见两个同学。一个小学的一个初中的。 神秘滚c上课练习切屏技术，只是为了补作业、、、 今天的内容是拓扑排序，感觉不难的。善良的老师还给我们买了饮料，大方地说随便喝。老师还是太好了。 回来之后简单玩了一会，写了一篇作文一篇阅读的作业。 晚上吃剩菜剩饭捏。反正没一样是现炒的，全是微波炉里热的呃呃呃。 又来写作业了。 今天的洛谷月赛怎么这么毒瘤，T1 最终拿了 15 分，这还有一千五百名能拿。 DAY 6 哦原来昨天比赛是黄绿蓝紫啊，那没事了 洛谷估值才加了 2 分，看来我离红名还远着呢。 今天盲盒大赚 500 罐头币，相当于把昨天亏得赚回来了。还是没开到我想要的 1999。 AtCoder 的 AWC 感觉挺有意思的，毕竟是 un，今晚打打看。 早上吃了一盘煎饺，好吃捏。 今天怎么又有一篇作文 看秋裤他们和2778超燃智斗。 今天去我妈公司那里吃了顿中饭 AWC？ 今天小码王内容是并查集，幸好我提前学了，非常轻松捏。 我们班有五个人，除了我之外都会切屏大法，吓哭了。 神秘滚c切屏被老师捉了 我去小码王这么大方给我们喝饮料，分水果还一人给我们一个春联（虽然我也不会贴这个的QAQ），这么好。 推荐刷题时放《千与千寻》，纯音乐版本，最好是陶笛演奏的，最后开 0.9x。个人感觉在刷题的时候听很好。 今天晚上来做做AWC 不是你们点赞我可以理解，但是你点十几个赞我就不理解了。这是骚扰，骚扰知道吗[愤怒][拍桌子] 坏了 AWC 就出来了前三题，还是太菜了。等我课程结束了我要闭关学新算法了，不然今年 CSP 要炸。 笑点解析：本场比赛允许使用 AI。 已严肃阅读帅童的 AWC 题解。 DAY 7 罐头币 5000 祭！ 为什么我开了这么多轮一次 1999 都没有。 今天没有作文（喜） 但是要上小码王（悲） 今天中午我姑姑他们来做客捏 今天小码王上的是最小生成树。今天是整个寒假里最后一节小码王了。 还行，题目都是板子，不难。 好的滚c左边那位同学用毕生积蓄抽了一个赌神盲盒，最终以 66 个的稀有战绩收场。 下课啦。 （跟踪滚c失败 不是啥阴，做一次地铁见一次同学是吧，还次次不重样，怀疑他们卡好时间来蹲我。 坏了就是冲着我来的（欸我明天不上小码王 其实，忘川秋库是 M。理由见此：链接描述 和秋裤做了好多题目，一共 15 题，数不过来了就不一一列举了。 一个 sib 天天抄我头像，可以看这里：链接描述。现在用马达加斯加的企鹅了。记得这图好像是洛谷截的。 米兰冬奥会捏。昨晚看到十点半。然后电视炸了、和我爸修。修完就睡觉了。 DAY 8 day 7 day 8 今天盲盒梭哈，只赚了 200 多个，为什么你们都能开出来 1999 啊，此时的我： ACGO 铃铛老是炸，怎么老被炸啊。发现一看全是刷罐头的，我真无语了，你们刷罐头的能不能消停一下，我真服了。 今天没有作文（喜）。 上完语文课了（喜） 没饭吃了（悲），呜呜呜，又是吃泡面的一天。但是泡面很好吃（喜）。 开始做题，找了一些黄/橙的贪心做做，联系下思维。 下午说要和我做题神秘秋裤不见了，所以： 神秘秋裤刚上线就走了，真是个神入。气死我了 6 秋裤一会上线一会下线，我直接在电脑旁边写作业了。结果他骂我 sib，555. 我就知道，私信 99+，一定是sib忘川秋库搞的鬼。然后跟忘川秋库刷屏，从 ACGO 刷到洛谷，从百草园刷到三味书屋（ 然而还是我更胜一筹，顺便骂了两句秋裤。 好的吃饭去了 晚上没菜吃整了四根香肠awa。 sib秋裤又给我私信炸了，气死我了。 米兰冬奥会。 sib 秋裤搞了个连点器刷我屏，后面给他拉黑了。让他受着 DAY 9 我人还是太好了，给秋裤解除拉黑了。 今天早上一碗年糕，好吃喵。 今天盲盒梭哈，5 个 199，我无语了，看来赚到 10000 还是很遥远的事了。 弄了这么多高雅人士显得我很 sib。但是我就弄 今天还是没有作文，嘻嘻嘻嘻。 关于我的背景：经典咏流传，我必须改名字。 请输入文本 要过年啦，也一页一页一页哦哦，笑点解析（对面是 wcqk）： 话说我真的越来越抽象了吗？ 中午吃了一个肉夹馍+一碗瘦肉丸。好吃好吃。 回来写了会作业，同时和秋裤聊天。准备基础赛。 基础赛 A 脑子抽抽吃了 5 发罚时，然后先把 B 做了。做完之后 A 也好了。 接下来跳了 1h 的 C 无果去和隔夜水了。 最终战绩： (100+100+20)pts(100 + 100 + 20) pts(100+100+20)pts。 神秘秋裤切出了 C，尝试查看他的代码结果出来滚木。所以简称滚C。 写作业去了。 宣传捏 晚上吃了老妈炖的牛骨汤。就是这个牛骨髓给我赤兔了、太击败腻了。但是其他的肉都是很好吃的。加上其他菜，这顿晚餐： 吃完饭练字捏。 练完啦，可以看电视啦。 证明题做多的忘穿秋裤尝试证明所有人都是非男： > 引理：1、所有男人都有格调 2、格调是可导的 3、格调是等插的 > 三个引理是显然的，不再证明 > 记一个人的格调数目随时间变化的函数为 f(x)f(x)f(x) > 假设存在一个男人，他的格调数目在某一时刻大于 000，即存在 x0,f(x0)＞0x_0,f(x_0)＞0x0 ,f(x0 )＞0 > 记这个男人的寿命为 lll，因为他在受精卵时期即死亡时刻不具备有生理活性的格调，易得 f(0)=0,f(l)=0f(0)=0,f(l)=0f(0)=0,f(l)=0，且对于x>l,f(x)=0x>l,f(x)=0x>l,f(x)=0 > 当p为非负整数时，记 f(p)f(p)f(p) 组成的数列为 ap{a_p}ap ，由引理 333 知 ap{a_p}ap 为等差数列，又由 a0=0,a[l+1]=0a_0=0,a_[l+1]=0a0 =0,a[ l+1]=0，易知a_p=0，（中括号为高斯函数，为保证下标为整数） > 取任意 p0∈N∗p_0∈N*p0 ∈N∗,所以 f(0)=0,f(p0)=0f(0)=0,f(p_0)=0f(0)=0,f(p0 )=0 > 记 f((p0)/q)f((p_0)/q)f((p0 )/q)，其中q为正整数组成的数列为 bq{b_q}bq ，同理知b_q=0,即f((p_0)/q)=0 > 由于 p0p_0p0 是任取的，我们知道，对于 x∈Q∗x∈Q*x∈Q∗，f(x)=0f(x)=0f(x)=0 > 由引理 222 知，f(x)f(x)f(x) 是可导的且连续的，因此对于 x∈R∗x∈R*x∈R∗，f(x)=0f(x)=0f(x)=0 > 即，这个人的格调数量在任意时刻等于 000，这与假设冲突 > 因此，世界上没有一个男人具有格调，根据引理 111 知，没有格调的人不是男人 > 因此，所有人都非男，证毕 我要暴打皓仔，暴打欢乐赛。大炮打蚊子（ 大水欢乐赛快速 AK 变换，可惜吃了一发罚时。 晚上写欢乐赛题解，结果听到狼叫，给我吓哭了。不过后面没有了。 踏马的是人在叫。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ DAY 10 早密码，五个盲盒全是九十九，亏死我了。 我的洛谷题解过审啦，太棒了。 还是没有作文（喜） 不是怎么调戏反作弊系统也要被棕啊，昨天月赛我就想干这事来着 吓哭了。 神秘滚c上线刷罐头 今天我奶奶他们又来玩了，111 带俩小孩出去玩。 看了忘川秋库给我发的猴子工单，太爽了必须共享。 这一个秋裤一个Stars 这俩人 中午饭真好吃捏。 我怀疑客服们都用了亲亲亲插件（喵喵喵插件），刚刚试着和忘穿秋裤这样说话给秋裤弄红温了，自己也绷不住了、、以后绝对不当客服。 晚饭吃剩菜、 门口有三位人和警察蜀黍吵起来了，不知道什么原因，然后我就坐在窗前吃瓜。 很神秘 DAY 11 尼玛怎么还是亏得，昨天不是大亏了一波吗，下次再也不五个梭哈买了，后面我分批买。 今天大扫除捏。 早上吃了一碗水煎饺，好吃好吃。 大扫除#1——擦玻璃 科技改变生活喵，现在都有擦玻璃机器人了。我们的阳台窗特别大，再也不怕擦玻璃累成狗了（ 这机器人还可以擦窗玻璃的外侧捏。我妈告诉我一个小技巧，在擦的时候喷点酒精，这样子擦完就没有印子，确实如此捏。 就是擦得有点慢捏，但是还是很方便的，还有自动寻路功能。 照片就不放了，我怕秋裤给我开户（ 我去我要擦全部的玻璃，至少擦一上午（甚至擦不完www） 沃德发，还真擦了一上午，还没擦完问题是 骇死我里 擦到下午两点 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 捉到滚C拉，www 和神秘秋裤聊了一会天，然后下了。 DAY 12 不是官方条概率了把，我都连亏四天了甚至一个 399 都没出过，我去。 早饭依旧煎饺。 去了趟医院，火速回归。 好的出发去买年货捏。 买了零食大礼包，四箱特能输，还有一堆薯片，瓜子之类杂七杂八的东西，花了小一千。 中午吃了个快餐，蹭了一点点可乐。 我爸要洗车，跟着去洗，是自助洗车。本来想帮忙但是被高压水枪冲成sib了，只能去晒太阳了。 后来还是帮上忙了，来擦车，甩毛巾。 我把上班去了，我们自己坐地铁回家。 一到家就看见一堆点赞，不用想一看就是刷罐头的。 还真是。 秋裤拉着我刷题，但是我要写作业，委婉的回绝了（ 打算寒假去湖北一趟，看看能不能见到秋裤。 神秘电脑突然关机，吓死我了。 作业写死我了。 简单放松一下，吃了过年吃的瓜子+南瓜子+开心果，太开心了。 DAY 13 密码的连亏五天 CXXP#1 开始了，看着 Lost 大佬 AK。 去买东西了 买了一堆海鲜还有各种菜，做年饭。我们这里是中午吃，叫做年饭，秋裤也是的。 买完回来了捏。 处理一下 CXXP#1 的事情 坏了被叫走当黑奴了，切蒜末去了。 呛死我了，终于切完了 吃年饭了捏。 好吃好吃，继续来 CXXP#1 当黑奴。 今天是二十一世纪的第 9178 天。 吃剩菜。 看春晚捏。 省流，春晚的标志是春晚四叠马。 我和你同时掉河里你就被电四了。 现在机器人越来越强了，后空翻都会了。 欸你换新手机了，旧的呢 旧的我放在（）（） 撇了！！！！！撇了！！！！！ 新年快乐！\HUGE\COLOR{RED} 新年快乐！新年快乐！ 密码的尝试抢洛谷第一发题解，交上去发现我这个电脑时间不准，密码。 DAY 14 如你所见这是半夜写的，至少这句是半夜写的。 盲盒终于赚了，888 一个，555 我太可怜了。祝各位新年都能 888 捏。 难忘今宵 饿啊睡醒了。 简单吃个早饭 出发去金华 没拍路上的风景，返程给你们拍。 笑点解析：去服务区上厕所，看见一个女的走到男厕所里去了，后来被保洁阿姨赶出来了、 中午 12:30 到，吃了一顿丰盛的中饭。 亲戚们都来了，和与我年龄相仿的人一起扎鞭炮，扎窜天猴的时候窜天猴飞我脚上了，吓哭了。 没事。 炸沙子，扎砖块这一块。 打扑克捏。 好的还是我赢得多。 耶耶耶收压岁钱了，才第一天就收了好多红包了。 《兵不厌诈》《暗度陈仓》 DAY 15 今天盲盒小亏 去祭祀了，祭拜祖宗。有图，等会给你们放。 走在乡间的小路上。 中午饭特别好吃，在外太婆家吃的（PS：外太婆是外婆的妈妈）。 回家喽、 舅妈他们也来了，我们暗度陈仓在严禁卖烟花的地方买了烟花，其实也不算严禁，这里的话就算警察看见了他也不会来管你，但是总有写喜欢fanjian'的人来举报，这个时候警察就不得不管了，所以每个商贩都把烟花藏起来，等有人来买的时候再拿出来。 我们买了整整一箱子。花了 500. 晚上吃火锅，和他们买火锅底料。顺带买了两盒草莓，还可以的。 继续当魔丸玩窜天猴，为什么说是魔丸，因为我窜天猴不往天上放，去炸沙子，炸枯树之类的东西。我们研究了一个好玩的，就是把窜天猴的尾巴扯掉，之后塞到摔炮的盒子里，严严实实的埋在沙堆里。到时候一点，点完之后把石头压上去。最后你会得到——自己去试试把（ 笑点解析：撒尿牛丸是鸡肉+猪肉调配而成的的，他吗一点牛肉的影子没有 什么满级黑心商家、、、 尼玛 洛谷你不乘哦。 晚上吃火锅捏。像我这种湖北的肯定要吃辣锅啊——我k怎么这么辣。 原来是底料没化开，吃了满口底料。后面就不拉了 一起放烟花啦。 放完了，准备读博，用扑克牌。 前面马上输完了，后面翻盘了。稍微赚了一点点。 DAY 16 早上起得很晚。 吃中饭ing 回家了。 到家在 3:30，比预测的时间快乐 30min。 简单玩了一会，吃完饭。 吃完晚饭立刻去看《飞驰人生3》，很好看，推荐大家去看。 看完回来九点，看了两个小时的电视，警匪片。 晚上十一点睡觉。 DAY17 起床了。 吃饭了。 写作业。 今天是我弟的生日捏，开心捏。 我姑姑他们来了，吃了个挺丰盛的中饭。 好的吃蛋糕、 好的吃晚饭，吃剩菜 好的看冬奥会 我去第四金出来了。一金一铜、 下播 DAY 18 出去爬山捏。 宝石山。 我去这不是小土坡吗，海拔没一百米。 不费吹灰之力爬完了捏。 下山了，走了很远的路在西湖找吃的。 吃了一碗面。已完成今日往鸡汤里加辣椒大学习。 到家了 DAY 19 上午一笔带过了，没啥好讲的（ 去了趟医院，路上就看见我爸和导航博弈，最后成功绕了 30min 的路（ 回来看谷爱凌冲金，没想到居然一金一银。 DAY 20 早上起床有点晚。 去你的洛谷为什么我还没有红。 DAY 22 21 失踪了。 我去盲盒大赚 2000. 跳过 明天看我和 Stars 下围棋，打爆他））） ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ DAY 23 打包皓仔了） DAY 24 和秋裤来了一把，椰子壳观战，秋裤被打爆了））） 中午简单吃了点菜。 你吗吓死我了，旁边一直在炸，声音特别响。还冒白烟。我以为炸弹仍我家门口了然后他吗是酒店开业放烟花。 现在啥都看不见了，能见度为 0，白花花一片。

# 官方题解 | 欢乐赛#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，在所有答案里面选择最大值并且输出。 参考代码