还好没去小码王集训蹲大牢，想听听你们的感受

点赞！！！！！！！！！！！！！

题目 我用同余的方法来求解，题目下面给的用例可以顺利通过。但是提交的时候所有用例都失败。 甚至不如暴力循环，暴力循环还能通过三个case，剩下均TLE。 求指导一下，是我题目理解有误，还是代码实现的不对。

本团目前正在招人。 本团福利多多，竞赛多多，机会也多多。 如果有感兴趣的可以点击以下链接来加入我们 邀请链接 我们天天一起吃瓜，那叫一个开心。 有专属的聊天场地，聊个够 有专门的机制，处理各种事情 快来加入我们吧

A7979.秘密代码（原题）

歪七七（三命（悲

https://www.acgo.cn/application/1819320347874357248

差分数组： 对有 nnn 个数据的数组 a[]a[]a[] ，其差分数组 d[]d[]d[] 使得 d[]d[]d[] 的前缀和可以获得 a[]a[]a[] ,即: ai=∑k=0idk(1)a_i=\displaystyle \sum_{k=0}^{i}d_k\tag{1} ai =k=0∑i dk (1) 由此移项，可得： di=ai−ai−1(2)d_i=a_i-a_{i-1}\tag{2} di =ai −ai−1 (2) 则易得若将 d[i]d[i]d[i] 增加 ccc ，则在数组 a[]a[]a[] 中，数据 ai、ai+1......、ana_i、a_{i+1}......、a_nai 、ai+1 ......、an 都会增加 ccc 。 因此，若要将序列 a[]a[]a[] 中 [l,r][l,r][l,r] 之间的数都增加 ccc ，则我们需要有dl+=cd_l+=cdl +=c且dr+1−=cd_{r+1}-=cdr+1 −=c，时间复杂度为 O(1)O(1)O(1) 例题： 区间修改(集训营入口) 区间修改(非集训营入口) STSTST表: 解决在线RMQRMQRMQ问题的工具。 步骤： 111 设Fi jF_{i\ j}Fi j 表示区间 [i,i+2j−1][i,i+2^j-1][i,i+2j−1] 区间的最值，区间长度为2j2^j2j，填表的时间复杂度为 O(nlog⁡n)O(n\log n)O(nlogn) ，递推式为： Fi j=max⁡(Fi, j−1,Fi+2j−1 j−1)(3)F_{i\ j}=\max(F_{i,\ j-1},F_{i+2^{j-1}\ j-1})\tag{3} Fi j =max(Fi, j−1 ,Fi+2j−1 j−1 )(3) 分治法： 指定对于一个规模为 NNN 的问题，将其分解为 MMM 个规模较小的子问题。这些子问题互相独立(即子问题之间不包含公共的子子问题)且与原问题形式相同，递归解这些子问题，合并其解可得原问题的解。分治的核心代码主要集中在分解和合并阶段，治理极端的核心点事递归参数和递归边界。 快速排序： 问题：对一个长度为 NNN 的序列 a[N]a[N]a[N] ，将其升序排列。 方法：从序列中任取一个元素 xxx ，将所有小于等于 xxx 的元素放到 xxx 的左边，所有大于等于 xxx 的元素放到 xxx 的右边，此时 xxx 的位置必定正确，下面是使用双指针的方式解决快速排升序问题的代码： 快速排序的一次划分算法从两头交替搜索，直到指针 low\mathrm{low}low 和指针 high\mathrm{high}high 重合，因此其时间复杂度是 O(n)O(n)O(n) 。而整个快速排序算法的时间复杂度与划分的趟数有关。理想的情况是每次划分所选择的中间数恰好将当前序列几乎等分，经过 log⁡2n\log_2nlog2 n 趟划分，便可得到长度为 111 的子数组。这样，整个算法的时间复杂度为 O(nlog⁡n)O(n\log n)O(nlogn) 。而最坏的情况是每次所选的中间数是当前序列中的最大或最小元素，这使得每次划分所得的子数组中一个为空，另一子表的长度为原数组的长度 −1-1−1。这样，长度为 nnn 的数据表的快速排序需要经过 nnn 趟划分后的时间复杂度为 O(n2)O(n^2)O(n2)。 归并排序： 步骤如下： 1.1.1. 将给定的包含 nnn 个元素的局部数组"分割"成两个局部数组，每个数组各包含 n2\dfrac{n}{2}2n 个元素。(划分) 2.2.2. 对两个局部数组分别执行 MergeSort\mathrm{MergeSort}MergeSort 排序。(处理) 3.3.3. 通过 Merge\mathrm{Merge}Merge 将两个已排序完毕的局部数组"整合"成一个数组。(合并) 代码： 树与图： 边的数量： 对于有 nnn 个节点的树，有且只有 n−1n-1n−1 条边。 路径： 在一棵树中，一个结点和根结点的通路称为路径。在第 kkk 层的结点的路径长度为 k−1k-1k−1 (如果称根结点处在第 111 层)。一个结点的路径长度乘以该结点的权值，为结点的带权路径长度，其中权是给一个结点赋予的有意义的值。树的带权路径长度规定为所有叶子结点的带权路径长度之和。 哈夫曼树： 使得的带权路径长度最短的树称为哈夫曼树，又称为最优二叉树。哈夫曼树通常为二叉树。 哈夫曼树的构造： 对于给定带有各自权值的 nnn 个结点，构造哈夫曼树： 1.1.1. 在 nnn 个权值中选出两个最小的权值，对应的两个结点组成一个新的二叉树的一个结点的左右孩子。 2.2.2. 删除使用过的两个权值，将新的权值加入到权值集合中。 3.3.3. 重复 111 和 222 ，直到无法再选出两个权值，此时这个二叉树就是哈夫曼树。 通俗点：最底下一层俩叶子，往上每层加一个叶子，叶子的权值下面小上面大。 详见百度百科-哈夫曼树 哈夫曼编码： 按照字符出现的概率分配哈夫曼树的叶子结点的权值，以实现平均码长最短的编码。每个字符的哈夫曼编码表示为：从根结点出发到目标结点，每走一个右子树加一个 111 ,否则加一个 000。 度： 节点的子节点数，特别的，称度为 000 的节点为叶子结点；树的度是其所有节点的度的最大值。 树的表示与储存： tree[i].child 存储着节点i的孩子的位置信息。tree[i].child.push_back(idx) 表示给节点i增加一个编号为 idx 的孩子. 完全二叉树: 若某二叉树深 kkk层，且除第 kkk 层外其他所有的层的结点总数达到最大值，同时第 kkk 层节点数小于等于 2k−12^{k-1}2k−1 并靠左侧连续，则称其为完全二叉树。即在完全二叉树中，编号为 iii 的结点与满二叉树中编号为 iii 的结点的位置相同。有 nnn 个结点的完全二叉树的深度为 ⌊log⁡2n⌋+1\lfloor \log_2 n\rfloor +1⌊log2 n⌋+1 。 二叉搜索树： 也称为二叉查找树、二分搜索树、有序二叉树或排序二叉树，其满足以下几个条件： 1.1.1. 若任意结点的左子树不空，则其左子树上所有结点的值均不大于它的根结点的值。 2.2.2. 若任意结点的右子树不空，则其右子树上所有结点的值均不小于它的根结点的值。 对二叉搜索树进行删除、查找、插入的操作的平均时间复杂度为 O(log⁡n)O(\log n)O(logn)，最坏为 O(n)O(n)O(n)。二叉搜索树的中序排列是一个有序序列。 AOVAOVAOV网：顶点表示活动，有向边表示活动之间的优先制约关系，(u,v)(u,v)(u,v) 表示活动 uuu 必须先于活动 vvv 进行，称这种有向图为顶点表示活动的网为 AOVAOVAOV 网。 拓扑排序-入度： 在有向图中，一个顶点 vvv 的入度指与该条边向关联的入边的条数。 拓扑排序-出度： 在有向图中，一个顶点 vvv 的入度指与该条边向关联的出边的条数。 拓扑排序： 拓扑排序解决的问题是给一个有向无环图的所有结点排序：每次去掉一个入度为 000 的顶点并更新所有与其有关系的顶点的入度。一个有向无环图的拓扑排序可能不唯一。 运算符重载 即在结构体内写sort函数的比较规则，下面是一个优先按照x降序排列的例子。

怎么歪七七呀，两次出金都没歪

> 自我反省：确实这次比赛没考好（问题不大，至少排位分没掉）。 博客园链接同步：点此跳转 第一题 - 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 代码如下：

第七章：神贡 第六章 拜神是什么，这个词语在瑰灵面前被完美呈现，齿轮转动，一道暗门打开了，仔细一看，竟是一个巨大的教堂，中间立着一道伟岸的身影，正是诡零，但神像并没有脸，不知为什么，瑰灵把病人推进去，轻放在祭台上，手术刀一转，病人的脖子就被割破，当场殒命，血液沿着祭台的纹路流动，形成了一个图案： 瑰灵仔细看了看，有种奇怪的感觉，他把这个图案记了下来，观察的时候，突然发现神像后面有个小神像，事做完后，瑰灵随手顺了一个藏在神像背后的神像，装进了兜里。 “额外收获”瑰灵离开了手术室，“该去哪呢” 此时的网友已经炸开了 “哇，那个蓝色药丸是什么鬼？先是把诡异刀了，后面又把医生刀了，为什么别的国家的医生这么猛啊” “这应该就是实力吧” “你们说，如果瑰哥真的要五星通关，有没有可能也许不是坏事” “应该是，俗话说付出多，收获就多，或许这个怪谈不仅会降临诡异，还可能有好的收获呢” “怎么可能？你是不是道德观有问题，诡异杀了这么多人，这可是人命，所以不是你的事你就不管是吗？” “不是，人家遭诡异入侵，那是人家天选者弱，你行你上啊” “其实也不是人家太弱，有没有可能是瑰哥太强” “上帝为了拯救我们，把瑰哥送上了规则怪谈” （此时拼尽一切想把龙国写好点的作者沉默了......明明是我写的为什么要感谢上帝啊！！！） “不是上帝。” （作者感到些许欣慰） “是玉皇大帝” （更离谱了啊！！） “你们就没人好奇那个纹路吗” "对啊，明明一个图案，看得我心惊胆战的” “我们对规则怪谈没有一点资料，要是瑰哥撑不住了，我们好像就真没了” “这次瑰哥回来，应该会带回来信息” “什么叫这次，难道还有下次？” “我猜的，但愿不会” 此时网友们所说的瑰哥，已经在员工宿舍里找到了下半部分规则....... 未完待续...... 第八章

我都用上矩阵了😡😡😡

vocal，这么难吗

新建了一个团队 希望有人加，但要做题哦，一个月不做会踢 链接描述

来玩儿，无正版验证，腐竹好！！！ 就在局域网

永远置顶，警钟长鸣 对于这次事件@Carl@我不叫叶珈@AC（耐摔王）@princess本次事件我因为对于一个帖子的的意见不和上升到了引战甚至人生攻击的严重后果。对此我们四个都有错误都不应该发帖引战***(九点半之后我会撤销所有关于此事件的帖除此以外)而@Carl@我不叫叶珈也会在最快的事件撤帖我们的私人恩怨可能造成了引战等后果，对于此我们都要郑重的对大家说一声：对不起加粗文本* 也希望大家也不要再转发对于此事件的看法（我们都有错）也希望@我不叫叶珈@Carl 尽快解决此事（希望让更多的人看到）！！！

有谁知道RE的结果是啥意思

本次挑战赛的难度有挑战赛的难度。听君一席话，如听一席话 T1 直接拓扑排序一下即可。注意可能有非 111 源点，需要把这些点的路径数量设为 000 再加入搜索队列，时间复杂度 O(n+m)O(n+m)O(n+m)。 T2 无论如何旋转都一样，相当于对于每一个 1≤i,j≤n1\leq i,j\leq n1≤i,j≤n，都有 a[i][j]=a[j][n−i+1]=a[n−j+1][i]=a[n−i+1][n−j+1]a[i][j]=a[j][n-i+1]=a[n-j+1][i]=a[n-i+1][n-j+1]a[i][j]=a[j][n−i+1]=a[n−j+1][i]=a[n−i+1][n−j+1]。因此，我们考虑将这些字符中的最大值分别减去每一个字符，得到的结果即为让这四个字符相同需要的操作次数。时间复杂度 O(n2)O(n^2)O(n2)。 T3 考虑对 aj−ai=j−ia_j-a_i=j-iaj −ai =j−i 条件进行变换：aj−j=ai−ia_j-j=a_i-iaj −j=ai −i。因此我们可以求出对于每一个 i≤ni\leq ni≤n 的 ai−ia_i-iai −i，并对其进行桶计数。容易得出，若一个桶内有 xxx 个元素，则这个桶对答案的贡献为 x(x−1)2\dfrac{x(x-1)}22x(x−1) 。时间复杂度 O(n)O(n)O(n)。 实现时有一些小细节：答案要开 long long，并且桶可能被放入负数，可以考虑对每一个放入桶中的元素都 +2×105+2\times 10^5+2×105。 T4 直接广搜即可，步长分别为 (−2,−2),(2,−2),(−2,2),(2,2)(-2,-2),(2,-2),(-2,2),(2,2)(−2,−2),(2,−2),(−2,2),(2,2)。时间复杂度 O(n2)O(n^2)O(n2)。 T5 发现 nnn 的数据范围极小，考虑暴力搜索。直接深搜即可。发现答案差值不会太大（不会超过 10910^9109），为了避免爆 long long，可以在 lil_ili 过大（大约 101010^{10}1010）时直接剪枝即可。但是过程中仍然可能爆 long long（646464 位乘 323232 位时），由于我不想写高精度，就用了 long long long long __int128。时间复杂度（大约） O(2n)O(2^n)O(2n)。 T6 好吧，这次的签到题竟然事 T6，让我想起了某届欢乐赛。 思路：找到 ? 所处的那一行，然后看那一行少了哪个字母。 后记 好吧，你说得对，但是这篇题解确实都是在集训营里肝出来的，所以非常生草。

最近由于学业等问题，并没有时间上线ACGO，导致没有及时回应评论，而且招人的论坛没有制作完全，导致出现了BUG，我对此向提瓦特大陆的队员和想加入提瓦特大陆的网友道歉，但我本人对论坛并不是很在行，所以需要一个网友帮忙发一下帖子，有意向的可以评论留言，我会去招人帖里提出问题的网友发送团队邀请，而想要入队的网友可以点这里，但由于技术原因，我并不确定能不能行，如果不行可以在评论留言，我会发送团队邀请，但最近我依然很忙，所以评论也可能不会马上回复，请见谅，以上就是我的道歉信，我对因为我的行为导致不便的网友们道歉，谢谢