首页 > 代码库 > hdu 5719(Arrange)(冷静分析)

hdu 5719(Arrange)(冷静分析)

2024-08-24 02:25:31   220人阅读

技术分享

 

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+10;
const int MOD=998244353;
int A[Max],B[Max],n;
int dfs(int cur,int pre)
{
    int premin,premax;
    premin=premax=pre;
    LL ans=1,sum,count=1;
    for(int i=cur;i<n;i++)
    {
        if(A[i]>B[i]) return 0;
        if(A[i]!=premin||B[i]!=premax)
        {
           if(A[i]!=premin&&B[i]!=premax) return 0;
           if(A[i]>premin||B[i]<premax) return 0;
           if(A[i]<premin) premin=A[i];
           if(B[i]>premax) premax=B[i];
           count++;
        }
        else
        {
            sum=premax-premin-count+1;
            if(sum<=0) return 0;
            ans=(ans*sum)%MOD;
            count++;
        }
    }
    return ans;
}
int main()
{
    int T;
    for(scanf("%d",&T);T;T--)
    {
        scanf("%d",&n);
        for(int i=0;i<n;i++)
        {
            scanf("%d",&A[i]);
        }
        for(int i=0;i<n;i++)
        {
            scanf("%d",&B[i]);
        }
        int ans;
        if(A[0]!=B[0]) ans=0;
        else ans=dfs(1,A[0]);
        printf("%d\n",ans);
    }
    return 0;
}
View Code

 

hdu 5719(Arrange)(冷静分析)


联系
我们