[CSP-S 2021] 括号序列

题目描述

小 w 在赛场上遇到了这样一个题：一个长度为 $n$ 且符合规范的括号序列，其有些位置已经确定了，有些位置尚未确定，求这样的括号序列一共有多少个。

身经百战的小 w 当然一眼就秒了这题，不仅如此，他还觉得一场正式比赛出这么简单的模板题也太小儿科了，于是他把这题进行了加强之后顺手扔给了小 c。

具体而言，小 w 定义“超级括号序列”是由字符 (、)、* 组成的字符串，并且对于某个给定的常数 $k$，给出了“符合规范的超级括号序列”的定义如下：

1. ()、(S) 均是符合规范的超级括号序列，其中 S 表示任意一个仅由不超过 $\mathbf{k}$ 个字符 * 组成的非空字符串（以下两条规则中的 S 均为此含义）；
2. 如果字符串 A 和 B 均为符合规范的超级括号序列，那么字符串 AB、ASB 均为符合规范的超级括号序列，其中 AB 表示把字符串 A 和字符串 B 拼接在一起形成的字符串；
3. 如果字符串 A 为符合规范的超级括号序列，那么字符串 (A)、(SA)、(AS) 均为符合规范的超级括号序列。
4. 所有符合规范的超级括号序列均可通过上述 3 条规则得到。

例如，若 $k=3$，则字符串 ((**()*(*))*)(***) 是符合规范的超级括号序列，但字符串 *()、(*()*)、((**))*)、(****(*)) 均不是。特别地，空字符串也不被视为符合规范的超级括号序列。

现在给出一个长度为 $n$ 的超级括号序列，其中有一些位置的字符已经确定，另外一些位置的字符尚未确定（用 ? 表示）。小 w 希望能计算出：有多少种将所有尚未确定的字符一一确定的方法，使得得到的字符串是一个符合规范的超级括号序列？

可怜的小 c 并不会做这道题，于是只好请求你来帮忙。

输入格式

第一行，两个正整数 $n,k$。

第二行，一个长度为 $n$ 且仅由 (、)、*、? 构成的字符串 $S$。

输出格式

输出一个非负整数表示答案对 ${10}^9+7$ 取模的结果。

样例 #1

样例输入 #1

7 3
(*??*??

样例输出 #1

5

样例 #2

样例输入 #2

10 2
???(*??(?)

样例输出 #2

19

提示

【样例解释 #1】

如下几种方案是符合规范的：

(**)*()
(**(*))
(*(**))
(*)**()
(*)(**)

【数据范围】

测试点编号	$n\le$	特殊性质
$1\sim 3$	$15$	无
$4\sim 8$	$40$	无
$9\sim 13$	$100$	无
$14\sim 15$	$500$	$S$ 串中仅含有字符 ?
$16\sim 20$	$500$	无

对于 $100\%$ 的数据，$1\le k\le n\le 500$。

转载一部写的非常好的题解

来源：洛谷
作者：wsyear

代码

#include <bits/stdc++.h>
using namespace std;const int M = 510, mod = 1e9+7;
typedef long long LL;
LL dp[M][M][10];
int n, k;
char c[M];bool cmp(int a ,int b){return (c[a]=='(' || c[a]=='?') && (c[b]==')' || c[b]=='?');
}int main()
{scanf("%d%d%s", &n, &k, c+1);for(int i=1 ; i<=n ; i++)   dp[i][i-1][0] = 1;for(int len=1 ; len<=n ; len++)for(int l=1 ; l<=n-len+1 ; l++){int r = l+len-1;if(len<=k) dp[l][r][0]=dp[l][r-1][0]&&(c[r]=='*'||c[r]=='?');if(len>=2){if(cmp(l,r)) dp[l][r][1]=(dp[l+1][r-1][0]+dp[l+1][r-1][2]+dp[l+1][r-1][3]+dp[l+1][r-1][4])%mod;for(int i=l ; i<r ; i++){dp[l][r][2]=(dp[l][r][2]+dp[l][i][3]*dp[i+1][r][0])%mod;dp[l][r][3]=(dp[l][r][3]+(dp[l][i][2]+dp[l][i][3])*dp[i+1][r][1])%mod;dp[l][r][4]=(dp[l][r][4]+(dp[l][i][4]+dp[l][i][5])*dp[i+1][r][1])%mod;dp[l][r][5]=(dp[l][r][5]+dp[l][i][4]*dp[i+1][r][0])%mod;}}dp[l][r][5]=(dp[l][r][5]+dp[l][r][0])%mod;dp[l][r][3]=(dp[l][r][3]+dp[l][r][1])%mod;}printf("%lld", dp[1][n][3]);return 0;
}

[CSP-S 2021] 廊桥分配

题目描述

当一架飞机抵达机场时，可以停靠在航站楼旁的廊桥，也可以停靠在位于机场边缘的远机位。乘客一般更期待停靠在廊桥，因为这样省去了坐摆渡车前往航站楼的周折。然而，因为廊桥的数量有限，所以这样的愿望不总是能实现。

机场分为国内区和国际区，国内航班飞机只能停靠在国内区，国际航班飞机只能停靠在国际区。一部分廊桥属于国内区，其余的廊桥属于国际区。

L 市新建了一座机场，一共有 $n$ 个廊桥。该机场决定，廊桥的使用遵循“先到先得”的原则，即每架飞机抵达后，如果相应的区（国内/国际）还有空闲的廊桥，就停靠在廊桥，否则停靠在远机位（假设远机位的数量充足）。该机场只有一条跑道，因此不存在两架飞机同时抵达的情况。

现给定未来一段时间飞机的抵达、离开时刻，请你负责将 $n$ 个廊桥分配给国内区和国际区，使停靠廊桥的飞机数量最多。

输入格式

输入的第一行，包含三个正整数 $n,m_1,m_2$，分别表示廊桥的个数、国内航班飞机的数量、国际航班飞机的数量。

接下来 $m_1$ 行，是国内航班的信息，第 $i$ 行包含两个正整数 $a_{1,i},b_{1,i}$，分别表示一架国内航班飞机的抵达、离开时刻。

接下来 $m_2$ 行，是国际航班的信息，第 $i$ 行包含两个正整数 $a_{2,i},b_{2,i}$，分别表示一架国际航班飞机的抵达、离开时刻。

每行的多个整数由空格分隔。

输出格式

输出一个正整数，表示能够停靠廊桥的飞机数量的最大值。

样例 #1

样例输入 #1

3 5 4
1 5
3 8
6 10
9 14
13 18
2 11
4 15
7 17
12 16

样例输出 #1

7

样例 #2

样例输入 #2

2 4 6
20 30
40 50
21 22
41 42
1 19
2 18
3 4
5 6
7 8
9 10

样例输出 #2

4

提示

【样例解释 #1】

在图中，我们用抵达、离开时刻的数对来代表一架飞机，如 $(1,5)$ 表示时刻 $1$ 抵达、时刻 $5$ 离开的飞机；用 $\surd$ 表示该飞机停靠在廊桥，用 $\times$ 表示该飞机停靠在远机位。

我们以表格中阴影部分的计算方式为例，说明该表的含义。在这一部分中，国际区有 $2$ 个廊桥，$4$ 架国际航班飞机依如下次序抵达：

1. 首先 $(2,11)$ 在时刻 $2$ 抵达，停靠在廊桥。
2. 然后 $(4,15)$ 在时刻 $4$ 抵达，停靠在另一个廊桥。
3. 接着 $(7,17)$ 在时刻 $7$ 抵达，这时前 $2$ 架飞机都还没离开、都还占用着廊桥，而国际区只有 $2$ 个廊桥，所以只能停靠远机位。
4. 最后 $(12,16)$ 在时刻 $12$ 抵达，这时 $(2,11)$ 这架飞机已经离开，所以有 $1$ 个空闲的廊桥，该飞机可以停靠在廊桥。

根据表格中的计算结果，当国内区分配 $2$ 个廊桥、国际区分配 $1$ 个廊桥时，停靠廊桥的飞机数量最多，一共 $7$ 架。

【样例解释 #2】

当国内区分配 $2$ 个廊桥、国际区分配 $0$ 个廊桥时，停靠廊桥的飞机数量最多，一共 $4$ 架，即所有的国内航班飞机都能停靠在廊桥。

需要注意的是，本题中廊桥的使用遵循“先到先得”的原则，如果国际区只有 $1$ 个廊桥，那么将被飞机 $(1,19)$ 占用，而不会被 $(3,4)$、$(5,6)$、$(7,8)$、$(9,10)$ 这 $4$ 架飞机先后使用。

【数据范围】

对于 $20\%$ 的数据，$n\le 100$，$m_1+m_2\le 100$。
对于 $40\%$ 的数据，$n\le 5000$，$m_1+m_2\le 5000$。
对于 $100\%$ 的数据，$1\le n\le {10}^5$，$m_1,m_2\ge 1$，$m_1+m_2\le {10}^5$，所有 $a_{1,i},b_{1,i},a_{2,i},b_{2,i}$ 为数值不超过 ${10}^8$ 的互不相同的正整数，且保证对于每个 $i\in [1,m_1]$，都有 $a_{1,i}<b_{1,i}$，以及对于每个 $i\in [1,m_2]$，都有 $a_{2,i}<b_{2,i}$。

【感谢 hack 数据提供】

• xingxuxin。
• cyslngsul。

题解

让我们先忽略廊桥数量的限制来安排航班。我们维护一个空闲的廊桥队列，每到达一架航班，就给它安排编号最小的廊桥供其使用。

现在加上廊桥数量的限制。容易发现刚才的廊桥分配方法直接就帮我们解决了廊桥限制的问题：如果当前有 n 个廊桥可供使用，则分配到 n+1 号及以后的廊桥实质上就是分配到远机位了，不需要再做任何额外的处理。

到这里做法就很清晰了：我们按照开头提到的分配方法来安排航班的停靠位置，记录各廊桥停靠的航班数，做一个前缀和，最后枚举分配给某个区的廊桥数，算出各情况下两区实际使用廊桥的航班数总和，即可解决本题。

代码

#include <bits/stdc++.h>
using namespace std;const int M = 1e5+100;
typedef pair<int,int> PII;
PII a[M], t1[M], t2[M];
int res1[M], res2[M], n, m1, m2, qzh1[M], qzh2[M];int main()
{scanf("%d%d%d", &n, &m1, &m2);for(int i=0 ; i<m1 ; i++)scanf("%d%d", &a[i].first, &a[i].second);sort(a, a+m1);for(int i=0 ; i<m1 ; i++)for(int j=1 ; j<=m1 ; j++)if(a[i].first > t1[j].first) {res1[i] = j;t1[j].first = a[i].second;t1[j].second++;break;}for(int i=0 ; i<m2 ; i++)scanf("%d%d", &a[i].first, &a[i].second);sort(a, a+m2);for(int i=0 ; i<m2 ; i++)for(int j=1 ; j<=m2 ; j++)if(a[i].first > t2[j].first){res2[i] = j;t2[j].first = a[i].second;t2[j].second++;break;}for(int i=0 ; i<=n ; i++)qzh1[i] = qzh1[i-1]+t1[i].second, qzh2[i] = qzh2[i-1]+t2[i].second;int res = 0;for(int l=0 ; l<=n ; l++)res = max(res, qzh1[l]+qzh2[n-l]);printf("%d", res);return 0;
}

[CSP-S 2021] 回文

题目描述

给定正整数 $n$ 和整数序列 $a_1,a_2,\dots ,a_{2n}$，在这 $2n$ 个数中，$1,2,\dots ,n$ 分别各出现恰好 $2$ 次。现在进行 $2n$ 次操作，目标是创建一个长度同样为 $2n$ 的序列 $b_1,b_2,\dots ,b_{2n}$，初始时 $b$ 为空序列，每次可以进行以下两种操作之一：

1. 将序列 $a$ 的开头元素加到 $b$ 的末尾，并从 $a$ 中移除。
2. 将序列 $a$ 的末尾元素加到 $b$ 的末尾，并从 $a$ 中移除。

我们的目的是让 $b$ 成为一个回文数列，即令其满足对所有 $1\le i\le n$，有 $b_i=b_{2n+1-i}$。请你判断该目的是否能达成，如果可以，请输出字典序最小的操作方案，具体在【输出格式】中说明。

输入格式

每个测试点包含多组测试数据。

输入的第一行，包含一个整数 $T$，表示测试数据的组数。对于每组测试数据：

第一行，包含一个正整数 $n$。
第二行，包含 $2n$ 个用空格隔开的整数 $a_1,a_2,\dots ,a_{2n}$。

输出格式

对每组测试数据输出一行答案。

如果无法生成出回文数列，输出一行 ‐1，否则输出一行一个长度为 $2n$ 的、由字符 L 或 R 构成的字符串（不含空格），其中 L 表示移除开头元素的操作 1，R 表示操作 2。

你需要输出所有方案对应的字符串中字典序最小的一个。

字典序的比较规则如下：长度均为 $2n$ 的字符串 $s_{1\sim 2n}$ 比 $t_{1\sim 2n}$ 字典序小，当且仅当存在下标 $1\le k\le 2n$ 使得对于每个 $1\le i<k$ 有 $s_i=t_i$ 且 $s_k<t_k$。

样例 #1

样例输入 #1

2
5
4 1 2 4 5 3 1 2 3 5
3
3 2 1 2 1 3

样例输出 #1

LRRLLRRRRL
-1

样例 #2

样例输入 #2

见附件中的 palin/palin2.in

样例输出 #2

见附件中的 palin/palin2.ans

提示

【样例解释 #1】

在第一组数据中，生成的的 $b$ 数列是 $[4,5,3,1,2,2,1,3,5,4]$，可以看出这是一个回文数列。

另一种可能的操作方案是 LRRLLRRRRR，但比答案方案的字典序要大。

【数据范围】

令 $\sum n$ 表示所有 $T$ 组测试数据中 $n$ 的和。

对所有测试点保证 $1\le T\le 100$，$1\le n,\sum n\le 5\times {10}^5$。

测试点编号	$T\le$	$n\le$	$\sum n\le$	特殊性质
$1\sim 7$	$10$	$10$	$50$	无
$8\sim 10$	$100$	$20$	$1000$	无
$11\sim 12$	$100$	$100$	$1000$	无
$13\sim 15$	$100$	$1000$	$25000$	无
$16\sim 17$	$1$	$5\times {10}^5$	$5\times {10}^5$	无
$18\sim 20$	$100$	$5\times {10}^5$	$5\times {10}^5$	有
$21\sim 25$	$100$	$5\times {10}^5$	$5\times {10}^5$	无

特殊性质：如果我们每次删除 $a$ 中两个相邻且相等的数，存在一种方式将序列删空（例如 $a=[1,2,2,1]$）。

【hack 数据提供】
@潜在了H2O下面。

题解

可以看出，第一个入队的数势必会在最后一个入队，而第二个入队的数势必会在倒数第二个入队。而倒数第二个入队的数和最后第一个入队的数必定是相挨着的（这里省略证明过程）。所以，我们先找到第一个入队的数的另一个位置，并把数组以这个位置向左和向右分成两个队列，把队头和队尾进行匹配，匹配成功就继续，失败则返回$-1$。

代码

由于苯人代码只有60分，这里就转载我的好同学huyuun的代码

#include <iostream>
#include <algorithm>
#include <cstring>
#include <stdio.h>using namespace std;const int N = 5e5 + 10;int n, a[N + N];
int first, last;
int stk1[N + N], stk2[N + N];
int t1, t2, h1, h2;
string ans[3];void solve(int mid) {h1 = h2 = 1;t1 = t2 = 0;int l1, l2;if (mid == first)l1 = 2, l2 = n + n;elsel1 = 1, l2 = n + n - 1;for (int i = mid - 1 ; i >= l1 ; i -- )stk1[ ++ t1] = a[i];for (int i = mid + 1 ; i <= l2 ; i ++ )stk2[ ++ t2] = a[i];while (t1 >= h1 || t2 >= h2) if (t1 >= h1 && ((t1 > h1 && stk1[h1] == stk1[t1]) || (t2 >= h2 && stk2[h2] == stk1[t1]))) {ans[3 - l1] += 'L';if (t1 > h1 && stk1[h1] == stk1[t1])ans[3 - l1] += 'L', h1 ++ ;else if (t2 >= h2 && stk2[h2] == stk1[t1])ans[3 - l1] += 'R', h2 ++ ;t1 -- ;continue;}if (t2 >= h2 && ((t2 > h2 && stk2[h2] == stk2[t2]) || (t1 >= h1 && stk1[h1] == stk2[t2]))) {ans[3 - l1] += 'R';if (t2 > h2 && stk2[h2] == stk2[t2])ans[3 - l1] += 'R', h2 ++ ;else if (t1 >= h1 && stk1[h1] == stk2[t2])ans[3 - l1] += 'L', h1 ++ ;t2 -- ;continue;}return;}
}int main() 
{int T;scanf("%d", &T);while (T -- ) {scanf("%d", &n);ans[1].clear(), ans[2].clear();for (int i = 1 ; i <= n + n ; i ++ ) {scanf("%d", a + i);if (a[i] == a[1])first = i;}for (int i = n + n - 1 ; i ; i -- )if (a[i] == a[n + n])last = i;ans[1] += 'L', ans[2] += 'R';ans[1] += 'L', ans[2] += 'L';solve(first);solve(last);if (ans[1].size() < n + n && ans[2].size() < n + n)puts("-1");else {if (ans[1].size() == n + n) {for (int i = 0 ; i < n + n ; i += 2)cout << ans[1][i];for (int i = n + n - 1 ; i >= 0 ; i -= 2)cout << ans[1][i];} else if (ans[2].size() == n + n) {for (int i = 0 ; i < n + n ; i += 2)cout << ans[2][i];for (int i = n + n - 1 ; i >= 0 ; i -= 2)cout << ans[2][i];}puts("");}}return 0;
}