Limited Permutation

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=6044

题意：现在有一个排列p1,p2,p3,p4,p5,p6…………pn，然后再给你n对区间[Li，Ri]【i表示第i个区间】。现在有一个这样的定义min(pL,pL+1,⋯,pR)=pi，也就是说对于第i个区间[Li,Ri]中最小的是一个pi，问这样的排列有多少个？

思路：我们先分析题目意思从min(pL,pL+1,⋯,pR)=pi中我们可以分析由于最终要确定这个排列所以必定存在一个区间是[1,n]这样才能确定最小的哪一位，假设这是第i组区间，就把整个[1,n]的区间分成两半，一个是[1,i-1].一个是[i+1,n],从而确定了最小的数1在第i个位置。对于两个子区间我们以[1,n-1]这个区间为例，我们是不是也需要一个区间刚好是[1,i-1]我们才能确定[1,i-1]这个区间内最小的那个值是哪一个。以此类推，又可以分成两个区间，右边的那个区间也是这样。所以我们可以的得到得到这样的一个结论，只要在这个分区间的过程中其中一个区间不存在，我就无法确定区间最小，也就无法形成一个区间，这个时候答案就是零。如果所有区间都存在着就是一个组合数的问题，我们思考对于[1,n]这个区间分成[1,i-1]和[i+1.n]两个区间对于左边区间是不是需要i-1个数，而总共是n-1个数，是不相当于乘以C（n-1，i-1）的组合数，然后进一步递归下去，链乘上分区间返回上来的组合数，还有右边返回上来的组合数这个具体看代码。

对于判断这个区间是否存在一开始的dfs，然后用map去判断结果超时了，可能是由于组合数取膜使用的乘法逆元是用快速幂求出来的，据说可以n的复杂度预处理逆元，不太会……所以超时了。后来发现一个规律，我们可以一开始的时候对于一个区间用以左节点升续排序，左节点相同以右节点的降序排列，这样就实际上就是一个dfs序，我们仔细分析我们之前操作。实际上就是一个dfs的过程，如果排列存在，那么我们在dfs过程中遇到的区间应该严格与我们排完序的区间吻合，如果不吻合，就说明区间不存在，可能不太好理解。自己模拟一遍这个dfs的过程就会明白了。

这道题还有一个究极输入挂：

代码：

const int MAXBUF = ;

char buf[MAXBUF], *ps = buf, *pe = buf+;

inline void rnext()

{

    if(++ps == pe)

        pe = (ps = buf)+fread(buf,sizeof(char),sizeof(buf)/sizeof(char),stdin);

}

template <class T>

inline bool readin(T &ans)

{

    ans = ;

    T f = ;

    if(ps == pe) return false;//EOF

    do{

        rnext();

        if('-' == *ps) f = -;

    }while(!isdigit(*ps) && ps != pe);

    if(ps == pe) return false;//EOF

    do

    {

        ans = (ans<<)+(ans<<)+*ps-;

        rnext();

    }while(isdigit(*ps) && ps != pe);

    ans *= f;

    return true;

}

由于数据量很大，所以需要这个超级输入挂，没有这个输入挂是过不了的，可以记下来。

AC代码:

 //Author: xiaowuga

 #include <iostream>

 #include <algorithm>

 #include <set>

 #include <vector>

 #include <queue>

 #include <cmath>

 #include <cstring>

 #include <cstdio>

 #include <ctime>

 #include <map>

 #include <bitset>

 #include <cctype>

 #define maxx INT_MAX

 #define minn INT_MIN

 #define inf 0x3f3f3f3f

 #define mem(s,ch) memset(s,ch,sizeof(s))

 #define da cout<<da<<endl

 #define uoutput(a,i,l,r) for(int i=l;i<r;i++) if(i==l) cout<<a[i];else cout<<" "<<a[i];cout<<endl;

 #define doutput(a,i,l,r) for(int i=r-1;i>=0;i--) if(i==r-1) cout<<a[i];else cout<<" "<<a[i];cout<<endl;

 const long long N= +;

 const long long mod=1e9+;

 using namespace std;

 typedef long long LL;

 LL mi[N];

 LL n,flag,ct;

 struct node{

     LL x,y,z;

     bool operator <(const node &m) const{

         if(x==m.x) return y>=m.y;

         else return x<m.x;

     }

 }oj[N];

 LL q_power(LL a,LL k){

     LL ans=;

     while(k){

         if(k%) ans=ans*a%mod;

         k/=;

         a=a*a%mod;

     }

     return ans;

 }

 void init(){

     mi[]=mi[]=;

     for(int i=;i<=N-;i++){

         mi[i]=mi[i-]*i%mod;

     }

 }

 LL cal(LL a,LL b){

      LL ans=;

      ans=mi[a]*q_power(mi[a-b],mod-)%mod;

      ans=ans*q_power(mi[b],mod-)%mod;

      return ans;

 }

 LL dfs(LL x,LL y){

     if(flag) return ;

     if(x>y) return ;

     if(oj[ct].x!=x||oj[ct].y!=y){

         flag=;return ;

     }

     node t=oj[ct];

     ct++;

     if(x==y) return ;

     LL res=cal(t.y-t.x,t.z-t.x)*dfs(t.x,t.z-)%mod;

     res=res*dfs(t.z+,t.y)%mod;

     return res;

 }

 const int MAXBUF = ;

 char buf[MAXBUF], *ps = buf, *pe = buf+;

 inline void rnext()

 {

     if(++ps == pe)

         pe = (ps = buf)+fread(buf,sizeof(char),sizeof(buf)/sizeof(char),stdin);

 }

 template <class T>

 inline bool readin(T &ans)

 {

     ans = ;

     T f = ;

     if(ps == pe) return false;//EOF

     do{

         rnext();

         if('-' == *ps) f = -;

     }while(!isdigit(*ps) && ps != pe);

     if(ps == pe) return false;//EOF

     do

     {

         ans = (ans<<)+(ans<<)+*ps-;

         rnext();

     }while(isdigit(*ps) && ps != pe);

     ans *= f;

     return true;

 }

 int main() {

     //freopen("data.txt","r",stdin);

     init();

     int h=;

     while(readin(n)){

         for(int i=;i<=n;i++) readin(oj[i].x);

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

             readin(oj[i].y);

             oj[i].z=i;

         }

         flag=;ct=;

         sort(oj+,oj+n+);

         printf("Case #%d: %lld\n",++h,dfs(1LL,n));

     }

     return ;

 }

巴特西

2017 Multi-University Training Contest - Team 1—HDU6044

Limited Permutation

最新文章

热门文章