hdu 5719(Arrange)(冷静分析)

A数组显示从0到i的最小值
B数组显示从0到i的最大值
由此可得：A数组是单调不增的(怎么也会不使得最小值变大)
B数组是单调不减的。
设premin和premax为i位以前的最小值和最大值.
可以得出以下几点：
1.第一位,A数组和B数组定然相同,否则无解
2.当A[i]>B[i] 无解
3.当A[i]<premin,更新最小值，同时意味着这意味只能放A[i],当B[i]>premax,同样操作
,当如果两者同时发生,说明有冲突,无解
4.当A[i]==premin&&B[i]==premax,此时可以放置的点有premax-premin+1个
但是题目要求数字都是唯一的,可以观察下以前的放置过程中占了多少个数字
1.可以看到,A数组单调不增,B数组单调不减,所以premax-premin的区间是递增的,也就意味着
前面所使用的数字都是从现在的可用区间内拿去的
2.首先首位是确定的,占去一位:count=1
3.更新premax和premin的时候,每次都会确定一个数count+=1
4.每次A[i]==premin&&B[i]==premax的时候,虽然可选的情况多,
但也就只确定一个数count+=1
最后利用乘法原理,就能过题了

#include <bits/stdc++.h>

using namespace std;

typedef long long LL;

const int Max=1e5+;

const int MOD=;

int A[Max],B[Max],n;

int dfs(int cur,int pre)

{

    int premin,premax;

    premin=premax=pre;

    LL ans=,sum,count=;

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

    {

        if(A[i]>B[i]) return ;

        if(A[i]!=premin||B[i]!=premax)

        {

           if(A[i]!=premin&&B[i]!=premax) return ;

           if(A[i]>premin||B[i]<premax) return ;

           if(A[i]<premin) premin=A[i];

           if(B[i]>premax) premax=B[i];

           count++;

        }

        else

        {

            sum=premax-premin-count+;

            if(sum<=) return ;

            ans=(ans*sum)%MOD;

            count++;

        }

    }

    return ans;

}

int main()

{

    int T;

    for(scanf("%d",&T);T;T--)

    {

        scanf("%d",&n);

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

        {

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

        }

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

        {

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

        }

        int ans;

        if(A[]!=B[]) ans=;

        else ans=dfs(,A[]);

        printf("%d\n",ans);

    }

    return ;

}