zaizwk

线段树介绍解决问题类型 单点修改 区间修改 区间查询 建议与提示 不同的操作对应不同的题目类型，有的不需要修改只需要查询，有的不需要查询只需要修改，这类题目一般有简单的做法，比如单调队列的最大值问题 一般的结合律和共享可累计性质的操作，都可以视作线段树里的操作，例如求和、求积、求最值、求最大公约数等 单点修改加上区间求和的题目也可以用树状数组来做，可以参考之前的文章 上述需求的组合，一般使用线段树来做 熟能生巧 写法本人是Java选手，因此使用Java来实现，其他语言是类似的，这里给出单点修改 + 区间求和的代码以及区间修改 + 区间求和的代码 单点修改 + 区间求和题目链接 树状数组模板题 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485import java.io.BufferedReader;import ...

单调栈 | 单调队列单调栈解决问题某位置之后（之前）的第一个大于（小于）自身的元素是谁 时间复杂度$O(n)$ 操作模板123456789public something solve(int[] a) { for (int i = 0; i < a.length; i++) { while (!d.isEmpty() && a[i] ? a[d.peek()] 这里的偏序符号(?)取决于是递增(<)还是递减(>)栈) { // do something 求和 or 赋值 or 做出自己的处理 } d.push(i); } return something} 记忆方式 下一个更大 $\to$ 递减 下一个更小 $\to$ 递增 例题1给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后 ...

树状数组特点和用途 一种数据结构 快速前缀和 快速修改某一个数字 上述两个操作可以动态进行 两个操作都是 $O(\log N)$ 实现由于本人是Java选手，因此使用Java实现 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.*;public class Solution { static int max(int... a) { int res = a[0]; for (int i : a) res = Math.max(res, i); return res ...

第二届ACC(AcWing Cup)全国联赛T1 人话版本对于最开始的 $0$，有两种操作： 加上非负数 $a$，代价为 $a$ 乘以 $2$，没有代价 问，把 $0$ 变成 $n$ 的最小代价 求解首先，注意非负整数，说明我们只能让我们的数字变大，因此不能操作到超过当前数，而另一个操作是把当前数字乘以2，因此这一步我们只能得到偶数 那么如果目标数是一个奇数，我们就得找到它最近的偶数，然后代价加上1即可，而最近的偶数，可以用同样的办法来得到 特别地，当目标数是2的整数幂的时候，答案是1，因为只需要得到1，然后不断地乘以2即可，而乘以2是不消耗代价的 代码12345678n = int(input())def solve(x): if not x&(x - 1): return 1 if x&1: return solve(x / 2) + 1 return solve(x / 2)print(solve(n)) T2 人话版本给一个 $n$ 进制数的前 $101$ 位权重值（也就是 $n ^ i$，其中$i = 0,1\ ...

分支界限法介绍分支界限法（Branch and Bound）是一种在搜索问题中用于优化解空间搜索的算法。它可以在搜索过程中动态地生成子问题，通过一定的策略选择最具有潜力的子问题进行求解，并且可以快速排除那些不能优化目标的子问题，从而缩小搜索空间，提高求解效率。 通俗来讲，分支界限法就是在搜索问题时，通过先生成一个大问题，再把它分成许多小问题，然后一步一步地解决这些小问题，找到最优解。在这个过程中，我们还会根据当前的解空间来确定哪些问题没有必要再去尝试，从而加快搜索的速度。 总之，分支界限法是一种高效的搜索算法，可以在很多优化问题中发挥重要的作用。 示例求解考虑如下 0 - 1背包问题 n = 4, w = [3, 5, 2, 1], v = [9, 10, 7, 4], c = 7 求解问题一定要明确自己再干什么，分支界限法实际上是一种剪枝的过程，而不是造树的过程，树已经造好了，做到心中有树，我们要把满二叉树尽可能的剪枝，然后求得最优解 如何剪枝？ 如果生成不了最优解，那么舍弃，考虑把当前位置以及之后的全部物品全选，看看能不能超过当前最优解 如果放不下，那么舍弃 选择过程中直接更新 ...