零件组装机

每个数会参与若干次合并，容易发现每次合并与它连边的节点的下标只增不减

需要判断合并的位置，然后递归求解

考虑与 \(n - 1\) 连边的最小编号 \(k\)，显然 \(n - 1\) 会在此时与 \(k\) 连边

如果 \(k+1 = n-k-1\)，则划分点为 \(k,k+1\)

否则，因为 \(len_l \le len_r\)，所以 \(n - k - 1\) 此时的最小值应该为划分点

检查应该存在的边之后递归下去即可

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;

int T, n, m, tp[N];

priority_queue <int, vector <int>, greater <int> > q[N];

bool solve_(int l, int r) {
	if (l == r)
		return q[l].empty();
	if (q[r].empty())
		return 0;
	tp[r] = q[r].top() - l;
	if (tp[r] < 0)
		return 0;
	int pos = r - tp[r];
	if ((tp[r] + 1)*2 > r - l + 1)
		return 0;
	for (int i = r; i >= pos; i--)
		if (q[i].empty())
			return 0;
		else 
			tp[i] = q[i].top() - l, q[i].pop();

	for (int i = r - 1; i >= pos; i--)
		if (tp[i + 1] - 1 != tp[i])
			return 0;
	if (tp[r] == pos - l - 1)
		return solve_(l, pos - 1) && solve_(pos, r);
	if (q[pos - 1].empty())
		return 0;
	int len = q[pos - 1].top() - l + 1;
	if (len <= tp[r])
		return 0;
	for (int i = l + len; i < pos; i++)
		if (q[i].empty())
			return 0;
		else {
			tp[i] = q[i].top() - l, q[i].pop();
			if (tp[i] != (i - l)%len) 
				return 0;
		}
	return solve_(l, l + len - 1) && solve_(l + len, r);
}

int main() {
	scanf("%d", &T);
	while (T--) {
		scanf("%d%d", &n, &m);
		for (int i = 0; i < n; i++)
			while (!q[i].empty())
				q[i].pop();
		bool eq = 0;
		for (int u, v, i = 1; i <= m; i++) {
			scanf("%d%d", &u, &v);
			if (u < v)
				swap(u, v);
			if (u == v)
				eq = 1;
			q[u].push(v); 
		}
		if (eq) {
			puts("NO");
			continue;
		}

		printf("%s\n", solve_(0, n - 1) ? "YES" : "NO");
	}
}

零件组装机

原文：https://www.cnblogs.com/iqx37f/p/14459586.html