2021CCF非专业级软件能力认证
CSP-J/S2021第二轮认证
提高组
时间：2021年10月23日14:30∼18:30
题目名称题目类型目录可执行文件名输入文件名输出文件名每个测试点时限内存子任务数目测试点是否等分
廊桥分配传统型airportairportairport.inairport.out1.0秒512MiB20是
括号序列传统型bracketbracketbracket.inbracket.out1.0秒512MiB20是
回文传统型palinpalinpalin.inpalin.out1.0秒512MiB25是
交通规划传统型traffictraffictraffic.intraffic.out3.0秒512MiB20是
提交源程序文件名对于C++语言对于C
语言
对于Pascal语言编译选项对于C++语言对于C
语言
对于Pascal语言
‐O2‐lm‐O2‐lm‐O2
airport.cppairport.cairport.pas
bracket.cppbracket.cbracket.pas
palin.cpppalin.cpalin.pas
traffic.cpptraffic.ctraffic.pas
注.意.事.项（.请.仔.细.阅.读）.
1.文件名（程序名和输入输出文件名）必须使用英文小写。
2.C/C++中函数main()的返回值类型必须是int，程序正常结束时的返回值必须是0。
3.提交的程序代码文件的放置位置请参考各省的具体要求。4.因违反以上三点而出现的错误或问题，申述时一律不予受理。
5.若无特殊说明，结果的比较方式为全文比较（过滤行末空格及文末回车）。6.程序可使用的栈空间内存与题目的内存一致。
7.全国统一评测时采用的机器配置为：Inter(R)Core(TM)i7-8700KCPU@3.70GHz，内存32GB。上述时限以此配置为准。
2021CCF非专业级软件能力认证CSP-J/S2021第二轮认证
8.只提供Linux格式附加样例文件。
9.评测在当前最新公布的NOILinux下进行，各语言的编译器版本以此为准。
第2页共13页
2021CCF非专业级软件能力认证CSP-J/S2021第二轮认证廊桥分配（airport）
廊桥分配（airport）
【题目描述】
当一架飞机抵达机场时，可以停靠在航站楼旁的廊桥，也可以停靠在位于机场边缘的远机位。乘客一般更期待停靠在廊桥，因为这样省去了坐摆渡车前往航站楼的周折。然而，因为廊桥的数量有限，所以这样的愿望不总是能实现。
机场分为国内区和国际区，国内航班飞机只能停靠在国内区，国际航班飞机只能停靠在国际区。一部分廊桥属于国内区，其余的廊桥属于国际区。
L市新建了一座机场，一共有n个廊桥。该机场决定，廊桥的使用遵循“先到先得”的原则，即每架飞机抵达后，如果相应的区（国内/国际）还有空闲的廊桥，就停靠在廊桥，否则停靠在远机位（假设远机位的数量充足）。该机场只有一条跑道，因此不存在两架飞机同时抵达的情况。
现给定未来一段时间飞机的抵达、离开时刻，请你负责将n个廊桥分配给国内区和国际区，使停靠廊桥的飞机数量最多。
【输入格式】
从文件airport.in中读入数据。
输入的第一行包含3个正整数n,m1,m2分别表示廊桥的个数、国内航班飞机的数量、国际航班飞机的数量。
接下来m1行是国内航班的信息，第i行包含2个正整数a1,i,b1,i，分别表示一架国内航班飞机的抵达、离开时刻。
接下来m2行是国际航班的信息，第i行包含2个正整数a2,i,b2,i，分别表示一架国际航班飞机的抵达、离开时刻。
每行的多个整数由空格分隔。
【输出格式】
输出到文件airport.out中。
输出一个正整数，表示能够停靠廊桥的飞机数量的最大值。
【样例1输入】
12345
3541538610914
第3页
共13页
2021CCF非专业级软件能力认证CSP-J/S2021第二轮认证廊桥分配（airport）
6710
13182114157171216
【样例1输出】
1
7
【样例1解释】
图1:样例图片
在图中，我们用抵达、离开时刻的数对来代表一架飞机，如(1,5)表示时刻1抵达、时刻5离开的飞机；用√表示该飞机停靠在廊桥，用×表示该飞机停靠在远机位。
我们以表格中阴影部分的计算方式为例，说明该表的含义。在这一部分中，国际区有2个廊桥，4架国际航班飞机依如下次序抵达：
1.首先(2,11)在时刻2抵达，停靠在廊桥2.然后(4,15)在时刻4抵达，停靠在另一个廊桥
3.接着(7,17)在时刻7抵达，这时前2架飞机都还没离开、都还占用着廊桥，而国际区只有2个廊桥，所以只能停靠远机位
4.最后(12,16)在时刻12抵达，这时(211)这架飞机已经离开，所以有1个空闲的廊桥，该飞机可以停廊桥
根据表格中的计算结果，当国内区分配2个廊桥、国际区分配1个廊桥时，停靠廊桥的飞机数量最多，一共7架。
【样例2输入】
1234
246203040502122
第4页
共13页
2021CCF非专业级软件能力认证CSP-J/S2021第二轮认证廊桥分配（airport）
5671011
41421192183456710
【样例2输出】
1
4
【样例2解释】
当国内区分配2个廊桥、国际区分配0个廊桥时，停靠廊桥的飞机数量最多，一共4架，即所有的国内航班飞机都能停靠在廊桥。
需要注意的是，本题中廊桥的使用遵循“先到先得”的原则，如果国际区只有1个廊桥，那么将被飞机(1,19)占用，而不会被(3,4)、(5,6)、(7,8)、(9,10)这4架飞机先后使用。
【样例3】
见选手目录下的airport/airport3.in与airport/airport3.ans。
【数据范围】
对于20%的数据，1≤n≤100,1≤m1+m2≤100。对于40%的数据，1≤n≤5000,1≤m1+m2≤5000。对于100%的数据，1≤n≤100000,1≤m1+m2≤100000。所有a1,i,b1,i,a2,i,b2,i为数值不超过108的互不相同的正整数。保证∀i∈[1,n],a1,i第5页共13页2021CCF非专业级软件能力认证CSP-J/S2021第二轮认证括号序列（bracket）
括号序列（bracket）
【题目描述】
小w在赛场上遇到了这样一个题：一个长度为n且符合规范的括号序列，其有些位置已经确定了，有些位置尚未确定，求这样的括号序列一共有多少个。
身经百战的小w当然一眼就秒了这题，不仅如此，他还觉得一场正式比赛出这么简单的模板题也太小儿科了，于是他把这题进行了加强之后顺手扔给了小c。
具体而言，小w定义“超级括号序列”是由字符(、)、*组成的字符串，并且对于某个给定的常数k，给出了“符合规范的超级括号序列”的定义如下：
1、()、(S)均是符合规范的超级括号序列，其中S表示任意一个仅由不.超.过.k个；.字符*组成的非空字符串（以下两条规则中的S均为此含义）
2、如果字符串A和B均为符合规范的超级括号序列，那么字符串AB、ASB均为符合规范的超级括号序列，其中AB表示把字符串A和字符串B拼接在一起形成的字符串；
3、如果字符串A为符合规范的超级括号序列，那么字符串(A)、(SA)、(AS)均为符合规范的超级括号序列。
4、所有符合规范的超级括号序列均可通过上述3条规则得到。
例如，若k=3，则字符串((**()*(*))*)(***)是符合规范的超级括号序列，但字符串*()、(*()*)、((**))*)、(****(*))均不是。特别地，空字符串也不被视为符合规范的超级括号序列。
现在给出一个长度为n的超级括号序列，其中有一些位置的字符已经确定，另外一些位置的字符尚未确定（用?表示）。小w希望能计算出：有多少种将所有尚未确定的字符一一确定的方法，使得得到的字符串是一个符合规范的超级括号序列？
可怜的小c并不会做这道题，于是只好请求你来帮忙。
【输入格式】
从文件bracket.in中读入数据。第1行，2个正整数n,k。
第2行，一个长度为n且仅由(、)、*、?构成的字符串S。
【输出格式】
输出到文件bracket.out中。
输出一个非负整数表示答案对109+7取模的结果。
【样例1输入】
第6页共13页
2021CCF非专业级软件能力认证CSP-J/S2021第二轮认证括号序列（bracket）
12
73(*??*??
【样例1输出】
1
5
【样例1解释】
如下几种方案是符合规范的：
12345
(**)*()(**(*))(*(**))(*)**()(*)(**)
【样例2输入】
12
102???(*??(?)
【样例2输出】
1
19
【样例3】
见选手目录下的bracket/bracket3.in与bracket/bracket3.ans。
【样例4】
见选手目录下的bracket/bracket4.in与bracket/bracket4.ans。
第7页共13页
2021CCF非专业级软件能力认证CSP-J/S2021第二轮认证括号序列（bracket）
【数据范围】
测试点编号1∼34∼∼1314∼1516∼20
n≤1540100500
S串中仅含有字符?
无无特殊性质
对于100%的数据，1≤k≤n≤500。
第8页共13页
2021CCF非专业级软件能力认证CSP-J/S2021第二轮认证回文（palin）
回文（palin）
【题目描述】
给定正整数n和整数序列a1,a2,...,a2n，在这2n个数中，1,2,...,n分别各出现恰好2次。现在进行2n次操作，目标是创建一个长度同样为2n的序列b1,b2,...,b2n，初始时b为空序列，每次可以进行以下两种操作之一：
1.将序列a的开头元素加到b的末尾，并从a中移除2.将序列a的末尾元素加到b的末尾，并从a中移除
我们的目的是让b成为一个回即令其满足对所有1≤i≤n，有bi=b2n+1−i。.文.数.列.，请你判断该目的是否能达成，如果可以，请输出字典序最小的操作方案，具体在【输出格式】中说明。
【输入格式】
从文件palin.in中读入数据。每个测试点包含多组测试数据。
输入的第一行包含一个整数T，表示测试数据的组数。
每组测试数据的第一行包含一个正整数n，第二行包含2n个用空格隔开的整数a1,a2,...,a2n。
【输出格式】
输出到文件palin.out中。对每个测试数据输出一行答案。
如果无法生成出回文数列，输出一行‐1，否则输出一行一个长度为2n的、由字符，其中L表示移除开头元素的操作1，R表示操作2。L或R构成的字符串（不含空格）
你需要输出所有方案对应的字符串中字典序最小的一个。
字典序的比较规则如下：长度均为2n的字符串s1..2n比t1..2n字典序小，当且仅当存在下标1≤k≤2n使得∀1≤i【样例1输入】12345
25
41245312353
321213
第9页共13页
2021CCF非专业级软件能力认证CSP-J/S2021第二轮认证回文（palin）
【样例1输出】
12
LRRLLRRRRL‐1
【样例1解释】
在第一组数据中，生成的的b数列是4531221354，可以看出这是一个回文数列。
另一种可能的操作方案是LRRLLRRRRR，但比答案方案的字典序要大。
【样例2】
见选手目录下的palin/palin2.in与palin/palin2.ans。
【数据范围】
令
n表示所有T组测试数据中n的和。
∑
对所有测试点保证1≤T≤100,1≤n,n≤5×105。
测试点编号1∼78∼1011∼1213∼1516∼1718∼2021∼25
=1≤100
≤5×105
≤5×105
有无
≤100T≤10
n≤10≤20≤100≤1000
∑n
特殊性质
∑
≤50≤1000≤25000
无
特殊性质：如果我们每次删除a中两个相邻且相等的数，存在一种方式将序列删空（例如a=[1,2,2,1]）。
第10页共13页
2021CCF非专业级软件能力认证CSP-J/S2021第二轮认证交通规划（traffic）
交通规划（traffic）
【题目描述】
给定一个平面上n条水平直线和m条垂直直线，它们相交形成n行m列的网格，从上到下第r条水平直线和从左到右第c条垂直直线之间的交点称为格点(r,c)。网格中任意两个水平或垂直相邻的格点之间的线段称为一条边，每条边有一个非负整数边权。
进行T次询问，每次询问形式如下：
给出k（T次询问的k可能不同）个附加点，每个附加点位于一条从网格边缘向外出发的射线上。所有从网格边缘向外出发的射线按左上-右上-右下-左下-左上的顺序依次编号为1到2n+2m，如下图：
图2:射线的编号
对于每次询问，不同附加点所在的射线互不相同。每个附加点和最近的格点之间的线段也称为一条边，也有非负整数边权（注意，在角上的格点有可能和两个附加点同时相连）。
给定每个附加点的颜色（黑色或者白色），请你将网格内每个格点的颜色染成黑白二者之一，并使得所有两端颜色不同的边的边权和最小。请输出这个最小的边权和。
【输入格式】
从文件traffic.in中读入数据。
第一行3个正整数n,m,T分别表示水平、垂直直线的数量，以及询问次数。接下来n−1行，每行m个非负整数。其中第i行的第j个非负整数x1i,j表示(i,j)和(i+1,j)间的边权。
接下来n行，每行m−1个非负整数。其中第i行的第j个非负整数x2i,j表示(i,j)和(i,j+1)间的边权。
第11页共13页
2021CCF非专业级软件能力认证CSP-J/S2021第二轮认证交通规划（traffic）
接下来依次输入T组询问。第i组询问开头为一行一个正整数ki表示这次询问附加点的总数。接下来ki行每行三个非负整数。其中第j行依次为x3i,j,pi,j,ti,j表示第i个附加点和相邻格点之间的边权、所在的射线编号以及附加点颜色（0为白色，1为黑色）。保证同一组询问内pi,j互不相同。
每行的多个整数由空格分隔。
【输出格式】
输出到文件traffic.out中。
输出T行，第i行输出一个非负整数，表示第i次询问染色之后两端颜色不同的边权和的最小值。
【样例1输入】
1234567
23194738105219311790
【样例1输出】
1
12
【样例1解释】
最优方案：(1,3),(1,2),(2,3)为黑色；(1,1),(2,1),(2,2)为白色。
【样例2】
见选手目录下的traffic/traffic2.in与traffic/traffic2.ans。
【样例3】
见选手目录下的traffic/traffic3.in与traffic/traffic3.ans。
第12页共13页
2021CCF非专业级软件能力认证CSP-J/S2021第二轮认证交通规划（traffic）
【样例4】
见选手目录下的traffic/traffic4.in与traffic/traffic4.ans。
【样例5】
见选手目录下的traffic/traffic5.in与traffic/traffic5.ans。
【数据范围】
测试点编号
1,23,4,56,7,,1011,1213,14,15,1617,18,19,20
∑T
n,m≤518102500
ki≤50250250250
对于所有数据，2≤n,m≤500,1≤T≤50,1≤ki≤min{2(n+m),50},1≤ki≤50,0≤x≤106,1≤p≤2(n+m),t∈{0,1}。保证对于每个i∈[1,T]，pi,j互不相同。
i=1
第13页共13页