題目鏈接：點擊查看

題目大意：現在有一個長度為 n 的排列 p ，但排列 p 暫時對我們保密，每個樣例將會給出 n - 1 個排好序后的子段，換句話說，對于 r ∈ [ 2 , n ] ，存在一個 l 滿足 l <??r ，題目會給出排列 p 中 [ l , r ] 這段，只不過是排好序后給出，現在讓我們還原排列 p?

題目分析：因為 n 非常小，只有 200 ，所以可以考慮 n^3 的算法，首先應該注意的地方是，對于所有子段的左右區間而言，雖然 l 并不確定，但是 r 是滿足 [ 2 , n ] 中每個位置都有且僅有一個的，這也就保證了答案的唯一性，因為假如已經知道了給出的是哪些區間，按照區間的右端點 r 排個序，就會發現當前某個區間內至少會有一個數是前一個區間內不存在的

到這里我們可以類比于拓撲的思想，因為第一個數是未知的，所以我們可以直接 O( n ) 去枚舉，現在確定好第一個數是什么了之后，可以對于所有的區間，都將第一個數刪去，那么 r == 2 的這組數據在刪去了第一個數后，就只剩下了第二個位置的數，同理，每次迭代到 i 時，因為已經將前 i - 1 個數都刪去了，那么 r == i 的這組數據按理說應該只剩下第 i 個位置的數了，如此往復就能求出排列 p 了

上述過程我們可以利用 set 完成，因為 set 的查找、插入和刪除效率都非常的高，每次找第 i 個位置的數時查找 size == 1 的區間即可，同時需要注意的是，在迭代的過程中，如果存在某一時刻：

沒有 size == 1 的區間

size == 1 的區間個數大于 1?

如果存在上述兩種情況之一的話，那就說明此時是無解的

此時我們已經構造出了一種可行方案 p 了，可不能著急輸出，具體參見第三個樣例，這就提醒我們需要檢查一下構造出的方案是否合理，具體的檢查方法就是 O( n * n?) 枚舉出所有的子段，如果存在 n - 1 個子段可以和題目給出的數據全部一一對應的話，那就說明答案合理，反之不合理

思路很簡單，但是實現還是有一定難度的，時間復雜度為 O( n * n * n * logn )

代碼：

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<unordered_map> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=2e5+100;int main() { #ifndef ONLINE_JUDGE // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); #endif // ios::sync_with_stdio(false);int w;cin>>w;while(w--){vector<set<int>>seg;int n;scanf("%d",&n);for(int i=1;i<n;i++){set<int>st;int k;scanf("%d",&k);while(k--){int num;scanf("%d",&num);st.insert(num);}seg.push_back(st);}for(int st=1;st<=n;st++)//枚舉第一個數 {vector<int>ans;vector<set<int>>cur=seg;bool flag=true;for(auto &it:cur)if(it.count(st))it.erase(st);ans.push_back(st);for(int i=1;i<n;i++)//迭代n-1次，找出剩余n-1個數 {vector<int>temp;for(auto &it:cur)if(it.size()==1)temp.push_back(*it.begin());if(temp.size()!=1)//無法找到 {flag=false;break;}ans.push_back(temp.front());for(auto &it:cur)if(it.count(temp.front()))it.erase(temp.front());}set<set<int>>all(seg.begin(),seg.end());if(flag)//構造出數列后，判斷是否合理{for(int l=0;l<n-1;l++){set<int>st;for(int r=l;r<n;r++){st.insert(ans[r]);if(all.count(st))all.erase(st);}}}if(all.empty())//判斷合理的話，直接輸出答案{for(auto it:ans)printf("%d ",it);puts("");break;}}}return 0; }

?

總結

以上是生活随笔為你收集整理的CodeForces - 1343F Restore the Permutation by Sorted Segments(思维)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。