此在Dasein

分类

/ 注册

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

每日一题@牛客网

150篇文章 197人学习

算法编程训练

16篇文章 439人学习

全部文章（共143篇）

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

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

2026-04-11

0 73

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

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

2026-04-10

2 86

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

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

2026-04-09

2 68

题解 | #抽卡# 来自专栏

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

2026-04-08

0 85

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

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

2026-04-06

4 197

题解 | #Kevin喜欢零(困难版本)# 来自专栏

1. 差分转化直接统计“恰好等于 ”较为困难，因为是一个非单调的约束。依据排除法原理，我们可以将约束转化为：令为满足的子段数量。条件等价于：这是一个具有二元单调性的判定问题，非常适合双指针或滑动窗口优化。 2. 双指针 + 滑动窗口对于确定的左端点，随着右端点的增...

2026-04-05

1 39

题解 | #树上行走# 来自专栏

问题分析本题的核心在于理解“节点消失”引发的动态图收敛过程。根据题目规则：一旦选定进入某点，所有与类型不同的点（即的点）及其关联边均会立即从图中移除。这意味着：可达性限制：牛牛只能在与起始点类型完全相同的点所构成的连通分量中移动。图的演变：原始树结构会被简化为若干个互不...

2026-04-04

0 73

题解 | #1=N# 来自专栏

问题分析本问题的核心是将一个正整数分解为若干个整数的乘积（即），使得这些因数的总和最小。讨论：我们需要权衡“一次性增加大的 ”还是“多次增加小的 ”。例如达到：方案 A：一次性选择，成本为 6。方案 B：先选，再选，成本为。显而易见，分解能够降低总成本。算...

2026-04-03

0 97

题解 | #收集金币# 来自专栏

1. 问题分析本题是一个典型的带有动态约束的网格路径最优化问题。其核心特征在于：移动限制：仅能向右或向下，构成了典型的有向无环图（DAG）结构。时空约束：方格变为障碍点（墙）的时间是动态的。这意味着一个方格是否可行，不仅取决于其坐标，还取决于到达该方格的时间步。即时判定：每一回合先发...

2026-04-02

1 72

题解 | #冥古之潮# 来自专栏

1. 问题分析本问题的核心在于无权联通图中基于距离约束的组合计数。我们需要从图中选取个点组成集合，满足这些点到给定中心点的最短路径长度（记为）呈严格升序且不为。拓扑结构与距离：由于所有边长均为 1，且不存在重边与自环，点到其他点的最短距离可以通过广度优先搜索（BFS）在时...

2026-04-01

1 71