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

时间：2021-10-22 09:05:12

对于小数的二分

可以写成循环\(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

对于二分图，还有：

  • 最大匹配=最小点覆盖
标签：

相关文章