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;
}