此在Dasein

分类

/ 注册

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

每日一题@牛客网

64篇文章 52人学习

算法编程训练

15篇文章 141人学习

全部文章（共62篇）

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

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

2025-11-17

0 32

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

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

2025-11-17

2 36

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

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

2025-11-17

4 39

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

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

2025-11-15

0 33

题解 | #子数组绝对值的最大值# 来自专栏

子数组的和可以表示为两个前缀和的差值。设为数组的前缀和，即，并定义。那么，从索引到的子数组和可以表示为：我们要找的最大值是。根据绝对值的性质，实际上是所有前缀和（包括到）中任意两个值之间的最大差值。要最大化，我们只需要找到所有前缀和中的最大值和最小值，...

2025-11-15

0 36

题解 | #小苯的因子查询# 来自专栏

核心思路因子总数：首先需要知道的因子总数。奇数因子总数：其次需要知道的奇数因子总数。概率：所求概率即为：模运算：最终结果需要以的形式输出，其中。 1. 阶乘的质因数分解首先，将进行标准质因数分解：其中是小于等于的最大质数。指数的计算：...

2025-11-15

0 36

题解 | 小红走矩阵来自专栏

1. 路径分析从 (1,1) 走到 (n,m)，小红总共需要走 n−1 步向下（D，Down）和 m−1 步向右（R，Right）。因此，总的步数是 (n−1)+(m−1)=n+m−2 步。每条不同的路径，都可以看作是一个包含 n−1 个 D 和 m−1 个 R 的序列。2. 组合公式问题转化为：在...

2025-11-13

0 49

题解 | 小心火烛的歪来自专栏

该问题要求从给定的烟花燃放计划中选择一个子集，使得最终燃放结果满足：所有有杂物的位置（初始状态为1）不燃放烟花，所有无杂物的位置（初始状态为0）燃放烟花。最终目标是找到满足条件的最小子集（计划数量最少）。由于n、m、q的约束均小于等于7，可以采用暴力枚举的方法，遍历所有可能的计划子集，检查每个子集是...

2025-11-13

0 44

题解 | 消减整数来自专栏

一、关键观察设第 i 步减去的数为 ai。规则要求a1=1,ai+1∈{ai,2ai}(i≥1)因此每个 ai 必然是 2 的幂，且指数序列非递减，且每一步的指数最多只能 +1。设出现的最高幂为 2k，则在序列中必有2^0,2^1,…,2^k每种至少出现一次。记 2i 出现的次数为 ci...

2025-11-12

1 35

题解 | 牛牛的构造来自专栏

#include <bits/stdc++.h> using namespace std; using ll = long long; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); ll ...

2025-11-12

1 40