HNOI 2019 多边形题解

First Post:

2023-11-30

Last Update:

2023-11-30

感觉比较简单的题，但有教育意义。

下文中，我们把这个多边形看成一个个点，条边的平面图。

首先考虑如何找到最小操作次数。显然，终止状态肯定是所有点都与相连。首先，对于每个没有与直接相连的点，我们至少需要操作次使得其与相连。其次，我们每次找到一个顶点包含的三角形，然后旋转这个三角形不包含的那条边，这样就可以保证每个不与相连的点都使用恰好次操作。那么第一问的答案就出来了，是 $与有直接连边的点数$ 。

那么第二问怎么做？考虑把所有端点为的边提出来，那么相邻两条边之间的部分也是一个多边形，且这些部分互不影响，所以可以独立解决，最后再把这些部分的操作序列归并起来。对于每个部分，一开始暂时没有点与相连，我们操作一次之后，会有一个点与相连，设其为。在操作一次之后，我们可以把这条边左边和右边的部分又分开操作，最后把两部分的操作序列归并起来。容易发现，过程中的每个部分在原多边形上都是一段区间，表示中的点与组成的一个子多边形。

观察上述过程，我们所做的只有“进行一次操作，然后将若干个子问题的操作序列归并起来”。不难发现，如果我们将划分子问题的分治过程建出一棵树，那么方案就是这棵树的拓扑序个数。

我们知道，一棵大小为的树的拓扑序个数为（其中为的子树大小）。回到这道题后，式子中的就是总操作次数，而其实是每个子多边形的大小减（即对于一个子多边形，为），画图不难得到这就是这个子多边形内的操作次数。

另一方面，我们在分治中找到的每个子多边形，其实都满足在原图中有边，而对于任意的边，我们也总会递归到以为端点的子多边形。那么答案其实就是，其中为边集。

这说明我们只要快速完成旋转操作，两问都能很方便地解决。要旋转，就需要找到对应的和。我们可以用 map 来存储这些信息，预处理时每找到一个三角形就更新 map。找三角形可以类似拓扑排序，将度数为的点入队，弹出队首后就找到一个三角形，然后将以队首为端点的边删掉，将新产生的度数为的点加入队中，循环往复即可。

于是本题就做完了，时间复杂度。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5,P = 1e9 + 7;
typedef pair<int,int> pii;
#define FI first
#define SE second
#define mkp make_pair
int SubId;
int n,m;
int U[N],V[N];
int fac[N],inv[N];
inline void init(int n) {
	fac[0] = 1;
	for(int i = 1;i <= n;i++) fac[i] = 1ll * fac[i - 1] * i % P;
	inv[1] = 1;
	for(int i = 2;i <= n;i++) inv[i] = 1ll * inv[P % i] * (P - P / i) % P;
}
struct Polygon {
	map<pair<int,int>,int> ida,idb,idd;
	set<int> E[N],Te[N];
	inline void adde(int x,int y) { E[x].insert(y);E[y].insert(x);}
	inline void UpdTriangle(int a,int b,int c) {
		int t[3] = {a,b,c};
		sort(t,t + 3);
		assert(t[0] != t[1] && t[1] != t[2] && t[0] != t[2]);
		idd[mkp(t[0],t[1])] = idd[mkp(t[1],t[0])] = t[2];
		idb[mkp(t[0],t[2])] = idb[mkp(t[2],t[0])] = t[1];
		ida[mkp(t[1],t[2])] = ida[mkp(t[2],t[1])] = t[0];
	}
	inline void Topo() {
		for(int i = 1;i <= n;i++) Te[i] = E[i];
		queue<int> Q;
		for(int i = 1;i <= n;i++) if(Te[i].size() == 2) Q.push(i);
		for(int _ = 1;_ <= n - 2;_++) {
			int x = Q.front();Q.pop();
			int t1 = *Te[x].begin(),t2 = *prev(Te[x].end());
			UpdTriangle(t1,t2,x);
			Te[t1].erase(x);Te[t2].erase(x);
			if(Te[t1].size() == 2) Q.push(t1);
			if(Te[t2].size() == 2) Q.push(t2);
		}
	}
	inline pii Rotate1(int a,int c) {
		if(a > c) swap(a,c);
		int b = idb[mkp(a,c)],d = idd[mkp(a,c)];
		E[a].erase(c);E[c].erase(a);
		E[b].insert(d);E[d].insert(b);
		UpdTriangle(a,b,d);UpdTriangle(b,c,d);
		return mkp(b,d);
	}
	inline pii Rotate2(int b,int d) {
		if(b > d) swap(b,d);
		int a = ida[mkp(b,d)],c = idb[mkp(b,d)];
		E[b].erase(d);E[d].erase(b);
		E[a].insert(c);E[c].insert(a);
		UpdTriangle(a,b,c);UpdTriangle(a,c,d);
		return mkp(a,c);
	}
} T;
inline int Solve(int l,int r) {
	if(r - l <= 1) return 1;
	int ps = T.idb[mkp(l,r)];
	return 1ll * Solve(l,ps) * Solve(ps,r) % P * inv[r - l - 1] % P;
}
inline int GetAns() {
	vector<int> Es(T.E[n].begin(),T.E[n].end());
	int mul = 1;
	for(int i = 0;i + 1 < Es.size();i++)
		mul = 1ll * mul * Solve(Es[i],Es[i + 1]) % P;
	return 1ll * mul * fac[n - 1 - Es.size()] % P;
}
int main() {
	cin >> SubId;
	cin >> n;init(n);
	for(int i = 1;i <= n - 3;i++)
		cin >> U[i] >> V[i],T.adde(U[i],V[i]);
	for(int i = 1;i <= n;i++) T.adde(i,i % n + 1);
	T.Topo();
	int pans = 0,pnum = n - 1 - (int)T.E[n].size();
	if(SubId == 0) printf("%d\n",pnum);
	else printf("%d %d\n",pnum,pans = GetAns());
	cin >> m;
	for(int i = 1;i <= m;i++) {
		int a,c;
		cin >> a >> c;
		int b = T.idb[mkp(a,c)],d = T.idd[mkp(a,c)];
		if(SubId == 0) printf("%d\n",pnum - (d == n));
		else {
			int nans = pans;
			printf("%d ",pnum - (d == n));
			if(d != n) nans = 1ll * pans * (c - a - 1) % P * inv[d - b - 1] % P;
			else nans = 1ll * pans * (c - a - 1) % P * inv[pnum] % P;
			printf("%d\n",nans);
		} 
	}
	return 0;
}

≡

HNOI 2019 多边形 题解

HNOI 2019 多边形题解