题解：P12558 [UOI 2024] Heroes and Monsters

· · 题解

Solution

这是人能想出来的吗我请问了。

把英雄看做红球，怪物当做蓝球，在数轴上按照 b 的大小排出来。

问对于给定的 i，有多少种给红球标上 \texttt L 和 \texttt R 的方案，使得有 i 个红球标上了 \texttt L，且所有红球都和对应方向上的一个蓝球匹配。

很容易发现，标同一种方向的两个球，如果 a_x<a_y，则一定有 b_{\text{mat}_x} < b_{\text{mat}_y}。而显然肯定让 b 更小的和 \texttt L 匹配。

很容易想到许多 O(n^3) 的做法。比如对于给定的 i，维护前 j 个数里面标上了 k 个 \texttt L。这个做法完全没有前途啊，因为 j 和 k 两个信息一个也省不掉，而且 i 会对 (j,k) 的转移产生影响。

考虑取出第 i 小的 b 为 b_i。

重要结论：如果最终确实有 i 个 \texttt L，那么 a_j > b_i 的 j 标 \texttt L 一定不会产生矛盾（找不到比他小的 b 进行匹配），另一个方向同理。

所以，我们只需要保证 a_j < b_i 的，填上 \texttt L 的 j 是合法的；a_j > b_i 的，填上 \texttt R 的 j 是合法的。

这样在同一段内，就不需要管另一种颜色是否合法了。这样状态直接被压到 O(n^2)，转移是 O(1) 的。足以通过本题。

总结：第一，我真的没做出来这道题。

第二，对于这种两种变量的限制问题，限制较为复杂。但是你发现，某一段对一个变量实际上是没有限制的，而另一段对另一个没有限制。那么你就应该把它们分离看。

#include<bits/stdc++.h>
#define int long long
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=5000+10,MOD=998244353;
int n,q,a[MAXN],b[MAXN],f[MAXN][MAXN],g[MAXN][MAXN],ans[MAXN]; 
signed main() {
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n;
    ffor(i,1,n) cin>>a[i];
    ffor(i,1,n) cin>>b[i];
    sort(a+1,a+n+1),sort(b+1,b+n+1);
    f[0][0]=g[0][0]=1;
    ffor(i,1,n) ffor(j,0,i) {
        f[i][j]=f[i-1][j];
        if(j&&a[i]>b[j]) f[i][j]=(f[i][j]+f[i-1][j-1])%MOD;
    }
    ffor(i,1,n) ffor(j,0,i) {
        g[i][j]=g[i-1][j];
        if(j&&a[n-i+1]<b[n-j+1]) g[i][j]=(g[i][j]+g[i-1][j-1])%MOD;
    }
    ffor(k,0,n) {
        int p=0;
        while(p+1<=n&&a[p+1]<b[k]) p++;
        ffor(x,0,k) {
            int y=x+n-p-k;
            if(0<=y&&y<=n-p) ans[k]=(ans[k]+f[p][x]*g[n-p][y])%MOD;
        }
    }
    ffor(i,1,n) ans[i]=(ans[i]+ans[i-1])%MOD;
    cin>>q;
    ffor(i,1,q) {
        int l,r,res;
        cin>>l>>r,res=ans[r];
        if(l) res=(res-ans[l-1])%MOD;
        cout<<(res%MOD+MOD)%MOD<<'\n';  
    }
    return 0;
}