CF1025D Recovering BST

Link

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

#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;
}