首页 > 代码库 > Permutation

Permutation

2024-11-25 11:25:39   203人阅读

Permutation

日照夏令营D2T2，赛场上40分，因为当时用的阶乘把康托展开算出来了，由于n很大，后6个点爆了。其实不用算，比如a是第x个排列，b是第y个排列，而想x、y能拆成rank数组，x+y实际上就是它们对应位上rank数组的值相加，因为最后要求的是排列，所以根本用不到阶乘。这里用的是类似高精度的加法，当然也要进位，对于某一个位，假设为(x+3)*x!,

则进位时对应系数要减（x+1），即（x+1）!+2*x!，为什么要进位呢？阶乘前的系数表示比当前位小的还未出现的数的个数，阶乘本身代表的是全排列，即剩下多位置可以放数，如果系数大于阶乘的数字，就放不开了，证毕。

 

//ktzk

#include<bits/stdc++.h>
using namespace std;
int n;
int r1[5010];
int r2[5010];
int r3[5010];
int a[5010];
int b[5010];
bool a1[5010];
bool b1[5010];
bool c[5010];
int ans[5010];

void kta()
{
  int cnt=0;
  int j;
  for(int i=0;i<n;i++)
  {
      for(j=0;j<n;j++)
      if(j<a[i]&&a1[j]==false) 
      cnt++;
      a1[a[i]]=true;
    r1[i]=cnt;
    cnt=0;
  }    
}

void ktb()
{
  int cnt=0;
  int j;
  for(int i=0;i<n;i++)
  {
      for(j=0;j<n;j++)
      if(j<b[i]&&b1[j]==false) 
      cnt++;
      b1[b[i]]=true;
    r2[i]=cnt;
    cnt=0;
  }    
}

void sum()
{
    int len=0;
    bool t=false;
    for(int i=n-1;i>=0;i--)
    {
      r3[len]+=r1[i]+r2[i];
      while(r3[len]>len)
      {
        r3[len]-=(len+1);
        r3[len+1]++;    
        t=true;
      }
      len++;
    }
}

void fkt()
{
    int cnt=0;
    int j;
    for(int i=n-1;i>=0;i--)
    {
        for(j=0;j<n;j++)
        {
        if(c[j]==false&&cnt<r3[i]) cnt++;
        else
        if(c[j]==false)
        {
            ans[i]=j;    
         c[j]=true;
         cnt=0;
        break;
        }
        }
        
    }
}

int main()
{
    freopen("perm.in","r",stdin);
    freopen("perm.out","w",stdout);
    cin>>n;
    for(int i=0;i<n;i++) cin>>a[i];
    for(int i=0;i<n;i++) cin>>b[i];
    kta();    
    ktb();    
    sum();
    fkt();
    for(int i=n-1;i>=0;i--)
    cout<<ans[i]<<‘ ‘;
    return 0;
}

 

Permutation


联系
我们