GCD & 二叉搜索树
问题描述
有一些数，这些数要拼成一棵树。
此树为二叉搜索树，且任意树边相连的两个节点的gcd都超过1。
求这些数是否满足要求。
|
第一行一个整数 t，表示数据组数。
对于每组数据，第一行输入一个 n，表示数的个数。
接下来一行有 n 个数，保证输入是升序的。
t ≤ 5，n ≤ 700，ai ≤ 1e9。
|
Output
每组数据输出一行，如果能够造出来满足题目描述的树，输出Yes，否则输出No。
无行末空格。
|
Sample
Input:
1
6
3 6 9 18 36 108
Output:
Yes
Input:
2
2
7 17
9
4 8 10 12 15 18 33 44 81
Output:
No
Yes
|
Limitation
Time limit 5000 ms
Memory limit 262144 kb
|
解题思路
一开始我是完全当作平衡二叉搜索树来做了，赛后补题才发现只是普通的二叉搜索树……
当时的思路是这样的：
中间位置为 root，分为左右两半，每半的中间位置是 father node，再分为左右两半……以此递归，可以确定节点以及其左右孩子，即确定数组的某位置与哪些位置相连，就像数组模拟的堆结构一样。
然而这棵树并不平衡，不可用数组这么“偷懒”，(按这么做的话样例 2 是错的，81不符合，当时我怎么就没发现呢。赛后补题觉得样例2好奇怪，看了好久才明白不是平衡二叉搜索树……)
既然他不平衡，如果要建树(我是觉得肯定不可能去写二叉树结构的，太费时间了)插入的时候就很有不确定性，有些节点无法明确插在哪，所以肯定不是要写树的结构。
然后一头雾水了。参考别人解法的时候发现这是个区间 dp 问题。
用两个数组 l[i][j], r[i][j] 表示以 i 为父节点，向左到 j、向右到 j 可以到达的左子树、右子树。用 dp[i][j] 表示 i, j 可以构成一棵树。
若 l[k][i] = r[k][j] = true，dp[i][j] = true，i 和 j 以 k 为父节点。
状态转移方程为：
初始化时将 l[i][i] = r[i][i] =true，表示当 i 左右子树为空，符合题意。
结果返回 dp[1][n] 表示这个数组是否能建树。
源代码
#include <iostream>
using namespace std;
const int maxN = 750;
int arr[maxN];
bool dp[maxN][maxN], l[maxN][maxN], r[maxN][maxN], g[maxN][maxN];
int gcd(int _a, int _b) {
return _b == 0 ? _a : gcd(_b, _a % _b);
}
bool has_gcd(int a, int b) {
return gcd(a, b) > 1;
}
bool isBST_GCD(int n) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n - i + 1; j++) {
for (int k = j; k <= i + j - 1; k++) {
if (l[k][j] && r[k][i + j - 1]) {
dp[j][i + j - 1] = true;
l[i + j][j] |= g[i + j][k];
r[j - 1][i + j - 1] |= g[j - 1][k];
}
}
}
}
return dp[1][n];
}
int main() {
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
for (int i = 1; i <= n; i++)
cin >> arr[i];
for (int i = 0; i < n + 10; i++)
for (int j = 0; j < n + 10; j++) {
l[i][j] = false;
r[i][j] = false;
dp[i][j] = false;
}
for (int i = 1; i <= n; i++) {
l[i][i] = true;
r[i][i] = true;
dp[i][i] = true;
for (int j = 1; j <= n; j++)
g[i][j] = has_gcd(arr[i], arr[j]);
}
if (isBST_GCD(n))
cout << "Yes" << endl;
else
cout << "No" << endl;
}
return 0;
}
|