此在Dasein

分类

/ 注册

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

每日一题@牛客网

134篇文章 124人学习

算法编程训练

16篇文章 347人学习

全部文章（共128篇）

题解 | #小苯的计算式# 来自专栏

算法思路分析问题理解需要统计满足 A+B=C 且字符串总长度为 n 的不同算式数量核心约束：A、B、C 均无前导零（数值为0时长度为1）字符串格式：A的十进制 + + + B的十进制 + = + C的十进制总长度：len(A) + len(B) + len(C) + 2 = n 关键观...

2025-11-21

1 71

题解 | #来点gcd# 来自专栏

算法分析一、算法思想该问题的核心是利用数论性质将子集存在性问题转化为整体GCD判定问题。关键数学性质：对于询问值 x，令 Mₓ 表示原多重集 S 中所有 x 的倍数的集合。则存在 S 的非空子集使得其 GCD 等于 x，当且仅当 Mₓ 中所有元素的整体 GCD 恰好等于 x。证明：充分性...

2025-11-20

1 81

题解 | #旅游# 来自专栏

这是一个典型的图论 + 二分答案 (Binary Search) 问题。我们需要结合最小生成树 (MST) 的思想和贪心策略来解决。核心思路二分答案 (Binary Search): 题目要求找到最小的。如果我们设定一个阈值，国家修好了所有的路。如果在这个下牛牛能修通...

2025-11-19

7 73

题解 | #奶牛排排站# 来自专栏

阶乘进制 (Factorial Number System) 原理介绍阶乘进制，又称为 Lehmer 码 (Lehmer code)，是一种混合基数系统 (Mixed Radix System)，它使用阶乘作为每一位的权值（基数），而不是像传统的进制（如十进制、二进制）那样使用的幂作为权值...

2025-11-18

3 106

题解 | #宵暗的妖怪# 来自专栏

状态定义设 dp[i] 为只考虑第 i 个位置（即 a[1] 到 a[i]）时，能够得到的最大饱食度。由于区间长度为 3，若在第 i 个位置结束一个区间，则该区间必覆盖 i‑2、i‑1、i 三个位置，贡献的饱食度为 a[i‑1]（区间的中点）。状态转移对第 i 个位置有两条决策： ...

2025-11-17

4 69

题解 | #【模板】差分# 来自专栏

这是一个典型的差分数组（Difference Array）应用场景。核心思想是：问题特点：只进行区间修改，且无需在中间过程查询，最终一次性输出结果。这允许我们将"区间操作"转化为"点操作"。关键观察：如果对原数组的区间 [l, r] 增加 d，等价于在差...

2025-11-17

1 69

题解 | #一道GCD问题# 来自专栏

加同一个数不改变差值对于任意两个下标都有因此，经过加法后的所有数的任何公约数必须同时整除原来的所有差值。可实现的必为差值的最大公约数的约数记任何一个满足的整数必须整除所有的差值，从而 . 于是可得到的最大可能的正好是本身。如何求出对应的由于是...

2025-11-17

0 65

题解 | #区间翻转# 来自专栏

1. 关键观察记第 i 个区间为 Ii = [li , ri]（li ≤ ri）。因为 li , ri 都是单调不降的，任意两区间不可能相交（即不会出现 li < lj ≤ ri < rj 的情形），只能在右侧出现以下两种情形：左间隙 li > l{i‑1} → 位置 l...

2025-11-17

4 77

题解 | #收集纸片# 来自专栏

这是一个典型的旅行商问题（TSP）变种，需要从起点出发，访问所有目标点（纸片）后返回起点，且只能沿坐标轴方向移动（曼哈顿距离）。由于纸片数量，数据规模很小，适合使用状态压缩动态规划（DP + Bitmask）进行精确求解。核心观察：两点间最短距离为曼哈顿距离：访问顺序影响总距离，需要找到最...

2025-11-17

4 77

题解 | #不相邻取数# 来自专栏

这是一个经典的动态规划 (Dynamic Programming) 问题，通常被称为最大不相邻子序列和或房屋偷盗问题 (House Robber Problem) 的变体。动态规划解法我们可以定义一个动态规划数组，其中表示考虑数组的前个元素时，能得到的最大不相邻元素之和。对于数组中的...

2025-11-15

0 69