P12964 [GCJ Farewell Round #4] Old Gold 题解

Planetary_system · 2025-10-30 20:26:14 · 题解

思路分析：

首先看数据范围考虑 DP，定义 dp_i 表示最后一个 o 在 i 的方案数，转移显然为 dp_i=\sum dp_j，在 j\sim i 中限制条件有：

• 对于每个 <（位置为 k），i+j>2\times k。
• 对于每个 >（位置为 k），i+j<2\times k。
• 对于每个 =（位置为 k），i+j=2\times k，且 j\sim i 中只能有 1 个 =。

合法转移点形成区间，得到如下的代码：

for(int i=1;i<=n;i++){
    if(s[i]!='.'&&s[i]!='o')continue;
    for(int j=i-1,l=1,r=i-1;j>=l;j--){
        if(s[j]=='=')l=max(l,2*j-i),r=min(r,2*j-i);
        else if(s[j]=='<')l=max(l,2*j-i+1);
        else if(s[j]=='>')r=min(r,2*j-i-1);
        else if(l<=j&&j<=r)dp[i]=(dp[i]+dp[j])%mod;
        if(s[j]=='o')break;
    }
}

不难发现对于取 \max 的，只与最靠近 i 的有关；对于取 \min 的，只与最靠近 j 的有关。所有取 \max 的，我们预处理出左边最近的 <，o 和 =，分别记为 l_i,o_i,e_i，直接求出左端点，又得到如下的转移：

for(int i=1;i<=n;i++){
    if(s[i]!='.'&&s[i]!='o')continue;
    int L=max({e[e[i]],2*l[i]-i,o[i]-1}),R=i-1;
    for(int j=i-1;j>L;j--){
        if(s[j]=='>')R=min(R,2*j-i-1);
        if(j<=R&&(j>e[i]||j==2*e[i]-i))
            dp[i]=(dp[i]+dp[j])%mod;
    }
}

用树状数组维护可以达到 O(n\log n)。

然后处理右端点，我们直接使用一个优先队列加入失效位置，到失效位置时直接删去贡献，直接正常查询即可。

实现如下：

priority_queue<Node>q;
for(int i=1;i<=n;i++){
    while(!q.empty()&&q.top().pos==i)
        upd(q.top().id,-dp[q.top().id]),q.pop();
    if(s[i]!='.'&&s[i]!='o')continue;
    int L=max({e[e[i]],2*l[i]-i,o[i]-1});
    dp[i]=(dp[i]+qry(i-1)-qry(max(L,e[i]))+mod)%mod;
    if(L<2*e[i]-i)dp[i]=(dp[i]+qry(2*e[i]-i)-qry(2*e[i]-i-1)+mod)%mod;
    upd(i,dp[i]),q.push({2*r[i]-i,i});
}

于是我们就正确且高效地完成了转移。

初始化部分，最前面的 . 和 > 是不影响的，只出现这两个的 . 处为 1，> 处为 0，出现其他的后面就为 0（第一个 o 为 1）。

求答案部分，最后面的 . 和 < 是不影响的，从后往前，在出现其他的之前的全都加入答案。

AC Code：

注意开 long long！！！作者调这个调了 2h……
十年 OI 一场空……

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e5+10,mod=1e9+7;
int n,dp[N],tr[N],l[N],r[N],e[N],o[N];
struct Node{int pos,id;};
bool operator<(Node x,Node y){
    return x.pos>y.pos;
}
void upd(int x,int y){
    for(;x<=n;x+=x&(-x))
        tr[x]=(tr[x]+y)%mod;
}
int qry(int x){
    int res=0;
    for(;x>0;x-=x&(-x))
        res=(res+tr[x])%mod;
    return res;
}
void solve(){
    string s;cin>>s;
    n=s.size(),s=" "+s;
    memset(dp,0,sizeof(dp));
    memset(tr,0,sizeof(tr));
    for(int i=2;i<=n;i++)
        l[i]=(s[i-1]=='<'?i-1:l[i-1]),
        o[i]=(s[i-1]=='o'?i-1:o[i-1]),
        e[i]=(s[i-1]=='='?i-1:e[i-1]);
    r[n]=n+1;
    for(int i=n-1;i;i--)
        r[i]=(s[i+1]=='>'?i+1:r[i+1]);
    for(int i=1;i<=n;i++){
        if(s[i]=='.'||s[i]=='o')dp[i]=1;
        if(s[i]!='.'&&s[i]!='>')break;
    }
    priority_queue<Node>q;
    for(int i=1;i<=n;i++){
        while(!q.empty()&&q.top().pos==i)
            upd(q.top().id,-dp[q.top().id]),q.pop();
        if(s[i]!='.'&&s[i]!='o')continue;
        int L=max({e[e[i]],2*l[i]-i,o[i]-1});
        dp[i]=(dp[i]+qry(i-1)-qry(max(L,e[i]))+mod)%mod;
        if(L<2*e[i]-i)dp[i]=(dp[i]+qry(2*e[i]-i)-qry(2*e[i]-i-1)+mod)%mod;
        upd(i,dp[i]),q.push({2*r[i]-i,i});
    }
    int ans=0;
    for(int i=n;i;i--){
        ans=(ans+dp[i])%mod;
        if(s[i]!='.'&&s[i]!='<')break;
    }
    cout<<ans<<'\n';
}
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int T;cin>>T;for(int i=1;i<=T;i++)
     cout<<"Case #"<<i<<": ",solve();
    return 0;
}

完结撒花！！！