为什么错了？

我已经做出来了哈：https://www.acgo.cn/discuss/study/73822 这能上榜大家多给点赞，刷罐头\color{yellow}{这能上榜大家多给点赞，刷罐头}这能上榜大家多给点赞，刷罐头 我不懂错在哪：

#创作计划# 矩阵快速幂

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

# 非官方题解 | 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难评 * ...

吉祥杯竞赛正式重启！

去年，我们曾向官方申报了「吉祥杯竞赛」，虽因故延期，但初心未改。时隔一年，我们带着更完整的构想，正式重启这场赛事。 这不仅仅是一场比赛，也是一次对竞赛体验的重新思考。 【我们做了什么】 * 全新题面显示系统，由 ZDZL 自主研发，提升阅读与答题体验 * ZDZL题面显示系统拥有严格的反作弊机制，保障公平竞争环境 * 出题/验题团队（持续更新中，排名不分先后）： @李总（不加团队） @wcqk @cjdst @yanghongzheng 【赛事信息】 * 形式：ACGO 官方公开赛 * 时间：2026 年 4 月 - 5 月（具体日期即将公布） * 更多细节，逐步揭晓 敬请期待。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 原竞赛贴

关于李总的事情|已和解

留给后人考古！ 李总网站：戳我加入 有些入抢了罐头还不加李总的网站，可恶，还来白嫖罐头！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 内容已下架 申明： * 我要开学了，懒的搞了，我宁可放弃，如果实在要追究，我还可以再发一遍 * 本帖下方不要骂人，已经没事了 * 希望本帖快点下榜，留给后人考古 开学快乐@李总（不加团队） ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 以和解 道歉信： 李总，我非常抱歉我的行为使你冤枉，你并没有错，我只是太生气了...对不起啊（我还要接着写）

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

【获奖公告】挑战赛#28

【获奖公告】挑战赛#28 名次 用户ID 用户昵称 奖励 1 5117471 @CuSn 拼图X1 +盲盒X1+1500罐头 2 4699151 @梦里初晴 拼图X1 +盲盒X1+600罐头 3 4181234 @你是不是喜欢c++ 拼图X1 +盲盒X1+600罐头 4 4997640 @Srobot 拼图X1 +盲盒X1+600罐头 5 1975597 @咕咕咕 拼图X1 +盲盒X1+600罐头 6 4787137 @x 拼图X1 +盲盒X1+300罐头 7 1779364 @yh24chenyiming 拼图X1 +盲盒X1+300罐头 8 3736031 @‏‮ 拼图X1 +盲盒X1+300罐头 9 4784858 @NULL 拼图X1 +盲盒X1+300罐头 10 5225529 @码龄不足1年的屑OIer 拼图X1 +盲盒X1+300罐头 11 2853133 @初识c++ 拼图X1 +盲盒X1+300罐头 12 4869476 @tantan1007 拼图X1 +盲盒X1+300罐头 13 4221310 @༼ つ ◕_◕ ༽つ(ˉ﹃ˉ)‮ 拼图X1 +盲盒X1+300罐头 14 1653365 @Xylophone 拼图X1 +盲盒X1+300罐头 15 494973 @不会C++的一只屑生姜 拼图X1 +盲盒X1+300罐头 幸运奖 1371791 @复仇者_天之神_银色子弹 100罐头币 幸运奖 4609559 @老杨 100罐头币 幸运奖 3891614 @金旭鑫 100罐头币 幸运奖 4770854 @顾易 100罐头币 幸运奖 4913862 @魏志飞 100罐头币 幸运奖 4643785 @skirmish 100罐头币 幸运奖 1180597 @孙若曦 100罐头币 幸运奖 4526806 @杰杰 100罐头币 幸运奖 4358016 @许宸旖 100罐头币 幸运奖 5429319 @CE君 100罐头币 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 🎁 获奖信息填写 恭喜以上获奖同学🎉 为了避免出现漏发或因未关注AC君而错过寄件信息的情况，请获奖的同学们尽快私信AC君提供收件信息。具体信息包括： 获奖赛事名称： 收件人姓名： 收件手机号码： 收件地址：需详细填写，包括省、市、区、街道及具体住址 请确保提供的信息准确无误，以便我们能够顺利将礼品送达。感谢您的配合！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ⚠️ 前100名违规名单 在本场赛事的审核中，我们对前 100 名选手的代码进行了检测，发现 46 名用户存在疑似 AI 生成或高相似度代码的情况。公平竞赛至关重要，请各位严格遵守规则，维护良好的竞赛环境。 用户ID 用户昵称 4997687 @YXO 4535677 @风止 3621376 @🥥 5371362 @不告诉你(会回关) 5207866 @张宸悦 百花小学育才路校区六年级 4976685 @消失的AC 无尽的RE 5007800 @.҈̊̔̇̊͐͌̄̾̿L大号被盗 5211372 @yeye 4919465 @黄睿宸 3580701 @༺༒༻C++菜鸟༺༒༻ 973701 @132****0720 3751693 @神-爸爸 3460964 @终极主宰大神（求关注必回） 2901632 @༺ཌༀ复仇者.凤凰.浅琪ༀད༻ 5346770 @Nike 4921199 @wwh 4531271 @RE RE RE 5408433 @一颗可爱的冰西瓜 3871431 @许睿xu rui 4174170 @山衔落日——乘风破浪 4597323 @随机名 3495853 @炎龙玄铁战神 3861543 @云雾星海 3137487 @哇！我传伞太准了 3298235 @yanghongzheng 1465462 @Yjp✅ 4816307 @TLE君 2439263 @人！！！(回关) 4913862 @魏志飞 526267 @复仇者_林克━╋══⁕═➢™ 4573273 @认真的王老师在教编程 5205552 @y=1/x 5205556 @黄羽飞 2367486 @复仇者_天之神_张起灵 4259470 @Eucatastrophe‌ 4683247 @IdssT_dx 5345022 @Phantom_73 5403433 @prediction 2317345 @bong 5445480 @复仇者 开心就好 3036559 @༺ཌༀཉི༒Dream༒༃ༀད༻ 1804874 @AKIOI 4795894 @Minecraft 3985064 @菜就多练 3668809 @kkkkkkkkkkkkkkkk 4747742 @古希腊掌管AC和WA的神 违规与处罚机制（挑战赛 & 巅峰赛） * 第 1–3 次违规： 内部记录，不扣表现分，取消礼品赠送； * 第 4 次违规： 视情况扣除表现分，并取消对应勋章； * 第 5 次及以后违规： 持续扣除表现分。 申诉机制 请在3月15日前👉 提交申诉（需提供详细解题思路）。经审核确认无违规，将撤销本次记录。如果提交申诉后，依旧被判为违规，则禁言7天以示警告。 本轮赛事审核 ：@Gragher，@cjdst，@不会C++的noah，@Zzzzzzsr（不处） 📎 ACGO 官方赛事公平审核规则 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ⚠️ 违规名单累计 * 累计违规 >3 次的用户，统一 禁言 30 天 并扣除ACGO竞赛分； * 累计违规 =3 次的用户，统一 禁言 30 天； * 仅违规 1 次者不予展示。 用户ID 用户昵称 累计历史违规次数 3751693 @神-爸爸 9 2901632 @༺ཌༀ复仇者.凤凰.浅琪ༀད༻ 7 3580701 @༺༒༻C++菜鸟༺༒༻ 5 4683247 @IdssT_dx 5 4976685 @消失的AC 无尽的RE 4

官方题解 | 挑战赛#28

官方题解 | 挑战赛#28 本次题目的总体难度如下，各位选手可以借此评估一下自身的技术水平 题目编号 题目标题 难度 T1 午枫的翻转 入门 T2 午枫的卡片交换 普及- T3 午枫的石头剪刀布大赛 普及- T4 午枫的复制魔法 普及- T5 午枫的用户记录 普及/提高- T6 午枫的数字分离 普及/提高- T1 午枫的翻转 题目大意 给定一个字符串和一个区间，输出翻转这段区间后的字符串。 解题思路 直接模拟或使用 reverse 函数即可。 参考代码 方法一 方法二 T2 午枫的卡片交换 题目大意 给定两个字符串 s,ts,ts,t ，问能否交换 sss 的相邻两个字符最多一次，使得 s=ts=ts=t 。 解题思路 枚举模拟每个相邻位置的交换，判断是否存在一个位置使得 s=ts=ts=t 即可。 参考代码 T3 午枫的石头剪刀布大赛 题目大意 有 2n2n2n 个人参加石头剪刀布比赛，一共 mmm 轮，每轮结束后重新排名，问最终的排名如何。 解题思路 使用结构体存储每名选手的编号、出拳顺序以及获胜场数，便于后续进行排序。 对每一轮比赛判断每组选手的胜负关系，记录每位选手的胜场数，每轮比赛结束对整体进行排序。 最终输出最终排名即可。 参考代码 T4 午枫的复制魔法 题目大意 给定一个数组 aaa ，将它无限复制得到新的数组 bbb ，从前往后依次累加，找出第一次使得累加和超过 xxx 的位置。 解题思路 直接一个一个累加计算判断很明显是通过不了的。设 sumsumsum 为数组 aaa 所有元素的和，于是可以 O(1)O(1)O(1) 计算出可以用最多多少个 sumsumsum ，剩下的部分一定能被数组 aaa 中某一个前缀超过，O(n)O(n)O(n) 遍历判断即可。 参考答案 T5 午枫的用户记录 题目大意 给出 nnn 名用户的起始登录时间以及连续登录天数，问对于每一个满足 1≤k≤n1\leq k\leq n1≤k≤n 的整数 kkk ，恰好有 kkk 人登录的天数。 解题思路 对于每一名用户，其对应登录的时间为一段连续的区间，不难想到使用差分前缀和来维护每天登录的人数。但由于数据范围较大，无法直接使用数组进行维护，考虑离散化，仅记录差分记录的时间点，因为前缀和后，相邻差分数组元素之间的值都是相等的，所以我们得到这段区间的值 valvalval 后可以直接计算出这段区间的长度 lenlenlen ，即为恰好有 valvalval 人的天数需要增加 lenlenlen 。 参考代码 T6 午枫的数字分离 题目大意 将给出的 nnn 进行重新排列，然后分离成两个不带前导零的正整数，求分离得到的两个数的乘积的最大值。 解题思路 考虑 dfsdfsdfs 或二进制枚举将所有分离情况全都找出来，并且判断分离是否合法，然后记录最大值即可。 参考代码

见鬼了

最近老是有人莫名其妙的被移到默认，疯了，我都几周没进去了，而且我发现被移进去的都是我团的高层，还有一次发现俩副队被移到禁闭室了。。。不可能是我啊，我查了所有权限，除了我和两个副队没人能移动分组（副队总不能把自己放禁闭室吧。而且俩副队信任值都挺高，一个是@CuSn，一个是@我不是滚c。无了，我感觉团会不会又要被毁了

#创作计划#淡谈线段树

本篇只讲基础线段树。以下内容以求区间和线段树为例。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 前置知识： 二分、分治思想，堆式建树。 对于节点 iii，他的左孩子节点索引为 2×i2\times i2×i，右孩子索引为 2×i+12\times i+12×i+1。这样我们可以将线段树储存在数组中。我们先准备两个取儿子函数，其中 now 为当前节点，后面要用。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 什么是线段树？ > 线段树是算法竞赛中常用的用来维护 区间信息 的数据结构。 > 线段树可以在 O(log⁡n)\mathcal{O}(\log n)O(logn) 的时间复杂度内实现单点修改、区间修改、区间查询（区间求和，求区间最大值，求区间最小值）等操作。 > —— OIOIOI WikiWikiWiki 线段树将一个区间按照递归顺序逐步往下分解，每个长度大于 111 的区间被分解为两个小区间，这些小区间会被继续分解知道不能再分为止。线段树可以用于维护具有结合律特性的区间查询操作。例如加法，乘法，最值。 举个例子，比如说对于序列 {1,2,3,4,5,6}\{1,2,3,4,5,6\}{1,2,3,4,5,6}，设定其左右区间分别为 1,61,61,6。那么可以绘制出线段树如下图所示： 为了方便理解我们转换成树形结构。 可见线段树通常被视为一颗完全二叉树（更准确地说是平衡二叉树）。这颗二叉树的每一个叶子节点都代表着这个序列其中一个元素的值。（因为左区间与右区间相等） 那么接下来，我们开始学习线段树的相关操作。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 建树 根据线段树的特性（即将每一个长度不为一的区间划分成左右两个区间），我们可以将一个区间对半分，然后递归对半分后的两个区间，再给它对半分，一直到区间长度为 111 为止，然后再回溯求区间和。下面我们用一个具体例子来描述这一过程。 首先我们有一个长度为 666 的序列，为 {1,20,2,6,5,4}\{1,20,2,6,5,4\}{1,20,2,6,5,4}。我们先构建出这棵线段树。 将区间 [1,6][1,6][1,6] 对半分，分为 [1,3],[4,6][1,3],[4,6][1,3],[4,6] 两个区间。 接下来来我们按照递归顺序递归左孩子，将区间 [1,3][1,3][1,3] 对半分，分为 [1,2],[3,3][1,2],[3,3][1,2],[3,3] 两个区间。 按照顺序，我们把区间 [1,2][1,2][1,2] 对半分，分为 [1,1],[2,2][1,1],[2,2][1,1],[2,2] 两个区间 此时我们发现两个区间的长度都为 111 了，那么我们就把这两个叶子节点赋值，分别为赋值为 1,201,201,20。回溯至区间 [1,2][1,2][1,2]，赋值为它的两个孩子值的和，即为 1+20=211+20=211+20=21。此时回溯到区间 [1,3][1,3][1,3]，递归右孩子 [3,3][3,3][3,3]，发现区间长度为 111，赋值为 222。回溯到区间 [1,3][1,3][1,3]，赋值为两个孩子之和，即为 21+2=2321+2=2321+2=23。 接下来我们回溯到区间 [1,6][1,6][1,6]，递归右孩子 [4,6][4,6][4,6]。对半分分为区间 [4,5],[6,6][4,5],[6,6][4,5],[6,6] 后面我就不细讲了，最终的线段树如下图所示。 那么我们就可以写出线段树的建树函数。 时间复杂度分析： 线段树可以被看作一棵完全二叉树，若序列长度为 nnn，那么线段树的节点数为 2n−12n-12n−1，故复杂度为 O(n)\mathcal{O}(n)O(n) ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 区间查询 现在我们构建好了一棵线段树，那么我们该如何进行区间查询操作呢？ 我们按照上述构建好的线段树为例，来查询区间 [2,4][2,4][2,4] 的和。 首先我们看区间 [1,6][1,6][1,6] 我们发现所求区间与区间 [1,6][1,6][1,6] 并不匹配[1]，所以我们向下进行寻找。我们来到区间 [1,6][1,6][1,6] 的两个孩子。 这时候我们发现这两个区间与所求区间仍然不匹配，我们就继续向下寻找 此时我们发现只有区间 [3,3][3,3][3,3] 与所求区间匹配，我们就将结果加上区间 [3,3][3,3][3,3] 的值 222。对于区间 [6,6][6,6][6,6]，我们发现他不匹配所求区间，我们直接返回 000 即可[2]。对于其他区间，我们继续向下递归。 同样的，筛去不匹配的区间，我们最终剩下了： 最后区间 [2,4][2,4][2,4] 的结果就是这三个区间的值相加。结果为 21+2+6=2921+2+6=2921+2+6=29。 由此我们可以写出线段树区间查询函数的代码，如下所示 时间复杂度分析 线段树最多有 2n+12n+12n+1 个节点，每次递归左右两边的区间，平均一下复杂度为 O(log⁡n)O(\log n)O(logn) ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 区间更新 如果根据查询函数直接写更新函数，需要下降更新这个区间中的每一个元素，复杂度高达 nlog⁡nn \log nnlogn，这个时候我们引入一个新的概念用以优化，懒标记。 > 懒标记 LAZY TAG 优化 > > 懒标记，顾名思义就是偷懒的（ > > 我们发现只有当操作时经过这一区间时才需要获取他的值，我们大可以等到需要用到这个区间的值时在进行更新。 > > 我们将储存线段树的数组加上一个值 lazylazylazy 用于储存这个节点的懒标记。只有当需要这个节点的值时，我们再将懒标记下发，并清空当前节点的懒标记。对于区间和问题，若需将区间 [l,r][l,r][l,r] 加上 kkk，下发懒标记时需要加上 (r−l+1)×k(r-l+1)\times k(r−l+1)×k。在懒标记优化后，每次搜索的时间可以优化为 O(log⁡n)O(\log n)O(logn)。 > > 据此，我们可以写出一个 pushdown 函数用来下传懒标记。如果当前节点懒标记不为 000 我们就下发他，否则不做任何操作，注意在下发完后把当前节点的懒标记设为 000。 在学习完懒标记优化后，我们来看区间更新代码实现过程。 1. 当区间完全不匹配时，我们直接返回。 2. 如果当前区间匹配，我们直接更新当前区间的值，并返回 3. 下发当前节点的懒标记 4. 更新左区间 5. 更新右区间 6. 将当前节点值更新为他的两个孩子的值之和。 代码易得 单点更新 这里不细讲，具体实现和区间更新函数类似。如果不想写可以在调用区间更新函数时将左右区间设为你想更新的那个点。具体代码如下。 完整代码 将上述函数封装，可得如下代码： 当然，线段树的模板需要根据实际情况进行填改或删改。 例题1：P3372 这是线段树的基础模板，将上述代码原模原样打上去即可。 例题2：P4513 （贴主也是半独立做的 题意： 现在有两种操作 1. 输出区间 [a,b][a,b][a,b] 的最大字段和 2. 将第 ppp 个值更改为 sss 思路： 本题需要我们在维护区间和线段树的情况下输出每一次查询的最大字段和。我们发现，某区间的最大字段和有如下三种情况： 1. 全部位于该区间的左孩子 2. 全部位于右孩子 3. 两边都有 所以我么可以额外开三个变量，分别维护从左边开始的最大字段和，从右边开始的最大子段和，整个区间的最大字段和。这里分别用 l,r,maxx 表示。把懒标记扔进垃圾桶，并在先前代码基础上那个修改可以得到如下代码： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 拓展——动态开点线段树 由于是拓展，这里讲的简略一点。 我们发现普通的线段树并不是所有节点都用到的，只有当经过该节点时才需要获取当前节点的值。所以我们可以等到需要这个节点在开。 因为这种实现方法，我们不能用堆式建树的方式来取左右孩子，我们会使用类似链表的方式，摒弃指针。在线段树结构体中储存当前节点的左右孩子，也就是在线段树结构体中再开两个成员变量 l,rl,rl,r。 区间更新 与普通线段树类似，只不过我们需要判断当前节点是否存在，不存在开一个点即可。代码易得： 区间查询： 一样的，判断该点是否存在即可。代码： 懒标记的下发 差不多，只不过需要提前开好左右孩子节点即可，代码： 例题：P13825 诶这不就是普通线段树模版吗，和模版 111 一模一样看我复制直接提交 诶我去怎么只有 50pts50pts50pts，不是这个 nnn 的上界怎么有 10910^9109 啊，吓哭了 这个时候我们把动态开点直接用上即可。由于原数列是等差数列，我们可以用等差数列公式进行求解，不需要建树代码。代码如下： 完结撒花 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 1. 这里我们定义当前区间为 [l1,r1][l_1,r_1][l1 ,r1 ]，所求区间为 [l2,r2][l_2,r_2][l2 ,r2 ]，我们说当前区间与所求区间相匹配当且仅当 l2≤l1≤r1≤r2l_2 \leq l_1 \leq r_1 \leq r_2l2 ≤l1 ≤r1 ≤r2 ↩︎ 2. 我们需要根据实际需求进行返回，这里返回 000 的原因是因为一个数加上 000 仍得原数。如果我们要求区间最大值，可以返回 INT_MIN。 ↩︎