HDU 5719 Arrange

待我称王封你为后i 2022-07-20 12:14 134阅读 0赞

题目链接：[http://acm.hdu.edu.cn/showproblem.php?pid=5719][http_acm.hdu.edu.cn_showproblem.php_pid_5719]

题目大意：有一个1-n的序列，你要根据下面给出的两个条件，找出这个序列一共有多少种排列方式  
第一个条件：一个有n个数的序列，假设这个序列中的数在第i位的数为a\[i\]，则表示1-i中最小的是a\[i\]（简称一序列）  
第二个条件:一个有n个数的序列，假设这个序列中的数在第i位的数为b\[i\]，则表示1-i中最大的是b\[i\]（简称二序列）

解题思路：小的只能越来越小，大的只能越来越大，所以一序列必定是递减的，二序列必定是递增的，同时一序列中的数一定小于与二序列中同位置的数。  
一序列二序列的中第一个数必定相等，因为在只有一个数的情况下，不可能有两个不同的最大最小值。  
对于之后的某个位置i有三种情况。  
1.是a\[i\]和b\[i\]都未在一序列和二序列出现过，这种情况显然是非法的，因为假设这个序列现在最小是x,最大是y，要变成最小是x1,最大是y1，肯定要出现两个数，而一个位置只有一个数，非法。  
2.a\[i\]和b\[i\]只有一个出现过，那么这个位置的值i一定是定的,因为假设这个序列现在最小是x,最大是y，变成最小是x,最大是y1,必定b\[i\]就是y1,变成另一个数同理。  
3.a\[i\]和b\[i\]都在前面的出现过，由于序列的是逐渐增长的，所以之前的数一定在a\[i\]和b\[i\]中，这个位置出现的数就有b\[i\]-a\[i\]-i种可能。

对每个位置进行计算即可得出结果

AC代码：

#include <iostream>
    #include <cstring>
    #include <cstdio>
    #define RI(N) scanf("%d",&(N))
    #define RII(N,M) scanf("%d %d",&(N),&(M))
    #define RIII(N,M,K) scanf("%d %d %d",&(N),&(M),&(K))
    #define mem(a) memset((a),0,sizeof(a))
    using namespace std;
    const int inf=1e9;
    const int inf1=-1*1e9;
    double EPS=1e-10;
    typedef long long LL;
    
    
    
    int n1[100005];
    int n2[100005];
    int n3[100005];
    
    int main()
    {
        int T;
        RI(T);
        while(T--)
        {
            memset(n1,0,sizeof(n1));
            memset(n2,0,sizeof(n2));
            memset(n3,0,sizeof(n3));
            int n;
            RI(n);
            for(int i=0; i<n; i++)
                RI(n1[i]);
            for(int i=0; i<n; i++)
                RI(n2[i]);
            bool mark=false;
            if(n1[0]!=n2[0]) mark=true;
            LL ans=1;
            for(int i=1; i<n; i++)
            {
                if(n1[i]>n1[i-1]) mark=true;
                if(n2[i]<n2[i-1]) mark=true;
                if(n1[i]>n2[i]) mark=true;
            }
            if(mark)
            {
                printf("0\n");
                continue;
            }
            else
            {
                n3[n1[0]]=1;
                for(int i=1; i<n; i++)
                {
                    if(!n3[n1[i]]&&!n3[n2[i]])
                    {
                        mark=true;
                        break;
                    }
                    else if(n3[n1[i]]&&n3[n2[i]])
                    {
                        if(n2[i]-n1[i]+1>i)
                        {
                            ans=ans*(LL(n2[i]-n1[i]+1-i))%998244353;
                        }
                        else
                        {
                            mark=true;
                            break;
                        }
                    }
                    else if(n3[n1[i]]&&!n3[n2[i]])
                    {
                        n3[n2[i]]=1;
                    }
                    else if(n3[n2[i]]&&!n3[n1[i]])
                    {
                        n3[n1[i]]=1;
                    }
                }
    
            }
            if(mark) printf("0\n");
            else cout<<ans<<endl;
        }
        return 0;
    }

[http_acm.hdu.edu.cn_showproblem.php_pid_5719]: http://acm.hdu.edu.cn/showproblem.php?pid=5719