此在Dasein

分类

/ 注册

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

每日一题@牛客网

134篇文章 124人学习

算法编程训练

16篇文章 346人学习

全部文章（共128篇）

题解 | #分元宵# 来自专栏

1. 问题分析本题本质上是一个带重复性的排列问题（Permutation with Repetition），或称之为从集合到集合的映射计数问题。元宵种类数：每个元宵由“馅”和“皮”唯一确定。设馅的种类为，皮的种类为，则元宵的总种类。槽位总数：碗是放置元宵的物理位置。题目明确指出桌子和碗...

2026-04-17

0 2

题解 | #小红树上染色# 来自专栏

问题分析该问题的核心约束是“不存在两个白色节点相邻”。在图论语境下，如果我们定义被染红的节点集合为，那么未被染红的节点（白色节点）集合为。题目要求中任意两个节点之间没有边相连，这等价于说是一个独立集（Independent Set）。进一步转化，若是独立集，那么其补集（即红色节...

2026-04-16

0 10

题解 | #小美的01串翻转# 来自专栏

问题分析该问题的核心在于计算所有子串的“权值”之和。给定一个串，权值的定义是将其转换为“相邻字符均不相等”的字符串所需的最小翻转次数。 1. 目标状态分析对于任意长度为的字符串，满足“相邻字符都不相等”的目标状态仅有两种：模式 A：010101...（以 '0' 开头）模式 B：1...

2026-04-14

2 16

题解 | #元素方碑# 来自专栏

1. 问题分析该问题的核心在于理解操作的局限性。虽然题目描述了方碑之间的能量流动，但这种流动并非在任意两个方碑之间自由进行，而是受到严格的几何结构限制。核心约束：操作中心性：对下标为的方碑进行操作，受到影响的是和。不变性：方碑在该操作下，自身的能量保持不变。耦合关系：下...

2026-04-13

0 24

题解 | #小红背单词# 来自专栏

1. 问题分析本问题的核心在于动态阈值的状态演变。传统的单词计数问题通常是静态频率统计，而本题引入了基于当前状态（已掌握单词数量）的递增记忆成本（需背诵新单词次）。核心约束：输入规模（）：线性或接近线性的复杂度即可满足需求。字符串长度（）：字符串哈希计算与比较的开销极低，可视为常...

2026-04-12

0 20

题解 | #圆覆盖# 来自专栏

问题分析该问题的核心是在二维平面内寻找一个以原点为圆心的最小半径，使得落在此闭圆盘区域内的点权之和达到预设阈值。单调性（Monotonicity）：覆盖点的权值之和与圆的半径之间存在非减的函数关系。即随着的增大，被覆盖的点集是单调不减的，因此权值和也是单调不减的。离散决策点（...

2026-04-11

0 17

题解 | #小红的图上加边# 来自专栏

一、问题分析 1. 问题抽象本问题的本质是在一个给定的森林（由多个连通分量组成的无向图）中添加边，使得所有节点最终处于同一个连通分量内。节点与边：节点数为，已有边数为。初始状态：给定边已经将图划分为个连通分量。操作代价：每添加一条连接两个不同连通分量和的边，代价为。即合...

2026-04-10

2 36

题解 | #绿豆蛙的归宿# 来自专栏

问题分析本题的核心在于求解有向无环图（DAG）上的期望路径长度。由于图的结构是 DAG，其天然具备偏序关系，这使得我们可以通过动态规划（DP）或递推的方式解决问题。关键性质：无环性（DAG）：保证了状态转移不会出现环路依赖，可以使用拓扑排序或递归记忆化搜索。期望的线性性质：期望值具...

2026-04-09

2 27

题解 | #抽卡# 来自专栏

1. 问题建模本问题的核心在于计算多个独立事件的并集概率。由于直接计算“至少抽到一个想要的卡”的概率涉及包含排除原理（Inclusion-Exclusion Principle），随着的增大，组合数项会呈指数级增长。因此，根据概率论的基本性质，计算其补集（余事件）是更优的策略。概率模型 ...

2026-04-08

0 36

题解 | #小苯的麦克斯# 来自专栏

一、问题分析问题的核心是寻找一个长度的连续子区间，使得最大化。 MAX：区间内的最大元素。 MEX：区间内未出现的最小非负整数（从 0 开始）。约束：，这意味着算法必须达到或的时间复杂度。由于涉及连续区间，通常考虑滑窗、单调栈或性质挖掘。二、性质：单调性与局部最优为...

2026-04-06

4 34