题解：AT_arc182_a [ARC182A] Chmax Rush!

lkjzyd20 · 2024-08-22 09:24:08 · 题解

思路

首先题目数据范围 (1\le Q \le 5000) 并不大，可以分别枚举操作 i 和 j。

接下来分类讨论:

• 当 V_i \le V_j 的时候，因为在替换的过程中序列元素只增不减，所以任何操作都是可以的。

• 当 V_i>V_j 的时候，有三种情况。

  • 当 P_i=P_j 的时候，这个时候只会让序列 S 元素越来越小，则这两次操作之间一定冲突。

  • 当 P_i<P_j 的时候，这种情况下，如果这个时候把较大的 V_i 直接安排在 P_i 右侧，这个时候会导致无论在 P_i 哪一边修改都会导致存在元素大于 V_i。则操作 i 一定替换前 P_i 个元素，操作 j 一定替换从 P_j 开始到末尾的元素。

  • 当 P_i>P_j 的时候，按照上面的思路，可以得出操作 i 一定替换从 P_i 开始到末尾的元素，操作 j 一定替换前 P_j 个元素。

最后注意如果答案不为 0，必定会有没有附加约束条件的操作（即每种操作必须在哪个位置执行或者不可执行），因为每种操作都有两种选择，设 k 为不确定的操作数量（及替换前面或后面都可以的操作），那么最后结果为 2^k \bmod 998244353 。

综上所述，时间复杂度为 O(Q^2)。

代码如下

#include <bits/stdc++.h>
#define int long long
using namespace std;
#define rep(i, l, r) for(int i = l; i <= r; ++ i)
#define per(i, r, l) for(int i = r; i >= l; -- i)
const int mod = 998244353, N = 5001;
int Q, a[N], b[N], ans = 1;
main()
{
    scanf("%lld %lld", &Q, &Q);
    rep(i, 1, Q) scanf("%lld %lld", &a[i], &b[i]);
    rep(i, 1, Q)
    {
        int l = 1, r = 1;
        rep(j, 1, i - 1)
            if(b[j] > b[i]) 
            {
                if(a[j] <= a[i]) l = 0;
                if(a[j] >= a[i]) r = 0;
            }
        rep(j, i + 1, Q)
            if(b[j] < b[i])
            {
                if(a[j] <= a[i]) l = 0;
                if(a[j] >= a[i]) r = 0;
            }
        ans = ans * (l + r) % mod;
    }
    printf("%lld", ans);
}