此在Dasein

分类

/ 注册

TA的专栏 150篇文章 0人订阅

每日一题@牛客网

134篇文章 124人学习

算法编程训练

16篇文章 347人学习

全部文章（共128篇）

题解 | #【模板】拓扑排序# 来自专栏

针对此问题，最稳健的解法是 Kahn 算法。该算法基于“入度 (In-degree)”这一关键图论概念，采用迭代的贪心思想。核心思想拓扑序的本质是“依赖消解”。入度为 0 的节点：没有任何前驱节点指向它，意味着它没有任何未满足的依赖条件。因此，它可以安全地排在拓扑序列的当前最前端。消解依赖...

2026-01-16

0 82

题解 | #小A取石子# 来自专栏

该问题属于经典的组合博弈论（Combinatorial Game Theory）范畴，具体为Nim游戏的一个变种。理论核心：Sprague-Grundy定理与Nim和在标准的Nim游戏中，每一个堆的石子数量对应一个Grundy值（即及其石子数本身）。游戏局面的胜负性由所有堆石子数量的异或和（XO...

2026-01-15

0 100

题解 | #many sum# 来自专栏

1. 问题分析本题的核心要求是处理两个具有依赖关系的序列和。序列 A：基于线性同余的递推关系，仅依赖于。这是一个单调生成的序列。序列 B：定义为的所有约数对应的之和。这是一个经典的数论变换问题（Dirichlet Convolution 的变种，即，其中是全 1...

2026-01-14

0 81

题解 | #子数列求积# 来自专栏

算法：前缀积与逆元鉴于序列是静态的，前缀和思想的变体——前缀积是解决该问题的最优范式。核心逻辑定义前缀积数组表示从到的乘积。理论上，区间的乘积可以表示为：在模意义下转化为：零值处理为了解决导致的“信息坍缩”和“不可逆”问题，我们需要引入双层数据结构：非零...

2026-01-13

1 79

题解 | #小红的平滑值插值# 来自专栏

问题分析该问题的核心在于通过最小化插入操作次数，使得数组的平滑值（相邻元素最大差绝对值）恰好等于。这包含两个核心约束：上限约束 (Upper Bound)：修改后的数组中，任意相邻两数的差的绝对值不能超过。存在性约束 (Existence)：修改后的数组中，必须至少存在一对相邻数值，其...

2026-01-10

1 83

题解 | #牛牛喜欢字符串# 来自专栏

核心算法：贪心竖向切片我们可以将这个长度为的子串想象成一个的字符矩阵：第 1 行：第 2 行： ... 第行：目标转化：要是所有行（子串）完全相同，意味着在这个矩阵中，每一列的所有字符必须相同。由于不同列之间的字符选择是相互独立的，我们可以将大问题分解为个独立的...

2026-01-09

0 94

题解 | #区间取反与区间数一# 来自专栏

针对此类经典的“区间修改+区间查询”问题，最优的算法是线段树。算法采用分治策略将序列划分为二叉树结构。节点维护信息 (Attribute)： sum：当前区间内 1 的总个数。 tag：布尔型或整型懒标记，表示当前区间是否积压了一次“取反”操作。状态转移逻辑：父子关系：父节点...

2026-01-08

0 79

题解 | #明日DISCO# 来自专栏

这是一个经典的网格操作与稳定性分析问题。我们可以通过分析操作的性质、状态的单调性以及“死锁”条件来得出一个基于贪心策略或事件驱动模拟的算法。问题分析我们需要判断是否可以通过有限次操作将整个网格的所有数值变为 0。操作规则是：局部最大值可以减小，局部最小值可以增加。这实际上是一个能量最小化或平滑...

2026-01-07

0 67

题解 | #统计个数# 来自专栏

数据结构为了平衡空间与查询速度，针对：邻接矩阵 (Adjacency Matrix)：使用二维布尔数组 adj[N][N]。优势：判断两点间是否有边的时间复杂度为。这对于三角统计中的频繁查边操作至关重要。空间消耗：是极其微小的内存开销。度数数组 (Degree Array)：...

2026-01-06

1 83

题解 | #构造数列# 来自专栏

问题的核心在于奇偶性对求和的影响。设，即前半部分和后半部分各包含个元素。前半部分（偶数部分）的和：任意个偶数的和一定是偶数。因为偶数可表示为，其和为，必然能被 2 整除。后半部分（奇数部分）的和：任意个奇数的和的奇偶性，取决于的奇偶性。若是偶数，则（奇数 ...

2026-01-04

0 75