树状数组和线段树 树状数组和线段树树状数组相比线段树更快，代码更短 一.树状数组 树状数组的下标是从1开始的 基本功能 在某个位置上加上一个数，即单点修改 求某个前缀和，即区间查询 树状数组的每个元素c[x]表示A[x]中区间[x-lowbit(x), x]里的数的和，lowbit(x)表示x的二进制形式后0的个数，也可以表示为x&-x 123456// 求和for(int 2022-03-15 algorithm 树状数组 线段树 数据结构
WOOP 我们从第一个字母开始。第一个字母是W。W就是wish的缩写，就是愿望的意思。请想象你最想通过努力实现的事情。如果你有好几个愿望，那就选一个对你而言最重要的。记住，一次只能想一个愿望。 想好了吗？好，现在我们来到第二个字母，O。O是outcome，结果。你实现愿望或解决心事之后，最好的结果是什么？在四周安全的情况下，你可以闭上眼睛想象,努力量化你的愿望，或者想象愿望实现的情景。想象一下这个结果。现在 2022-03-11 advice inspiration 心理学
ACDaily 8 枚举、模拟问题续1.移动距离X星球居民小区的楼房全是一样的，并且按矩阵样式排列。 其楼房的编号为 1,2,3…当排满一行时，从下一行相邻的楼往反方向排号。 比如：当小区排号宽度为 6 时，开始情形如下： 1 2 3 4 5 612 11 10 9 8 713 14 15 …..我们的问题是：已知了两个楼号 m 和 n，需要求出它们之间的最短移动距离（不能斜线方向移动）。 输入格式输 2022-03-10 ACDaily 模拟 规格化输入与输出
ACDaily 7 枚举、模拟问题这类问题通常没有一个非常契合的算法作为计算模板，但通常数据量是有过精心设计的。 我们可以通过以下问题来看一看。 1.连续区间段 没有思路时，从暴力做法入手 整体复杂度由每一步的复杂度进行组合后确定 一般可以通过一半的小数字样例 遍历复杂度为O(n)，排序算法复杂度为nlogn 当多重循环内包含大于等于10句话，就属于长代码了。 形成暴力做法的思考闭环后，有想法可以对算法进行优化 逆 2022-03-09 ACDaily 模拟 枚举
ACDaily 6 背包问题练习与LeetCode初体验这两天做题效率低了一些，不过背包是一块难啃的骨头，要集中一些。 波动数列观察这个数列： 1 3 0 2 -1 1 -2 … 这个数列中后一项总是比前一项增加2或者减少3，且每一项都为整数。 栋栋对这种数列很好奇，他想知道长度为 n 和为 s 而且后一项总是比前一项增加 a 或者减少 b 的整数数列可能有多少种呢？ 输入格式共一行，包含四个整数 n,s,a,b，含 2022-03-06 ACDaily DP 背包问题 LeetCode 字符串拆分与拼接
ACDaily 5 从集合角度分析DP问题算法特点 一般问法：最值（价值等属性）、达到某一目标的方向总数 背包问题的本质为组合问题，即在一定条件下从一部分物品中挑选物品；同时也类似于图论的最短路，可以说，DP是一种特殊的图论 暴力做法：方案数量为指数级 化零为整：挖掘不同方案间的共同关系，把有相同关系的元素放在一起 化整为零：把一个集合划分为多个子集，进行分析 解决问题的过程中一定抓住从实际含义出发 具 2022-03-05 ACDaily DP 背包问题
ACDaily 4 不简单DP01背包问题有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。 第 i 件物品的体积是 vi，价值是 wi。 求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。输出最大价值。 输入格式第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。 接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。 输出格式输 2022-03-04 ACDaily DP 背包问题
ACDaily 3 数学与简单DP数学（根据例题讲解）买不到的数小明开了一家糖果店。 他别出心裁：把水果糖包成4颗一包和7颗一包的两种。 糖果不能拆包卖。 小朋友来买糖的时候，他就用这两种包装来组合。 当然有些糖果数目是无法组合出来的，比如要买 10 颗糖。 你可以用计算机测试一下，在这种包装情况下，最大不能买到的数量是17。 大于17的任何数字都可以用4和7组合出来。 本题的要求就是在已知两个包装的数量时，求最大不 2022-03-03 ACDaily 算法中的数学
ACDaily 2 二分与前缀和的练习分巧克力儿童节那天有 K位小朋友到小明家做客。 小明拿出了珍藏的巧克力招待小朋友们。 小明一共有 N 块巧克力，其中第 ii 块是 Hi×Wi 的方格组成的长方形。 为了公平起见，小明需要从这 N 块巧克力中切出 K 块巧克力分给小朋友们。 切出的巧克力需要满足： 形状是正方形，边长是整数 大小相同 例如一块 6×6 的巧克力可以切出 66 块 2×2 的巧克力或者 2 块 2022-03-02 ACDaily 二分与前缀和
ACDaily 1 前缀和模板题1. 前缀和输入一个长度为 n 的整数序列。 接下来再输入 m 个询问，每个询问输入一对 l,r。 对于每个询问，输出原序列中从第 l 个数到第 r 个数的和。 输入格式第一行包含两个整数 n和 m。 第二行包含 n 个整数，表示整数数列。 接下来 m 行，每行包含两个整数 l 和 r，表示一个询问的区间范围。 输出格式共 m行，每行输出一个询问的结果。 数据范围1≤l≤r≤n,1≤n 2022-03-01 ACDaily 前缀和
