题解：P11456 [USACO24DEC] Interstellar Intervals G

教练讲了本题的线性做法，自己写一篇题解加深理解。

对于求方案数的问题，一般有两种方法解决。一是组合数学，二是动态规划。像本题这种序列问题，可以考虑动态规划。

设

f_i

表示前

i

个位置中，合法序列的方案数。

如果当前位置没有限制，则可以顺承上一个位置的方案数，即

f_i = f_{i-1}

。如果当前位置有限制，那么找到一段前面的合法连续子段，记其左端点为

l

，右端点为

r

，则转移方程为

f_i = f_{i-1} + \sum_{j=l}^r f_j

，显然可以用前缀和优化后面的一坨求和。

接下来考虑如何求左端点和右端点。统一对右端点进行操作，先预处理每个位置之前最晚出现的两种颜色下标，记为

prer

和

preb

。在转移过程中假设当前下标为

i

，能转移到

i

的下标为

j

，那么右端点为

i - 2(i-j+1)

，左端点为

preb_j

，因为如果再往右就会到上上一个合法序列。

代码实现需要注意细节和特殊限制。

CPP

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int N = 5e5+5;
const int p = 1e9+7;
int n,l,prer[N],preb[N];
ll f[N],sum[N];
vector<int> v[N];
string s;

ll cal(int now,int l,int r){
	int L=now-2*r,R=now-2*l;
	if(L>R) return 0;
	if(L<2) return sum[R];
	return (sum[R]-sum[L-2]+p)%p;
}
int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>s; l=s.size(),s=" "+s;	 
    int lb=0,lr=0;
    for(int i=1;i<=n;i++){
    	prer[i]=lr,preb[i]=lb;
    	if(s[i]=='R') lr=i;
    	if(s[i]=='B') lb=i;
	}
    for(int i=1;i<=n;i++){
    	if(s[i]=='X') v[i].push_back(i);
    	if(s[i]=='B'){
    		for(int j=i;j<=min(n,i*2-preb[i]-2);j++) //预处理j能被哪些i转移 
    			v[j].push_back(i);
		}
	}
	sum[0]=f[0]=1;
	for(int i=1;i<=n;i++){
		if(s[i]!='R'){
			if(s[i]=='X') f[i]=f[i-1];
			int lim=i-prer[i]; //注意这里的限制 
			for(auto j:v[i]){
				int l=i-j+1;
				if(l>lim) continue;
				int r=min(lim,(i-preb[j])>>1);
				(f[i]+=cal(i,l,r))%=p;
			}
		}
		sum[i]=(i==1 ? f[1] : sum[i-2]+f[i])%p; //前缀和优化 
	}
	cout<<f[n];
	return 0;
}

题解：P11456 [USACO24DEC] Interstellar Intervals G

文章操作

相关推荐

评论

题解：P11456 [USACO24DEC] Interstellar Intervals G