- Hydro
CF1025D Recovering BST题解
- @ 2026-11-10 15:03:46
先贴场切代码。
MX模拟赛场上切掉了这道紫题。
#include <bits/stdc++.h>
using namespace std;
const int N = 705;
void pt() {
puts("No");
}
int n, a[N];
struct tr{
int l, r;
int fa;
int v;
tr() {
l = r = fa = -1;
}
}t[N];
struct node {
int no;
int nm;
}p[N];
bool cmp(node a, node b) {
return a.nm < b.nm;
}
inline int read() {
int res = 0;
bool bo = 0;
char c;
while(((c = getchar()) < '0' || c > '9') && c != '-');
if(c == '-') bo = 1;
else {
res = c - 48;
}
while((c=getchar()) >= '0' && c <='9') {
res = (res<<3) + (res<<1) + c-48;
}
return bo ? ~res+1:res;
}
int tot;
vector<int> v[N];
bool l1[N], r1[N];
int cr[N], cl[N];
int main() {
// freopen("bst.in","r",stdin);
// freopen("bst.out","w",stdout);
ios :: sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
n = read();
for(int i=1; i<=n; ++i) {
a[i] = read();
t[i].v = a[i];
}
for(int i=1; i<=n; ++i) {
bool flag = 0;
for(int j=1; j<=n; ++j) {
if(j != i) {
if(__gcd(a[i], a[j]) > 1) {
flag = 1;
break;
}
}
}
if(!flag) {
pt();
return 0;
}
}
for(int i=1; i<=n; ++i) {
for(int j=1; j<=n; ++j) {
if(i != j) {
if(__gcd(a[i], a[j]) > 1) {
v[i].push_back(j);
v[j].push_back(i);
}
}
}
}
for(int i=1; i<=n; ++i) {
memset(cr, 0, sizeof(cr));
memset(cl, 0, sizeof(cl));
memset(l1, 0, sizeof(l1));
memset(r1, 0, sizeof(r1));
int rt = i;
if(rt == 1) {
r1[1] = 1;
}
else if(rt == n) {
l1[n] = 1;
}
else {
l1[rt] = r1[rt] = 1;
}
for(int j=rt+1; j<=n; ++j) {
for(int k=0; k<v[j].size(); ++k) {
int o = v[j][k];
if(o < rt) {
cr[j]++;
}
}
}
for(int j=1; j<=rt-1; ++j) {
for(int k=0; k<v[j].size(); ++k) {
int o = v[j][k];
if(o > rt) {
cl[j]++;
}
}
}
for(int j=1; j<=rt-1; ++j) {
t[j+1].l = j;
t[j].fa = j+1;
l1[j+1] = 1;
}
for(int j=n; j>=rt+1; --j) {
t[j+1].r = j;
t[j].fa = j-1;
r1[j-1] = 1;
}
int st = 1;
bool fl1 = 1, fl2 = 1;
while(1) {
if(st == rt) break;
if(__gcd(a[st], a[t[st].fa]) == 1) {
tot = 0;
for(int j=rt+1; j<=n; ++j) {
if(cr[j] && __gcd(a[st], a[j]) > 1 && !l1[j]) {
p[++tot].no = j;
p[++tot].nm = cr[j];
}
}
if(tot == 0) {
fl1 = 0;
}
sort(p+1, p+1+tot, cmp);
l1[p[1].no] = 1;
t[t[st].fa].l = 0;
t[st].fa = p[1].no;
t[p[1].no].l = st;
cr[p[1].no] = 0;
}
st++;
}
st = n;
while(1) {
if(st == rt) break;
if(__gcd(a[st], a[t[st].fa]) == 1) {
tot = 0;
for(int j=1; j<=rt-1; ++j) {
if(cl[j] && __gcd(a[st], a[j]) > 1 && !r1[j]) {
p[++tot].no = j;
p[++tot].nm = cl[j];
}
}
if(tot == 0) {
fl2 = 0;
break;
}
sort(p+1, p+1+tot, cmp);
r1[p[1].no] = 1;
t[t[st].fa].r = 0;
t[st].fa = p[1].no;
t[p[1].no].r = st;
cl[p[1].no] = 0;
}
st--;
}
if(fl1 && fl2) {
puts("Yes");
return 0;
}
}
puts("No");
return 0;
}
0 條評論
目前还没有评论...