CCF 非专业级软件能力认证

CSP-J/S  第二轮认证

计算机技术代写 1. 文件名(程序名和输入输出文件名)必须使用英文小写。 2. C/C++ 中函数 main() 的返回值类型必须是 int,程序正常结束时的返回值必须是 0。3. 提交的程序代码文件的放置位置请参考各省的具体要求。
4. 因违反以上三点而出现的错误或问题…

提高组

计算机技术代写
计算机技术代写

提交源程序文件名

编译选项

计算机技术代写
计算机技术代写

注 .意 .事 .项( .请 .仔 .细 .阅 .读)

  1. 文件名(程序名和输入输出文件名)必须使用英文小写。
  2. C/C++ 中函数 main() 的返回值类型必须是 int,程序正常结束时的返回值必须是 0。
  1. 提交的程序代码文件的放置位置请参考各省的具体要求。
  2. 因违反以上三点而出现的错误或问题,申述时一律不予受理。
  3. 若无特殊说明,结果的比较方式为全文比较(过滤行末空格及文末回车)。
  4. 程序可使用的栈空间内存限制与题目的内存限制一致。
  5. 全国统一评测时采用的机器配置为:Inter(R) Core(TM) i7-8700K CPU @3.70GHz,内存 32GB。上述时限以此配置为准。2021 CCF 非专业级软件能力认证 CSP-J/S 2021 第二轮认证
  1. 只提供 Linux 格式附加样例文件。
  2. 评测在当前最新公布的 NOI Linux 下进行,各语言的编译器版本以此为准。

 

廊桥分配(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 输入】

计算机技术代写
计算机技术代写

【样例 1 输出】

【样例 1 解释】

计算机技术代写
计算机技术代写

图 1: 样例图片

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

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

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

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

【样例 2 输入】 计算机技术代写

【样例 2 输出】

【样例 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 < b1,i, a2,i < b2,i

第 5 页 共 13 页2021 CCF 非专业级软件能力认证 CSP-J/S 2021 第二轮认证

括号序列(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 页2021 CCF 非专业级软件能力认证 CSP-J/S 2021 第二轮认证

括号序列(bracket)

1 7 3

2 (*??*??

【样例 1 输出】

1 5

【样例 1 解释】

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

1 (**)*()

2 (**(*))

3 (*(**))

4 (*)**()

5 (*)(**)

【样例 2 输入】

1 10 2

2 ???(*??(?)

【样例 2 输出】

1 19

【样例 3】

见选手目录下的 bracket/bracket3.in bracket/bracket3.ans

【样例 4】

见选手目录下的 bracket/bracket4.in bracket/bracket4.ans

【数据范围】

计算机技术代写
计算机技术代写

对于 100% 的数据,1 k n 500 。

回文(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+1i

请你判断该目的是否能达成,如果可以,请输出字典序最小的操作方案,具体在【输出格式】中说明。

【输入格式】 计算机技术代写

从文件 palin.in 中读入数据。

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

输入的第一行包含一个整数 T,表示测试数据的组数。

每组测试数据的第一行包含一个正整数 n,第二行包含 2n 个用空格隔开的整数a1, a2, . . . , a2n

【输出格式】

输出到文件 palin.out 中。

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

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

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

字典序的比较规则如下:长度均为 2n 的字符串 s1..2n t1..2n 字典序小,当且仅当存在下标 1 k 2n 使得 1 i < k si = ti sk < tk

【样例 1 输入】

1 2

2 5

3 4 1 2 4 5 3 1 2 3 5

4 3

5 3 2 1 2 1 3

【样例 1 输出】

1 LRRLLRRRRL

2 ‐1

【样例 1 解释】

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

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

【样例 2】

见选手目录下的 palin/palin2.in palin/palin2.ans

【数据范围】 计算机技术代写

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

对所有测试点保证1T 100, 1 n,n 5 × 105。

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

交通规划(traffffic)

【题目描述】

给定一个平面上 n 条水平直线和 m 条垂直直线,它们相交形成 n m 列的网格,从上到下第 r 条水平直线和从左到右第 c 条垂直直线之间的交点称为格点 (r, c)。网格中任意两个水平或垂直相邻的格点之间的线段称为一条边,每条边有一个非负整数边权。

进行 T 次询问,每次询问形式如下:

给出 kT 次询问的 k 可能不同)个附加点,每个附加点位于一条从网格边缘向外出发的射线上。所有从网格边缘向外出发的射线按左上-右上-右下-左下-左上的顺序依次编号为 1 到 2n + 2m,如下图:

计算机技术代写
计算机技术代写

图 2: 射线的编号

对于每次询问,不同附加点所在的射线互不相同。每个附加点和最近的格点之间的线段也称为一条边,也有非负整数边权(注意,在角上的格点有可能和两个附加点同时相连)。

给定每个附加点的颜色(黑色或者白色),请你将网格内每个格点的颜色染成黑白二者之一,并使得所有两端颜色不同的边的边权和最小。请输出这个最小的边权和。

【输入格式】

从文件 traffffic.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) 间的边权。

接下来依次输入 T 组询问。第 i 组询问开头为一行一个正整数 ki 表示这次询问附加点的总数。接下来 ki 行每行三个非负整数。其中第 j 行依次为 x3i,j , pi,j , ti,j 表示第 i 个附加点和相邻格点之间的边权、所在的射线编号以及附加点颜色(0 为白色,1 为黑色)。保证同一组询问内 pi,j 互不相同。

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

【输出格式】 计算机技术代写

输出到文件 traffffic.out 中。

输出 T 行,第 i 行输出一个非负整数,表示第 i 次询问染色之后两端颜色不同的边权和的最小值。

【样例 1 输入】

1 2 3 1

2 9 4 7

3 3 8

4 10 5

5 2

6 19 3 1

7 17 9 0

【样例 1 输出】

1 12

【样例 1 解释】

最优方案:(1, 3),(1, 2),(2, 3) 为黑色;(1, 1),(2, 1),(2, 2) 为白色。

【样例 2】

见选手目录下的 traffffic/traffffic2.in traffffic/traffffic2.ans

【样例 3】

见选手目录下的 traffffic/traffffic3.in traffffic/traffffic3.ans

【样例 4】

见选手目录下的 traffffic/traffffic4.in traffffic/traffffic4.ans

【样例 5】

见选手目录下的 traffffic/traffffic5.in traffffic/traffffic5.ans

【数据范围】

对于所有数据,2 n, m 500, 1 T 50, 1 ki min{2(n + m), 50}, 1 Ti=1ki 50, 0 x 106, 1p 2(n + m), t ∈ {0, 1}

保证对于每个i [1, T],pi,j 互不相同。