您当前处于兼容模式。某些功能在此模式下不可用。我们强烈建议在现代浏览器上切换为标准模式以获得更好的体验。 标准模式 隱藏

先贴场切代码。

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) {
	    fill(cr, cr + N + 1, 0);
	    fill(cl, cl + N + 1, 0);
	    fill(l1, l1 + N + 1, 0);
	    fill(r1, r1 + N + 1, 0);
		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;
}

2 條評論

  • 1