题解：CF2144C Non-Descending Arrays

chu_yh · 2025-09-16 17:16:00 · 题解

解题思路

简单 DP 题（甚至可能不算 DP），提供一种容易理解并且好写的做法，复杂度 O(n)。

容易想到设 f_i 表示只考虑下标小于等于 i 的 a,b 数组的方案数。

然后考虑转移，我们不妨假定前 i-1 个元素已经非递减了。当 a_i\ge a_{i-1} 并且 a_i\ge b_{i-1} 时，a_i 换不换均满足条件。同理，当 b_i 同时满足 b_i\ge a_{i-1} 和 b_i \ge b_{i-1} 时，那么 b_i 换或不换也满足条件。如此那么对于下标 i，我们有换或不换两种方案，转移方程式为：

但如果 a_i 或 b_i 至少有一个并不是两个条件都满足，就只有一种选择，不会产生贡献。因为题目保证了“there is at least one good subset”，所以不会存在 a_i 或 b_i 两个条件都不满足的情况。

::::info[代码] 不开 long long 见祖宗。

#include<bits/stdc++.h>
using namespace std;
const int N=1002,M=1002,mod=998244353;
#define A (a[i]>=a[i-1])
#define B (b[i]>=b[i-1])
#define C (a[i]>=b[i-1])
#define D (b[i]>=a[i-1])
int T,n,a[N],b[N];
long long f[N];
//bool c[N];

int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        for(int i=1;i<=n;i++){
            scanf("%d",&b[i]);
            f[i]=0;//,c[i]=false;
        }
        f[1]=2;//,c[1]=true;
        for(int i=2;i<=n;i++){
            int x=0;
            x=(A&&B?1:0)+(C&&D?1:0);
            f[i]=(f[i-1]*x)%mod;
        }
        printf("%lld\n",f[n]);
    }
    return 0;
}

::::

没用的小优化

发现 f_i 仅有的一维 i 可以滚动掉，将数组 f_i 优化为一个变量。

::::info[代码] 不开 long long 见祖宗。

#include<bits/stdc++.h>
using namespace std;
const int N=1002,mod=998244353;
int T,n,a[N],b[N];
long long ans;

int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        for(int i=1;i<=n;i++) scanf("%d",&b[i]);
        ans=2;
        for(int i=2;i<=n;i++)
            if(a[i]>=a[i-1]&&b[i]>=b[i-1]&&a[i]>=b[i-1]&&b[i]>=a[i-1])
                (ans<<=1)%=mod;
        printf("%lld\n",ans);
    }
    return 0;
}

::::