CF1025D Recovering BST

tony102

2021 年 02 月 19 日

1035 次浏览

暂无评论

818字数

题解

[Link](https://www.luogu.com.cn/problem/CF1025D)

## Sol

注意到这是一个二叉树，而且是一棵二叉排序树

一棵二叉树，也就是说对于一个点它只有左右两个儿子。我们可以在一个区间内dp来选择它的左右儿子。我们设$f[i][j][k]$表示在区间$[i,j]$内以是否能以$k$为根并且满足任意两个直接相连的点之间的权值最大公约数不是$1$的条件。$O(n^2)$ 地枚举区间，$O(n)$ 地枚举根，$O(n)$ 地枚举儿子节点。时间复杂度为 $O(n ^4)$

因为这是一棵BST，它的中序遍历的话权值就是从小到大的。构造合法的树也会满足这样的条件。也就是说，区间$[i,j]$组成子树的父节点一定是$i-1$或$j+1$

设$opt[i][j]$表示$a[i]$和$a[j]$的公因数是否**不为1**。设$f[i][j][0/1]$ 表示区间$[i,j]$以$0: i-1$ 或 $1: j +1$ 为父节点时是否可行。若该区间本身可行，当前枚举的根为$k$， 若$opt[i-1][k] = 1$ ，则$f[i][k][0] = 1$。 以$j+1$为父节点的情况同理

这样以来省去一维状态，时间复杂度降至$O(n^3)$，可以通过本题。具体实现的时候可以预处理两个数的最大公因数是否为$1$来转移。当区间$[1,n]$出现一种合法状态的时候，即可输出`Yes`，否则无解。

## Code
```cpp
#include <bits/stdc++.h>
using namespace std;

const int SIZE = 7e2 + 5;

int n;
int a[SIZE], opt[SIZE][SIZE], f[SIZE][SIZE][2];

namespace ae86 {
	const int bufl = 1 << 15;
	char buf[bufl], *s = buf, *t = buf;
	inline int fetch() {
		if (s == t) { t = (s = buf) + fread(buf, 1, bufl, stdin); if (s == t) return EOF; }
		return *s++;
	}
	inline int read() {
		int a = 0, b = 1, c = fetch();
		while (!isdigit(c))b ^= c == '-', c = fetch();
		while (isdigit(c)) a = a * 10 + c - 48, c = fetch();
		return b ? a : -a;
	}
}
using ae86::read;

int gcd(int a, int b) {
	return !b ? a : gcd(b, a % b);
}

int main() {
	// freopen("code.in", "r", stdin);
	n = read();
	for (int i = 1; i <= n; ++ i) a[i] = read(), f[i][i][0] = f[i][i][1] = 1;
	for (int i = 1; i <= n; ++ i) {
		for (int j = i + 1; j <= n; ++ j) {
			if (gcd(a[i], a[j]) != 1) opt[i][j] = opt[j][i] = 1;
		}
	}
	for (int len = 1; len <= n; ++ len) {
		for (int i = 1, j; i + len - 1 <= n; ++ i) {
			j = i + len - 1;
			for (int k = i; k <= j; ++ k) {
				if (f[i][k][0] && f[k][j][1]) {
					if (i == 1 && j == n) { puts("Yes"); return 0; }
					if (opt[i - 1][k]) f[i - 1][j][1] = 1;
					if (opt[k][j + 1]) f[i][j + 1][0] = 1;
				}
			}
		}
	}
	puts("No");
	return 0;
}
```

最后修改：2021 年 08 月 20 日