19 年 7 月

港控/mmm° 2023-08-17 16:38 121阅读 0赞

综合专题

1、

树形 DP 的第一个数组继承，优化复杂度。字典树分叉数为 O(n) 。dsu on tree。

树形 DP f\[x\]\[min(SIZE, m)\] ，复杂度 O(nm) ，组合证明。

2、

状态为有向边的树形 DP 。

树的直径中点唯一，可以用来枚举树的直径。

3、

分数规划 dinkelbach 优化复杂度。

题意：100 \* 100 的数字矩阵，找子矩阵满足 数字和 / 周长 最大。

4、

题意：给由 N 个字符串组成的序列，要求划分成两个子序列，使得每个子序列中的字符串前一个是后一个的子序列（或子串）

修正贪心。

5、

题意：给定一个长度为 n 的正整数序列 A ，可以任意将序列中的数变为相反数，问逆序对数为 1, 2, ..., m 的方案数。

对于 a\[i\] > a\[j\] ，只有改变 a\[i\] 会影响这一对是不是逆序对。

利用 bitset 优化背包。

几何专题

花了四天才解决第一天讲课的内容。。我好菜啊。

1、极角序

以原点为基准点的极角排序。

2、凸包

（1）向量 a1, a2, ..., an ，若 b1+b2+...+bn = 1，则 a1b1 + a2b2 + ... + anbn 的区域为 a1, a2, ..., an 的凸包。

（2）

数凸包点数可以转化为数凸包边数。

凸包的边满足所以点在其一侧。

BZOJ 1027：给定点集 S 和 T ，选择 S 的最小子集使得 T 被包围。

OI Camp 16：求一个点集的所有子集的凸包的点数之和，对 998244353 取模。

（3）线性规划对偶

![815718-20190707205658289-1697007782.png][]

CF 605C：给定 (a1, b1), (a2, b2), ..., (an,bn)，(p, q)，求 x1, x2, ..., xn>=0 ，满足 a1x1+...+anxn >= p, b1x1+...+bnxn >= q ，最小化 x1 + x2 + ... + xn 。

直接做的方法弄了好久都不透彻，对偶完就是一个两个未知数的线性规划，半平面交然后三分。

（4）旋转卡壳

BZOJ 1068：最大四边形面积

3、最小圆覆盖

会写 K 维最小圆覆盖就好。

【过程一】

构造 d\[1 .. m\] 与 p\[1 .. n\] 的 K 维最小圆覆盖：

找点 ans 到 d\[1 .. m\] 的距离相等

for i = 1 to n：

当前有 d\[1..m\] 与 p\[1 .. i-1\] 的 K 维最小圆覆盖，构造 d\[1..m\] 与 p\[1 .. i\] 的 K 维最小圆覆盖：

若 p\[i\] 在圆内，则无须改动

否则 d\[m + 1\] = p\[i\] ，递归构造 d\[1 .. m + 1\] 与 p\[1 .. i-1\] 的 K 维最小圆覆盖

【过程二】

找点 ans 到 d\[1 .. m\] 的距离相等：d\[1 .. m\] 在一个 m-1 维的圆上，考虑求出这个 m-1 维的圆的圆心。选 d\[m\] 作为基准点，d\[1 .. m-1\] 可看作 m-1 个向量。由向量基本定理，圆心可以表示为

$$O = x\_1 d\_1 + x\_2 d\_2 + ... + x\_\{m-1\} d\_\{m-1\}$$

又因为

$$O ^ 2 = (O - d\_i) ^ 2$$

化简得

$$d\_i ^ 2 = 2 d\_i \* O$$

代入得

$$2 d\_i d\_1 x\_1 + ... + 2 d\_i d\_\{m - 1\} x\_\{m - 1\} = d\_i ^ 2$$

$m - 1$ 个式子 $m - 1$ 个未知数，高斯消元快乐完事。

这种方法相比于 BZOJ 1013 ，可以更兼容地处理高维空间下的低维外接圆的问题。

4、平面图欧拉定理

R = E - V + 2

ASC 05：给若干个圆，问把平面分成多少区域。

5、平面最近点对

大型口胡：按 x 排序，分治，归并按 y 排序，d = min(左，右)，将右边在 mid.x 到 mid.x + d 的点提出来，对每个左边的点 p\[i\] ，取右边 p\[i\].y - d 之后的前 6 个。

证明：首先可能作为答案的点一定在区域内。然后区域内最多只可能有 6 个点，抽屉原理证明。

CodeJam 09：最小周长的三角形。

6、闵科夫斯基和

定义：C = A + B = \{z | z = x + y, x in A, y in B\}

两个凸包的闵科夫斯基和的凸包可以快速求，当前凸包上的点是 ai + bj ，下一个点是 a(i+1) + bj 与 ai + b(j+1) 较外侧的一个点。

JSOI 2018，需要学会判断一个点是否在凸包内：先二分锁定点所在的区域，然后判凸包边与当前点的位置关系。

7、皮克定理

S = a + b / 2 - 1

用热量扩散趋势来感性证明。

（1）LOJ 九个太阳 Original

$$\\sum\_\{i = 1\} ^ n \\lfloor \\frac\{ai + b\}\{c\} \\rfloor$$

保证 $c | an + b$

（2）给定若干个整点，求这些整点围成的凸包内的整点个数。

（3）给定二维平面内的整点 A(x0, y0) ，找到多个点 B ，满足 OAB 内没有整点。他们讲的皮克定理的做法应该不太对，给出另一种直观的思路：

是把这条线段往上移，碰到第一个整点 (x, y) ，那么 (x, y) 最小化距离 $d$ 。

直线为 $y = y0 / x0 x$ 即 $y0 x - x0 y = 0$ 。

$$d = \\frac\{|y0 x - x0 y|\}\{\\sqrt(x0 ^ 2 + y0 ^ 2)\}$$

当 $y0x - x0y = (x0, y0)$ 时取得最小，扩展欧几里得算法求得多组解。

8、simpson 积分

（1）陈老师：p 是 0..1 中的实数，边权为 a \* p + b \* (1 - p) ，求最短路期望。

（2）圆的面积并，圆的 k 重面积并

（3）g(l, r) = (r - l) \* (f(l) + f(r) + 4 \* f(m) / 6

calc(l, r) =

g(l, r) approx g(l, m) + g(m, r) ?

g(l, m) + g(m, r)

:　　calc(l, m) + calc(m, r)

contest 2

1、重现

直接把整个比赛复述一遍，看着自己写的东西找出问题。

> 昨天就告诉自己要在比较狂躁的时候眨一下眼，调整一下呼吸，保持冷静。逐题去读，秒不了就跳。然后比赛就开始了。A 题先二分答案，然后感觉像网络流，想了很久造不出图，跳。B 题，读完题就感觉要用线段树维护等差数列优化建图，然后跑个最短路，秒不掉，跳。C 题就是一个简单的树形 DP ，直接秒。写完看过一遍程序之后运行一下，发现答案和样例不同。心态有点崩，稍微调整一下，发现自己的算法是错误的。这时候已经过来一个小时，很多人都过了 A 和 H 。这时候我已经想到了 C 的正解，但暂时秒不了，所以先去看 H 。接下来的规划大概是一个小时的时间内先干完 A 和 H 。首先是 H 题，二分加数位 DP 的暴力方法过掉了。然后是 A ，看到很多很多人过了，觉得应该不可能是网络流。“二分答案之后，假如每个人都选第一个？” 剩下的都顺理成章，A 题解决。接下来的规划是用半个小时干完 C ，然后大概就用了半个小时拿到了 C 的一血。看一下榜，发现 D 和 E 比较多人做，然后就 D、E 两道题逐题去开。做 D 的时候还遇到了读题出错的问题，在写完代码调样例的时候发现了问题，好在正解也能用我这种方法做，不需要做什么改动，然后 TLE 。发现自己罚时已经很高，所以关键是题目数量的问题了。想着怎么优化，发现矩阵内很多 0 ，就在矩阵乘法的时候判了一下 0 ，然后就过了。之后就开 E 题大模拟，打完就比赛结束了。最后干了 5 道题，全场最高 5 道，我罚时最多 rank 4 。

小结：

（1）保持冷静。

（2）对于读题这个过程，动机应该是读懂题目，然后要用心去做就好了。记得读样例，防止对题意的理解出现失误，可以避免今天 C 题和 D 题的问题。

（3）自己赛后的学习，至少要做到 再次遇到这道题或相关的题的时候 秒掉它们。

2、给定序列 a ，支持两种操作：

（1）a\[x\] := y

（2）求 $$a\_l + \\frac\{1\}\{a\_\{l + 1\} + \\frac\{1\}\{a\_\{l + 2\} + ...\}\}$$

这种连分数的处理方法是把分子和分母设出来，然后就只是一个线性变换或矩阵乘法了。

我记得高三的时候解过这样一个递推式，用的也是同样的方法：

$$\\begin\{aligned\} & f(0) = 1 \\\\ & f(n) = 1 + \\frac\{1\}\{f(n - 1)\} \\end\{aligned\}$$

复习了一下 zkw ，跑得还挺快的。

![815718-20190712094918576-153156681.png][]

![815718-20190712094945579-2016134862.png][]

![815718-20190712095010778-419598925.png][]

![815718-20190712095146409-2035447514.png][]

3、

（1）题意

n 个点 m 组边 (x, l, r, k, b):

for i = l to r

directed\_link(x, i, k \* (i - l) + b)

求最短路。

（2）做法

想好暴力的 dij ，用李超线段树优化，支持三种操作即可：

1）区间对等差数列取 min

2）删除一个点

3）查询全局最小值及其位置

区间最小值其实也是可以查询的。

**注意自己的函数是 k \* (x - l) + b ，不是 k \* x + b 。（要么换种写法也行）**

（3）李超线段树解决斜率优化

fi = max(fj + ai \* sj)

如果 a 和 s 都没有单调性，李超线段树就是一种很简洁地解决办法了。

（4）区间对区间连边，求最短路。

可以不需要线段树优化建图，直接按这道题来做，O(n log n) 。

图论专题

1、最短路

（1）01-BFS

给定一张图，边权只有 0 和 1 ，求点 1 到每个点的最短路。

直接进行 BFS ，边权是 0 就加到队列首，边权是 1 就加到队列尾。

双端队列的实现：

1）deque<int> que;

que.empty();

que.push\_front(); que.pop\_front(); que.front();

que.push\_back(); que.pop\_back(); que.back();

2）手动开数组

int que\[2 \* N\], \* qh = que + N, \* qt = qh;

例题：给定一张图，边权是 0, 1, 2, 3, 4, 5 ，求点 1 到每个点的最短路。

将边权为 k(k > 1) 的边中间加入 k-1 个点，然后跑 01-BFS 。

（2）差分约束系统

1）minimize　　z = x1 + x2 + x3

s.t.　　xi >= 0

x1 - x2 >= 3

x1 - x3 >= 2

x2 - x3 >= -1

x3 - x1 >= 2

所有值大于等于 0 且最小，松弛得到最小就是从负无穷开始的，所以跑最长路，最长路的约束是 xi >= max(xj + w) >= xj + w ，将原有的约束条件改写。

上面陈述的就是到底要跑最长路还是最短路的思考思路。

2）看看还能出什么有趣的问题。考虑把上面问题对偶：

maximize　　z = 3y1 + 2y2 - y3 + 2y4

s.t.　　yi >= 0

(　　1　　1　　0　　-1　　)　　( y1)　　　　　(1)

(　　-1　　0　　1　　0　　)　　(y2)　　<=　　(1)

(　　0　　-1　　-1　　1　　)　　(y3)　　　　　(1)

考虑其组合意义：

有长度为 m = 3 的序列，给定 n = 4 个区间 \[l, r\] ，每次将区间内的数增加一个非负实数 yi ，要求下一个位置不能比上一个位置大超过 1 ，每个区间有一个实数权值 bi ，最大化 b1y1 + b2y2 + ... + bnyn 。

想不到直接的做法，那么就考虑对偶回去做。

睡十分钟等会打 CF 一场上橙。预定上橙失败。

（3）SPFA

考虑一类特殊的松弛问题：

1）给定一条直线上的 n 个位置，相邻两个位置有距离 wi ，起点到每个点的距离为 di ，求起点到每个点的最短距离。

2）给定一棵树，每条边有权值 wi ，起点到每个点的距离为 di ，求起点到每个点的最短距离。

都可以进行两次单项松弛解决问题。

（4）K 短路

今天写了一个第 K 小的操作次数的八数码问题，注意康拓展开的编码方式，怎么 encrypt ，怎么 discrypt 。

（5）最短路 DAG ，最短路树

1）对每个点问，删去从 1 号点到它的最短路径的最后一条边后 的最短路。

最短路树，并查集路径压缩。

2）问最少将边权增加多少才能改变最短路的值。

3）一个 DAG ，问删掉每个点 / 每条边后从 1 到 n 的最短路。

转载于:https://www.cnblogs.com/Sdchr/p/11143263.html

[815718-20190707205658289-1697007782.png]: /images/20230810/c9410a67c9894676958d29d10bda3b25.png
[815718-20190712094918576-153156681.png]: /images/20230810/ec74c2ca022e44238f0ffa9b9784165c.png
[815718-20190712094945579-2016134862.png]: /images/20230810/12e76b3a20864b47b8b712c151eb5544.png
[815718-20190712095010778-419598925.png]: /images/20230810/0dca7488db334518b4ed33a3430fbc60.png
[815718-20190712095146409-2035447514.png]: /images/20230810/3af464644f174d54a8df7bfcbb507325.png