建筑方面的网站,青岛网站seo价格,安徽网站建设制作,网站cms传送门 文章目录题意#xff1a;思路#xff1a;题意#xff1a;
给你两个圆#xff0c;上面依次有nnn个点#xff0c;编号为1−n1-n1−n的排列#xff0c;给出一种连边方式#xff0c;使得每个点都被遍历且连线不能相交#xff0c;没有方式的话输出−1-1−1。
思路思路题意
给你两个圆上面依次有nnn个点编号为1−n1-n1−n的排列给出一种连边方式使得每个点都被遍历且连线不能相交没有方式的话输出−1-1−1。
思路
首先容易想到一个n2n^2n2的算法就是遍历每个点以它为起点让后往两边扩展即可。这样正确性是可以保证的但是复杂度很高我们考虑优化这个算法。 考虑我们从当前点遍历了2−3−52-3-52−3−5这个时候再走就不合法了那么通过观察我们可以得到3,53,53,5两个点为起点的时候也是不可以的。所以我们标记一下如果这个点被走过就跳过这个点复杂度O(n)O(n)O(n)。
//#pragma GCC optimize(Ofast,no-stack-protector,unroll-loops,fast-math)
//#pragma GCC target(sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tunenative)
//#pragma GCC optimize(2)
#includecstdio
#includeiostream
#includestring
#includecstring
#includemap
#includecmath
#includecctype
#includevector
#includeset
#includequeue
#includealgorithm
#includesstream
#includectime
#includecstdlib
#define X first
#define Y second
#define L (u1)
#define R (u1|1)
#define pb push_back
#define mk make_pair
#define Mid (tr[u].ltr[u].r1)
#define Len(u) (tr[u].r-tr[u].l1)
#define random(a,b) ((a)rand()%((b)-(a)1))
#define db puts(---)
using namespace std;//void rd_cre() { freopen(d://dp//data.txt,w,stdout); srand(time(NULL)); }
//void rd_ac() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//AC.txt,w,stdout); }
//void rd_wa() { freopen(d://dp//data.txt,r,stdin); freopen(d://dp//WA.txt,w,stdout); }typedef long long LL;
typedef unsigned long long ULL;
typedef pairint,int PII;const int N1000010,mod1e97,INF0x3f3f3f3f;
const double eps1e-6;int n,cnt;
int a[N],b[N];
int p[N];
int ans[N];
bool vis[N];int add(int x)
{x; x%n;return x;
}int del(int x)
{x--; xn;x%n;return x;
}bool check(int id)
{int stid;int pos-1;for(int i0;in;i) if(b[i]a[st]) posi;int l1del(st),r1add(st);int l2del(pos),r2add(pos);int tot0;ans[tot]a[st];vis[st]1;for(int i1;in-1;i){if(a[l1]b[l2]) ans[tot]a[l1],vis[l1]1,l1del(l1),l2del(l2);else if(a[l1]b[r2]) ans[tot]a[l1],vis[l1]1,l1del(l1),r2add(r2);else if(a[r1]b[l2]) ans[tot]a[r1],vis[r1]1,r1add(r1),l2del(l2);else if(a[r1]b[r2]) ans[tot]a[r1],vis[r1]1,r1add(r1),r2add(r2);else return false;}for(int i1;itot;i) printf(%d ,ans[i]);puts();return true;
}bool check()
{vectorintv;for(int i0;in;i){int posp[a[i]];int x1a[del(i)],y1a[add(i)];int x2b[del(pos)],y2b[add(pos)];if(x1y1) swap(x1,y1);if(x2y2) swap(x2,y2);if(x1x2||x1y2||y1x2||y1y2) v.pb(i);}if(!v.size()) return false;for(auto x:v) if(!vis[x]) { if(check(x)) return true; }return false;
}int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0);scanf(%d,n);for(int i0;in;i) scanf(%d,a[i]);for(int i0;in;i) scanf(%d,b[i]),p[b[i]]i;if(!check()) puts(-1);return 0;
}
/**/
