USACO 2011 February Silver Cow Line /// 康拓展开模板题 oj22713

题目大意：

输入n k，1-n的排列，k次操作

操作P：输入一个m 输出第m个排列

操作Q：输入一个排列输出它是第几个排列

Sample Input

5 2
P
3
Q
1 2 5 3 4

Sample Output

1 2 4 3 5
5

康拓展开裸题然而因为用了getchar(); 所以一直在超时

康拓展开：http://www.cnblogs.com/dong008259/archive/2011/12/12/2283436.html

#include <bits/stdc++.h>

using namespace std;

int n,a[],b[];

long long int fac[]={,,,,,,,,,,,

,,,,,,

,,,};

void ops0()

{

    long long sum=;

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

        scanf("%d",&a[i]);

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

    {

        int tem=;

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

            if(a[j]<a[i]) tem++;

        sum+=tem*fac[n-i];

    }

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

}

void ops1()

{

    long long m; scanf("%lld",&m); m--;

    for(int i=n-;i>=;i--)

    {

        int tem=m/fac[i];

        for(int j=;j<=tem;j++)

            if(b[j]) tem++;

        if(i) printf("%d ",tem+);

        else printf("%d",tem+);

        b[tem]=;

        m%=fac[i];

    }

    printf("\n");

}

int main()

{

    int k;

    while(~scanf("%d%d",&n,&k))

    {

        while(k--)

        {

            memset(b,,sizeof(b));

            char ops; scanf(" %c",&ops);

            if(ops=='P') ops1();

            else ops0();

        }

        printf("\n");

    }

    return ;

}

巴特西

USACO 2011 February Silver Cow Line /// 康拓展开模板题 oj22713

最新文章

热门文章