Problems
我的力扣主页： 算法花园，代码仓库：xiang578/acm-icpc
[[2025/05]]
[[2025/05/07]] 3341. 到达最后一个房间的最少时间 I 搜索
- 比常规搜索多了一个限制条件，如果到达某一个位置的时间小于 moveTime，那么需要强行将花费的时间改成 moveTime+1
[[2025/05/07]] 2962. 统计最大元素出现至少 K 次的子数组滑动窗口
看错题目，以为是要子数组最大元素至少出现 k 次。。。想了半天，后来发现是整个数组中中最大元素在子数组中出现 k 次。
原始题意是滑动窗口，维护 l 和 r， 区间内最大元素出现次数超过 k，对答案的贡献是 n-r，然后 l–，一直到出现次数小于 k 为止。如果出现次数小于 k，一直 r++到满足条件或者r=n
想错了的题目解法，即以为是要子数组最大元素至少出现 k 次，还是滑动窗口，但是需要维护一个单调栈，维护区间内最大值，如果超过 k 次可以计算对最终答案的贡献，如果遇到更大的值，清空单调栈，然后重新积累。
[[2025/05/14]] 3335. 字符串转换后的长度 I模拟
- 数据量比较小，按题意模拟即可。看这种形式应该可以写出递推公式，然后再上个矩阵快速幂加速。
[[2025/05/15]] 3337. 字符串转换后的长度 II 递推 + 矩阵快速幂
- 模板题目
[[2025/05/15]] 2900. 最长相邻不相等子序列 I 动态规划
- 按题意模拟
[[2025/05/16]] 2901. 最长相邻不相等子序列 II 动态规划
- 和昨天的题目类似，多增加一个用汉明距离 判断。
[[2025/04]] 8
[[2025/04/28]] 2302. 统计得分小于 K 的子数组数目 滑动窗口/尺取法/双指针
最近写过最简单的 hard 题。
维护一个区间 lr， r 增加，判断区间是否满足要求，如果不满足增大 l 一直到区间为 0 或者满足条件，因为元素都是正的，l 越小，lr 的和肯定是越小。找到满足的 lr 之后，对答案的贡献就是 r-l+1.
[[2025/04/25]] 2845. 统计趣味子数组的数目 前缀和
刚开始想处理后缀，搞半天都调不对。。。其实方法不对。
看答案是处理前缀，差一步啊。
[[2025/04/24]] 2799. 统计完全子数组的数目 暴力
- 数据量比较小，可以平方暴力。感觉可以改成尺取之类的方法
[[2025/04/23]] 1399. 统计最大组的数目 模拟
- 数据量比较小，按题意模拟即可。后来再想有什么规律，没有找到。。。
[[2025/04/22]] 2338. 统计理想数组的数目： [[素数筛]]+[[组合数学]]
有点难，只能看到出暴力的方案。题解也看了好久。
最后转化成，n 个盒子放 m 个球的问题（包含 k 种球）
[[2025/04/21]] 2145. 统计隐藏数组数目
- 模拟。数据第一个数字确定后，整个数组就确定。先计算数组中相对于第一个数字的最大和最小偏差。然后枚举第一个数字，计算该数字加上最大和最小偏差后得到的数字是否还在要求的范围内。如果符合要求就是一个可行解。
[[2025/04/19]] 2364. 统计坏数对的数目：暴力算法平方，常规找规律降到线性
[[2025/04/17]] 2176. 统计数组中相等且可以被整除的数对：按题意模拟
[[2023/07]]
[[2023/03]]
[[LC1630. 等差子数组]] #[[Brute Force]]
[[LC887. 鸡蛋掉落]] #二分搜索 #动态规划 挺好一个题目，刚开始以为是一个简单的二分，然后找了几个小时都没有找到规律。然后想用 dfs 去解，又发现超时。
- 几年前碰到过类似的题目，求最小满足题目条件的答案。很难直接计算，转化成二分结果+检验结果的方法去求解。
[[2022/01]]
-
记录一个第二次访问终点需要经过多少个点
点数确定通过时间和等待时间都能算出来。
2034. 股票价格波动 模拟 + 有限队列
1332. 删除回文子序列 多读几遍题意，每次产出的是子序列而不是子串
- 刚开始没有仔细读题，还整理了[[Manacher Algorithm]]……
1345. 跳跃游戏 BFS
简单题，写了快半个小时，先想清楚流程再写，不要边写变想。
按 arr[i] 聚合数字，然后每个点只能访问一次，访问后删除。
2029. 石子游戏 IX
推荐博弈论找规律，反正是类似于
1-(1-2)-...和2-(2-1)-...形式写不出简洁的规律，直接上了模拟……
-
hash
效率更高一些，滑动窗口内 hash
-
- 按题意模拟，坑点在于时间是一个环，需要考虑左边和右边最近的时间。
1220. 统计元音字母序列的数目 简单 DP
- 数据忘记初始化导致浪费十多分钟看问题。
-
python
random.randint(st, ed)蓄水池抽样：遍历链表，假设当前遍历到第 i 个节点，以 $1/i$ 的概率选择第 i 个节点作为最后的答案。
1716. 计算力扣银行的钱 简单模拟或求等差数列通项公式
-
暴力：两个数组最多前 1000 个数字组合，然后排序取前 k 个
看题解
- 使用优先队列，每次取出最小的数字 $(a_i, b_j)$ 后，往队列中 push $(a_{i + 1}, b_j)$ 和 $(a_i, b_{j+})$
-
第一反应是用最长上升子序列的方法。
仔细想了一下，对一个位置 i 维护之前最小的结果 $$min(nums[0…i-1])$$ 和之后最大的结果$$max(nums[i+1…n-1])$$。如果这三个数不相同，就是一个可行解。
1036. 逃离大迷宫 搜索 + 优化剪枝
19 年就尝试过这题，然后当时暴力写了一个搜索，第一个样例就超时了……
坐标范围是 1e6，所以暴力搜索的空间可能是 1e12。题目关键是
blocked.length <= 200这些 blocked 形成包围圈最大是 100*100？(在一个角上借助两条边围成封闭的正方形)。从起点和终点开始搜索，如果可以访问到超过 1e4 个空间，那么代表没有被包围住。
306. 累加数 DFS
枚举最开始两个数字，然后check之后的数据是否合法。
字符串最长长度等于 35，这个数字会超过 long long 的范围。但是观察一下可以发现 a + b = c 情况下，三个数字的长度不会超过字符串长度的 1/2，大概是 18 位，枚举时一个数字最大18位，这样就不会超出 long long 范围。
反思：没有考虑字符串长度小于 3 的特殊情况
-
空间复杂度 $O(n)$ 写法：维护后缀乘积结果。
空间复杂度 $O(1)$ 写法：用返回数组保存前 $0…i$ 的乘积，然后逆序用一个变量保存 $i+1..n-1$ 的乘积，然后可以根据这两个信息得到结果。
[[2021/09]]
5847. 找到所有的农场组 暴力，一个格子是不是起点可以通过判断上边格子和左边格子得知。
5848. 树上的操作 模拟，先想清楚然后再写
5849. 好子集的数目 枚举所有合法组合的个数
5866. 数组的最大公因数排序 [[并查集]] + [[素数筛]]，有相同因子的数会在同一个集合中。
5865. 访问完所有房间的第一天 漏看一个条件，实际上是傻逼题，还是错了好几次，1e9 相加会爆 int 以及返回答案前也需要取模。
1977. 划分数字的方案数 挺复杂的，写了好几个小时，看题解才过…… n=3500，暗示是 $O(n^2)$ 的算法
设以 nums[i…j] 为结尾的方案数是 $dp_{i,j}$
可以发现 $dp_{i,j}=\sum_{k=2i-j-1}^{i-1}dp[k][i-1], dp_{i,j+1}=dp_{i,j} + dp_{2i-j-2,i-1}$，维护一个前缀和。
比较 nums[i…j] 和 nums[2*i-j-1…i-1] 大小，可以先预处理出以 i 和 j 开始的字符串的最大相同长度 lcp[i][j]。
LCP 42. 玩具套圈：r 比较小，可以暴力枚举，被抬一手还是没有写出来。。。需要注意细节。不要提交 debug。
36. 有效的数独：判断数独当前局面是否合法。
37. 解数独：求解数独，上一题的进阶。
[[2021/08]]
[[LC5832. 构造元素不等于两相邻元素平均值的数组]] 排序 + 贪心
[[LC526. 优美的排列]] DP + 状态压缩
5856. 完成任务的最少工作时间段：DP + 子集合枚举
5857. 不同的好子序列数目：不重复的 01 子序列个数，DP
940. 不同的子序列 II：和 5857 类似，字符串包含小写字母
2019 WF
- Problem - J - Codeforces 500 个洞，50 个人。a[500][50]，可以将 a[i][j] 用 l 替代，然后对 a[i] 求和，再从小到达排序，得到 i 的名次。问每个 i 最小的排名是多少？