CSP-S 2021 游记&题解

CSP-S 2021的终曲。

游记非常简单，主要是题解。（话说这次 CSP 炸的太厉害差点没进 NOIP……）

Day -1

上午是运动会，机房很多人都请假了，但是文科班人少所以没能摸掉，被安排去走方队和跑 100 米。

SDFZ 的运动会竟然没下雨，这真是出乎意料——从初一到高二，似乎是第一次（合理怀疑某位老师是龙王）。初中部的方队完全就是摇旗呐喊，外加几个皮卡丘熊本熊，整活能力实属不足，还得看高中：

• 高二一班：达成成就【让书记临时改演讲稿】“今天大家都很高兴，和过年一样。”——运动会为什么要舞龙啊，淦。
• 高二二班：“下面走来的是高二二班的交感神经和副交感神经……”。
• 高二三班（我们班）：“5310，警钟长鸣；必须猛卷，不能躺平！”

100 米跑的很拉，rank 7 收场，但确实没放到心上：没安排我去 3000 米已经是万幸了，谢谢。

跑完大概 10 点，直接摸走，回家准备行李，打了两把雀，手气不错（谁知道是不是消耗欧气了），12点下楼买了几个包子吃，直奔东站赶动车。到火车站继续雀（为什么这么摸鱼啊）。车上看了看《考试手册》，自己整理了一点板子和常见问题。

晚上到日照。因为离万达很近就去半天妖吃烤鱼，然而人很多，等到 8 点 30 才吃上，心态很爆炸（给爆 0 埋下伏笔了属于是）。回宾馆继续看板子，看到了一个 dp 题，想写一下结果很困睡了。

Day 0

上午睡到 8 点多，起来看到空间里 zsy 他们去海边散步（感觉海边会很冷）。吃了点面包，写了一遍高精度加减乘除模，复习了一圈数论算法（完全没有猜对的说）。中午到万达吃饭，看到山东 NOIP 群里出了普及组的题，秒了 ABC。

2：00

到了 SWUT，看到 zkw 和 shy 神在旁边的小树林里复习。给 zzc 发了 QQ，然而没有收到回复，就先进去了。绕了半天走到 401 结果才 2：10，拿出手机又跟 zzc 发了一条消息，仍然没有回复。2：30进考场了。打了一波快读快写板子，存盘重启一遍，打了个 dij 就到点了。

2：30

四道题都看了一遍，制定了一个错误的思路：先打暴力。上来打 A 的 40 分暴力，写了两个队列（事实上换成堆就差不多过了），结果忘记考虑 \(n<m_1+m_2\) 的情况，中样例都过不去。调了一会，感觉脑子很混乱，竟然放弃了，开始看 B。

3：30/4：00 /4：30/5：00/5：30/6：00……

T2 就是爆炸的开端——完全忘记考虑正解，dfs 又不知道怎么判断，写了几遍都 WA on 小样例，当时就感觉完蛋了，静不下心来。看了看 CD 也完全没想正解，打了两个 dfs 又回来想 AB……直到 6：30 收卷。

晚上到火车站才见到 zzc 和机房的神们，人均 300+ 啊，而我要爆零了（绝望）。当然最后没有退役，\(10+0+12+0=22\)，卡线进 NOIP 了。上车之后没有打 Atcoder 的心情，继续颓雀，连续放铳更加痛苦。

简单总结一下，题目难度确实比较大，但确实也没能发挥出实力。首先应该合理分配时间，其次保证思维清楚，积极考虑正解，最后打暴力，不要本末倒置。在遇到困难的时候，要放平心态，一步一步调试查错，不要崩掉。

NOIp::rp++;

，加油！

题解

A 廊桥分配

可以认为廊桥是无限多的，让到达的飞机随便停。为了使得方案最优，肯定要让到达的飞机停在最靠前的空余的廊桥——如果前面有飞机飞走，出现空当，就停过去；否则就往后扔。

这件事情可以开两个堆实现：堆 \(A\) 存停靠的飞机（按照时间排序），堆 \(B\) 存空余的廊桥编号（从小到大）。分别处理国内区和国际区：枚举每一架飞机，对堆 \(A\) 检查是否有飞机离开，扔掉它们，把它们占据的廊桥编号再压入堆 \(B\)；取出堆 \(B\) 顶（最靠前的廊桥），和飞机编号一起扔进堆 \(A\) 并从堆 \(B\) 里弹掉，当然还要记录一下答案，

res[B.top()]++

，即又有一架飞机在这个廊桥停靠过。

最后对国内区和国际区的 \(res\) 数组分别做一次前缀和。这时，\(res_i\) 表示为这个区分配 \(i\) 个廊桥时，总共有多少架飞机能够停靠。那么我们枚举从 \(0\) 到 \(n\)，记录 \(res1_i+res2_{n-i}\) 的最大值，即为答案。

下面是 AC 代码：

const int N = 1e5 + 10;
pair<int, int> a[N], b[N];//国内区和国际区飞机的停留区间
int n, res1[N], res2[N];

bool cmp(pair<int, int> a, pair<int, int> b) {
	return a.first < b.first;
}

void calc(pair<int, int> *t, int m, int *res) {
	priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > air;
	priority_queue<int, vector<int>, greater<int> > id;
	for (int i = 1; i <= n; ++i) {
		id.push(i);//开始的时候，所有的廊桥都是空余的
	}
	for (int i = 1; i <= m; ++i) {
		while (!air.empty() && air.top().first <= t[i].first) {//删除飞走的飞机
			id.push(air.top().second);
			air.pop();
		}
		if (id.empty())
			continue;
		int now = id.top();
		id.pop();
		res[now]++;
		air.push({t[i].second, now});//注意堆air中的first是离开时间，second是占用廊桥编号
	}
	for (int i = 1; i <= n; ++i) {
		res[i] += res[i - 1];
	}
}

void main() {
	//输入略
	sort(a + 1, a + m1 + 1, cmp);
	sort(b + 1, b + m2 + 1, cmp);
	calc(a, m1, res1);
	calc(b, m2, res2);
	for (int i = 0; i <= n; ++i) {
		ans = max(ans, res1[i] + res2[n - i]);
	}
	printf("%d\n", ans);
}
           

B 括号序列

观察数据范围 \(n\le 500\)，合理猜测是 \(\mathcal{O(n^3)}\) 的区间 dp，套路化的设计状态为 \(f_{l,r}\) 表示区间 \([l,r]\) 内合法的“超级括号序列”个数，发现并不好转移——\(\texttt{(A)(SA)(AS)(S)}\) 和 \(\texttt{ASB AB}\) 有比较大的区别（外层括号是否匹配），故此考虑分别处理：

设 \(f_{l,r}\) 为两端括号不匹配的括号序列数量，\(g_{l,r}\) 为两端括号匹配的括号序列数量。emmmm……听起来有点奇怪，形象的说，\(f\) 对应的是这样的 \(\texttt{(****)()(**)}\)，而 \(g\) 对应的是这样的 \((****())\)。

转移只需“按题意模拟”，对于 \(g\) 数组，如果当前区间两段【是】或【可以是匹配的括号，\(\texttt{()}\) 型可以直接加 \(1\)，\(\texttt{(SA)(AS)(S)}\) 可以通过设置指针向左右扫连续 \(\texttt{*?*****?}\) 段进行更新。而对于 \(f\) 数组，可以设置双指针，同样是找连续 \(\texttt{*?*****}\) 段，进行转移。

这样的时间复杂度是 \(\mathcal{O(n^4)}\) 的，原因是 \(f\) 的转移为 \(n^2\)。我们可以使用前缀和预处理 \(\texttt{ASB}\) 里的 \(\texttt{B}\)，以 \(\mathcal(O(n))\) 的实现转移。

下面是 AC 代码：

void main() {
	int n,m;
	scanf("%d%d%s",&n,&m,s+1);
	for(int l=n-1; l; --l)
		for(int r=l+1; r<=n; ++r) {
			if((s[l]=='('||s[l]=='?')&&(s[r]==')'||s[r]=='?')) {
				if(l+1==r) ++g[l][r],g[l][r]%=mod;//()型
				else {
					g[l][r]+=(f[l+1][r-1]+g[l+1][r-1])%mod,g[l][r]%=mod;//（A)型
	 				int p=0;
					while(p<m&&l+1+p<r-1&&(s[l+1+p]=='*'||s[l+1+p]=='?')) {//（SA)型
						g[l][r]+=(f[l+1+p+1][r-1]+g[l+1+p+1][r-1])%mod;
						g[l][r]%=mod,++p;
					}
					p=0;
					while(p<m&&r-1-p>l+1&&(s[r-1-p]=='*'||s[r-1-p]=='?')) {//（AS)型
						g[l][r]+=(f[l+1][r-1-p-1]+g[l+1][r-1-p-1])%mod;
						g[l][r]%=mod,++p;
					}
					if(p<m&&r-1-p==l+1&&(s[l+1]=='*'||s[l+1]=='?'))//（S)型
						++g[l][r],g[l][r]%=mod;
				}
			}
			pre[l]=0;
			for(int k=l+1; k<=r; ++k)
				pre[k]=(pre[k-1]+(f[k][r]+g[k][r])%mod)%mod;
			for(int k=l,now=l; k<r; ++k) {
				if(now<k) now=k;
				while(now+1<r&&now+1-k<=m&&(s[now+1]=='*'||s[now+1]=='?'))//ASB型或AB型
					++now;
				f[l][r]+=1ll*g[l][k]*(pre[now+1]-pre[k]+mod)%mod;
				f[l][r]%=mod;
			}
		}
	printf("%d\n",(f[1][n]+g[1][n])%mod);
}
           

C 回文

真没想到这题是用 bfs 过的……实质上还是四指针。

预处理出与 \(a_1\) 和 \(a_{2n}\) 相等的位置 \(pos1,pos2\)，我们可以得到搜索的初状态 \((1,2n+1,pos1,pos1)\) 和 \((0,2n,pos2,pos2)\)。这四个维度代表四个指针，前两个由外向里，后两个由里向外。如果转移到最后，两边“碰上了”，则有解，否则无解输出 \(-1\)。

struct node {
	int x,y,i,j;
	int tp1,tp2,pre;//外层转移，内层转移，从何而来
} p[10000010];//内存池

std::queue<int> q;

void dfs(int u) {
	ans1[++cnt1]=p[u].tp1,ans2[++cnt2]=p[u].tp2;
	if(p[u].pre) dfs(p[u].pre);
}

void print(int u) {
	cnt1=cnt2=0,flag=true;
	dfs(u);
	for(int i=cnt1; i; --i) putchar(ans1[i]==1?'L':'R');
	for(int i=1; i<=cnt2; ++i) putchar(ans2[i]==1?'L':'R');
	putchar('\n');
}

//in main()
for(scanf("%d",&T); T--;) {
	int n,tot=0;
	scanf("%d",&n);
	memset(ans1,0,sizeof(int)*n);
	memset(ans2,0,sizeof(int)*n);//多测务必清空，但内存池不必清空（太大了会TLE)
	flag=false;
	for(int i=1; i<=(n<<1); ++i) scanf("%d",&a[i]);
	int pos1,pos2;
	for(int i=2; i<=(n<<1); ++i)//预处理pos1,pos2
		if(a[i]==a[1]) {
			pos1=i;
			break;
		}
	for(int i=1; i<(n<<1); ++i)
		if(a[i]==a[(n<<1)]) {
			pos2=i;
			break;
		}
	p[++tot]=node {1,(n<<1)+1,pos1,pos1,1,1,0},q.push(1);
	p[++tot]=node {0,(n<<1),pos2,pos2,2,1,0},q.push(2);
	while(!q.empty()) {
		int u=q.front();
		q.pop();
		if(p[u].x+1==p[u].i&&p[u].j+1==p[u].y) {
			print(u);
			while(!q.empty()) q.pop();//一定要清空队列！
			break;
		}
		if(p[u].x+1<p[u].i-1&&a[p[u].x+1]==a[p[u].i-1]) {//LL
			p[++tot]=node {p[u].x+1,p[u].y,p[u].i-1,p[u].j,1,1,u};
			q.push(tot);
			continue;
		}
		if(p[u].x+1<p[u].i&&p[u].j+1<p[u].y&&a[p[u].x+1]==a[p[u].j+1]) {//LR
			p[++tot]=node {p[u].x+1,p[u].y,p[u].i,p[u].j+1,1,2,u},
			q.push(tot);
			continue;
		}
		if(p[u].x<p[u].i-1&&p[u].j<p[u].y-1&&a[p[u].i-1]==a[p[u].y-1]) {//RL
			p[++tot]=node {p[u].x,p[u].y-1,p[u].i-1,p[u].j,2,1,u};
			q.push(tot);
			continue;
		}
		if(p[u].j+1<p[u].y-1&&a[p[u].j+1]==a[p[u].y-1]) {//RR
			p[++tot]=node {p[u].x,p[u].y-1,p[u].i,p[u].j+1,2,2,u};
			q.push(tot);
			continue;
		}
	}
	if(!flag) puts("-1");
}
           

THE END