bzoj 3301 Cow Line

题目大意：

n的排列，K个询问

为P时，读入一个数x，输出第x个全排列

为Q时，读入N个数，求这是第几个全排列

思路：

不知道康拓展开是什么，手推了一个乱七八糟的东西

首先可以知道

把排列看成是一个每一位进制不同的数

每一位进制可以看做是：

(n-1)! (n-2)! ...... 2 1 1

然后对于第一种询问

像正常进制转换一样，处理出每一位应该填第几个数

这时需要处理一下哪些数可以被取到

然后取可以取到的数里的第“几”个每一位输出就可以了

对于第二种询问

直接一位一位减，同样在处理的时候记录哪些数可以被取到

答案+=每一位进制*该位置权值

 #include<iostream>

 #include<cstdio>

 #include<cmath>

 #include<cstdlib>

 #include<cstring>

 #include<algorithm>

 #include<vector>

 #include<queue>

 #define inf 2139062143

 #define ll long long

 #define MAXN 100100

 using namespace std;

 inline ll read()

 {

     ll x=,f=;char ch=getchar();

     while(!isdigit(ch)) {if(ch=='-') f=-;ch=getchar();}

     while(isdigit(ch)) {x=x*+ch-'';ch=getchar();}

     return x*f;

 }

 ll n,T,t[],x,pos,vis[],i,cnt,tot,res,f;

 char ch[];

 int main()

 {

     n=read();

     t[n]=t[n-]=;

     for(i=n-;i;i--) t[i]=t[i+]*(n-i);

     //cout<<t[1]<<endl;

     for(T=read();T;T--)

     {

         scanf("%s",ch);

         pos=,tot=f=;

         memset(vis,,sizeof(vis));

         if(ch[]=='P')

         {

             x=read()-;

             while(x)

             {

                 while(x<t[pos])

                 {

                     for(i=;i<=n;i++) if(!vis[i])

                     {

                         if(f) printf(" %lld",i);else {printf("%lld",i);f=;}

                         break;

                     }

                     vis[i]=;

                     pos++;

                 }

                 while(x>=t[pos]) x-=t[pos],cnt++;

                 for(i=;i<=n&&cnt!=-;i++) if(!vis[i]) cnt--;

                 vis[i-]=,tot++,cnt=,pos++;

                 if(f) printf(" %lld",i-);else {printf("%lld",i-);f=;}

             }

             if(tot!=n)

                 for(i=;i<=n;i++)

                     if(!vis[i])

                         if(f) printf(" %lld",i);else {printf("%lld",i);f=;}

             puts("");

         }

         else

         {

             res=;

             for(i=;i<=n;i++)

             {

                 x=read();

                 for(ll j=;j<x;j++) if(!vis[j]) cnt++;

                 res+=t[i]*cnt;

                 vis[x]=,cnt=;

             }

             printf("%lld\n",res+);

         }

     }

 }

巴特西

bzoj 3301 Cow Line

最新文章

热门文章