生活随笔
收集整理的這篇文章主要介紹了
newcode Islands 思维
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
傳送門
文章目錄
題意：
給你兩個圓，上面依次有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)。
#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<map>
#include<cmath>
#include<cctype>
#include<vector>
#include<set>
#include<queue>
#include<algorithm>
#include<sstream>
#include<ctime>
#include<cstdlib>
#define X first
#define Y second
#define L (u<<1)
#define R (u<<1|1)
#define pb push_back
#define mk make_pair
#define Mid (tr[u].l+tr[u].r>>1)
#define Len(u) (tr[u].r-tr[u].l+1)
#define random(a,b) ((a)+rand()%((b)-(a)+1))
#define db puts("---")
using namespace std
;
typedef long long LL
;
typedef unsigned long long ULL
;
typedef pair
<int,int> PII
;const int N
=1000010,mod
=1e9+7,INF
=0x3f3f3f3f;
const double eps
=1e-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
--; x
+=n
;x
%=n
;return x
;
}bool check(int id
)
{int st
=id
;int pos
=-1;for(int i
=0;i
<n
;i
++) if(b
[i
]==a
[st
]) pos
=i
;int l1
=del(st
),r1
=add(st
);int l2
=del(pos
),r2
=add(pos
);int tot
=0;ans
[++tot
]=a
[st
];vis
[st
]=1;for(int i
=1;i
<=n
-1;i
++){if(a
[l1
]==b
[l2
]) ans
[++tot
]=a
[l1
],vis
[l1
]=1,l1
=del(l1
),l2
=del(l2
);else if(a
[l1
]==b
[r2
]) ans
[++tot
]=a
[l1
],vis
[l1
]=1,l1
=del(l1
),r2
=add(r2
);else if(a
[r1
]==b
[l2
]) ans
[++tot
]=a
[r1
],vis
[r1
]=1,r1
=add(r1
),l2
=del(l2
);else if(a
[r1
]==b
[r2
]) ans
[++tot
]=a
[r1
],vis
[r1
]=1,r1
=add(r1
),r2
=add(r2
);else return false;}for(int i
=1;i
<=tot
;i
++) printf("%d ",ans
[i
]);puts("");return true;
}bool check()
{vector
<int>v
;for(int i
=0;i
<n
;i
++){int pos
=p
[a
[i
]];int x1
=a
[del(i
)],y1
=a
[add(i
)];int x2
=b
[del(pos
)],y2
=b
[add(pos
)];if(x1
>y1
) swap(x1
,y1
);if(x2
>y2
) swap(x2
,y2
);if(x1
==x2
||x1
==y2
||y1
==x2
||y1
==y2
) v
.pb(i
);}if(!v
.size()) return false;for(auto x
:v
) if(!vis
[x
]) { if(check(x
)) return true; }return false;
}int main()
{
scanf("%d",&n
);for(int i
=0;i
<n
;i
++) scanf("%d",&a
[i
]);for(int i
=0;i
<n
;i
++) scanf("%d",&b
[i
]),p
[b
[i
]]=i
;if(!check()) puts("-1");return 0;
}
總結
以上是生活随笔為你收集整理的newcode Islands 思维的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
