[CC-SEAPERM2]Sereja and Permutations

题目大意：

有一个\(n(n\le300)\)排列\(p\)，将其中一个元素\(p_i\)拿掉,然后将原来大于\(p_i\)的元素减一，这样就得到一个新的排列。

将\(p\)中每一个数拿掉之后都会得到一个新的排列，这样就得到了\(n\)个新的排列。

现在给出最后得到的\(n\)个新的排列（顺序随机），请求出原来的排列。如果有多个解，输出字典序最小的解。保证至少有一个解。

思路：

枚举哪一个排列被删掉了\(p_1\)，那么剩下排列的第一个数，要么是\(p_1\)，要么是\(p_1-1\)。（如果剩下不止两种数，或者相差超过\(1\)，说明被删去\(p_1\)的不可能是这个排列。）

这样，我们就可以得到\(p_1\)，从而得到初始的排列，但是我们还要删去每一个数看看是否和给你的排列一样来验证。做法是hash+map。

时间复杂度\(\mathcal O(n^3)\)。

源代码：

#include#include
     
      #include
      
       #include
       
        #include
        
         inline int getint() {    register char ch;    while(!isdigit(ch=getchar()));    register int x=ch^'0';    while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');    return x;}typedef unsigned long long uint64;const int N=301;const uint64 base=31;bool have_ans;int n,a[N][N],b[N],ans[N];std::map
         
           map;inline uint64 hash(int a[]) { uint64 ret=0; for(register int i=1;i
          
           ans[i]) return false; } return false;}inline void upd() { if(!have_ans||check()) { have_ans=true; for(register int i=1;i<=n;i++) ans[i]=b[i]; }}int main() { for(register int T=getint();T;T--) { n=getint(); if(n==1) { puts("1"); return 0; } for(register int i=1;i<=n;i++) { for(register int j=1;j
           
            max[k]) std::swap(max[k],tmp); } three|=tmp; } } if(three||(max[1]&&max[0]-max[1]!=1)) continue; for(register int val=max[0];val<=max[0]+1;val++) { for(register int i=1;i<=n;i++) map[hash(a[i])]++; b[1]=val; for(register int j=2;j<=n;j++) b[j]=a[i][j-1]+(a[i][j-1]>=b[1]); for(register int i=1;i<=n;i++) { uint64 ret=0; for(register int j=1;j<=n;j++) { if(i!=b[j]) ret=(uint64)ret*base+b[j]-(b[j]>i); } map[ret]--; } bool flag=true; for(auto &i:map) { if(i.second!=0) flag=false; } map.clear(); if(flag) upd(); } } for(register int i=1;i<=n;i++) { printf("%d%c",ans[i]," \n"[i==n]); } } return 0;}

转载于:https://www.cnblogs.com/skylee03/p/9847711.html

你可能感兴趣的文章