第一章 0x00 基本算法

0x01 位运算

• a^b 标准快速幂取余
• 64位整数乘法
  • $10^{18} \times 10^{18}$ 大数相乘，超过范围，是1就加，base增增
• 最短Hamilton路径: 集合，状压DP
• 起床困难综合症
  • 通过暴力验证 不符合 交换律
  • 利用位运算的性质: 第$k$位置的的运算不会影响其它位
  • 时间$32 \times 2 \times 10 ^5$

0x02 递推与递归

01序列: 子集枚举

• 排列,全排列
• Strange Towers of Hanoi
• Sumdiv ?
• Fractal Streets ?

0x03 前缀和与差分

• 前缀和与差分一对互逆映射,对应的序列一一对应
• 任何在原序列上的区间操作都可以转成前缀和序列($sub seq$)的一对单点操作
• 应用
  • 多个区间，多个点 ,某个区间是否含有点

0x05 二分

• 二分常用应用
  1. 第一个/最后一个元素x出现的位置
  2. 某个元素的数量
  3. 不在区间中的点： 多个区间，多个点，判断某一个点是否在任一区间里
     1. 方法: 二分过滤出$l_i < dot$的区间,$max\_right(i) = \max_{1 \le j \le i} \{r_j\} > dot$ 表明点 $dot$在某一个区间内

Best Cow Fences

• $\times 1000$然后输出,说明保留三位精度,那么答案不是精确算出来的,是逼近的,能逼近的算法: 实数二分
• P,Q公共条件( >=L )
• 若P: a序列的最大平均数是ave
• 则Q: b需要 maxsum_subseq = 0
• P => Q
• P1: a序列的最大平均数是ave,且 x < ave,Q1: b( [bi | bi = ai-x ]). maxsum_subseq > 0: $P1 \Rightarrow Q1$
• 利用DP单调性(滑动窗口,转移区间只加) : 存在O(n)的算法求出最大(>=L)的最大字段和
• 总结:二分答案: 最大子段和(b序列)与 最大字段平均数(a序列)直接的关系: $max_subseq b > 0 \Rightarrow max\_ave(seq a) < x$ ,$[b_i | b_i = a_i - x]$

Innovative Business

TODO

0x05 排序

题目Cinema

二维元组大小比较, 需要离散化($O(logn)$),再来扫一遍$O(n)$

题目货仓选址

证明: 创建点x,使得x到数轴上其它的距离和最小
证明: 递归,数学归纳

1. a---b 两个的点时答案集合为$[a,b]$,分类讨论
2. a--b--c--d,4个点时,最外层的a,b答案(贡献)$[a,b]$,当保证最终答案$ans \in [a,b]$时,就变成了两个点b--c的子问题,且$[b,c] \subset [a,b]$(贪心: 决策包容性)
3. 奇数个点,可以把中间的那个点当成:两个重合的点,于是奇数变成偶数.

七夕祭

前提题目:

• 多个均分纸牌: luogu P1031 T565389 环形 P2125 P2512
• 证明: 可拆性: 最优答案不可能成环(存在相邻两个人,不传递)

1TODO