简单构造求助(错第14个点)
查看原帖
简单构造求助(错第14个点)
227728
冰糖鸽子TJ鸽子协会楼主2021/2/7 15:35

RT,输出了一堆超出 nn 的翻转/yun


// Problem: CF512E Fox And Polygon
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/CF512E
// Memory Limit: 250 MB
// Time Limit: 2000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)

#include <bits/stdc++.h>
using namespace std;
#define M 1050
#define mp make_pair
int n,cnt,cnto,cnte,cntA,fo,one[M];
struct node
{
	int u,v,uu,vv;
}edge[M],ans[M];
map<pair<int,int>,int>R;
void rev(int x,int y)
{
	int z=R[mp(x,y)],K,k,fk;
	for(int i=1;i<=cnte;i++)
	{
		if(edge[i].u==x)
		{
			if(R[mp(min(y,edge[i].v),max(y,edge[i].v))]&&edge[i].v!=1)
			{
				K=edge[i].v;
			}
		}
		else if(edge[i].v==x)
		{
			if(R[mp(min(y,edge[i].u),max(y,edge[i].u))]&&edge[i].u!=1)
			{
				K=edge[i].u;
			}
		}
	}
	fo++;cnt++;cntA++;
	one[fo+cnto]=edge[z].v=K;
	edge[z].u=1;
	ans[cnt].u=x;ans[cnt].v=y;
	ans[cnt].uu=1;ans[cnt].vv=K;
	R[mp(x,y)]=0;
	R[mp(1,K)]=z;
}
void init()
{
	int U,V;
	for(int i=1;i<=n-3;i++)
	{
		cin>>U>>V;
		if(U>V) swap(U,V);
		cnte++;
		if(U==1)
		{
			cnto++;
			one[cnto]=V;
		}
		edge[cnte].u=U;edge[cnte].v=V;
		R[mp(U,V)]=cnte;
	}
}
void Re()
{
	cnto=2;fo=cnte=cntA=0;
	R.clear();
	one[1]=2;one[2]=n;
	for(int i=1;i<n;i++)
	{
		cnte++;
		edge[cnte].u=i;
		edge[cnte].v=i+1;
		R[mp(edge[cnte].u,edge[cnte].v)]=cnte;
	}
	cnte++;
	edge[cnte].u=1;
	edge[cnte].v=n;
	R[mp(1,n)]=cnte;
}
void done()
{
	Re();
	init();
	while(cnto<n-1)
	{
		fo=0;
		sort(one+1,one+1+cnto);
		for(int i=2;i<=cnto;i++)
		{
			if(one[i]-one[i-1]>1)
			{
				rev(one[i-1],one[i]);
			}
		}
		cnto+=fo;
	}
}
int main()
{
	cin>>n;
	done();
	done();
	cout<<cnt<<endl;
	for(int i=1;i<=cnt-cntA;i++)
	{
		cout<<ans[i].u<<' '<<ans[i].v<<endl;
	}
	for(int i=cnt;i>=cnt-cntA+1;i--)
	{
		cout<<ans[i].uu<<' '<<ans[i].vv<<endl;
	}
	return 0;
}
2021/2/7 15:35
加载中...