CSP-S 2021 题解

CSP-S 自爆了，来补一补

目录

• T1. 廊桥分配
• T2. 括号序列
• T3. 回文
• T4. 交通规划

不保证没问题。

将国内航班和国际航班分开考虑。

考虑将所有飞机以二元组 (抵达时刻，离开时刻) 的形式塞到一个

set<pair<int,int> >

里。

假如一架飞机可以占一个廊桥的话，那么这架飞机离开后，第一个抵达的飞机可以占着同一个廊桥。于是可以维护若干条链，链上 \(x\) 的下一个是 \(y\) 表示 \(x\) 离开后 \(y\) 是第一个抵达的（保证一架飞机只会出现在一条链中，因为一架飞机只会占一个廊桥）。可以用

set

upper_bound

轻松维护。

然后，如果我们给国内分配 \(x\) 个廊桥的话，就相当于选 \(x\) 条链头抵达时刻最早的链。计算出每条链中有多少个点，枚举国内分配多少个廊桥算一下即可。

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5;
int n,m1,m2,x,y,ans;
struct node{
	set<pair<int,int> >s;
	int tot,cnt[N];
	void work(){
		while(s.size()&&tot<=n){
			pair<int,int>p=*s.begin();
			s.erase(p),tot++,cnt[tot]=1;
			while(s.size()){
				x=p.first,y=p.second;
				auto it=s.upper_bound(make_pair(y,0));
				if(it!=s.end()) p=*it,s.erase(it),cnt[tot]++;
				else break;
			}
		}
		for(int i=1;i<=n;i++) cnt[i]+=cnt[i-1];
	}
}A,B;
signed main(){
	scanf("%d%d%d",&n,&m1,&m2);
	for(int i=1;i<=m1;i++)
		scanf("%d%d",&x,&y),A.s.insert(make_pair(x,y));
	for(int i=1;i<=m2;i++)
		scanf("%d%d",&x,&y),B.s.insert(make_pair(x,y));
	A.work(),B.work();
	for(int i=0;i<=n;i++) ans=max(ans,A.cnt[i]+B.cnt[n-i]);
	printf("%d\n",ans);
	return 0;
}
           

显然是区间 DP，就是写之前得想清楚。

\(f_{l,r}\) 表示区间 \([l,r]\) 的答案。然后你发现，转移的时候，

()()()

会被算两次，所以我们做一些规定。

我们把区间分为三类：

• 第 \(0\) 类区间：形如 ( ... )，也就是整个区间被一对匹配的括号包起来。
• 第 \(1\) 类区间：形如 (...) ... (...)，也就是 \(\geq 2\) 个括号并列。
• 第 \(2\) 类区间：形如 (...)*(...) 也就是两个括号，中间若干个 *。

然后在做并列式的转移，也就是 \([l, k]+[k+1,r]\to [l,r]\) 时，我们强制右半部分（也就是 \([k+1,r]\)）为第 \(0\) 类区间就可以了。

#include<bits/stdc++.h>
using namespace std;
const int N=510,mod=1e9+7;
int n,m,f[N][N][3],s[N][N],R[N];
char a[N];
bool is(int i,char c){return a[i]==c||a[i]=='?';} 
int get(int l,int r){
	return ((f[l][r][0]+f[l][r][1])%mod+f[l][r][2])%mod;
}
signed main(){
	scanf("%d%d%s",&n,&m,a+1);
	for(int i=1;i<=n;i++){
		R[i]=i;
		for(int j=i+1;j<=min(n,i+m)&&is(j,'*');j++) R[i]=j;
		if(!is(i,'(')) continue;
		if(is(i+1,')')) f[i][i+1][0]=1;
		for(int j=i+2;j<=min(n,i+1+m);j++){
			if(!is(j-1,'*')) break;
			if(is(j,')')) f[i][j][0]=1;
		}
	}
	for(int j=1;j<=n;j++)
		for(int i=j;i>=1;i--) s[j][i]=(s[j][i+1]+f[i][j][0])%mod;
	for(int len=4;len<=n;len++)
		for(int i=1;i<=n-len+1;i++){
			int j=i+len-1;
			for(int k=i+1;k<j-1;k++){
				f[i][j][1]=(f[i][j][1]+1ll*get(i,k)*f[k+1][j][0])%mod;
				/*for(int l=k+1;l<j-1&&l-k<=m;l++){
					if(!is(l,'*')) break;
					f[i][j][2]=(f[i][j][2]+1ll*get(i,k)*f[l+1][j][0]%mod)%mod;
				}*/
				int r=min(R[k],j-2);
				if(k+1<=r){
					int tmp=(s[j][k+2]-s[j][r+2]+mod)%mod;
					f[i][j][2]=(f[i][j][2]+1ll*get(i,k)*tmp%mod)%mod;
				}
			}
			if(is(i,'(')&&is(j,')')){
				f[i][j][0]=(f[i][j][0]+get(i+1,j-1))%mod;
				for(int k=i+1;k<j-2&&k-i<=m&&is(k,'*');k++) f[i][j][0]=(f[i][j][0]+get(k+1,j-1))%mod;
				for(int k=j-1;k>i+2&&j-k<=m&&is(k,'*');k--) f[i][j][0]=(f[i][j][0]+get(i+1,k-1))%mod;
			}
			for(int j=len;j<=n;j++)
				s[j][j-len+1]=(s[j][j-len+2]+f[j-len+1][j][0])%mod;
				//for(int i=j;i>=1;i--) s[j][i]=(s[j][i+1]+f[i][j][0])%mod;
		}
	printf("%d\n",get(1,n));
	return 0;
} 
/*
0/1/2: ( ... )   (...)...(...)   (...)*(...)
*/
           

分类讨论第一个取左边还是右边，这样最后一个的位置就确定了。两边两个指针，中间一段区间，两边向中间靠拢，中间往两边扩大，类似于 four pointers，这样搜一下。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
int t,n,a[N],p;
char ans[N];
bool dfs(int l1,int r1,int l2,int r2){
	if(r2-l2+1==n) return 1;
	int k=r2-l2+2;
	if(l1<l2-1&&a[l1]==a[l2-1]){
		ans[k]='L',ans[n*2-k+1]='L';
		if(dfs(l1+1,r1,l2-1,r2)) return 1;
	}
	if(l1<l2&&a[l1]==a[r2+1]){
		ans[k]='L',ans[n*2-k+1]='R';
		if(dfs(l1+1,r1,l2,r2+1)) return 1;
	} 
	if(r1>r2&&a[r1]==a[l2-1]){
		ans[k]='R',ans[n*2-k+1]='L';
		if(dfs(l1,r1-1,l2-1,r2)) return 1;
	}
	if(r1>r2+1&&a[r1]==a[r2+1]){
		ans[k]='R',ans[n*2-k+1]='R';
		if(dfs(l1,r1-1,l2,r2+1)) return 1;
	}
	return 0;
}
signed main(){
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n),ans[2*n]='L',ans[2*n+1]='\0';
		for(int i=1;i<=2*n;i++) scanf("%d",&a[i]);
		for(int i=2;i<=n*2;i++)
			if(a[i]==a[1]){p=i;break;} 
		if(dfs(2,n*2,p,p)){ans[1]='L',printf("%s\n",ans+1);continue;}
		for(int i=1;i<n*2;i++)
			if(a[i]==a[n*2]){p=i;break;} 
		if(dfs(1,n*2-1,p,p)) ans[1]='R',printf("%s\n",ans+1);
		else puts("-1"); 
	}
	return 0;
}