Day1 2月4日戳这里！！ 🏷️ 本集标题： 寒假第二天：在“拖延”与“自律”间走钢丝 🎵 氛围BGM： 依旧活跃 📈 今日能量值： ▮▮▮▮▮▯ (自我充能 x/ 耗能报告 y ) 🎮 主线任务进展： 项目1 项目2 完成情况1 完成情况2 ⚡ 突发副本： (计划外的神奇事件) 😎 高光/崩坏时刻： (图文记录今日之最) 🗣️ 经典台词： 点个赞吧, 点赞的身体健康万事如意金榜题名 欢迎跟帖！

我承认我懒了。 寒假学的东西就都放在这一个讨论里吧。 不过好像打多了字加载会很慢。 ———————————————————————————————— 先梳理一下要复习什么……马上要集训了。 可以性剪枝，最优性剪枝，kmp，记忆化搜索，折半搜索，贪心，反悔贪心，双向深搜。 主要是重新梳理概念，补题和做一些蓝蓝绿绿的题。 然后刷一刷CSP-S复赛的题目好了。 做完也就差不多要去集训了……好像有20天。 ————————————————————————————————— 一.可行性剪枝 说实话，剪枝是很玄乎的东西，考场上，你永远都不会知道这份经过了你一剪再剪的代码能不能A。 这里，我有两份解释： 嗯，可行性剪枝就是将无论如何都已经不会为最终答案做出贡献的枝剪掉。 这边顺便一起把最优性剪枝的概念一起顺了好了，因为我找不到“可行性剪枝”标签的题目。只有“剪枝”类别的。 二.最优性剪枝 这个挺好理解的，就不总结了。 看到OI-Wiki里面把记忆化搜索也归为剪枝了，那把那个一起弄掉吧。 三.记忆化搜索 记忆化搜索和DP本质差不多吧。 或者说就是一种。 递归式DP，用数组保存已有的答案。 想要使用记搜，你得保证一件事： 比如DP[i][j]它第一次求出的值是x，后面无论多少次求，它的值都必定是x。 它本质是没有模板的，或者说我认为所有的算法都是没有模板的。 只要你能把题目要求实现出来就好。 但是我的老师认为背模板可以让你打代码完成题目更快。 所以我就拉一道简单一点的题目介绍一下模板好了。 采药 ……我下午还要连上4h文化课补课你们敢信？ 三.折半搜索 *在OI-wiki中，我了解到二分搜索和折半搜索是不同的搜索，但是目前我没查出两者有什么不同，希望对此了解的同学可以解答。不过这里，我就将它们视作同一种算法进行解释。 先进行一个介绍： 折半搜索，又称 meet in the middle（折半搜索）。 这种算法，往往争对于n=40左右 的题目。 此时你不会DP，剪枝无法拿满分。 而mitm可以帮助你将时间复杂度从O(ab)O(a^b)O(ab)转化为O(ab2)O(a^\frac{b}{2})O(a2b )。 关于实现： 折半搜索会先在1−n21 - \frac{n}{2}1−2n 之间进行搜索。 并且将搜索的结果存储。 然后再在n2+1−n\frac{n}{2}+1 - n2n +1−n之间进行搜索。 然后在用例题看看模板： 题目大意：想将1-n的所有数划分成两个子集，要求两个子集的和相等。问有多少中方案。 观察：数据范围 ST表 四.双向广度优先搜索 五.倍增算法求最近公共祖先 六.Tarjan算法求最近公共祖先

寒假，致力把CSP-J的真题刷完。 每道题都会写题解。 从简单到难。 P5660 [CSP-J 2019] 数字游戏 题目大意：问一串字符串中字符一的个数 使用知识点：字符串的输入和遍历 注意点：是字符串，不要int类型输入啊。 代码： 难度评价：入门中的入门 P5681 [CSP-J 2019 江西] 面积 题目大意：问aa 和 bc 谁更大 使用知识点：int的范围 字符串输出 if else 注意点：19∗191^9 * 1^919∗19超出了 int 的范围 请使用 long long 代码： 难度评价：在人门中需要一点心眼，但不多 题目拓展： 这个题目，但拉出来简单，却会成为在难题中隐藏的小炸弹。 “不开long long 见祖宗”，想必各位都并不陌生。 所以在对题目进行检查的时候/做题的时候，切记要注意是否算出的答案会爆int。 （我的建议是最好直接用typedef 开，因为很多是你意想不到的：比如说折半搜索的答案最后往往是要爆的） P7071 [CSP-J 2020] 优秀的拆分 题目大意：对于数字n，询问其是否能分解为若干个不同的2的正整数次幂。 题目思路：对于“2的次幂”，需要有一定的敏感度，联想到二进制。 代码： 难度评价：入门中的战斗机，似乎有点普及-的影子。 题目拓展：可以去用“&"判断两者之间是否互相包含。对二进制要有一定敏感度。 P8813 [CSP-J 2022] 乘方

现在大概有洛谷，xmw，数学三个课。 到时候集训上完了可能还有。 集训 Day1 D1学习前缀和，差分，单调栈，单调队列。 早上是前缀和与差分。 在进行这两个算法的时候，你往往要注意到一件事： 如何体现其处理优势？ 有的时候，它们的用处可能仅仅是优化掉一次方N. 但有的时候，它们可能可以优化很多。 仅仅只是做区间和还不够体现它们的优势。 T1 优美子数列 链接描述 这道题的大意是让你在一段序列中找出和为k的倍数的子序列。 1.浅层运用前缀和： 首先预处理出所有子序列的前缀和。 然后枚举左右两个端点。 但不容易发现这样其实是在前缀和无效化。 那么如何更好地去运用前缀和？ 2.前缀和理解加深 当需要查找最终值为定值的序列中，我们首先需要观察等式的关系： pre[r]-pre[l-1]=-k -2k -3k -4k k 2k 3k …… 发现这里我们要查找的是k的倍数。 即%k=0的数 (pre[r]-pre[l-1])%k=0 也就是 (pre[r]%k-pre[l-1]%k)%k=0 在这种式子里，我们只需要确定两个未知数的一个即可知另一个未知数。 那么大概就能够得出如何去做了。 额注意一下负数取模。 要复习的题目： 课前小测-优美子数列 体现前缀和处理优势？ 区间段和为定值： pre[r]-pre[l-1]=x 当x被确定后 构造回文数组 模型：积木堆叠 上升：操作增加 下降：操作不变 本题本质上是一个差分，但需要再次分析一下。 在进行前缀和操作的时候，或者其他累加累乘操作的时候 要注意小心，开Longlong 会爆int mex 统计：利用前缀和 找出e前面有多少个m e后面有多少个x 比较复杂的代码要学会分块，更加容易调试。 前缀和与差分 - 区间操作 现在开始缓慢地写题解。 T1 优美子数列 下午开始学单调栈和单调队列 单调栈模板： 需要保证栈是否为空再去判断。否则会发生奇怪的问题 动物园的等待 链表？ 下一个更大的元素： 写单调栈和单调队列的时候要注意判断栈和队列是否为空。 在写单调栈和单调队列的时候要注意判断栈和队列是否为空。 构造回文数组 前缀和不开long long 见祖宗的嗷！ 前缀和：pre[r]-pre[l-1] 差分：pre[l]+x pre[r+1]-x D2 早上开模拟赛 下午摸题解。 想要找到第n大的质数。 欧拉筛：O(n) 每一个和数 都只会被自己的最小质因数标记。 埃氏筛：O(n log lon n) T2：可以使用暴力，也可以使用优先队列。 我觉得，做错的原因主要是我当时思路不太清晰。 做一道题，应该先想清楚思路在开始吧。 等一下。 我去找老师对了一下思路。理论上而言，我的思路应该是正确的。 不过正确了也T。 我觉得这题我没做出来的主要原因是我以前的东西忘得有点太多了。 啥都不记得了。 在想优化的时候大脑空空。 啥都不知道。 反正最后结果就是我养了优先队列。 然后我去看看欧拉筛是怎么写的。 用分块来写代码后，可以写一个快，检查一下 在做难题或者复杂的题目的时候，要先自己做一些小的样例。 然后慢慢总结规律。 摸个T4吧。 好可惜啊。 T4要是考场上再想想可能就写出来了。 但我去刷小红书了喵。（逃跑 但是没关系，让我们来美美地写一个题解吧遗憾弥补一下吧！ 这道题，它主要是想问在一颗树上，如何加才能使整体数值加到它期望的样子。 我觉得此题的难点有两个： 1.它的范围不太好判断。如果初读的话，你可能会有点懵。 （不过这个也是题目的必须点，亦是突破点） 2.它的思路有点难想（虽然其实很简单，但是如果你正常做的话，你可能会觉得自己遇到了一堆难点） 就这两个，平均下来应该是绿题里面比较简单的题目吧。 然后说说具体是怎么做的吧。 想动态规划一样，有两种遍历方法： 1.自顶向下 2.自底向上 这个提出的好像有点早了，到时候再说好了。 可以从一条链开始推。 然后你就会发现一个核心点： 从最下方开始，并且最好是取每个点的最大值（这个稍微推一推就出来了） 然后就没有了。 欧拉筛： 然后接下来去做点好玩的 咪。 1.优先队列 链接描述 神奇的优先队列介绍！ 优先队列分为两种：1.小根堆 2.大根堆 再要细分的话，还有结构体优先队列 和 数字优先队列。 看看： 1.数字大根堆（默认，大的数字在前）： 2.数字小根堆 结构体大/小根堆： 好的，那么现在理论成立，实践开始。 优先队列的运用主要有两个（为我所知的）： 1.优化 2.反悔贪心 这里主要介绍一下优先队列用来优化。 关于如何优化，让我们用一道题目见识一下。 舞蹈演出 这道题的题意非常清晰，在此就不过多赘述了。 暴力如何打应该已经知晓： 每次二分k的最小值，设置出k个值为t的变量，然后每次找值最小的一个减一个。 如果说，想要找最小的值且用暴力的话，一次就是O(n)界别。 而1e4的n没办法支撑O(n^2logn)的时间复杂度。 只能支撑O(nlogn)或者O(n)又或是O(nloglogn) 也就是，要优化一个log。 而且是要找动态最小值。 哦豁，答案呼之欲出！ 优先队列是也。喵。 关于神奇的链表！ 通常，我们不是用STL里面的链表（太难用了喵），而是自己通过结构体来模拟。 现在我们一起来做一道模板题目。 模板双向链表 这道题目钟一共要求了三个关于链表的更改操作。 1.将x插入到y的左侧 2.将x插入到y的右侧 3.删除x这个节点 我们来分析一下这三个操作： 将A插入到B的左/右侧 它本质是两个操作： 1.删除 2.插入 如果A原本存在于这个数组之中，那么将其删除。 先来看看如何实现删除这个操作： 删除一个元素，意味着这个元素的左边的右边要变成它的右边。 这个元素的右边的左边要变成它的左边。 这个就是删除操作： 然后思考一下插入操作怎么整。 将A插入到B的左边，也就意味着： B左边的右边变成A，B的左边变成A的左边，A的右边变成B，B的左边变成A 也就是这样： 最后输出一下就好了： 枚举： 枚举什么？ 1.确定枚举范围 2.如何是枚举不重不漏 要把一个大问题分解成若干个小模块去解决 T4：绝对值即距离 对于距离，考虑相对位置的情况。 1.重叠，包含 2.b在a 前面 3.a在b前 重点在于维护：amin bmin amax bmax 归并排序： 分治是很重要的思想：分而治之。 这是所有庞大规模问题的基础。 下午上倍增和ST表 关于倍增： RMQ问题：区间最值问题 额主要讲一讲如何使用吧。 一句话概括：倍增是思想，ST表是框架。 ST表的模板虽然是取区间最值，但是这并不代表它只能用来取区间最值。 相反，它的运用面是很广泛的。 拿一道题目来举例吧。 链接描述 利用ST表的框架。 先考虑大致思路框架： 每走一步，需要想的是：走到了哪里->拿了几个胡萝卜 而我们已知的是：我们走了几步 如果一次一次推的话，时间复杂度大概是O(m) 太高了。 如何优化？ 下午讲了选讲内容： 离散化

适合3级以下入团https://www.acgo.cn/application/2018639252972699648

适合三级以下入团https://www.acgo.cn/application/2018639252972699648

这题只有质子才看的懂

悬赏鬼灭粉！！ #互动 #角色扮演 #杀青梗 私信@蝴蝶忍 加入团队选角色（先到先得！！）

招人链接

所以我从明天开始也写吧...

求求各位狗友！团队适合萌新加入，氛围很好。在这里努力+实力=权力链接在这里->哦https://www.acgo.cn/application/2018639252972699648

🏷️ 本集标题： 寒假第一天：我的“躺平”与“折腾”计划 🎵 氛围BGM： 活跃 📈 今日能量值： ▮▮▮▮▯▯ (自我充能 5 / 耗能报告 1000) 🎮 主线任务进展： 作业进度 (/) 编程进度(___) ⚡ 突发副本： (计划外的神奇事件) 😎 高光/崩坏时刻： (图文记录今日之最) 暂无，今晚21时更新 🗣️ 经典台词： 放假第一天，我要玩到通宵（可是这不可能qwq）！！ 点个赞吧, 点赞的身体健康万事如意金榜题名 欢迎跟帖！

小广告 最近，AC局接到了一项来自神秘组织的特别委托。这个组织常年活跃在网络世界的深处，他们掌握着大量与算法和编程相关的机密信息，但近年来，由于内部人员的频繁变动和资料管理不善，许多关键数据变得杂乱无章。为了重新整理这些资料，他们决定举办一场面向全球编程爱好者的线上挑战赛，而所有题目的数据校验工作，都交给了AC局来完成。 队长接到的任务，正是为这场挑战赛中最基础、也是最重要的一道入门题准备测试数据和完整的题目描述。这道题目看似简单，却关系到整个比赛的稳定性，因为成千上万的选手都会从这道题目开始他们的挑战之旅。如果题目有任何歧义或者数据不够严谨，就可能导致大量选手在起跑线上就陷入困惑，甚至影响他们后续的发挥。 为了设计出一道既符合入门水平，又足够严谨的题目，队长翻阅了大量过往的比赛记录，分析了无数新手选手在解题过程中常犯的错误。他发现，很多初学者在处理输入时，往往会在细节上出现问题，比如没有正确读取所有数据、忽略了边界条件，或者在累加过程中出现了逻辑错误。于是，他决定设计一道题目，专门考察选手对循环结构和条件判断的掌握情况。 这道题目的背景被设定在一个虚拟的“任务处理系统”中。AC局的队长需要编写一个程序，来模拟这个系统如何处理来自不同任务源的数据。具体来说，系统会接收到一系列的任务指令，每条指令都包含两个关键参数：一个表示任务类型的整数 k，另一个表示任务的重要程度 j。队长需要编写一个程序，根据这些指令来计算最终的重要程度总和。 在任务处理系统中，只有当任务类型 k等于 1 时，该任务的重要程度 j才会被计入总和；如果任务类型 k不等于 1，那么这条指令将被系统忽略，不会对总和产生任何影响。队长需要确保程序能够正确处理大量的输入数据，并且在处理过程中不会出现任何错误。 为了验证程序的正确性，队长需要设计多组测试数据，包括正常情况、边界情况和一些极端情况。例如，当输入的任务数量 n为 0 时，程序应该输出 0；当所有的任务类型 k都不等于 1 时，程序也应该输出 0；当任务类型 k等于 1 的次数非常多时，程序需要能够快速计算出正确的总和，而不会出现溢出或者其他错误。 在设计测试数据的过程中，队长还考虑到了选手们可能会使用的各种编程语言和编程习惯。他确保输入数据的格式简单明了，输出要求清晰明确，不会给选手带来额外的困扰。同时，他还为题目添加了一些背景故事，让选手们在解题的同时，也能感受到AC局和神秘组织之间的这场特殊较量。 经过几天的努力，队长终于完成了这道题目的设计和测试数据的准备工作。当他将题目提交给神秘组织时，对方对题目的严谨性和创意给予了高度评价。神秘组织的代表在回信中写道：“这道题目不仅考察了选手的基本编程能力，还通过生动的背景故事激发了他们的兴趣。我们相信，这道题目将成为本次挑战赛的一大亮点。” AC局的队长看着电脑屏幕上的回信，脸上露出了欣慰的笑容。他知道，自己的努力没有白费，这道题目将会帮助无数新手选手迈出编程世界的第一步。而他，也将继续带领AC局的队员们，迎接更多的挑战，为编程社区贡献自己的力量。 现在，轮到你来接受AC局队长的挑战了。请你编写一个程序，模拟这个任务处理系统，计算出所有任务类型 k等于 1 时的重要程度 j的总和。

链接：https://www.acgo.cn/application/2018579499194056704

点点赞吧大佬们TAT ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ DAY0： 2026-02-03 * 喜\COLOR{RED}{喜}喜：期末考完啦！ * 嗯对，就是语文好难（90能上吗?)，科学一般（95有吗?），英语一般（95有吗?），数学简单（100有希望？），管他呢，考都考完了 * 03:36 P.M. * 放学了，找到我妈妈，坐到车上快快乐乐回家！ * 03:50 P.M. * 回到家了，过了一会儿，我妈妈去接我姐姐了，我收拾了一下我的房间（昨天把学校所有东西都搬回来了，手好痛TAT…… * 大概6:30 P.M. * 然后正常吃饭和家人聊天 * 大概7:30 P.M. * 和家人一起看了《小小的愿望》，好看 * 大概9:30 P.M. * 电影看完了，和姐姐在沙发上玩，她看电视，我玩蛋仔 * 大概11:30 P.M. * 洗澡睡觉 * 大概12:00 P.M. * 睡着了 DAY1： 2026-02-04 * 大概 00:00 a.m. * 睡着了 * 10:00 a.m. * 美美起床 * 11:40 a.m. * 吃饭 * 12:20 a.m. * 送姐姐上学 * 大概12:50 p.m. * 姐姐到学校了 * 01:19 p.m. * 到我上课的学校了 * 01:41 p.m. * 忍痛下车上课（05:00 p.m.下课TAT） * 04:10 p.m. * 写到这里

积分榜以社区账号名为准 队长 ∞