题解：P11456 [USACO24DEC] Interstellar Intervals G

· · 题解

题目比较关键的点在于存在两种不同的点，因此而存在两种约束条件，对我们问题处理影响非常大。

这类计数题目使用动态规划的概率很大，那么先考虑动态规划。

我们设状态 dp_i 表示在目前已经选择了前 i 段的方案数，转移通过前缀和判断是否合法，暴力添加即可。

那么此时的时间复杂度是 O(n^2) 的，考虑如何进行优化。

首先最显而易见的是区间长度一定是偶数，因此我们可能需要按照奇偶进行分类处理。

我们拆开红色的影响和蓝色的影响进行判断。

假设我们现在需要处理出 dp_i 的值，我们想要得到对于红色合法的转移。

假设上一个红色的位置为 la，那么我们的左端点选择在 [la-(i-la)+1,i]，当然是保证奇偶相同的。

那么我们就需要将 [la-(i-la),i-1] 的值转移过来。

但是我们还有蓝色的情况仍然存在影响，需要继续判断。

蓝色的并不像红色的可以直接判断，因为你选择覆盖的红色区间左右端点都在移动，所以这些可以选择进行转移的位置并不是一个区间。

那么我们反过来考虑，处理出每一个点可以被转移到的位置，做一个类似差分的修改操作，然后通过数据结构按照位置维护，通过修改值的大小满足蓝色的条件，通过查询的范围得到维护红色的条件，并且开两组数据结构分别维护即可。

那么我们很明显可以使用树状数组进行维护。

那么继续推出每个值在哪个范围内进行转移即可，只需要考虑下一个蓝色不会包含在红色内即可。

代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9+7;
int n,la,lb,dp[500005];
char s[500005];
vector<int> e[500005];
struct BT{
    int c[500005];
    int lowbit(int x){
        return x&-x;
    }
    void add(int x,int y){
        x++;
        for(int i=x;i<=n+1;i+=lowbit(i))c[i]=(c[i]+y+mod)%mod;
    }
    int query(int x){
        x++;
        int ans=0;
        for(int i=x;i;i-=lowbit(i))ans=(ans+c[i])%mod;
        return ans;
    }
    int query(int l,int r){
        if(l>r)return 0;
        if(!l)return query(r);
        return (query(r)-query(l-1)+mod)%mod;
    }
}bit[2];
signed main(){
    cin>>n>>s+1;
    dp[0]=1;
    bit[0].add(0,dp[0]);
    for(int i=1;i<=n;i++){
        if(s[i]=='X')dp[i]=dp[i-1];
        if(s[i]=='R')la=i;
        if(s[i]=='B'){
            while(lb<i){
                if(i+(i-lb)<=n)e[i+(i-lb)].push_back(lb);
                lb++;
            }
        }
        for(int v:e[i])bit[v&1].add(v,-dp[v]);
        int l=max(la-(i-la),0ll);
        dp[i]=(dp[i]+bit[i&1].query(l,i-1))%mod;
        bit[i&1].add(i,dp[i]);
    }
    cout<<dp[n];
    return 0;
}