题解：AT_arc182_a [ARC182A] Chmax Rush!

· · 题解

题目传送门

思路

我们只需要枚举每一个 v_i，对于 i 后面的 v_j 如果 v_i > v_j 进行以下讨论。

当 p_i = p_j 的时候。因为不论选哪个方案 p_i 这个位置都要替换，所以无解，直接输出。
当 p_i < p_j 的时候。我们可以确定对于 i 只能选方案一，对于 j 只能选方案二，这样才能保证两段没有交集。
而当 p_i > p_j 的时候。我们可以确定对于 i 只能选方案二，对于 j 只能选方案一，这样才能保证两段没有交集。

对于每一个 i 最初都有两种选择，而在讨论的时候，每排除一种情况 i 与 j 的方案数都要减一，最后答案就是每一个 i 的方案数的乘积。

代码

#include<bits/stdc++.h>
using namespace std;
int n,m;
int p[1000000],v[1000000];
int hh[6000][5];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(),cout.tie();
    cin>>n>>m;
    for(int i=1;i<=m;i++)
        cin>>p[i]>>v[i];
    for(int i=1;i<=m;i++)
        hh[i][1]=hh[i][2]=1;
    for(int i=1;i<=m;i++)
    {
        for(int j=i+1;j<=m;j++)
        {
            if(v[i]>v[j])
            {
                if(p[j]>p[i])
                {
                    hh[i][2]=0;
                    hh[j][1]=0;
                }
                if(p[j]<p[i])
                {
                    hh[i][1]=0;
                    hh[j][2]=0;
                }
                if(p[j]==p[i])
                {
                    cout<<0;
                    return 0;
                }
            }
        }
    }
    int ans=1;
    for(int i=1;i<=m;i++)
    {
        ans*=(hh[i][1]+hh[i][2]);
        ans%=998244353;
    }
    cout<<ans;
    return 0;
}