树状数组和线段树 树状数组和线段树树状数组相比线段树更快,代码更短 一.树状数组 树状数组的下标是从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 前缀和