「Summary」寒假第一期集训小结

Posted on Edited on In

寒假第一期小结

总结

感觉最大的进步是学会了卡常。

这一期主要学了和单调队列有关的dp优化和各种高级搜索，合起来无非是优雅的暴力。。。

dp优化

单调队列优化学得还好，斜率优化硬是花了一天半的时间才想明白，但是如果模式化地去理解，还是比较好懂。

单调队列优化

单调队列优化针对于普通版本的，没有 $i \times j$ 这样的结构的状态转移方程。

如果将其看作函数，真正影响其值的大小的量其实是于 $i$ 无关的变量(可以把含有$i$的值看作常量)，那么就可以用单调队列去维护区间的最值。

常规操作
1
2
3
4
while (head <= tail && q[head] 的值不在可更新的范围内) head++; // 踢队头
dp[...] = dp[q[head]] ...;
while (head <= tail && i 的贡献比 q[head] 的贡献更大) tail--; // 踢队尾
q[++tail] = i;

斜率优化

当状态转移方程中出现了 $i$ 与其它变量的乘积的时候，单调队列无法单纯的去维护时，就需要斜率优化。

个人认为代数法是最好理解的。。。

举个例子？
以Cats Transport一题为例:

怎么又是这道

$dp_{i,j} = min_{0 < k} ^{j-1}(dp_{i-1,k} + (j - k) * a_j - sum_j + sum_k)$
$dp_{i,j} = dp_{i-1,k} + (j - k) * a_j - sum_j + sum_k$

假设有$k_1$、$k_2$两个状态点, $k_2$在$k_1$后，且$k_2$比$k_1$更优。

则可以知道:

$dp_{i-1,{k_1}} + (j - k_1) * a_j - sum_j + sum_{k_1} \geq dp_{i-1,{k_2}} + (j - k_2) * a_j - sum_j + sum_{k_2}$

化简:

$dp_{i-1,{k_1}} + (j - k_1) * a_j + sum_{k_1} \geq dp_{i-1,{k_2}} + (j - k_2) * a_j + sum_{k_2}$

将带有$i$的和没有的整理得：

$ (dp_{i-1,{k_2}} + sum_{k_2}) - (dp_{i-1,{k_1}} + sum_{k_1}) \leq a_j \times (k_2 - k_1)$
因为$k_2$在$k_1$后，所以$(k_2 - k_1) \geq 1$。
将$(k_2 - k_1)$移到左边:

$ \frac{(dp_{i-1,{k_2}} + sum_{k_2}) - (dp_{i-1,{k_1}} + sum_{k_1})}{(k_2 - k_1)} \leq a_j$

所以得到了啥？

。。。

当初一直不懂为啥要推式子，想了很久终于明白了它的意义。。。

回忆单调队列的操作，首先维护队头的最优解，然后去掉队尾的亢余

那么按照操作来可以知道：

$q[head + 1]$和$q[head]$在满足上面的公式的时候，$q[head + 1]$比$q[head]$更优。

所以可以踢掉队头。

那么可以通过状态转移方程知道解的单调性。

回忆$ZSJ$在数学课上讲的线性规划 (当时就看到他用一根线在坐标系上移来移去，不知道在干啥。。。)

要是最后的答案最小，那么就要让基准线的截距最小(不考虑交点在2、3、4象限)

而基准线要经过其中的一个决策点：

那么如下图：

...

可以看出无论是选择$q[tail - 1]$或者$i$，得到的答案都会比选择$q[tail]$优，那么此时，利用点连线间的斜率关系，就可以把$q[tail]$弹出去。

可以有： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#
int X(int i) { return ...; }
int Y(int i) { return ...; }

long double K(int i, int j) {
	return (Y(j) - Y(i)) / (X(j) - X(i));
}

int main() {
	/*单调队列*/
	head = 1, tail = 1;
	q[tail] = 0;
	for (int i = 1; i <= n; i++) {
		while (head < tail && head 与 head + 1 的关系满足你推出的式子) head++;
		dp[i] = ...;
		while (head < tail && tail不可能成为决策点(用K(i, q[tail - 1]) 和 K(q[tail - 1], q[tail])的大小关系)) tail--;
		q[++tail] = i; //不要忘记。。。
	}
	/*单调栈*/
	return 0;
}

高级搜索

首先说明：其实所学内容并非高级搜索，而且我也不是十分赞同这个名字，但是为了与gm所讲的内容大致合拍，我使用了这个标题。

我认为这些搜索算法应该分为基于合理预判的贪心性搜索算法、对于可不完全合并性题目的折半搜索，和已知明确终态的双向搜索

名字取得有点儿奇怪，但他们的本质的确如此。

因而，总结的逻辑也出来了。

基于合理预判的贪心性搜索算法

忽略掉iddfs，它只不过是应付那些不用idAstar就能水过去的题目而已了。说白了，就是个低配版本的idAstar

所以，总结Astar和idAstar即可。关系其实和bfs和dfs差不多

分开写也没必要。。。

所谓基于合理预判，其实就是指的算法中的h()函数。h()函数满足一个要求 $h(x) \leq f(x)$ 即估计值要小于实际的权值。

简单说一下：假如没有遵循这个原则，可以预见到某些最优状态将会一直被压在队底而弹不出来，导致扩展出来的路径并非最优解。

所以，写一个比较好的估价函数是整个算法的关键。而且估价函数的值越接近实际值，算法的效率越高。

估价函数的值可以定义为与目标状态不同点的个数 或是 不同点之间的距离。

给出两种算法的伪代码:

Astar

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
struct state {
	int g, h;
	int H() {
		...
		return 估价值;
	}
	bool operator < (node other) const {
		return (g + h) > (other.g + other.h);
	}
}
priority_queue<state> q;

int Astar() {
	q.push(s);
	while (q.size()) {
		state u = q.top();
		q.pop();
		if (达到目标状态) {
			return ...;
		}
		for (每一个分支) {
			state v = ...;
			q.push(v);
		}
	}
	return -1;
}

idAstar

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int H() {
	...
	return 估价函数;
}

bool Check() {
	if (...) return 1;
	else return 0;
}

bool idAstar(int step, int limit) {
	if (H() + step > limit) return 0;
	if (Check()) return 1;
	for (每一个分支) {
		...
		if (idAstar(step + 1, limit)) return 1;
		...
	}
	return 1;
}

对于可不完全合并性题目的折半搜索

在一般情况下，你会算出暴力的时间复杂度在 $2^{40}$ 左右。。。

折半搜索可分为方程模型和选择模型，方程模型一般可以将式子拆成等价的两边，在集合一半的范围类进行搜索，在此基础对两个结果集合合并(不完全合并)，从而减少时间复杂度。选择模型思路也大致类似.

伪代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void dfs(int* ans, int& size, int now, int sum, int limit) {
    if (now > limit) {
        ans[++size] = sum;
        return;
    }
    if (sum + p[now] <= m)
        dfs(ans, size, now + 1, ..., limit);
    dfs(ans, size, now + 1, sum, limit);
}
dfs(lans, cnt1, 1, 0, n / 2);
dfs(rans, cnt2, n / 2 + 1, 0, n);
sort(rans + 1, rans + 1 + cnt2);
for (int i = 1; i <= cnt1; i++) {
    int sum = upper_bound(rans + 1, rans + 1 + cnt2, m - lans[i]) - rans - 1;
    ans += sum;
}

已知明确终态的双向搜索

使用前提是有明确的终态。

那么可以从起点和终点同时开始搜索，在理论上可以将搜索树减少。

实现与bfs相似:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
int bfs() {
	s.opt = 1, t.opt = 0;
	q.push(s);
	q.push(t);
	int ss = p.hash(s.m), tt = p.hash(t.m);
	ans[s.opt][ss] = 0;
	ans[t.opt][tt] = 0;
	vis[s.opt][ss] = 1;
	vis[t.opt][tt] = 1;
	while (q.size()) {
		node u = q.front();
		q.pop();
		int now = p.hash(u.m);
		if (vis[!u.opt][now] == 1) {
			return ans[!u.opt][now] + ans[u.opt][now];
		}
		for (int i = 1; i <= 4; i++) {
			int nx = u.x + dx[i];
			int ny = u.y + dy[i];
			if (nx < 1 || nx > 3 || ny < 1 || ny > 3) continue;
			node v;
			v.coopy(u);
			v.x = nx, v.y = ny;
			swap(v.m[nx][ny], v.m[u.x][u.y]);
			int tmp = p.hash(v.m);
			if (vis[v.opt][tmp] == 0) {
				vis[v.opt][tmp] = 1;
				q.push(v);
				ans[v.opt][tmp] = v.step;
			}
		}
	}
	return -1;
}

END

终究是写完了。。。

如有不妥当之处，还请各位路过高手不惜赐教。

The End
「Ô mon âme, n'aspire pas à la vie immortelle, mais épuise le champ du possible.」