大意: 给定 $n$ 个数, 任意两个 $gcd>1$ 的数间可以连边, 求是否能构造一棵 BST.
数据范围比较大, 刚开始写的 $O(n^3\omega(1e9))$ 竟然 T 了.. 优化到 $O(n^3)$ 才过.
思路就是先排个序, 记 $L[i][j]$ 表示区间 $[i,j]$ 是否能组成以 $i-1$ 为根的 $BST$, $R[i][j]$ 为区间 $[i,j]$ 能否组成以 $j+1$ 为根的 BST. 然后暴力转移即可.
- #include <iostream>
- #include <algorithm>
- #include <cstdio>
- #include <queue>
- #define pb push_back
- #define REP(i,a,n) for(int i=a;i<=n;++i)
- using namespace std;
- const int N = 750;
- int n, a[N], g[N][N];
- vector<int> fac[N];
- int L[N][N], R[N][N], c[N][N];
- vector<int> calc(int x) {
- vector<int> v;
- for (int i=2; i*i<=x; ++i) if (x%i==0) {
- v.pb(i);
- while (x%i==0) x/=i;
- }
- if (x>1) v.pb(x);
- return v;
- }
- int main() {
- scanf("%d", &n);
- REP(i,1,n) scanf("%d", a+i);
- sort(a+1,a+1+n);
- REP(i,1,n) {
- fac[i] = calc(a[i]);
- a[i] = 1;
- for (int j:fac[i]) a[i] *= j;
- }
- REP(i,1,n) REP(j,i+1,n) {
- for (int t:fac[i]) {
- if (a[j]%t==0) c[i][j]=c[j][i]=1;
- }
- }
- REP(d,1,n) for (int l=1,r=l+d-1;r<=n;++l,++r) {
- if (d==1) {
- L[l][r] = c[l-1][l];
- R[l][r] = c[l+1][l];
- continue;
- }
- if (L[l+1][r]) {
- if (d==n) return puts("Yes"),0;
- if (l!=1&&!L[l][r]) L[l][r]=c[l-1][l];
- if (r!=n&&!R[l][r]) R[l][r]=c[r+1][l];
- }
- if (R[l][r-1]) {
- if (d==n) return puts("Yes"),0;
- if (l!=1&&!L[l][r]) L[l][r]=c[l-1][r];
- if (r!=n&&!R[l][r]) R[l][r]=c[r+1][r];
- }
- REP(k,l+1,r-1) {
- if (R[l][k-1]&&L[k+1][r]) {
- if (d==n) return puts("Yes"),0;
- if (l!=1&&!L[l][r]) L[l][r]=c[l-1][k];
- if (r!=n&&!R[l][r]) R[l][r]=c[r+1][k];
- }
- }
- }
- puts("No");
- }
来源: http://www.bubuko.com/infodetail-3112550.html