挑战赛27题解 本次题目的总体难度如下，各位选手可以借此评估一下自身的技术水平 题目编号 题目标题 难度 T1 午枫的矩形 入门 T2 午枫的字符串移动2 入门 T3 午枫打砖块 普及/提高- T4 午枫的子序列之和 普及/提高- T5 午枫的星星树 普及- T6 午枫的数字华容道 普及/提高- T1 午枫的矩形 题目大意 给定一个矩阵，判断这个矩阵的任意子矩阵是否满足 左上角的数+右下角的数≤左下角的数+右上角的数左上角的数+右下角的数\leq 左下角的数+右上角的数左上角的数+右下角的数≤左下角的数+右上角的数 。 解题思路 由于数据范围只有 1≤n,m≤501\leq n,m\leq 501≤n,m≤50 ，所有直接四层循环嵌套枚举左上角和右下角，同时也能知道左下角和右上角的坐标，直接计算判断即可。 参考代码 T2 午枫的字符串移动2 题目大意 给定一个字符串，可以进行左移和右移的操作任意次，找到所有可以得到的字符串中字典序最小以及最大的字符串。 解题思路 因为可以操作任意次，所以只要单独往一个方向不断移动并且更新字典序最小和最大的字符串即可。 这里可以直接使用 string 类型进行移动的操作，并且也可以使用 min 和 max 函数进行比较字典序大小。 参考答案 T3 午枫打砖块 题目大意 给定 nnn 行砖块，每行向右无限延伸并且有且有一段连续的区间为奖励砖，每次可以选择一个区间长度 ddd ，并且将这 ddd 列每行所有的砖块都破坏，奖励砖只要被破坏一个格子就会被全部破坏，求将所有奖励砖都破坏需要的最少操作次数。 解题思路 这是一道经典的贪心问题，在排序时我们会想到，如果破坏一个奖励砖的最右端，那么就会破坏更多的奖励砖，所以我们按照右端点排序，模拟每次打破当前剩余第一个奖励砖的最右端即可。 参考答案 T4 午枫的子序列之和 题目大意 给定一个长度为 nnn 的数组和一个整数 kkk ，求数组 aaa 的所有连续子序列中，元素之和等于 kkk 的个数。 解题思路 首先我们可以预处理前缀和数组 sss ，即需要求区间满足 sr−sl−1=ks_r-s_{l-1}=ksr −sl−1 =k 的区间个数。问题就转化成了非常经典的问题。 枚举区间右端点 rrr ，同时统计已枚举前缀每个 sls_lsl 的个数，那么对于这个 rrr ，对答案贡献为满足 sl−1=sr−ks_{l-1} = s_r - ksl−1 =sr −k 的所有 lll 的个数。那么问题又进一步简化为：统计 si=xs_i = xsi =x 的个数。注意到数据范围无法用桶数组直接记录元素个数，考虑使用离散化或 map 直接统计都可完成。 参考代码 方法一：map 方法二：离散化 T5 午枫的星星树 题目大意 给定一棵树，问是否存在一个点与其他所有点直接相连。 解题思路 记录所有点的度数，判断是否存在一个点的度数为 n−1n-1n−1 即可。 参考代码 T6 午枫的数字华容道 题目大意 有 999 个点 mmm 条边的无向图，其中有 888 个数字放置在不同点上，有一个没有数字的点，可以通过移动将数字移动到相邻没有数字的点上，求最终将数字 1∼81\sim 81∼8 分别放在顶点 1∼81\sim 81∼8 上的最少操作次数。 解题思路 我们可以将 999 个顶点上所存放的数字用字符串表示状态，例如 254806137 表示顶点 111 存放数字 222 ，顶点 222 存放数字 555 ，依此类推，特殊地，数字 000 表示该点为空。那么终点就可以用 123456780 表示。 由于每次移动都会从一种状态变为另一种状态，我们不妨将每种状态看作一个结点，那么所有状态以及状态与状态之间的变换就可以形成一张无向图，于是我们只需要在图上用 bfsbfsbfs 跑最短路即可。由于结点是以字符串表示的，所以可以使用 map 存储从起点状态到达所有状态结点的最短路径长度。 参考代码

终于补完离线算法了（ 莫队是三大离线算法之一（毒瘤且少用的线段树分治不算），同时也是许多人入坑的第一种离线算法。虽然思路比较简单，但是莫队题型多、容易出错、写代码时常常粗心，部分理论可能难以理解，本创作计划旨在帮助读者完善莫队知识盲点、学习带修和回滚莫队的思想（因为网上的资源比较难懂，本人也曾深受其害）。 关于莫队，有个特点是代码比较好写，常数也很小。难绷三大离线算法两个（莫队和整体二分）常数小得逆天容易跑得比同复杂度甚至更优复杂度解法快还特别适合 O2 一个（CDQ 分治）就常数大（使用大量 sort 的话还会明显变慢）然后天天被 K-D 树和多维分块（WorldMachine%%%)打压。 莫队是什么 > 莫队算法是由莫涛提出的算法．在莫涛提出莫队算法之前，莫队算法已经在 Codeforces 的高手圈里小范围流传，但是莫涛是第一个对莫队算法进行详细归纳总结的人．莫涛提出莫队算法时，只分析了普通莫队算法，但是经过 OIer 和 ACMer 的集体智慧改造，莫队有了多种扩展版本. > 莫队算法可以解决一类离线区间询问问题，适用性极为广泛．同时将其加以扩展，便能轻松处理树上路径询问以及支持修改操作．(from OI-wiki) 从一道模板题入手。 P2709 【模板】莫队 / 小B的询问 题目描述 小 B 有一个长为 nnn 的整数序列 aaa，值域为 [1,k][1,k][1,k]。 他一共有 mmm 个询问，每个询问给定一个区间 [l,r][l,r][l,r]，求： ∑i=1kci2\sum\limits_{i=1}^k c_i^2 i=1∑k ci2 其中 cic_ici 表示数字 iii 在 [l,r][l,r][l,r] 中的出现次数。 小 B 请你帮助他回答询问。 输入格式 第一行三个整数 n,m,kn,m,kn,m,k。 第二行 nnn 个整数，表示小 B 的序列。 接下来的 mmm 行，每行两个整数 l,rl,rl,r。 输出格式 输出 mmm 行，每行一个整数，对应一个询问的答案。 说明/提示 【数据范围】 对于 100%100\%100% 的数据，1≤n,m,k≤5×1041\le n,m,k \le 5\times 10^41≤n,m,k≤5×104。 总之就是询问你一个区间里每个数出现次数的平方加起来是多少。 这题维护的东西用普通 ds 和算法维护看上去很不可做。如果用暴力呢？ 我们只需要定义一个 cnt 数组，定义 cnticnt_icnti 表示数值 i 在序列中出现的次数。当加入一个新数时，把当前答案加上这个原来出现的次数再 +1 就行了。很容易证明正确性。但是这样复杂度是 O(NM)O(NM)O(NM). 而莫队算法仅用了一个排序的技巧，就优化了时间复杂度。如何做到？ 首先，假设我们有大量询问： （画得丑致歉） 注意到不同区间有很多重复的地方，在询问中会被重复计算，这个地方能不能节省呢？ 先看看以下情况： 只需要将粉色区间左端点略微右移，右端点也右移就与绿色区间一样了。 莫队为了节省这些计算，将数列分为 N\sqrt NN 块（假设 N=M)，每一块长度为 N\sqrt NN .接下来对询问进行排序，将询问按左端点所在的块从左到右排序，左端点所在块一样则按右端点升序排序。然后按照排序顺序从前到后处理询问，存储上一次询问的左端点和右端点，并对其进行移动使得左端点和右端点与当前询问吻合，然后存储当前答案。 对于本题，左端点和右端点的移动都是 O(1)O(1)O(1) 的。 时间复杂度是多少？ 每次处理新的询问，左端点和右端点都会进行移动。对于左端点的移动，由于对左端点所在块排序，所以一个块内询问左端点的移动一次是 O(N)O(\sqrt N)O(N ). 如果要到右边的块，由于一个块长度为 N\sqrt NN , 也只需要 O(N)O(\sqrt N)O(N ) 的时间复杂度进行一次移动。总共进行 M 次移动，因此所有左端点移动的时间复杂度是 O(MN)O(M\sqrt N)O(MN ). 那么右端点的移动呢？对于每个块内的询问，右端点是从小到大递增的，所以一个块内右端点的移动共为 N 次，总共有 N\sqrt NN 个块，所以移动右端点的时间复杂度为 O(NN)O(N\sqrt N)O(NN ). 两者相加，O(MN)+O(NN)=O(NN)O(M\sqrt N)+O(N\sqrt N)=O(N\sqrt N)O(MN )+O(NN )=O(NN )（N=M) 本题要怎么移动左端点和右端点？当左端点向左时，新添加的数 x 给答案做的贡献是 (cntx+1)2−cntx2=2×cntx+1(cnt_x+1)^2-cnt_x^2=2\times cnt_x+1(cntx +1)2−cntx2 =2×cntx +1, 因此我们先将答案加上 2×cntx+12\times cnt_x+12×cntx +1, 再更新 cnt 数组即可。其它移动操作自己推。 本题数据为 1≤n,m,k≤5×1041\le n,m,k \le 5\times 10^41≤n,m,k≤5×104, 时间复杂度正确。 小优化：大部分莫队可以用奇偶性优化减少常数。对于左端点为第奇数块的询问，右端点从左到右排，否则从右到左排。如图所示： 注：实际上是曼哈顿距离，这里为了方便画的是欧式距离。 这个优化最多优化一半的计算量，一般可以提升几十毫秒的速度，但是也有一些数据反而会跑更久。 还有一点需要注意：初始 l=1,r=0. 记住，当莫队需要在 x 和 x+1 直接设置初始位置并向左右分别扩展时，l=x+1,r=x. 以下是本题代码： 这段代码采用的是莫队常用的写法，其中 &1 可以判断一个数是否为奇数。 请对照模板题代码自己理解。 莫队分块 当 N=M 时，分块大小为 N\sqrt NN 最优。但是当 N≠MN\neq MN=M 时，分块为 NM\frac{N}{\sqrt M}M N 是最优的。这时候左端点移动复杂度为 O(M×NM)=O(NM)O(M\times \frac{N}{\sqrt M})=O(N\sqrt M)O(M×M N )=O(NM ), 右端点移动复杂度为 O(M×N)=O(NM)O(\sqrt M\times N)=O(N\sqrt M)O(M ×N)=O(NM ), 总时间复杂度为 O(NM)O(N\sqrt M)O(NM ) 普通莫队例题 P1494 [国家集训队] 小 Z 的袜子 自行看题。 如何回答询问？我们需要知道区间内每一种颜色的袜子抽到一样的方案数，除以区间总方案数。区间总方案数的计算是入门的。很明显我们要维护 cntx×(cntx−1)2\frac{cnt_x\times (cnt_x-1)}{2}2cntx ×(cntx −1) . 最后那个 12\frac{1}{2}21 不用维护，因为会约分所以只要总方案数也不乘以 12\frac{1}{2}21 就能抵消了。像上题一样维护 cntx2cnt_x^2cntx2 就行了，维护完还要对每个 xxx 减去 cntxcnt_xcntx （由上式可知）, 由于一个区间里所有出现数值 xxx 的出现次数之和就是这个区间的长度，因此求出 ∑cntx\sum{}^{}cnt_x∑cntx 后直接减去区间大小即可。每个查询算完还要进行约分，但是约分时间复杂度较小直接并入总复杂度。以下代码进行了特判，但是似乎这个方法实现不需要特判。 Code:Code:Code: P1997 FAEBDC 的烦恼 本题其实就是让你求区间众数出现的次数。 普通莫队似乎不能维护删除操作，因为区间众数是回滚莫队才能维护的。但是，不要小看普通莫队啊！ 设 maxn 为答案，每个询问不重置 maxn, 仅改动 maxn. 加入操作可以通过 c(cnt) 数组直接维护最大值。那么删除操作如何实现？设 ccicc_icci 为 i 在 c 中出现的次数，删除第 i 个数字时如果 ccci＞1cc_{c_i}＞1ccci ＞1 则直接将 cccicc_{c_i}ccci 减一， cic_ici 更新后再将当前 cccicc_{c_i}ccci 加一。当删除元素等于众数且众数只有一个时，依旧维护以上两个数组并将 maxn 减一，因为原来的众数都没了，刚刚删掉一个原来出现了 maxn 次的众数，所以现在这个数出现的次数为 maxn-1. Code:Code:Code: P11659 小夫 注意到出题人又让我们维护不是人的东西了，所以容易联想到莫队。怎么维护呢？ 维护三个数组：cnt,cnt42,cnt23. cnticnt_icnti 表示 i 在区间内出现的次数，cnt42icnt42_icnt42i 表示序列中 l≤x<y≤r,ax=4×i,ay=2×il\le x<y\le r,a_x=4\times i,a_y=2\times il≤x<y≤r,ax =4×i,ay =2×i 的二元组数量， cnt23icnt23_icnt23i 表示序列中 l≤x<y≤r,ax=2×i,ay=3×il\le x<y\le r,a_x=2\times i,a_y=3\times il≤x<y≤r,ax =2×i,ay =3×i 的二元组数量。 左端点左移时，加入一个数，先不更新 cnt(因为要用到原来序列的 cnt) ,如果 ala_lal 可以被 4 整除，cnt42al4cnt42_{\frac{a_l}{4}}cnt424al 要加上与 ala_lal 符合 4:2 比的数的个数，即 cntal2cnt_{\frac{a_l}{2}}cnt2al , 同时也更新答案，将答案加上 cnt23al4cnt23_{\frac{a_l}{4}}cnt234al . 如果 ala_lal 可以被 2 整除，cnt23al2cnt23_{\frac{a_l}{2}}cnt232al 要加上 cntal×32cnt_{a_l\times \frac{3}{2}}cntal ×23 . 其它操作也按这个原理做，注意删除操作要先更新 cnt. 注：数组要开两倍，自己想为什么。 Code:Code:Code: 经过以上锻炼，可以发现莫队的优势是可以维护其它东西很难维护的条件，但是相对应的，莫队是一个离线、不便于修改的算法，具有一定的局限性。 带修莫队 带修莫队有什么用基本没题考 以上的莫队都是只查询不修改的。那要是加上单点修改呢？ 对于 CDQ 分治有大量经验的你可能会想到，把时间也看成一个维度进行排序不就行了？将询问进行排序，然后左端点、右端点、时间一起移动成当前询问。时间移动时如果往后移动就按顺序修改，往前就倒序回溯过去。 带修莫队的操作是将元素按左端点所在块排序，一样则按右端点所在块排序，还是一样就按时间从小到大排（一个询问的时间为这个询问前面进行的修改操作的数量）。 但是分块显然要改了，因为如果还是按原来分的话时间维度的总移动复杂度是 O(NM)O(NM)O(NM) ，显然这不是我们想要的。这个时候你会干什么呢？ 当块长为 N23N^{\frac{2}{3}}N32 时，左端点移动的时间复杂度是 O(N23×M)=O(MN23)O(N^{\frac{2}{3}}\times M)=O(MN^\frac{2}{3})O(N32 ×M)=O(MN32 ), 右端点移动一样是 O(MN23)O(MN^\frac{2}{3})O(MN32 ), 时间移动是 O(N13×N13×M)=O(MN23)O(N^{\frac{1}{3}}\times N^{\frac{1}{3}}\times M)=O(MN^\frac{2}{3})O(N31 ×N31 ×M)=O(MN32 ), 所以总的时间复杂度还是 O(MN23)O(MN^\frac{2}{3})O(MN32 ). 例题：P1903 【模板】带修莫队 / [国家集训队] 数颜色 / 维护队列 直接上代码。注意本题的单点修改直接将 aci,pa_{c_{i,p}}aci,p 与 ci,colc_{i,col}ci,col 交换（把要修改的原位置值和修改操作的新值调换），这和人不能连续向一个方向跨过同一条河流是一个道理，当你执行了一次修改操作后当前时间就会大于这个操作的所在时间，所以下一次调用这个函数只有一种可能：当前时间在减小，即时间回溯操作，这时候再调换回来即可。 Code:Code:Code: 带修莫队似乎没什么用同时这题还有 O(Nlog2N)O(Nlog^2N)O(Nlog2N) 的树套树和 CDQ 分治解法，学习了 CDQ 分治的读者可以尝试，因为这题其实就是P4690 [Ynoi Easy Round 2016] 镜中的昆虫的弱化版。虽然是 Ynoi easy round 的…… （偷图致歉） 回滚莫队 他们说回滚莫队没用，我觉得有用。 回滚莫队有两种：不删除莫队（有点用）和不添加莫队（有存在必要吗）。不添加莫队我没见过题，更不会做，也不会写，所以不讲，知道怎么计算初始整体状态并且能翻到例题的请容我%%%。 不删除莫队用于莫队算法添加容易删除难的情况。以下是例题： P14420 [JOISC 2014] 历史的研究 / Historical Research 题目要你求序列内一个数的值乘以这个数出现次数的积的最大值。添加元素只需要将出现次数更新然后取答案最大值就行了。如何删除？ 不删除！ 接下来我们使用显性分块编码，存储每个位置所在块和每个块的左右端点。 先假设我们的所有询问左右端点都在不同的块上，即右端点所在块在左端点所在块右边。 回滚莫队遍历每一个块，一开始将 l 设为这个块右端点位置+1，r 设在右端点。 然后先扩展右端点。 我们将这个答案保存，然后扩展左端点。 这时候记录答案。这时候，我们将 l 一步步右移，把辅助数组回溯成原来的样子。注意，是回溯不是删除（因为答案没有更改）。 到了下一个询问，初始答案直接设为上次保存的答案就行了，然后在区间基础上扩展右端点，因为右端点是递增的只需要添加，情况又回到了一开始。以此类推，这个块算完了就跳到下一个块。整个过程只用了添加和回溯操作，答案不通过回溯更新（因为答案更新更难）而是直接用上次答案。注意到回溯操作根本不用复杂维护，只要你能确保辅助数组回到上次状态就行。 时间复杂度是多少？左端点的移动一次 O(N)O(\sqrt N)O(N ), 右端点也没变，所以还是 O(NN)O(N\sqrt N)O(NN ) 的时间复杂度。 等等，那左右端点在同一块的询问呢？直接暴力就行了，因为这时候一次暴力 O(N)O(\sqrt N)O(N ). 很容易想到，回滚莫队自然不能用奇偶性优化了。 对于这道例题，我们依旧 cnt 数组，扩展时先更新 cnt 再更新最大值，回溯 cnt 时遇到一个就将它的 cnt 减去 1. 暴力是有手就行的。其实这题就是一道变形的区间众数。 注意看 Code:Code:Code: 闲话：这个模板也是我选的而不是洛谷官方模板，回滚莫队和线段树合并一样都是有一道题既用到知识点又最简单然后被推崇为模板但是官方模板却要经过一定的思考。不过雨天的尾巴这个名字好好听啊你值得模板之名QvQ. 既然已经做出了这道题那么区间众数也很简单了： P13984 数列分块入门 9 回滚莫队入门9（误） 所以 Ynoi 是不是叫数列分块提高 更新答案时就不用乘以这个数的值了。注意到要求出现次数一样时答案为最小者，所以要保存两个答案：答案出现次数和答案数值大小，方便比较更新。 同时此题告诉我一个很重要的点：调回滚莫队一定要把每次遍历块时初始化的那个（些）变量当作实际维护的答案，不要当成中间值变量。小朋友们不要忘记一开始初始化辅助数组哦。 此题套模板做的 6 分钟一道紫我太强了 Code:Code:Code: 此题的效率也跑到了一个丧心病狂的程度： 接下来是真正的模板题： P5906 【模板】回滚莫队&不删除莫队 本题独立 3 分钟解出来我太强了我要进省队了 这题可以维护 4 个数组，左端点左移遇到的某数的最左值、左端点右移遇到的某数的最右值、右端点左移遇到的某数的最左值、右端点右移遇到的某数的最右值，最左/最右取左右端点答案的最值即可得到，记得要初始化数组，回溯时将左端点遇到的最左和最右端的值都回溯成初始化时的状态即可。当然我还开了两个数组进行暴力。不会你们学回滚莫队尝试自己默时忘记写暴力了吧。 Code:Code:Code: 回滚莫队的例题有点少，但是当比赛遇到普通莫队题然后删除操作怎么都想不出来时应该可以试试回滚偷 AC. 莫队＋根号分治/值域分块 莫队算法需要进行 (N+M)N(N+M)\sqrt N(N+M)N 次增删操作和 MMM 次答案记录操作，这就导致莫队特别适合出一些考察复杂度平衡的题。 P12598 参数要吉祥 别争论扶苏是男的还是女的了，扶苏是一个大语言模型。 由于是非人哉的东西所以可以想到莫队。莫队怎么维护呢？ 首先删除和添加可以很容易地维护出现次数 c 和出现次数出现的次数 cc,但是怎么快速地把每个值不为 0 的 ci×cccic_i\times cc_{c_i}ci ×ccci 抓出来呢？ 暴力显然不现实。所以…… 设分块的大小为 t, 我们先遍历整个数组，把值小于 t(就是 N\sqrt NN ) 的 cic_ici 的值存在一起（这种值最多有 N\sqrt NN 个），另外存储存储满足 ci>tc_i>tci >t 的 i. 因为 c 代表的是一个数出现的次数，而出现次数大于 N\sqrt NN 的数最多只能有 N\sqrt NN 个，所以这部分数的数量最多也是 N\sqrt NN . 随后进入莫队环节，每次移动完区间后遍历这两个表更新答案，每个询问需要 O(N)O(\sqrt N)O(N ) 的时间复杂度，总共 O(MN)O(M\sqrt N)O(MN ), 总体复杂度依然是 O((M+N)N)O((M+N)\sqrt N)O((M+N)N ). Code:Code:Code: P4867 GTY的妹子序列 自行读题。 一眼树套树、 K-D 树、 CDQ 分治，但是假设我们除了莫队什么都不会，因为题目的空间是丧心病狂的 32.00MB（说你呢，丧心病狂的 20MB ＋强制在线的简单题）. 有两个约束条件如何莫队？某个金名金钩的大佬发了篇 O((N+M)NlogN)O((N+M)\sqrt Nlog N)O((N+M)N logN) 的所谓题解，但是这题本意完全不是这样，并且这个做法也只有卡常才能过。 本题如果用 O(1)O(1)O(1) 的时间复杂度单点增加或删除一个数、不大于 O(N)O(\sqrt N)O(N ) 的时间查询一个区间内的答案值就可以维持时间复杂度不变，我们只需要更新 cnt, 增加时如果以前没有这个数就按值域插入一个 1, 删除时如果现在没有这个数就设为 0, 最后移动完区间更新答案时求区间值。那么哪里有这样的 ds? 套值域分块模板即可。 Code:Code:Code: P4396 [AHOI2013] 作业 这题因为没有空间限制所以可以树套树、CDQ 分治、K-D 树。当然也可以从刚才那题的代码上改，新开一个分块存和就行了。2分钟过紫题我进国家集训队吧（其实系复制粘贴上一题然后改） Code:Code:Code: 结语 莫队其实练的还是基础的一些 ds 和做题的思路，比如我就复习了值域分块，学了 bitset 维护莫队等。应该很久之后才会更新了，不过没有树上莫队和莫队二离的话看这一篇足够了。能不能点个赞大佬们QvQ

孔融还小，怎么可能拿动300克的梨？原来孔融之所以是神童是因为他从小就是个肌肉男啊。

现在，屏幕前的你一定会很疑惑，为什么有的大型开源平台没有语言选项，英语不好的人绝对不会用那些开源平台。但是国内的开源平台太少了，而你需要一个国内中文开源平台。 现在，我和我的团队HCE准备开发一个名为stdimHCE的开源平台，来解决这个问题，希望平台建成的那一天你能打开这个网站 TNH，HCE团队 2025.10.29 剧透一下（happy） @几个人出来看看 @Stars_Seeker，@DOG，@54188（（（（官方正版挂壁猴，@Stars_Seeker，@AC君，@‮🐱‍🚀

这道题第一眼没看出来，然后看了一眼题解，32篇几乎只有一种代码 建议AC君查明，把抄袭的删掉

WOC榜10了，感谢各位大佬观看，点赞的全家健康，长命百岁，比赛次次都AK 出了商城功能以后，凡是在我这个帖子里随便发几条评论、点个赞都能拿罐头！ 求官方批准@AC君 求点赞 点个赞吧 求你了求你了求你了求你了求你了求你了求你了求你了求你了 狗友们真是太6了！ 一起冲破榜一 回归正题： 非官方题解 | 嘻哈赛#1题解(C++&PYTHON) 赛纲介绍 本次题目的总体题目难度如下，各位选手可以借此评估一下自身的技术水平 题目编号 题目名称 题目难度 T1 可爱表情 入门 T2 自我介绍 入门 T3 生日祝福 入门 T4 比价格 入门 T1 可爱表情 题目大意： 直接输出5行表情： 解题思路： c++版： 直接用cout输出并换行 python版： 直接用print输出并换行 参考代码 c++版： python版： T2 自我介绍 题目大意： 直接输出3行自我介绍的内容： 解题思路： c++版： 直接用cout输出并换行 python版： 直接用print输出并换行 参考代码 c++版： python版： T3 生日祝福 题目大意： 按照以下固定格式： 注意：标点符号要使用中文标点 解题思路： c++版： 首先定义一个字符串用string和cin输入，在把祝福语和变量连接起来用cout一起输出 python版： 首先input()函数进行输入一个变量，在用printd的固定格式输出(如f格式化输出.....) 注意：标点符号要使用中文标点!!! 参考代码： c++版： python版： T4 比价格 题目大意： 同一本书，比较两家书店的价格，从中找出价格最低的输出那个价格 解题思路： c++版： 首先定义两个整数用int和cin输入，在用cout输出min比较两个数谁大谁小大结果 python版： 首先input()函数进行输入两个整数，在用print输出min比较两个数谁大谁小大结果 参考代码： python版： 团队传送门（你敢不敢加入此团队？） 如果要团队合作，请私信。

最近上洛谷刷了一些题，遇到了一点小困难，希望有大佬来指点 标题为：B3651 [语言月赛202208] 数组调整 这就是题目 写完的代码按照输入输出样例测试也对了，数组开的大小也没问题 但是就是不对，最后五个测试点错了 以下是源代码： 有没有大佬能帮帮忙，小弟在此谢过！

啊啊啊啊啊！！快疯了，好不容易找到一个，结果需要测试点探照灯

ac君，这个人很喜欢抄代码和抄题解，他在欢乐赛也可能抄代码

https://www.luogu.com.cn/problem/P11831 考虑到评测机性能差距，本题较官方赛事增加了 3 秒的额外时限。 我常常追忆过去。 生命瞬间定格在脑海。我将背后的时间裁剪、折叠、蜷曲，揉捻成天上朵朵白云。 云朵之间亦有分别：积云厚重，而卷云飘渺。生命里震撼的场景掠过我的思绪便一生无法忘怀，而更为普通平常的记忆在时间的冲刷下只留下些许残骸。追忆宛如入梦，太过清楚则无法愉悦自己的幻想，过分模糊却又坠入虚无。只有薄雾间的山水，面纱下的女子，那恰到好处的朦胧，才能满足我对美的苛求。 追忆总在不经意间将我裹进泛黄的纸页里。分别又重聚的朋友，推倒又重建的街道，种种线索协助着我从一个具体的时刻出发沿时间的河逆流而上。曾经的日子无法重来，我只不过是一个过客。但我仍然渴望在每一次追忆之旅中留下闲暇时间，在一个场景前驻足，在岁月的朦胧里瞭望过去的自己，感受尽可能多的甜蜜。美好的时光曾流过我的身体，我便心满意足。 过去已经凝固，我带着回忆向前，只是时常疏于保管，回忆也在改变着各自的形态。这给我的追忆旅程带来些许挑战。 我该在哪里停留？我问我自己。 题目描述 给定一个 n 个点 m 条边的有向图 G，结点由 1 至 n 编号。第 i (1≤i≤m) 条边从 u i 指向 v i ，保证 u i <v i 。节点 j (1≤j≤n) 有两个权值 a j ,b j ，保证 [a 1 ,…,a n ] 与 [b 1 ,…,b n ] 均是 1∼n 的排列。 你需要进行 q 次操作。操作有以下三种： 1 x y：交换 a x 和 a y ； 2 x y：交换 b x 和 b y ； 3 x l r：你需要输出满足以下两个条件的点 y 中 b y 的最大值，若不存在满足条件的点则输出 0： l≤a y ≤r。 图 G 中存在一条 x 到 y 的有向路径，即存在整数 k≥1 与 k 个结点 p 1 ,p 2 ,…,p k ，满足 p 1 =x，p k =y，且对于所有 1≤i<k，图 G 中存在从 p i 指向 p i+1 的有向边。特别地，图 G 中总是存在一条 x 到 x 的有向路径。 输入格式 本题有多组测试数据。输入的第一行两个整数 c,T，分别表示测试点编号和测试数据组数，接下来输入每组测试数据。样例满足 c=0。 对于每组测试数据， 第一行三个整数 n,m,q，分别表示图 G 的节点数、图 G 的边数和操作次数， 接下来 m 行，第 i (1≤i≤m) 行两个整数 u i ,v i ，描述一条边， 接下来一行 n 个整数 a 1 ,a 2 ,…,a n ，描述每个节点的 a 权值， 接下来一行 n 个整数 b 1 ,b 2 ,…,b n ，描述每个节点的 b 权值， 最后 q 行，第 i (1≤i≤q) 行三或四个整数 o i ,x i ,y i 或 o i ,x i ,l i ,r i ，描述一次操作，格式同题目描述。 输出格式 对于每个 3 操作输出一行一个整数，表示对应操作的答案。 输入输出样例 输入 #1复制 0 1 4 4 7 1 2 1 3 2 4 3 4 4 2 3 1 1 3 2 4 3 2 1 3 3 3 2 4 1 1 4 3 1 1 3 2 2 4 3 1 2 3 3 4 1 1 输出 #1复制 4 2 3 4 0 说明/提示 【样例 1 解释】 该组样例共有 1 组测试数据。该组测试数据共包含 7 个操作。 对于第一个操作，所有满足条件的点为 2,4，因此答案为 max{b 2 ,b 4 }=4。 对于第二个操作，所有满足条件的点为 3，因此答案为 b 3 =2。 对于第三个操作，交换 a 1 ,a 4 后得到的权值序列 a 为 [1,2,3,4]。 对于第四个操作，所有满足条件的点为 1,2,3，因此答案为 max{b 1 ,b 2 ,b 3 }=3。 对于第五个操作，交换 b 2 ,b 4 后得到的权值序列 b 为 [1,4,2,3]。 对于第六个操作，所有满足条件的点为 2,3，因此答案为 max{b 2 ,b 3 }=4。 对于第七个操作，没有满足条件的点，因此答案为 0。 【样例 2】 见选手目录下的 recall/recall2.in 与 recall/recall2.ans。 该组样例满足测试点 1∼5 的限制。 【样例 3】 见选手目录下的 recall/recall3.in 与 recall/recall3.ans。 该组样例满足测试点 7 的限制。 【样例 4】 见选手目录下的 recall/recall4.in 与 recall/recall4.ans。 该组样例满足测试点 10∼12 的限制。 【样例 5】 见选手目录下的 recall/recall5.in 与 recall/recall5.ans。 该组样例满足测试点 13,14 的限制。 【样例 6】 见选手目录下的 recall/recall6.in 与 recall/recall6.ans。 该组样例满足测试点 18 的限制。 【样例 7】 见选手目录下的 recall/recall7.in 与 recall/recall7.ans。 该组样例满足测试点 23∼25 的限制。 【子任务】 对于所有测试点， 1≤T≤3， 1≤n,q≤10 5 ，1≤m≤2×10 5 ， ∀1≤i≤m，1≤u i <v i ≤n， ∀1≤i≤n，1≤a i ≤n，且 [a 1 ,…,a n ] 是 1∼n 的一个排列， ∀1≤i≤n，1≤b i ≤n，且 [b 1 ,…,b n ] 是 1∼n 的一个排列， ∀1≤i≤q，o i ∈{1,2,3}，1≤x i ,y i ≤n，1≤l i ≤r i ≤n。 测试点编号 n,q≤ m≤ 特殊性质 1∼5 2000 4000 无 6 8×10 4 1.6×10 5 AB 7 6×10 4 1.2×10 5 B 8,9 8×10 4 1.6×10 5 10∼12 AC 13,14 6×10 4 1.2×10 5 A 15,16 8×10 4 1.6×10 5 17 6×10 4 1.2×10 5 D 18 8×10 4 1.6×10 5 19,20 6×10 4 1.2×10 5 无 21,22 8×10 4 1.6×10 5 23∼25 10 5 2×10 5 特殊性质 A：∀1≤i≤q,o i  =1。 特殊性质 B：∀1≤i≤q,o i  =2。 特殊性质 C：∀1≤i≤q,l i =1,r i =n。 特殊性质 D：保证在每个 3 操作的时刻，∀1≤i≤n,a i =b i 。 【提示】 请注意本题特别的时空限制。 附件下载 recall.zip 25.30MB

之前的题目做出来了（也因为比较“水”所以删了） 补充一下题目： 蓝题也许不水了吧（但愿是这样）

null

本篇包含树上主席树、可持久化并查集、CDQ 分治套 CDQ 分治、CDQ 分治优化 DP 等内容，例题都是知识点的进阶，请在知识点基础上学习。 第一篇 第二篇 该系列已加入洛谷保存站大套餐。 第三部分（续） 2.树上主席树模板 P2633 Count on a tree 不用看题，树上链第 kkk 小。 这道题乍一看又像是树链剖分又像是主席树。 实际上是一道极好的主席树例题，可以先想5分钟正解。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 欢迎回来。 其实很简单。看到是离线就知道不能树上整体二分，考虑主席树。注意到主席树是一种“可加”的数据结构，可以通过差分和前缀和计算区间，对于树上链条要怎么计算前缀和？将新版本的权值线段树建立在父亲节点的树上即可，计算时使用树上差分，将 uuu 版本的节点值加 vvv 版本的节点值再减去 LCA(u,v)LCA(u,v)LCA(u,v) 版本的节点值和 faLCA(u,v)fa_{LCA(u,v)}faLCA(u,v) 版本的节点值即可得到链上的权值线段树某个节点的节点值。其它的按照标准的主席树差分求第 kkk 小值编码即可。还是能用到树链剖分，不过是用来求 LCA 的（LCA 肯定是树剖最快啊，怎么会有人用树上倍增呢）。代码中在 dfs1 中建主席树的版本。 Code:Code:Code: 时间复杂度： O((M+N)logN))O((M+N)logN))O((M+N)logN)) 3.P2468 [SDOI2010] 粟粟的书架 还是有一定难度的。 这次没写最优解主席树，而是写了整体二分（没忍住）。 标准做法是当作二合一题做，后半是主席树二分的模板，索引为从大到小排序的书本厚度，二分需要拿的最薄的书籍，如果左节点足够厚就递归左节点，否则递归右节点。前半部分大部分题解用了毫无美感（暴论）的二维前缀和+二分，枚举权值 ppp，维护 (1,1)(1,1)(1,1) 到 (i,j)(i,j)(i,j) 的矩阵大于等于 kkk 的数的总和以及这个矩阵中大于等于 kkk 的数的个数并二分，利用 0≤pi,j≤10000\leq p_{i,j}\leq 10000≤pi,j ≤1000 的特殊性质用 O(RCmax{pi,j})O(RCmax\{p_{i,j}\})O(RCmax{pi,j }) 的时间复杂度卡过第一问，也有一些神犇优美地用二维差分主席树解掉达到所有点 O(RClog2(RC))O(RClog_2(RC))O(RClog2 (RC))的时间复杂度，值得学习👍。 但是我们不用主席树。注意到这题和国家集训队的矩阵乘法那题很像，可以从厚到薄排序然后用整体二分解决。只需要在整体二分中累加答案即可，分到右组时加上需要添加的书籍数量，甚至不用写两份代码，准备两个大小不同的树状数组即可。注意整体二分的二分与一般二分不同，找第一个不符合的值域（或下标）时要特判，如图： 时间复杂度每个点都是 O(RClog2(RC))O(RClog^2(RC))O(RClog2(RC)). Code:Code:Code: 4.水题：P7424 [THUPC 2017] 天天爱射击 肥肠简单，请先自行构思。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 如果把每个子弹当作询问的话，处理射击后的每个木板的状况会很麻烦。考虑整体二分，综上所述只能把木板当作询问，直接二分第几发子弹射出后木板破碎，这就在树状数组的解决范围内了，统计对每个木板来说 midmidmid 发子弹发出后有多少打在这个木板区间内即可 check.最后确定答案时，把贡献算在最后这发打坏木板的子弹上就行了。小 Trick: 整体二分时将值域加一，这样完成不了的询问就会落在值域加一的答案区间，这题中可以将这些答案忽略掉因为加到第 m+1m+1m+1 个子弹的答案不算数（只有 mmm 发）不会输出。 Code:Code:Code: 时间复杂度： O((N+M)log2M)O((N+M)log^2M)O((N+M)log2M) 5. 一道毒瘤来啦！ P9175 [COCI 2022/2023 #4] Mreža 依旧 COCI. 自行看题。 有不同做法，这里采用时间复杂度最优的算法。可以使用 P2633 的树上主席树技巧，转化为树上主席树二分。首先将 viv_ivi 和 sis_isi 共同离散化（就是因为一不小心离散化了两个后面才没 WA,纯运来的，实际上这一步不是必要的）以 viv_ivi 为下标建立权值线段树，叶子节点值为 cic_ici ,维护每个 viv_ivi 区间的 cic_ici 总和，如果预算够就往右递归，否则往左递归。除此以外，单独计算链上 sis_isi 最小值，取这两个答案的最小值即可。 可以用树上 ST 表求解链上最小值，设 fai,ufa_{i,u}fai,u 为节点 uuu 向上 2i2^i2i 个祖先，sti,ust_{i,u}sti,u 为从节点 uuu 向根节点延伸的长度为 2i2^i2i 的链上的最小值，有： sti,u=min(sti−1,u,sti−1,fai−1,u)st_{i,u}=min(st_{i-1,u},st_{i-1,fa_{i-1,u}}) sti,u =min(sti−1,u ,sti−1,fai−1,u ) 区间的合并如图所示： 然后像倍增 LCA 一样先让低的跳，如果一个是另一个的祖先就返回，否则一起跳，跳到 LCA 的下一层，最后再跳 LCA 这层即可。 时间复杂度：O((n+q)log2n)O((n+q)log_2n)O((n+q)log2 n) 目前无特意卡常跑进除隐私保护外第6优解，但是离散化了还没跑过卡常+没离散化的某篇题解，之所以题解可以不用离散化是因为主席树动态加点只会给 update 过的节点开空间，其它空间不会浪费，因此空间开到 O(nlog2V)O(nlog_2V)O(nlog2 V) 即可。 Code:Code:Code: 6.P3402 【模板】可持久化并查集 这题很罕见地考模板不强制在线，导致题解区有很多离线的 O(Nlog2N)O(Nlog_2N)O(Nlog2 N) 做法，如果想练习可持久化并查集请自觉 （不是）。 首先，可持久化数据结构不可以用任何均摊，所以合并不能使用路径压缩，可以用时间复杂度稳定为单次 O(log2N)O(log_2N)O(log2 N) 的按秩合并进行合并。按秩合并采用高度法，将高度小的数作为高度大的树根的儿子。用主席树维护 fa 数组和 dep 数组的更改。注意这里一次修改要开两条链，一条连向 fa 更新的叶子节点一条连向 dep 更新的叶子节点，因为按秩合并时 fa 头儿子 dep 头爸爸。每次修改都进行一次主席树操作，时空复杂度 O(Nlog2N)O(Nlog^2N)O(Nlog2N). Code:Code:Code: 各种函数意义看英文字面意思。pos 函数是辅助按秩合并的，它返回某个版本第 k 个元素在动态开点的主席树内的编号。 CDQ 分治进阶 7.P3769 [CH弱省胡策R2] TATT 直到做完这道题都不知道题目是什么意思 四维空间最长上升子序列。需要 CDQ 分治套 CDQ 分治和 CDQ 优化 DP 的技巧。 这里先说 CDQ 的顺序。对于 cdq2 函数，定义 cdq2(l,r) 意为计算 [l,mid][l,mid][l,mid] 区间对 [mid+1,r][mid+1,r][mid+1,r] 区间元素的贡献。按照 DP 从左到右的顺序，先分治左半部分的区间，计算好左半部分的答案，再计算左半部分对右半部分的贡献，最后分治右半区间计算右半部分内部互相的贡献。DP 计算用树状数组即可。 但是这是四维空间，要怎么用 CDQ 分治呢？可以用 CDQ 套 CDQ，一个 CDQ 解决第二维，嵌套另一个 CDQ 解决第三维。先回顾三维 CDQ:排序解掉第一维，左右子区间内部排序确保有序性然后双指针解决第二维，数据结构解决第三维。四维时如何确保第一维的有序性？注意到永远是第一维小的向第一维大的元素贡献答案， 可以在第一个 CDQ 中先计算左区间，然后（此时左边的第一维比右边的小）把左边的所有元素打上标记0，右边的打上1，再排序第二维，进入 cdq2,cdq2 中先计算左组，再将左右分别按第三维排序，双指针遍历，左区间该元素的标记为0则插入树状数组，右区间该元素的标记为1则计算答案，（所有被打上0的元素第一维都比所有打上1的小）完事清理树状数组并将右区间按第二维排序递归计算右区间。 于是能过矣。 注意到当双指针过后，DP 的值受到改变，树状数组清除时不知道该减去多少，不过插入树状数组的位置（第四维度的值）还存着，对于每个位置，树状数组把这个位置的数直接设为0即可。由于每次是计算区间 [1,x][1,x][1,x] 的 DP 最大值，树状数组是可以的。 时间复杂度：O(Nlog3N)O(Nlog^3N)O(Nlog3N) 记得依旧查重。 Code:Code:Code: 8.P4849 寻找宝藏 比较难的题。 CDQ 套 CDQ 的部分不讲了（这里给出的 CDQ 代码略有不同，不过意思是一样的，自己想），我们来讲讲 DP. 下文的长度表示最长上升子序列长度。计算 iii 结尾的方案数，我们遍历 jjj 符合条件的 dpjdp_jdpj 值，如果 iii 目前的最长子序列长度小于 jjj 计算的长度值，将 iii 的最长子序列长度和方案数设为当前 jjj 的值（很好理解），如果恰好相等，说明又有一种方法达到当前的 dpidp_idpi 值，将方案数加上当前遍历元素的方案数（也很好理解）。树状数组计算时也按这个思路统计答案，最后直接返回计算到的答案，修改时如果当前位置的长度小于插入值的长度就设其为插入值的长度，相等则累加方案数。为什么正确？DP 式中需要的是长度的最大值，由于树状数组每个元素存储的是一个区间内的元素信息，可以把不同区间的答案合并。 时间复杂度： O(Nlog3N)O(Nlog^3N)O(Nlog3N) Code:Code:Code: 9.P5621 [DBOI2019] 德丽莎世界第一可爱 毒瘤，和上题差不多，只不过值域有负数和零。查重和树状数组的部分有不同，答案初始是 -INF，并取 sz 的最大值；去重合并同类项时如果贡献是负数就不累加；树状数组初始化和删除是 -INF.时间复杂度懒得打了一模一样。 10.P2487 [SDOI2011] 拦截导弹 前一问和寻找宝藏差不多，只不过是三维的。注意树状数组要统计更大值（看题！），所以树状数组的索引用 m−aiv+1m-a_{i_v}+1m−aiv +1.双指针的判断部分也是反的。 第二问：反着计算最长上升子序列长度和方案数。将 ididid 和 aiva_{i_v}aiv 倒过来，aiha_{i_h}aih 取相反数然后再跑一遍 CDQ 就行了。接下来可以把值域这样把两个答案并在一起（加在一起再减去重复计算的当前元素，也就是说-1），如果等于全局最长上升子序列长度就说明是方案的一部分，两个答案的方案数相乘即是贡献的方案数，最后除以全局最长上升子序列的方案数得到概率；否则输出0（不在最优方案中）。O(Nlog2N)O(Nlog^2N)O(Nlog2N). Code:Code:Code: ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 大抵不会再更新了。

用的空间在6MB以内，不过还没有到极限

LaTeX数学公式的常用语法讲解传送门 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ Markdown是一种轻量级标记语言，用于格式化纯文本，本文为Markdown的一些常用语法讲解。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 标题： 使用#符号来创建标题，1个#代表一级标题，2个#代表二级标题，以此类推，最多支持六级标题。 效果： 一级标题 二级标题 三级标题 四级标题 五级标题 六级标题 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 强调和斜体和划线： 使用*包围文本以实现斜体效果，使用**包围文本以实现加粗效果，使用~~包围文本以实现加粗划线效果。 效果： 斜体文本 加粗文本 划线文本 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 链接： 创建链接使用[],()。[]中放置链接文字，()中放置链接地址。 效果： 点击这里百度一下 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 图片： 插入图片使用!,[],()。[]中放置替代文字，()中放置图片链接。 效果： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 列表： 无序列表使用-,+,*开头，有序列表使用数字 +.。 效果： * 无序列表项 * 无序列表项 1. 有序列表项 2. 有序列表项 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 引用： 使用>来创建引用块，可以引用叠引用。 效果： > 这是引用的内容 > > > 这也是引用的内容 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 代码块： 用三个反引号`包围代码块，后面可以跟着一个语言名称来指定代码块的语言，以便语法高亮。 记得去掉\。 效果： 一个反引号`可以作为单行代码块。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 水平分隔线： 使用三个或更多连续的*来创建水平线。 效果： ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 表格： 表格由表头和表格内容组成，使用|,-来分隔不同的行列，下面是一个简单的表格示例： 使用|来分隔每一列，而使用-在表头下创建分隔线。表头是必需的，它定义了每一列的标题。 效果： 标题1 标题2 标题3 内容1 内容2 内容3 内容4 内容5 内容6 希望表格的内容居中或靠右对齐，可以使用:来指定对齐方式，例如： 输出结果如下： ---左对齐--- ---居中对齐--- ---右对齐--- 内容1 内容2 内容3 内容4 内容5 内容6 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 脚注： 在文本中需要添加脚注的位置，使用[^]来标记脚注的引用标记，方括号内可以填写任何标识符，通常是数字例如[^1]。 在文档的末尾，添加一个相匹配的脚注内容，使用[^]: 内容的形式来定义脚注内容。例如[^1]: 这是脚注的内容。 下面是一个示例： 结果： 这是一个示例[1]，在文末可以看到脚注的解释。 脚注会显示在全文的最下面，请到最底部查看脚注。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 数学公式： 单个$用于表示行内数学公式或数学表达式，用于排版数学符号、方程式、上下标、分数等数学内容，他的使用通常与LaTeX\LaTeX{}LATE X数学语法相对应，因为Markdown支持一些LaTeX\LaTeX{}LATE X的数学语法，例如： 效果： y=mx+by = mx + by=mx+b 两个$用于表示多行数学公式或数学表达式，例如： 效果： n!k!(n−k)!=(nk)\frac{n!}{k!(n-k)!} = \binom{n}{k} k!(n−k)!n! =(kn ) 数学公式里，^,_用于表示上标与下标，后面可以用括号包括进一大串数字与字母 效果： ai+j+bja^{i+j}+b_{j}ai+j+bj ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 以上是Markdown的常用语法讲解，欢迎评论讨论。 评论区用不了Markdown，题目，团队介绍能用，忘记说了赶紧补充 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 1. 这是脚注的内容，用于解释示例的含义。 ↩︎

无敌了，居然是2008年的题

🔍 一、深入题目解析：抓住本质 ✅ 题目在问什么？ 视为一个水坑”，而“相连”定义为八连通（8-directional）：即一个格子可以和它上、下、左、右、左上、右上、左下、右下共8个方向的格子连通。 所以—— 🔹 每个 'W' 是潜在水坑的“候选单元”； 🔹 若若干 'W' 通过八连通路径彼此可达（中间全为 'W'），它们就属于同一个水坑； 🔹 我们要统计的是：这样的极大连通 'W' 子图的个数 → 即 无向图（Connected Components）的数量。 💡 类比思考：这就像地图上的岛屿——海水是 '.'（不可通行），陆地是 'W'（可通行），八连通=你可以斜着走（比如从(0,0)能走到(1,1)）。问：一共有几个孤岛？ ✅ 样例验证（动手标一标！） 请拿出草稿纸，把样例的10×12网格画出来（哪怕只画前3行），然后： 用不同颜色/数字标记出你认为属于同一水坑的 'W'； 特别注意：第2行 "WWW" 和第1行末尾的 "WW" 是否连通？→ 看位置：第1行末尾是 (0,9) 和 (0,10)，第2行开头是 (1,1)，但 (0,10) 和 (1,11) 是相邻的（右下），而 (1,11) 正是 'W'！再看 (1,10) 也是 'W'…… → 这提示我们：不能凭直觉跳着连，必须严格按坐标差 ≤1 来判断八连通。 ✅ 所以难点之一浮现了： ⚠️ 八连通 ≠ 四连通！很多同学习惯性只上下左右走（四向BFS/DFS），会漏掉斜线连接，导致水坑被错误拆分成多个 → 输出偏大。 🧭 二、系统解题指导：分步构建解法 我们把问题拆成可执行的、信奥人熟悉的步骤： ▶ 步骤1：建模 —— 把网格变成“图” 每个 'W' 格子是一个顶点； 如果两个 'W' 格子八连通（即横纵坐标差的绝对值都不超过1，且不同时为0），就连一条无向边； 但我们不需要真的建邻接表！因为网格结构规则，我们可以现场计算邻居。 ▶ 步骤2：遍历所有可能起点 枚举每个格子 (i, j)： 如果 grid[i][j] == 'W'，且尚未访问过 → 发现一个新水坑！计数器 ans++； 然后从 (i, j) 出发，把所有与它八连通的 'W' 全部标记为“已访问”（防止重复计数）。 ▶ 步骤3：如何“把所有连通的 'W' 标记完”？→ 两种经典策略（你选一个深入！） 方法 核心思想 信奥要点 DFS（深度优先搜索） 递归/栈：从起点出发，每到一个 'W'，立刻向8个方向递归探索 ✅ 简洁，但注意：N,M≤100 → 最坏情况10⁴格子，递归深度可能达10⁴ → 可能爆栈（C++默认栈小！）→ 需考虑手动栈 or 改用BFS BFS（宽度优先搜索） 队列：逐层扩展，每次取出队首，检查8邻，是 'W' 且未访问就入队 ✅ 更安全，天然避免深递归；适合初学者掌握队列操作（queue<pair<int,int>>） 🌟 关键提醒：无论DFS/BFS，访问标记必须及时！ ❌ 错误做法：进队/进栈时标记 → 可能导致同一格子被多次加入（因多个邻居同时发现它）； ✅ 正确做法：刚取出/刚访问到该格子时，立即标记 vis[i][j] = true（或直接把 'W' 改成 '.' —— 原地修改法，省空间！但要注意题目是否允许修改原数组）。 ▶ 步骤4：八连通方向怎么写？ 定义方向数组（这是信奥必备技巧！）： int dx[8] = {-1, -1, -1, 0, 0, 1, 1, 1}; int dy[8] = {-1, 0, 1, -1, 1, -1, 0, 1}; // 对应：↖ ↑ ↗ ← → ↘ 然后循环 for(int k=0; k<8; k++)，新坐标 nx = i + dx[k], ny = j + dy[k]，再判断是否在 [0,N)×[0,M) 范围内，且 grid[nx][ny]=='W'。 📚 三、信奥知识聚焦：这些你必须掌握 知识点 为什么重要？ 如何巩固？ 连通块（Connected Component）模型 是图论最基础应用之一，后续拓展到洪水填充（flood fill）、岛屿数量、棋盘染色等 ✨ 动手改题：如果改成“四连通”，答案变多少？再改成“只允许上下左右+不能斜走”，重新跑样例 BFS/DFS 的框架与边界处理 NOIP常考模板级实现；本题虽简单，但方向数组、越界判断、访问标记顺序是高频扣分点 ✍️ 默写BFS模板队列+vis标记），对照标准库 queue 和 pair 用法 空间与效率意识 N,M≤100 → 总格子≤10⁴，O(NM)算法完全可行；但若写成O(N²M²)暴力连边就会超时 💡 提问自己：我的算法时间复杂度是多少？有没有重复扫描？ 输入输出细节 字符间无空格 → cin >> grid[i] 可直接读整行字符串；注意 string 下标从0开始，别混淆行列 🧪 小实验：用 cout << grid[0][0] << endl; 打印第一字符，确认读取正确 ✨ 最后，给你一个「思考阶梯」任务（请务必动手！） 画图实践：在纸上画出样例的前3行（10×12太长，取局部），标出所有 'W'，用箭头手动连出一个水坑（比如左上角那个），数一数它包含几个 'W'； 伪代码演练：不写C++，用中文写出BFS主流程（从“找到第一个W”开始，到“标记完整个连通块”结束）； 方向数组验证：写出 (0,0) 的8个邻居坐标，确认 dx/dy 数组是否真能覆盖全部； 边界陷阱自查：如果当前在 (0,0)，尝试 dx[0]=-1, dy[0]=-1 → (−1,−1)，此时不合法！你的代码如何避免越界访问？（提示：加 if(nx >= 0 && nx < N && ny >= 0 && ny < M)） 当你完成以上思考，并尝试写出初步代码（哪怕有bug也没关系！），欢迎随时带着你的代码片段 + 你卡在哪一步 + 你观察到的现象（比如输出是5不是3） 来找我。我会帮你逐行分析逻辑，而不是告诉你“哪里错了”，而是问你：“如果这个格子是 'W'，下一步它应该去哪几个位置？你检查过这几个位置了吗？” 记住：信奥高手不是背算法的人，而是能把抽象问题‘翻译’成计算机可执行步骤的人。 你现在已经在翻译的路上了 🌟

他告诉我： 这是一个非常有趣的题目，涉及到图论、深度优先搜索（DFS）和区域判断等概念。首先，让我们来深入解析一下题目： 理解定义：确保你理解了什么是山谷、边缘连续、点状连续、区域、洞穴和边界。这些定义是解决问题的基础。 输入解析：题目提供了一个 N×N 的网格，每个单元格都有一个高度。你需要处理这个输入，并找到所有的山谷。 关键算法：你可以使用DFS来遍历这个网格。当你遇到一个单元格时，检查它是否是一个山谷的开始。如果满足以下条件，可以认为它是山谷的一部分： 它的邻居（上、下、左、右）都比它高。 当你继续沿着DFS搜索时，确保所有相邻的单元格都是山谷的一部分，且没有洞穴（即，从任何山谷内的单元格出发，都可以到达其他所有山谷内的单元格，而不需要穿过边界或更高高度的单元格）。 计数和更新：在DFS过程中，当你找到一个山谷时，计数器加一。同时，记录下山谷的大小（即山谷内单元格的数量）。 输出：最后，将所有山谷的大小相加，得到的结果就是你要找的总和。 解题步骤可以这样设计： 读取输入，创建一个表示网格的二维数组。 遍历网格中的每个单元格，用DFS检查它是否是山谷的起点。 如果是山谷，进行DFS遍历并计算山谷的大小。 更新总山谷大小的计数。 输出总山谷大小。 在实现过程中，注意边界条件的处理，比如当移动到边界之外时。此外，为了避免重复计数，可以在访问过的单元格上标记，确保每个山谷只被计数一次。 现在，试着根据这些思路自己编写代码。如果在实现或测试过程中遇到问题，再向我询问具体的细节。记住，实践是检验理解和学习效果的最好方式。祝你好运！ 好像知道思路了，又好像没知道。。。