专栏文章

题解：P9522 [JOISC 2022] 错误拼写

llkjzyd20
P9522题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minncxfh
此快照首次捕获于
2025/12/02 05:14
3 个月前
此快照最后确认于
2025/12/02 05:14
3 个月前
查看原文
https://www.luogu.com.cn/problem/P9522
  • A<BA<B
如果 sA+1≠sAs_{A+1}\ne s_A，那么它们的大小关系就决定了 TAT_A 和 TBT_B 的大小关系。 如果 sA+1=sAs_{A+1}=s_A，我们继续比较下一位。TAT_A 的第 A+1A+1 位是 sA+2s_{A+2}，TBT_B 的第 A+1A+1 位是 sA+1s_{A+1}。因为 sA+1=sAs_{A+1}=s_A，所以我们实际在比较 sA+2s_{A+2} 和 sAs_A，我们以此类推继续比较下一位，也就是说我们实际比较的是 sA+1∼B<sA∼B−1s_{A+1\sim B}<s_{A\sim B-1}。
  • A>BA>B 跟上面类似，在区间 [B,A−1][B, A-1] 上，第一个满足 si≠si+1s_i \ne s_{i+1} 的位置 ii 必须满足 si<si+1s_i < s_{i+1}，我们实际比较的是 sB∼A−1<sB+1∼As_{B\sim A-1}<s_{B+1\sim A}。
设 fi,jf_{i,j} 为前 ii 个位置，且 si=js_i=j 的方案数，因为从前往后转移会转移重复，我们在给状态再加一维 0/10/1 表示是否 si−1≠sis_{i-1}\ne s_i。
对于 fi,j,0f_{i,j,0} 显然从 fi−1,j,0+fi−1,j,1f_{i-1,j,0}+f_{i-1,j,1} 转移过来，接着我们枚举 l,kl,k 两个端点，fi,j,1f_{i,j,1} 从 l,kl,k 转移过来。
这样我们就是 O((26n)2)O((26n)^2)，考虑如何优化。
首先我们可以消掉 2626 的常数，我们令 sumi,j=∑j=126fi,j,1sum_{i,j}=\sum^{26}_{j=1}f_{i,j,1}，但这还是远远不够。
我们接着对每个起点 ss 预处理出该起点出发，类型为 0/10/1 的边的最大终点 mxsmx_{s}，那么我们把每个起点 ss 的贡献视作对区间 [s+1,mxs][s+1, mx_{s}]，用大根堆维护当前仍然有效的起点。
因为我们知道了起点和终点，这样便于我们把对 ll 的前缀和保存下来，对于每次转移，我们只需要 O(1)O(1)，这样我们就通过了此题。
CPP
#include<bits/stdc++.h>
#define int long long
#define rep(i,l,r) for(int i=l;i<=r;++i)
#define per(i,r,l) for(int i=r;i>=l;--i)
using namespace std;
const int N=500000+10,mod=1e9+7;
int n,m,tot;
int f[N][26][2],ans;
int s[N][26];
int mx0[N],mx1[N];
int l0[N],l1[N];
int S[26][N];
vector<int> V0[N],V1[N];
priority_queue<pair<int,int>> q0,q1;
signed main(){
    // freopen("misspelling.in","r",stdin);
    // freopen("misspelling.out","w",stdout);
    cin>>n>>m;
    rep(i,1,m){
        int x,y; cin>>x>>y;
        if(x==y) continue;
        ++tot;
        if(x>y) mx0[y]=max(mx0[y],x);
        else mx1[x]=max(mx1[x],y);
    }
    rep(i,1,n-1){
        if(mx0[i]>0) V0[i+1].push_back(i);
        if(mx1[i]>0) V1[i+1].push_back(i);
    }
    rep(i,1,n){
        for(auto st:V0[i]) q0.push({st,mx0[st]});
        for(;!q0.empty()&&q0.top().second<i;) q0.pop();
        l0[i]=q0.empty()?0:q0.top().first;
        for(auto st:V1[i]) q1.push({st,mx1[st]});
        for(;!q1.empty()&&q1.top().second<i;) q1.pop();
        l1[i]=q1.empty()?0:q1.top().first;
    }
    rep(i,0,25) f[1][i][1]=1;
    rep(j,0,25) s[1][j]=j+1;
    rep(t,0,25) S[t][1]=s[1][t];
    rep(i,2,n){
        rep(j,0,25){
            f[i][j][0]=(f[i-1][j][0]+f[i-1][j][1])%mod;
            int R=i-1;
            if(j<25&&l0[i]<=R){
                f[i][j][1]=(f[i][j][1]+S[25][R]-S[j][R]-(S[25][l0[i]]-S[j][l0[i]])+mod)%mod;
            }
            if(j>0&&l1[i]<=R){
                f[i][j][1]=(f[i][j][1]+S[j-1][R]-S[j-1][l1[i]]+mod)%mod;
            }
        }
        s[i][0]=f[i][0][1];
        rep(j,1,25) s[i][j]=(s[i][j-1]+f[i][j][1])%mod;
        rep(t,0,25) S[t][i]=(S[t][i-1]+s[i][t])%mod;
    }
    rep(i,0,25){
        ans=(ans+f[n][i][0]+f[n][i][1])%mod;
    }
    cout<<ans;
    return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...