100好题分享

题目	思路	代码
[SCOI2005] 王室联邦[SCOI2005] 王室联邦	树上分块板题，考虑一个栈，dfs时如果一个子树栈的大小已经可以单开一个块了，就新开一个块，让其根为x，如果有暂时无法解决的，就先塞进去，别人pop时拉一条“警戒线”，不允许他pop。到最后点数量不够B，不能单开一块，就将其进入到最后一个块中。	代码
SP10707 COT2 - Count on a tree II SP10707 COT2 - Count on a tree II	用括号序将树上操作改为线性操作，易得出结论：两点之间的路径为其在线性序列上的中间元素，特别的，对于中间出现两次的元素不能算贡献因为他相当于进来又出来了，不在路径内，尤其特别的，若LCA不在序列中，需将LCA加进去	代码
苹果树苹果树	与上题代码相似，加特判色盲即可	代码
Ex - Yet Another Path Counting (AI)Ex - Yet Another Path Counting (AI)	一眼采花生，世界就是一个大大的采花生(雾)，但是采花生只针对一部分数据，所以我们对另一部分数据的路径数采用组合数学计算，这玩意路径选择相当A(i,j)，B(x,y),在（x-i+y-j）个选择中选（x-i）个向右走，或者向下移是同理，这是典型的根号分治	代码
#loj144. DFS 序 1#loj144. DFS 序 1	用dfs序转成序列操作，树状数组维护之	代码
#jzyz3182. 【高手训练】字符串排序 jzyz3182. 【高手训练】字符串排序	显然是个线段树啊，只不过LazyTag变为了是否为升降序，代码实现很简单但是码量大	代码
#jzyz530. [CF1477B]Nezzar and Binary String #jzyz530. [CF1477B]Nezzar and Binary String	首先题意有些难懂，总之就是要优先满足她的要求，其次在判断能否达到目标。发现如果我们按题目说的顺序做的话比较难做，所以正难则反，考虑倒着做，对答案是没影响的	代码
#abc223fL. F - Parenthesis Checking (AI) #abc223fL. F - Parenthesis Checking (AI)	这道题对我来说挺不错的，那就是让我认识到了一个处理合法括号序的常用操作，当且仅当 $cnt_(==cnt_)$ (这么个玩意相当于其区间和为0)且将(视作+1,)视作-1，对于任意的一个i都有其前缀和大于等于0。知道这个结论后，做法很显然啊，使用线段树维护区间前缀和和最小值及区间和，当区间和恰好为0且最小前缀和大于等于0时答案为真	代码
#abc256hL. Ex - I like Query Problem (AI)吗？	讲这题前我要先讲一下花神 (挖坑)
#BZOJ3211. 花神游历各国 #BZOJ3211. 花神游历各国	首先我们都知道开根号且向下取整值下降会很快，即使是1e5 也承受不了几下就会变成1，以后的操作对于这个区间来说已经没有意义了，所以考虑将lazytag改为是否整个区间均为1，是则不用修改，经过势能分析后发现时间复杂度优秀，然后就做完了。	代码
#abc256hL. Ex - I like Query Problem (AI)#abc256hL. Ex - I like Query Problem (AI)	显然与花神那题有异曲同工之妙，只是多了个操作罢了	代码
abc331fL. F - Palindrome Query (AI)abc331fL. F - Palindrome Query (AI)	回文串是吧，如何高效判断呢，可以将回文串撕成两半，计算它们的Hash值，判断即可	代码
#P946G. Almost Increasing Array #P946G. Almost Increasing Array	DP，然后线段树优化之，是因为这是线段树作业，可是我觉得这活我们树状数组也能做啊	代码
#P1705E. Mark and Professor Koro#P1705E. Mark and Professor Koro	很巧妙地一道题，需要将合并的操作转化成二进制高精度加法，然后就分类讨论，将修改看作删除后在加，使用线段树维护即可(这个唐人手敲线段树的时候change的时候没有pushup导致俩人瞪了30min没查出来QAQ)	代码
矩阵乘法矩阵乘法	二维整体二分！！！我对整体二分的理解已经深入骨髓了！！！总之就是将整体二分中的树状数组改成二维的，然后在ask外面套一个前缀和即可	代码
天天爱射击天天爱射击	小水题，考虑不是对每个子弹打木板，而是木板被子弹打，整体二分即可，注意树状数组的add时，add是下标，所以上限应是2e5，不能是n，否则你就会样例不过但是可以AC(这不好事么？)	代码
【模板】字典树【模板】字典树	建个Trie跑就行了	代码
The XOR Largest PairThe XOR Largest Pair	利用异或的性质，不同为1，相同为0，所以每个数都二进制拆分，尽可能地反向跑就可以做到最大	代码
Compress Words Compress Words	hash水过。。。。。	代码
Distinct SubstringsDistinct Substrings	结论题:字符串中本质不同的字串数量为 $(n+1)*n/2-\sum_{i=2}^{i<=len}height[i]$ 证明也是不难的，就是总子串的数量减去重复的吗，重复的数量，不就是相邻两个的后缀的最长前缀之和吗	代码
串分割串分割	看到最大值最小，考虑到了二分答案，破环之后，二分起始位置就做完了	串分割
「AHOI2013」差异「AHOI2013」差异	式子题先拆式子 $\frac{n(n+1)(n-1)}{2}-2*\sum _{i=1}^{i<=n}\sum _{j=1}^{j<=n}lcp(i,j)$ 前半部分好说，后半部分使用lcp的一个性质， $lcp(i,j)=min(lcp(i,k),lcp(k,j)),i<=k<=j$ ，由此我们可以推广知，lcp(i,j)就等于i到j区间任意两个相邻的height，取min。最后在加起来，而区间最值和使用单调栈维护	代码
「NOI2015」品酒大会「NOI2015」品酒大会	好题！用了一个转换的思想，因为r相似和我们的height数组非常之像，所以我们考虑对枚举到的每个r，看作分割(毕竟我们选酒时必须是连续的height>r的，中间不能经过任何一个height<r)，对每个连通块单独算贡献。另外对于答案算乘积最大值，发现他给的数据有负数，所以最大值只可能是两最大值相乘或最小值相乘(两个绝对值很大的负数吗)，结果发现如果按分割的思路的话，区间最大最小值是不好维护的，所以我们考虑，倒着做由分割变成合并操作，使用并查集维护即可。总之是一道思路层层递进的绝世好题。	代码
「SDOI2016」生成魔咒「SDOI2016」生成魔咒	如果按正常思路去做的话，每新加进一个字符所有之前算好的height全都没有用了，所以考虑将在末尾插，变成插到开头，很有道理，然后就做完了	代码
工艺工艺	最小表示法版题	代码
NecklaceNecklace	第二问是版题，第一问有个小结论，那就是最小表示法一样的两个字符串一定是某个字符串的循环同构，这挺显然的吧	代码
隐藏口令隐藏口令	最小表示法都这么版吗？？？？	代码
最长双回文串最长双回文串	Manacher，枚举中间那个连接点就做完了	代码
Prefix-Suffix Palindrome (Hard version)	有意思的题，卡了我好久。首先应该不难发现，答案应该是由原串最长前后缀加上去掉最长前后缀后的贴着边界的最长回文子串相加，挺有意思的反正。	代码
TJOI2015」弦论TJOI2015」弦论	首先t=0是好处理的，t=1就是先DP一遍在跑t=0	代码

火山引擎 ADG 社区

火山引擎开发者社区是火山引擎打造的AI技术生态平台，聚焦Agent与大模型开发，提供豆包系列模型（图像/视频/视觉）、智能分析与会话工具，并配套评测集、动手实验室及行业案例库。社区通过技术沙龙、挑战赛等活动促进开发者成长，新用户可领50万Tokens权益，助力构建智能应用。

更多推荐

Chess用户界面设计：Tailwind CSS样式系统和组件库

GitHub推荐项目精选中的ch/chess是一个类似chess.com的多人在线象棋平台，它采用现代化的前端技术栈构建，尤其在用户界面设计上通过Tailwind CSS样式系统和组件库实现了优雅且功能丰富的交互体验。本文将深入探讨该项目如何利用Tailwind CSS打造一致的设计语言和高效的组件系统，为象棋爱好者提供沉浸式的游戏界面。## 🎨 Tailwind CSS样式系统：构建统一视

火山引擎 ADG 社区

终极指南：GPT-Engineer如何通过AI自动发现代码问题并提升质量

GPT-Engineer是一款强大的AI驱动代码工具，它能帮助开发者自动检测潜在代码问题、优化代码质量，让编程效率提升3倍以上。无论是新手还是资深开发者，都能通过这款工具轻松发现代码中的隐藏缺陷，减少调试时间，释放更多精力在创造性工作上。## 一键发现代码问题：GPT-Engineer的AI审查魔力GPT-Engineer的核心能力在于其内置的智能代码分析系统。通过集成Python代码格式

火山引擎 ADG 社区

SatDump中的纠错编码技术：从RS码到Turbo码的完整实现指南

在卫星数据传输过程中，信号往往会受到各种干扰，导致数据错误。SatDump作为一款通用卫星数据处理软件，集成了多种先进的纠错编码技术，确保从卫星接收到的数据能够准确解码。本文将深入解析SatDump中从Reed-Solomon（RS）码到Turbo码的实现细节，帮助读者理解这些技术如何保障卫星通信的可靠性。## 为什么纠错编码对卫星数据至关重要？卫星与地面站之间的通信链路面临着空间辐射、大