挑战程序设计竞赛（第2版）第3章札记

挑战程序设计竞赛（第2版）第3章笔记

对于小数的二分

可以写成循环$n$次的形式，$100$次循环可以达到$10^{-30}$的精度。小心因为eps设得太小导致死循环。

最大化平均值的二分

一些有除法的题目都需要用到这种技巧。

例题

有$n$个有价值和重量的物品，从中选出$k$个使得单位重量的价值最大。

算法

二分答案$x$，然后就需要判断：$$\sum {v_i} \div \sum {w_i} \geqslant x$$
就有$$\sum {v_i - x \cdot w_i} \geqslant 0$$
接着贪心选取即可。

开灯问题（矩阵中）的新解法

核心：只要枚举第一行的开关情况，就能够确定其他格子的操作。

集合的枚举

枚举大小为$k$的子集方法：

int comb = (1 << k) - 1;
whlie (comb < 1 << n) {
    // insert code here
	int x = comb & -comb;
	int y = comb + x;
	comb = ((comb & ~y) / x >> 1) | y;
}

折半搜索

适用于$n(30)$的题目。

find函数

例子：

posi = find(a.begin(), a.end(), 1024) - a.begin()

`i -= i & -i`等价于 `i &= i - 1`

区间修改，区间询问

如果操作的高的结果可以用$i$的$n$次多项式表示，那么就可以使用$n + 1$个树状数组来维护。

例子：区间加上一个值，询问区间值的和。

令$s(i)$为前缀和。表示成如下形式$$s(i) = a \cdot i + b$$

如果在$[l,r)$加上x，那么有：
$i < l : s'(i) = s(i)$
$l \leqslant i \leqslant r : s'(i) = s(i) + x \cdot i - x \cdot (l-1)$
$r < i : s'(i) = s(i) + x \cdot (r - l + 1)$

merge函数

用于归并排序！

merge(data1.begin(), data1.end(), data2.begin(), data2.end(), datanew.begin());

二分图的特殊的东西

对于任意图：

不存在孤立点：最大匹配+最小边覆盖=n
最大独立集+最小点覆盖=n

对于二分图，还有：

最大匹配=最小点覆盖

挑战程序设计竞赛（第2版） 第3章札记