1.1 数据结构的基本概念 数据：信息的载体 数据元素：数据的基本单位，通常作为一个整体进行考虑，一个数据元素可由若干数据项组成，数据项是构成数据元素的不可分割的最小单位。 数据结构：相互之间存在一种或多种特定关系的数据元素的集合 数据对象：具有相同性质的数据元素的集合，是数据的一个子集。 数据结构的三要素：逻辑结构、数据的运算、物理结构 数据的逻辑结构 集合 线性结构 树形结构 图形结构（网状结构） 数据的物理结构（存储结构） 顺序存储（物理上连续） 链式存储（物理上离散） 索引存储 哈希存储/散列存储 存储结构会影响存储空间分配的方便程度和数据运算的速度 数据的运算：施加在数据上的运算，包括运算的定义和实现。 运算的定义是针对逻辑结构的，运算的实现是针对存储结构的。 数据类型：一个值的集合和定义在此集合上的一组操作的总称 原子类型。其值不可再分的数据类型。 结构类型。其值可被分解为若干成分的数据类型 抽象数据类型(ADT)：抽象数据组织及与之相关的操作。 1.2 算法的基本概念 程序 ...

2.1 数制与编码进位计数制基数：每个数码位所用到的不同符号的个数，$k$ 进制的基数为 $k$$$k进制: a_na_{n-1}…a_{2}a_1a_0…\=a_nk^n+a_{n-1}k^{n-1}+…+a_2k^2+a_1k+a_0+…$$其中 $k$ 的次幂称之为 位权 。 二进制转八进制或者十六进制，只要按3、4位一组转换即可。 整数：除基取余法，比如模2的结果是整数的低位 小数点：乘基取余法，比如乘2的整数是小数的高位 真值与机器数 真值：实际的带正负号的数 机器数：把正负号数字化的数 定点数的编码表示 无符号数 有符号数 原码 / 反码 / 补码 / 移码 若真值为 $x$ ，则用 $[x]_{原}$ 表示原码，其它同理。 反码：若符号位为 $1$ ，数值位全部取反。是补码的中间状态 补码：正数的补码=原码，负数的补码=反码末位+1 规定定点整数补码 $[x]_{补}=1,000…=-2^k$ 小数 $[x]_{补}=1.000…=-1$ 移码：在补 ...

C2Ladder C2Ladder之旅-1300 1 Number of Pairs You are given an array \(a\) of \(n\) integers. Find the number of pairs \((i, j)\) (\(1 \le i < j \le n\)) where the sum of \(a_i + a_j\) is greater than or equal to \(l\) and less than or equal to \(r\) (that is, \(l \le a_i + a_j \le r\)). For example, if \(n = 3\), \(a = [5, 1, 2]\), \(l = 4\) and \(r = 7\), then two pairs are suitable: \(i=1\) and \(j=2\) (\(4 \le 5 + 1 \le 7\)); \(i=1\) and \(j=3\) (\(4 \le 5 + 2 \le 7\ ...

Codeforces等级分突破1200分纪念 之前听闻CF 1200 分是入门，本来以为很轻松就能达到，实际上一直在1100徘徊，在 cf round 1068 div2. 中，总算实现了这一目标，十分激动。看到名字从灰变绿，内心是不可能无动于衷的，我热爱这些传统算法，思考的过程让我着迷，但也未像 Oier、acmer 那样由于一定的压力持续努力。上次icpc-online落选，遗憾错过区域赛。现已经大三上，犹豫是否要参加 ACM-ICPC，因为本来是要决定考研。但我想着，还是上吧。谁教我选了软件工程专业后，最爱算法呢？

C2Ladder C2Ladder之旅-1200 1 Same Differences You are given an array $a$ of $n$ integers. Count the number of pairs of indices $(i, j)$ such that $i < j$ and $a_j - a_i = j - i$. 注意到， \(a_j-a_i=j-i \Rightarrow a_j-j = a_i-i\) ，用哈希记录值为 \(a_i-i\) 的个数 \(n_i\) ，假设共有 \(m\) 组，则有： \[ ans = \sum\limits_{i=1}^m C_{n_i}^2 \] 2 Challenging Cliffs You are a game designer and want to make an obstacle course. The player will walk from left to right. You have \(n\) heights of mountains alread ...

C2Ladder之旅——序章 C2Ladder 是一个提供专于 Codeforces OJ平台的刷题题单网站，是对于 a2oj 的更新、重构。这里，我们将从 Rating 1200 的题出发，开始我们的——C2Ladder 之旅。

参考资料：树形 DP - OI Wiki 树形DP 树形 DP，即在树上进行的DP。由于树固有的递归性质，一般通过递归DFS（或 BFS） 进行 基础 P1352 没有上司的舞会 - 洛谷 某大学有 $n$ 个职员，编号为 $1\ldots n$。 他们之间有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。 现在有个周年庆宴会，宴会每邀请来一个职员都会增加一定的快乐指数 $r_i$，但是呢，如果某个职员的直接上司来参加舞会了，那么这个职员就无论如何也不肯来参加舞会了。 所以，请你编程计算，邀请哪些职员可以使快乐指数最大，求最大的快乐指数。 不妨设 \(f(i,0/1)\) 表示以 \(i\) 为根的子树当其根节点的值 取/不取 的最优解（ \(0\) 表示 \(i\) 不去舞会，反之要去） 对于每个状态，都存在两种决策（以下 \(x\) 为 \(i\) 的所有儿子） 上司不参加舞会时，下属可以参加，也可以不参加，是否参加取决于所能产生的最大快乐值，因此有 \[ f(i,0) = ...

前缀和、差分、离散化 参考资料： 前缀和 & 差分 - OI Wiki 离散化 - OI Wiki 前缀和 数列前 \(n\) 项的和，是一种重要的预处理方式。 一维前缀和 可得到其递推式\(S_0=0,S_i = S_{i-1}+a_i\) 作一维前缀和数组 \(ps\)，其中下标i表示前 \(i\) 项的和 对区间[l,r]求和，显然用 \(ps[r]-ps[l-1]\) 即可，时间复杂度为 \(O(1)\) 二维/多维前缀和 将一维前缀和扩展到多维的情形。其常见的求解方法有两种 基于容斥原理 多用于二维前缀和的情形。给定大小为 \(m\times n\) 的二维数组 \(A\) ，要求求出其前缀和 \(S\)。那么，\(S\) 同样是大小为 \(m\times n\) 的二维数组，且 \[S_{i,j} = \sum\limits_{i'\leq{i} }\sum\limits_{j'\leq{j}}A_{i'j'}\] 显然，对于 \(S_{i,j}\)，我们可以通过容斥原理获得: \[S_ ...

神技 记录网上看到的，泛用性较强的解题神技，持续更新 前缀“乘” 713. 乘积小于 K 的子数组 - 力扣（LeetCode） 往往前缀和，当用乘法表示加和时，是会很容易爆ll的，那么，我们可以通过 \(log\) 对数将乘法转换成加法，把之转化成真正的前缀“和“。尽管，我们无法得到精确的值，但用来作为条件判断已经足够了 前缀和求解转化为 $ ps[i] = ps[i-1]+log(nums[i])$ 求 \([l,r]\) 的乘积小于 \(k\) 可表示为 \(ps[m]-ps[i-1]+10^{-10}<logk\) double 类型只能保证 \(15\) 位有效数字是精确的。为了避免计算带来的误差，相减后要加上 \(10^{-10}\)（题目中的 double 数值整数部分的数字不超过 5 个） ，从而防止不等式两边数值相等却被判定为大于的情况。 浮点数的妙用 Problem - B - Codeforces 对于这个题，我们想要找到大于从最高处下滑的所需时间 \(tn\) ，又想让结果处靠近山底。 由于耗 ...