2026/6/1
P1422 小玉家的电费
P1424小鱼的航程
P1888三角函数
P1046陶陶摘苹果
P4414 ABC
P1055 ISBN
P5718 最小值
P2866 单调栈例题
单调栈就是内部具有单调性的栈。可以解决”求取以某一个值为最值的最大区间“的问题。
虽然说是“栈”，但是只是运用栈的模式，本质上是可以用数组进行模拟的。
本题中，我们要求去“一头牛能看见多少头别的牛”的问题，我们将它转换成“一头牛能够被多少别的牛看到”。因为牛都往右边看，所以我们需要计算的是，“一头牛的左边有多少头比它高的牛”。
我们需要维护一个递减（严格递减，不是不增）的栈，将c[i]c[i]c[i]放到栈顶之前，将所有比它小的全部移走。最后的答案就是每一次移走完，放入前栈中元素的数量。
另外：极端情况下，最终答案数量会达到n2n^2n2，记得开long long 。
P1950 长方形
题目大意：
想在一张由n∗mn*mn∗m个格子组成的长方形纸片上裁剪出长方形。
有以下要求：1.只能沿着格子的边缘剪（注意这里说的不是长方形纸片的边而是格子的边，意思就是要沿着格子剪） 2.剪出的长方形不能包含∗*∗ 3.长方形没有大小限制
现在想问问有多少种裁剪的方法。
这道题让我想起了玉蟾宫。有点点相似。
一行一行地去统计三个数组：h,l,rh,l,rh,l,r
（只统计...格子，不统计∗*∗格子）。
hhh存放当前格子和上方的第一个∗*∗格子的距离（即能拓展的高度）。
lll存放当前格子左边第一个hhh数值的小于等于自己的格子。rrr存放当前格子右边第一个hhh数值小于自己的格子。（注意这里说辞的差距，l是小于等于，r是小于。这是为了防止重复统计，所有的格子只往右边拓展）
依据乘法原理，截至当前这一行，包含当前格子且受hhh高度限制的长方形的数量为h∗(i−l[i])∗(r[i]−i)h*(i-l[i])*(r[i]-i)h∗(i−l[i])∗(r[i]−i)。
最后就是时间复杂度的问题了。如果暴力求取总时间复杂度为O(n3)O(n^3)O(n3)，会超时。
此时我们可以用单调栈来优化寻找“寻找在自己左边hhh值第一个小于等于自己的数”的操作。时间复杂度就会优化到O(n2)O(n^2)O(n2)，可以写了。
另外：记得开long long。
P5719 分类平均
P5720 砍半
P5721 数字三角形
P1980 数字统计
2026/6/2
P10112 [GESP202312 八级] 奖品分配
题目大意：
nnn名同学，学号从000到n−1n-1n−1。有mmm种奖品，第i中奖品总共有a[i]a[i]a[i]个。
每位同学都可以恰好分到一个奖品，最最后剩余的奖品不超过111个。
要求求出每个班级礼物分配的方案数对109+710^9+7109+7取模后的结果。
前情提要：排列与组合
1.排列 ：从nnn个不同元素中，取出mmm个按顺序排列（也就是关注每个被取出来的元素在哪个位置）。记作AnmA^m_nAnm 。（我觉得可以这么记：nnn大mmm小，nnn在下(位置比较像分母)mmm在上（位置比较像分子），母比子大，所以是从nnn个元素中挑选mmm个元素（即从下面的数中挑选上面数的个数））。
可以看成一个有mmm个坑，nnn个萝卜，要把萝卜塞进坑里。每塞一个，下一个坑的选项就少一个。
公式：Anm=n(n−1)(n−2)∗...∗(n−m+1)=n!(n−m)!A_n^m=n(n-1)(n-2)*...*(n-m+1)=\frac{n!}{(n-m)!}Anm =n(n−1)(n−2)∗...∗(n−m+1)=(n−m)!n!
规定：0!=10!=10!=1
2.组合：从nnn个不同元素中，取出mmm个不考虑顺序排成一组。记作CnmC_n^mCnm 。
如果说前面是要塞萝卜进坑，那么现在就是要从nnn个坑里拔mmm个萝卜，然后堆在一起，不记顺序。
公式：***=AnmAmm=n!m!(n−m)!C_n^m=\frac{A_n^m}{A_m^m}=\frac{n!}{m!(n-m)!}*** =Amm Anm =m!(n−m)!n!
来源：Anm=***∗AmmA_n^m=C_n^m*A_m^mAnm =*** ∗Amm （从nnn个东西中选取出来mmm个并且排序（即要求顺序）的方案数=从nnn个东西中选出mmm个的方案数∗*∗给mmm个物品排序的方案数）
其他：
***=Cnn−mC_n^m=C_n^{n-m}*** =Cnn−m （计算出来其实是一样的：n!m!(n−m)!=n!(n−m)!(n−n+m)!\frac{n!}{m!(n-m)!}=\frac{n!}{(n-m)!(n-n+m)!}m!(n−m)!n! =(n−m)!(n−n+m)!n! ）
Cn0=CnnC_n^0=C_n^nCn0 =Cnn （常识形问题。不过你也可以选择计算，反正算出来是一样的。）
Cn−1m+Cn−1m−1=CnmC_{n-1}^m+C_{n-1}^{m-1}=C^m_nCn−1m +Cn−1m−1 =*** (这个不建议死记硬背。可以这样记：从nnn个数里选mmm个，第一个可以选也可以不选。第一个选了，那么就是从后面的n−1n-1n−1个中选取m−1m-1m−1个。第一个没有选，那么就是从后面的n−1n-1n−1个中选取mmm个。两个加在一起就是完整的方案了)
接下来关于本题内容来自CleverRaccon的题解。如果你们真的对本题有疑问，还是去看这个题解吧，TA写的更好。后续的内容本质是我用来给自己理解写的。
本题需要两层理解：
1.需要用到排列组合且组合需要初始化
可以将本题看作是往nnn个坑（小朋友）里放mmm个萝卜（礼物）。第iii个礼物有Cn−∑j=1i−1a[j]a[i]C_{n-\sum_{j = 1}^{i-1}a[j]}^{a[i]}Cn−∑j=1i−1 a[j]a[i] 种摆放方案。
所有的拜访方案就是将从111到nnn所有的拜访方案乘起来（乘法原理）。
2.空气领奖位
注意到总奖品的个数可能是nnn但也可能是n+1n+1n+1。我们可以把多出来的那个奖品看作发给了
空气。如果奖品总数是n+1n+1n+1我们就可以设置一个空白领奖位（初始人数+1）。
另：方案数（比如组合数排列数）一定要开long long。
P1888 三角函数（重做）
P4414 ABC（重做）
P1950 长方形（重做）
P8218 一位前缀和例题
前缀和可以用来求取区间和，而差分可以用来做区间修改操作。
P2367 一维差分模板
P1719 二维前缀和例题
这道题目有两种做法。一种O(n4)O(n^4)O(n4)，一种 O(n3)O(n^3)O(n3).
法一：O(N4)O(N^4)O(N4)
二维前缀和和以为前缀和其实差不多。
s[i][j]s[i][j]s[i][j]的定义是从a[1][1]a[1][1]a[1][1]到a[i][j]a[i][j]a[i][j]所有数值加起来的和。
公式：s[i][j]=s[i−1][j]+s[i][j−1]−s[i−1][j−1]+a[i][j]s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j]s[i][j]=s[i−1][j]+s[i][j−1]−s[i−1][j−1]+a[i][j]
(x1,y1)(x_1,y_1)(x1 ,y1 )到(x2,y2)(x_2,y_2)(x2 ,y2 )的和=s[x2][y2]−s[x2][y1−1]−s[x1−1][y2]+s[x1−1][y1−1]s[x_2][y_2]-s[x_2][y_1-1]-s[x_1-1][y_2]+s[x_1-1][y_1-1]s[x2 ][y2 ]−s[x2 ][y1 −1]−s[x1 −1][y2 ]+s[x1 −1][y1 −1]
注：x1，y1，x2，y2x_1，y_1，x_2，y_2x1 ，y1 ，x2 ，y2 之间是有大小关系的。
2026/6/3
法二：O(N3)O(N^3)O(N3)
O(n^3)方法前置知识点
优化的方式是：枚举i,ji,ji,j。枚举上边界为第iii行，下边界为第jjj行的最大矩形。第一层循环遍历iii，第二层循环遍历jjj，第三层循环遍历kkk。kkk枚举列。
P2367 一维差分（重做）
P1950 长方形
6/1做过的题目。这边来提一个比较容易弄错的点。
正确的代码：
错误的代码：
在写代码的时候，可能会认为加上一条continue是无关紧要的。并且还减小时间复杂度。但是如果加上continue代码就是错的。这是因为在正常不加的时候，st是会有变化的。
当有一行是这样**..的时候，第三个字符的lll数值应该是222。但是如果直接continue，那么值就会变成000，最后算ans的时候就会算错。
B - Two Rings
这道题主要考察的是数学知识。在平面直角坐标系中，圆C1C_1C1 的半径是R1R_1R1 ，圆C2C_2C2 的半径是R2R_2R2 。当两个元存在公共点∣R1−R2∣≤|R_1-R_2|\le∣R1 −R2 ∣≤ 两圆圆心的距离 \leR_1+R_2。
由于精度问题。我们可以把它们都算成平方。不过平方一定要开long long。
公倍数问题
打暴力可以获得50pts50pts50pts：
接下来我的称述内容大部分来自superballll的题解。如果你真的对本题有疑问，建议直接去看这位同学的题解。TA的思路妙极了。
本题其实在表述方面埋了坑。如果有心可以发现，题面在引导你往二维数组的方向去想。但如果你用了二维数组，开出101010^{10}1010大小的数组你就会发现：要完。
转变思路可以发现，kkk是iii和jjj的公倍数，也就是说iii和jjj是kkk的因数。
1=1∗11=1*11=1∗1，111是111的因数，所以A[1][1]A[1][1]A[1][1]的值可以是kkk；2=1∗22=1*22=1∗2，111和222都是222的因数，所以A[1][1],A[1][2],A[2][1],A[2][2]A[1][1],A[1][2],A[2][1],A[2][2]A[1][1],A[1][2],A[2][1],A[2][2]的值都可以是kkk。
总结出来，如果想要A[i][j]A[i][j]A[i][j]有可能是kkk，那么iii和jjj都是kkk的因数。
这里容易想出来一些会TLE的思路。比如说：枚举kkk的每一个因数。
这里需要一个巧妙的思路转变：iii和jjj都是kkk的因数。那么我们可以用两个两层循环，
1.第一层遍历1−n1-n1−n，第二层循环遍历1−k1-k1−k，统计出iii是哪个kkk的因数。
2.第一层遍历1−m1-m1−m，第二层循环遍历1−k1-k1−k，统计出jjj是哪个kkk的因数。
最后用乘法原理的思路：两个两层循环各得出一个数组，存储每个kkk有多少个因数，将它们乘在一起就好。
时间复杂度：
前置知识点：调和级数
Hn=∑k=1n1k=11+12+13+...+1kH_n = \sum_{k = 1}^{n} \frac{1}{k}=\frac{1}{1}+\frac{1}{2}+\frac{1}{3}+...+\frac{1}{k} Hn =k=1∑n k1 =11 +21 +31 +...+k1
当n=105n=10^5n=105，HnH_nHn 大概是101010。
本题中，第二层循环看似遍历1−k1-k1−k，超时离谱，实则每次循环都遍历H106H_{10^6}H106 ，时间复杂度并不太高，不会超时。
注：十年OI一场空。不开long long 见祖宗。
P2669 金币
P5722 数列求和
P5723 质数口袋
P1217 Prime
这道题我想稍微提一下质数筛法。
这是我比较常用的质数筛写法：for(int j=2;j<i;j++)
这是OIer普遍使用的质数筛写法：for(int j=2;j<=i*i;j++)
为什么第二种写法能够使用呢？答：由于因数都是成对出现的。如果，一个数是质数，那么你一定能在i\sqrt{i}i 以内找到它得因数。
P1423 游泳
2026/6/4
分治，就是把一个复杂的问题转换成为若干个简单一些的问题，然后递归下去解决简单一些的问题。（from《深入浅出进阶篇》）
这让我想到了DP的”重叠子问题“（虽然不确定是不是同一种东西）。或许计算机本身的意义，就是去帮助人类做一下重复的东西。但是也不禁让人感慨，缺乏了那些无趣的重复，我们还能有创新吗？
P1177 归并排序模板
归并排序
归并排序是基于分治的思想去完成的。分治，分而治之。假设有两个有序的数组aaa和bbb（aaa数组有nnn个元素，bbb数组有mmm个元素），如何将它们合并成一个有序的数组呢？
维护两个下标iii和jjj。将a[i]a[i]a[i]和b[j]b[j]b[j]进行比较：如果a[i]<b[j]a[i]<b[j]a[i]<b[j]，将a[i]a[i]a[i]填到新数组中，让iii自增。如果b[j]b[j]b[j]较小，让jjj自增。当i=ni=ni=n或者j=mj=mj=m的时候，我们就可以把另一个数组剩下的所有数值给添加到最终数组中。
这是在aaa和bbb都有序的情况下。那么我们如何将一个无序数组变成这样呢。这个时候就要利用分而治之的思想。一个数组长度为nnn，当它只有一个数的时候，它天然有序。当n>1n>1n>1，尝试将它分成两个长度为n2\frac{n}{2}2n 的数组。对这两个子序列递归地进行排序：先分成两块往前递归，递归完成后会吐出两个有序序列，然后再按照上述操作进行排序。
时间复杂度为O(nlogn)O(nlogn)O(nlogn)。
大概是长这样：
P1908 逆序对
逆序对
在做逆序对之前，我想稍微提一提分治。二分是分治的儿子，不难发现无论是二分答案还是二分查询，它都有一个类似于checkcheckcheck函数的东西。而分治的分而治之，一般情况下它做的都是同一套体系的东西（不管是从宏观的角度：所有的分治是有相似点的。还是从微观的角度：一道题中使用分治，每一次”治“的过程都是同一份代码），往往是一个函数，去做递归。从大的分到小的，再从小的回到大的。
分治既是一种无形的思想，也是有形的框架。（回到逆序对）
我们不再分析分治的框架了，直接沿用归并排序的框架。尝试一边排序一边寻找逆序对。当序列长度n=1n=1n=1时，肯定没有逆序对。当n>1n>1n>1，将其拆分成两个序列。对两个子序列递归地求出内部的逆序对。
递归地计算好之后，考虑如何合并。一个大序列中的逆序对，肯定有一个元素来自前半序列；一个元素来自后半序列。如何计算两个子序列对答案的贡献？
回忆归并排序的过程。如果我们现在要将a[i]a[i]a[i]放入新数组，而和a[i]a[i]a[i]作比较的是b[j]b[j]b[j]，那么就代表：b[1],b[2]...b[j−1]b[1],b[2]...b[j-1]b[1],b[2]...b[j−1]全部小于a[i]a[i]a[i]。此时出现了j−1j-1j−1对逆序对。答案加上j−1j-1j−1。
我们可以用这样的思路去完成代码。
注：逆序对偏向于方案数，建议开 long long。
P1966 火柴排队
首先，我们将∑(a[i]−b[i])2\sum{(a[i]-b[i])^2}∑(a[i]−b[i])2进行拆解（如果题面中有这种神奇的数学公式，那我们肯定优先选择去拆解它，看看能拆出什么）。
∑(a[i]−b[i])2=∑(a[i]2+b[i]2−2a[i]b[i])=∑a[i]2+∑b[i]2−∑2a[i]b[i]\sum{(a[i]-b[i])^2}=\sum{(a[i]^2+b[i]^2-2a[i]b[i])}=\sum{a[i]^2}+\sum{b[i]^2}-\sum{2a[i]b[i]}∑(a[i]−b[i])2=∑(a[i]2+b[i]2−2a[i]b[i])=∑a[i]2+∑b[i]2−∑2a[i]b[i]
显然，无论如何拆解，∑a[i]2+∑b[i]2\sum{a[i]^2}+\sum{b[i]^2}∑a[i]2+∑b[i]2都不会有变化。想要使得距离最小，那就得想办法让∑2a[i]b[i]\sum{2a[i]b[i]}∑2a[i]b[i]最大。
前置知识点：
排序不等式证明
结论：当有两组实数aaa和bbb，aaa和bbb都为乱序时的∑aibi\sum{a_ib_i}∑ai bi 小于aaa和bbb数列都单调不减时的∑aibi\sum{a_ib_i}∑ai bi 。
即a1≤a2≤...≤ana_1\le a_2\le ... \le a_na1 ≤a2 ≤...≤an 且b1≤b2≤...≤bnb_1\le b_2\le ... \le b_nb1 ≤b2 ≤...≤bn 时，∑aibi\sum{a_ib_i}∑ai bi 最大。
证明：
当a1≤a2≤...≤ana_1\le a_2\le ... \le a_na1 ≤a2 ≤...≤an 且b1≤b2≤...≤bnb_1\le b_2\le ... \le b_nb1 ≤b2 ≤...≤bn 时，任给一组乱序配对a1bx1,a2bx2,...,anbxna_1b_{x_1},a_2b_{x_2},...,a_nb_{x_n}a1 bx1 ,a2 bx2 ,...,an bxn
只要存在两个下标p<qp<qp<q且xp>xqx_p>x_qxp >xq ，交换bxqb_{x_q}bxq 和bxpb_{x_p}bxp ，∑aibxi\sum{a_i b_{x_i}}∑ai bxi 就会变大。
有了这个结论，我们可以知道：对于每个kkk，我们应该将第kkk小的aka_kak 元素与bkb_kbk 元素配对，这样∑aibi\sum{a_ib_i}∑ai bi 最大。可以发现：在第一盒火柴交换iii和i+1i+1i+1根，与在第二盒火柴中交换是一样的。所以，我们只需要考虑对一盒火柴进行交换。
首先排序，然后计算出两个数组ccc和***。cic_ici 表示a[i]a[i]a[i]在数组aaa中是第cic_ici 大的。did_idi 表示b[i]b[i]b[i]在数组bbb中是第did_idi 的。
如果只是单想着如何把ccc序列变成***序列，是有难度的。所以我们可以换个方向去想：n≤105n\le 10^5n≤105，需要使用的算法时间复杂度可能是O(n)O(n)O(n)或者是O(nlogn)O(nlogn)O(nlogn)，想要将第kkk小的aka_kak 元素与bkb_kbk 元素配对。我们可以使用映射+排序的方法。
我们将did_idi 映射成iii。由此，数组***变成了1,2,3..,n1,2,3..,n1,2,3..,n。即pos[d[i]]=ipos[d[i]]=ipos[d[i]]=i。接着，我们将cic_ici 映射成pos[c[i]]pos[c[i]]pos[c[i]]。问题转化为每次可以交换相邻两个位置，求至少要交换多少次来排序一个序列。
可以这样考虑：
1.当前序列中没有一个相邻的逆序对，就代表已经完成任务了
2.当前序列中有相邻的逆序对，那么我最多需要也最少需要一次“交换相邻两个位置”的操作，将数列中的逆序对数量减少一个。
现在，我们只需要算出ccc中逆序对数量，就可以得出最终答案了。
各种整形与二的次幂之间的关系
−231≤int<231-2^{31} \le int < 2^{31}−231≤int<231
−263≤longlong<263-2^{63} \le long long < 2^{63}−263≤longlong<263
0≤unsignedlonglong<2640 \le unsigned long long < 2^{64}0≤unsignedlonglong<264
2026/6/6
P1217 Prime
如何巧妙压缩时间
这里只是列举一些比较常见的（因为刚好做到了Prime这题）。
它的代码是这样的：
注意到我用了三个优化。将看似不能卡过去的题卡过去了。优化3前几天已经分析过了。我们来说说优化1和优化2.
优化1：注意到除了2之外的偶数不可能是质数。且a>5a>5a>5，所以我们可以在开头直接把偶数特判掉。不要认为这样没用，加了这行代码，你就会多过一个测试点。苍蝇再小也是肉。万一你就差这一个点呢。
优化2：我们在“质数”和“回文数”之间进行比较。发现回文数的数量小于质数。所以我们先判断回文，如果不是直接将它continue掉即可。（也就是将更能筛的判断放在前面，且回文的时间复杂度也小于质数筛）。
另外还有一些优化，比如剪枝什么的。不过这个就有门槛了，后面我会着重提及。
P10263 公倍数问题
将时间复杂度比较高的循环分解
在谈论循环分解之前，我要先提一个比较常见也比较容易错的问题：神奇的long long 问题。这是正确代码：
注意到k,a,bk,a,bk,a,b都开了long long。你做题的时候很有可能会以偏概全，认为只有ansansans需要开long long，而a[i]∗b[i]∗ia[i]*b[i]*ia[i]∗b[i]∗i不需要开。我的建议是：
1.直接全开：
不过这样会有一点点MLE的风险（当然啦，不多）。但是这样真的比较保险。
2.分析全面：
这是很难做到的。比如说S组四个小时，你就算带一箱子精神饮料，也未必能保证每时每刻你的精神都足够好。想要分析全面，最好的方法是检查。第一次如果难免疏漏，那就用后面的时间来补。这种习惯建议从小题养起，不然等到考场上，挂分的就是你。（比如你样例全过了之后，不着急交，而是返回检查）
回到我真正想说的：将时间复杂度比较高的循环分解
这是这道题目很妙的一个点。如果正常人来做，你第一时间可能会想到这个代码：
没写完
二叉堆
P3378 堆
给定一个数列，初始为空，请支持下面三种操作：
1. 给定一个整数 xxx，请将 xxx 加入到数列中。
2. 输出数列中最小的数。
3. 删除数列中最小的数（如果有多个数最小，只删除 111 个）。
堆是建立在完全二叉树基础上的一种数据结构，首先了解完全二叉树的存储方式：
观察每个结点的编号，可以得出两个结论：
1.xxx结点的父亲节点编号是⌊x2⌋\lfloor \frac{x}{2} \rfloor⌊2x ⌋
2.编号为xxx的节点左子节点编号是2x2x2x，右子节点编号是2x+12x+12x+1
依靠着这种性质，如果想找一个节点的父亲或孩子，只需要对下表进行算术运算。这种存储方式叫做“堆式存储”经常用于存储二叉堆之类的完全二叉树。只需要一个数组，就可以存储二叉堆。
二叉堆是一棵树，每个节点有一个值。满足以下性质：1.二叉堆是一颗完全二叉树 2.对于大根堆而言，父节点的值一定大于或等于子节点的值。小根堆刚好相反。
这是一个大根堆示例：
这是一个小根堆示例：
接下来我们来看看如何完成题目中的三个要求：
1.输出数列中最小的数 ：这个比较简单，直接输出数组中的第一个值就好了
2.将元素xxx加入集合
首先，我们先将xxx放入树的尾部
这个时候，我们需要考虑到xxx有可能会违反二叉堆的性质2，所以我们需要对二叉堆进行调整和修复。“修复”是二叉堆的主要思想。
刚刚插入的节点在最底层，对它进行以下操作：
(1).如果它大于等于自己的父节点，或者已经是根，停止操作
(2).如果它小于自己的父节点，将它的父节点和自己交换位置。然后对父节点执行同样的操作。（这里建议配合下面的代码一起理解，不然可能会对“父节点”是谁产生混淆）
3.删除堆顶元素
我们显然不能直接将堆顶元素去除。不然二叉树就没有头了，它会彻彻底底地分裂成两半。我们在此选择将堆顶元素和最后一个元素互换位置，然后开始修复。这次修复的逻辑和加入集合的修复逻辑差不多。
(1).如果自己已经是叶子节点，或者数值比自己的两个自己点小，停止操作
(2).否则，把自己与子结点中数值较小的那个交换，然后继续修复。
堆排序
一个堆的应用，和上一题是相似的逻辑。
所有需要的零部件也是一样的。
优先队列
P1090 合并果子
一个比较容易的贪心，每次选择最小的两堆加在一起，把这个每次加出来的和用一个ansansans加在一起，然后把加出来的和重新塞进优先队列里，重复上述操作即可。
P2168 河马史诗
前置知识点：哈夫曼树
1.基础定义
给定nnn个带权叶子节点w1,w2,w3,...,wnw_1,w_2,w_3,...,w_nw1 ,w2 ,w3 ,...,wn ，构造一棵二叉树，带权路径总长最小，即为哈夫曼树。
·带权路径长度:
WPL=∑i=1nwi∗liWPL = \sum_{i = 1}^{n}w_i*l_i WPL=i=1∑n wi ∗li
·li:l_i:li :叶子wiw_iwi 路径长度：根 ——> 该节点经过的边数
构造规则：
(1).初始时，每个节点各为单节点树
(2).每次选出根节点权值最小的两棵树，新建父节点，权=两子权之和，合并为新树
(3).放回森林，重复直到只剩下一棵树
2.哈夫曼树性质
(1).无度为1的节点（度：一个节点相连的边的条数）
哈夫曼树中所有的节点要么有两个子节点，要么是个叶子节点。
BIT逆序对
2026/6/8
未来想要多尝试思维独立。自从拿了深入浅出的教材书，感觉自己有点太依赖教材，失去了独立思考的能力。所以每道题会分为两个部分：1.自己独立思考20min思考出的部分内容 2.看完题解理解并融会贯通后的内容
P11380 [GESP202412 八级] 排队
自己的思考部分：
将mmm对这样的关系建模成图，统计图上一共有多少个连通块，设一共有xxx个连通块。
问题在于如何判断有没有相互违背的关系，还需要去重边。
违背关系应该不止需要一个判断方面：1.两人需要在队伍中相邻。这个我已经想到办法了，我可以统计它们的入度。如果一个点的入度>1>1>1就代表有问题，直接输出000即可.
难点在于如何统计“互相违背”，就像是样例333中的那种情况。将这种有可能很复杂的情况进行简化，就会变成：AAA要在BBB的前面，BBB又要在AAA的前面，这种情况就会出问题。我认为这种情况化成图就会变成这样：
将这张图的情况简化成图，那么大致情况就是：编号三要在编号六前面，编号六又要在编号三前面，会出现问题。
如何将这种情况判断出来？我的初步判断是，它们会形成环。所以我只需要判断是否存在环就好了。
判断重边可以使用mapmapmap,它的时间复杂度是O(mlogm)O(mlogm)O(mlogm)应该还不至于超时。
用这段代码拿了40pts40pts40pts。剩下的测试点看不了具体数据，就在外围看了看，发现大多是是误判为000。为什么呢。
好吧我不太会。拼劲全力无法战胜。我要看题解。
看完题解后写的部分：我去看了一些和我思路相仿的题解，它们会使用并查集（应该是叫这个）去判环。但是我也不太能理解为什么我的判环会错。
列举一下自己的几个问题：
1.没有判断自环
实在是不太会调，发现自己的图论遍历和连通块判断这类比较基础的东西好像根本就没有学过（？）所以打算去寻觅一点别的图论题去写。
P3916 图的遍历
一开始写了一个很奇怪的MLE出来：
问题主要集中在：会无限递归。
所以得加判断语句(vis)：
最后可以拿60pts。
写不动了。还要复习文化课。明天再调吧。可能后续会着重练一点图论基础相关的问题。
2026/6/9
先来梳理一下今天的文化课内容：1.语文练习册（20min）2.语文注释背诵(20min)3.数学一张卷子（30min)4.历史作文重写（15min）5.物理笔记整理（？）6.物理卷子半张（35min）
一共需要至少两个小时。所以我八点开始写文化课。OK。
另外我的数学老师和英语老师都和我说，我应该要试着去变得更细心，所以后续写代码的时候，我会尽量尝试仔细纠错，看看能不能一遍过。
P5318 【深基18.例3】查找文献
这是一道图论基础题。我打算从这里开始重新学一下图论。
自己的思考：唔。这道题是一道DFS和BFS的模板题嘛。然后还考了一点图的存储。那刚好把DFS和BFS复习一下。
DFS
（部分内容参考oi-wiki）
DFS是一种遍历或搜索树或图的算法，每次都朝着更深的节点走。行走路径大概像这样：
按照我以前的老师的说法，DFS有一种“不撞南墙不回头”的感觉，它会沿着一条路一直走，直到没有点可以让它继续遍历，而后它就返回，然后继续找路。
它一般是用递归函数实现的。（我有一个问题：为什么DFS会用函数实现，但是BFS一般用队列实现呢？关于这个没什么用但是我很好奇的问题我问了豆包，我直接把这个截图贴上来了，就不手打了）
我觉得这个还挺有意思的，是可以对日常做题产生启发的：你可以根据题目的逻辑去选择算法（或者说写程序）。DFS的操作需要它一层层深入，然后再一层层返回。这种操作方法就刚好对应了递归，而递归用函数实现。BFS中，一层一层的点都是平等的，先进先出，所以它用队列来实现。
DFS会在递归时，将自己遍历的点打上标记，遍历图的时候，跳过遍历过的顶点。
下面的代码是DFS的实现方案：
DFS的时间复杂度是O(n+m)O(n+m)O(n+m)，空间复杂度是O(m)O(m)O(m)。
BFS
广度优先搜索（又叫广度优先搜索）的遍历顺序与DFS不同。它每次都会访问一整层的节点，这一层访问完毕之后，再访问下一层。遍历顺序如下图所示：
BFS的遍历顺序会导致一个很直接的结果：BFS所遍历的路径是从起点开始最短的合法路径之一。因为这个特性，BFS天然地与“寻求最短路”适配，所以你可以发现最短路（dijkstra，bellman）都有一点BFS的影子，同时，如果图上的所有边权为1，那么你可以直接使用BFS进行求解。
BFS使用队列(queuequeuequeue)实现：首先将头节点塞入队列。将队首元素视作当前元素，遍历所有与当前节点相邻的节点，如果没有标记，打上标记，并将其塞入队列。重复“将队首……到塞入队列”的操作，直到队列为空。
代码是这样的：
但是不知道为什么。样例挂机了。重新阅读题目，发现题目要求说：如果有很多篇文章可以同时阅读，要先看较小的那篇。这个怎么弄呢。
在修改的过程中发现了一些问题：1.我输入的时候写的是for(int i=1;i<=n;i++)但是一共有mmm条边。好鬼畜的错误。接下来做这样的修改就好了：
但是这样还是有问题。主要是在DFS里面。由于是递归，所以nonono数组中的东西会随着递归变化。所以，我又进行了更改，并且通过了样例。
评测！
？我要验牌。
是这样的。如果把10610^6106的数组开在一个不断递归的函数中，空间就会超限。那怎么办呢？
题解部分：我们可以将边现在开头排好。
代码长这样：
然后就过了。
由于洛谷的机子卡住了。在等的时候顺便写了一道入门。
然后我们看一下昨天把我给弄死的图的遍历。
我尝试把第八行的代码改成了：
if(vis[x]||dis[x])return dis[x];。现在TLE是不T了。WA了60pts60pts60pts。
看题解。
2026/6/10
老样子，先来整理一下文化课的作业：1.半张困难数学卷子（35min）2.英语默写单（25min）3.复习物理(1h)。所以今天可以做3.5h。挺好。
书接上回。我看完题解了。我本来以为，这题只考图的遍历，没想到它还考了技巧（？）。
如果正常的遍历，我们对每一个点都进行一次DFS，时间复杂度为O(n(n+m))O(n(n+m))O(n(n+m))。肯定会超时，拿到60pts60pts60pts。如果你有一颗有点聪明的大脑，你会想到一个神奇的优化：在遍历一个点的过程中把路上的点一起给算了（就是我40pts40pts40pts挂机的那个做法，有点类似于记忆化搜索）。但这种方法是错的。如果有一张这样的图：
比方说你现在在点222，然后你就会以这个顺序遍历：2->3->4->5->2。你有可能在遍历别人的路上遍历到你自己。然后就看你的初始化和你的DFS怎么写的了。有可能是WA也有可能是TLE。
那么什么是正确的做法呢？我们需要做一个思想的转变：正难则反。当时我第一次听说应该是在某个排列组合的提里面，cjdst评论了几句，然后我就记住了，写在看来好像用于计算机也很合适。
包括后面的最短路里也很会有类似于反向建边的内容，感觉很相似。这道题的正确做法是：如果你找不到大的点，那就让大的点来找你。反向建边，从nnn到111去遍历顶点。从nnn开始遍历，将遍历到的点的最大值设为nnn（因为当前以nnn开头遍历，由于从大到小挨个遍历，所以被遍历到的点答案就是当前遍历正在遍历的点iii）。将每次遍历到的顶点标记，下次不再遍历。注意记得把开头的点标记，这是刚开始做图论的小朋友很容易忽略的地方。
P11380 [GESP202412 八级] 排队
重新搓了一版代码：
?
我的心路历程：这次一定能对->可能能对->让我对吧求你了->我*
我知道可以用并查集做。但为什么我的DFS过不了。我不能理解。
我打算学习一下对拍。
我们需要几个东西：
1.一份肯定正确的代码 2.一份你想要知道对不对的代码 3.一个数据生成器 4.一个拍子
拍子比较简单，我们需要一份这样的代码：我忘记我的dev-c++用不了了。等我重新安装一下。在这个缝隙里，我们来看一下这个：
DAG与拓扑排序
因为拓扑排序没有系统性地学过。所以拓扑排序是现学的，大部分内容来自：深入浅出基础篇。
题目大意：有很多任务要完成，每一项任务都需要一定的时间。有些任务必须在另一些任务完成的情况下才能进行，把这些先要完成的工作成为准备工作。至少有一项任务不要求有准备工作，这个能够最早进行的工作成为任务一。现在需要完成的有nnn个任务，并且这份清单是有一定的顺序的。杂物kkk的准备工作只可能在杂物111到k−1k-1k−1。从111到nnn读入每个杂物的工作说明，计算出所有杂物都被完成的最短时间。互相没有关系的杂物可以同时工作。
分析：将整个任务关系建模成图。乐意发现这个图是一个有向无环图(杂物kkk的准备只能在111到k−1k-1k−1中，即无环。工作有顺序，即有向)，简称DAGDAGDAG。所有任务完成的最短时间取决于最晚被完成的那个任务。
问题简化成：求一个DAGDAGDAG的最长链。
这里给出一个有动态规划思想的做法：用visvisvis数组来记录下需要完成这个任务的最短时间。然后考虑在DFS的过程中算出每个任务所需要的最短时间。由于每个人无必须在所有准备任务完成之后才能完成，所以完成每个任务所需要的最短时间就是其所有准备任务里面最晚完成的世间加上这个完成这个任务所需要的时间。
除此之外，我还要补充一个写代码的点：如何保证在dfs遍历一个点时，一个点所需要完成的任务都已经完成了？我们可以在每个点与别的点建边的时候，统计入度。
当我们建边的时候（绿）统计入度（黄）。当我们从点111遍历到点555，点555会有一条与点111相连的边，当我们for循环到这条边，我们就将入度为三的点222的入度减一，后面点333点555依次类推即可，最后遍历到点五，点222的入度为000，这就代表它所有的预备任务都已经完成。可以开始遍历点222了。
代码：
好了，穿插了一点题外话。我们回到排队的拍子。
我们需要这么一段代码作为拍子：（接下来的这段代码来自oi-wiki，不过拍子都长得一样，文件名改一改也没什么区别了）
2026/6/11
分析一下有什么要做的文化课：1.数学卷子比较难的三道题（20min）2.化学三面练习（10min）今天剩的比较少，但是我马上要期末考试了，所以得复习化学，复习半个小时好了。那么我今天大概可以做三个半小时。今天想要做两道八级题，然后再做一点拓扑。还有对拍。
对拍
（对拍章节的大部分内容来自我一个老师录得视频，这个会讲的很详细，推荐看这个）
昨天写了拍子，今天来看看怎么写剩下的。比如如何生成数据。
这一段代码可以帮助我们生成两个intintint类型的≤100\le100≤100的随机数。
最后，我们需要一个肯定正确的代码和一个你想确定正不正确的代码。
然后我没来看一下它的集合体：
1.拍子
（这里的"data","std","solve"都是文件名，如果需要更改的话不能只改这份对拍里的文件名哦）
2.一定正确的代码：solvesolvesolve（这份代码的名字叫solvesolvesolve）
3.想知道是否正确的代码：stdstdstd
4.数据生成器datadatadata
注意：这四份代码需要在同一个文件夹里，也就是这样：
（多出来的那些文件是需要运行拍子得到的）
它们在你的dev中应该是这样呈现的：
最后，运行拍子（我这里的命名是duipai，你们可以写自己的名字），它就会弹出一个运行框，效果大概是这样：
如果你想知道自己的代码“WA”在了哪里，你可以看这些文件
data.indata.indata.in是当前的输入，diff.logdiff.logdiff.log里面有两份不同的文件分别的输入。
好了，对拍的内容就说完了，我们来看一下八级的题目：
八级-排队
这道题我已经做了好几天了，没能看出来为什么做错了，所以就拿拍子拍一下好了。
我先得写一份一定正确的代码：
? 就这么对我。
好的，接下来来看一下我正确的代码，忽略掉刚刚的意外。
这是一个用并查集判环（应该是这么叫）的代码：
然后附上我错误的代码（但是我不知道哪里错了）：
将它们一个放在solvesolvesolve，一个放在stdstdstd。
然后做一个数据生成器。
最后开始对拍。拍出来的样例是：
错误代码会输出000，正确代码会输出222。唔。所以我的代码有一个比较大的漏洞是，它会先遍历一个点，但是这个点可能不止有一个约束条件，然后当它的下一个约束条件被遍历到，它就会输出000。怎么办呢。感觉可以用拓扑排序的思路去做。但是拓扑排序要求DAG。
如果。是环。用拓扑排序做。它就一定会出现负数吧。啊。我试试看。
有点累。穿插几道水题放松一下喵。
?
为什么我水题还炸
笑点解析：查看样例的机会没有用在黄题或者绿题或者蓝题上。而是选择了一道红题。
终于过了。
我想讲一下这个红题。
