北京理工大学 2020 年计算机学院小学期程序设计方法与实践 – 现场赛 Beijing Institute of Technology, 26 September 2020
Problem A. 红绿灯
Input file: Output file: Time limit: Memory limit:
standard input standard output 1 second
256 megabytes
小张在上下学的路上会经过漫长的一段公路，这条漫长公路被分割为若干段，经过每一段公路 都要花费 t 秒时间。在他生活的城市，红绿灯都是同步的，在 0 时刻到 A 时刻之间的 A 秒时 间红绿灯为绿灯，在 A 时刻到 B(0) 时刻的 B − A 秒时间红绿灯为红灯。
请注意，时刻 B 与时刻 0 是重合的，就像钟表一样 12 时和 0 时是重合的。为了方便讨论，我 们不考虑通过路口的时间。
如果小张在第一段公路的起点时，红绿灯恰好处于 0 时刻，请问走到第 k 段公路的终点时红绿 灯处于什么时刻?
Input
本题有多组用例。第一行一个整数 T(1 ≤ T ≤ 300)。接下来 T 行，每行 4 个整数 A,B,t,k(1 ≤ A < B ≤ 1000,1 ≤ t ≤ 1000,1 ≤ k ≤ 5)。含义见题面描述。
Output
对于每组数据输出一个整数，表示小张走到第 k 段公路的终点时红绿灯处于的时刻。 Example
standard input
standard output
11 3621 3622 3623 3624 3625 3631 3632 3641 3642 3661 3662
2 4 2 4 2 3 3 4 4 0 0
Note
在样例中情况均为红绿灯 0-3 为绿灯，3-6 为红灯。因此在时刻 0,1,2 是可以通过路口的，在时 刻 3,4,5 则无法通过路口。
当通过时间为 2 秒时:到达第 1 个路口终点为时刻 2，直接通过，到达第 2 个路口终点为时刻 4，等待到 0 时刻通过，到达第 3 个路口终点为时刻 2，直接通过，到达第 4 个路口终点为时刻 4，等待到 0 时刻通过，到达第 5 个路口终点为时刻 2。
当通过时间为 3 秒时:到达第 1 个路口终点为时刻 3，等待到 0 时刻通过，到达第 2 个路口终 点仍然为时刻 3。
Page 1 of 7
北京理工大学 2020 年计算机学院小学期程序设计方法与实践 - 现场赛 Beijing Institute of Technology, 26 September 2020
当通过时间为 4 秒时:到达第 1 个路口终点为时刻 4，等待到 0 时刻通过，到达第 2 个路口终 点仍然为时刻 4。
当通过时间为 6 秒时:到达第 1 个路口终点为时刻 0，直接通过，到达第 2 个路口终点仍然为 时刻 0。
Page 2 of 7
北京理工大学 2020 年计算机学院小学期程序设计方法与实践 - 现场赛 Beijing Institute of Technology, 26 September 2020
Problem B. 露营
Input file: Output file: Time limit: Memory limit:
standard input standard output 2 seconds
256 megabytes
没有什么比在假期出去露营更令人开心的事情了，至少 Tob 是这么想的。 这天，他终于前往了梦想中的 etselec 山。他需要在天黑之前搭起一顶帐篷。
Tob 在这片空地上画了一个 n ∗ n 的矩形网格，其中连接两个格点的边均是等长的。他想把支撑 帐篷的点选在网格的格点上，并且已经提前观察好了每一处的土质情况。
每个格点的状况均属于以下三种中的一种:"." 代表这一点上生长着灌木丛，"*" 代表这一点上 布满了坚硬的石头，"I" 代表这一点是空地。
Tob 的经验告诉他，要搭起结实的帐篷，需要选择四个空地点作为支撑点。而且由于他的强迫 症，这四个空地点需要刚好是一个正方形的四个顶点(正方形的边不需要与矩形网格的边平行)。 换句话说，以这四个点为支撑点最终搭起的帐篷底面必须是正方形。
趁着天色未晚，Tob 还有一定的力气来清理一块有灌木丛的格点，使之变成空地。而对于有石头 的空地，他却无能为力。
现在 Tob 想知道，他能搭起的帐篷最大面积是多少 Input
输入共包含 n+1 行:
第一行包含一个整数 n(3 ≤ n ≤ 100)，代表矩形的边长;
接下来 n 行，每行一个长度为 n 字符串，分别代表矩形格点第 1, 2, 3...n 行。
Output
输出一个数，代表能搭起帐篷的最大面积。如果不能搭起帐篷，则输出 “0”。(不包含引号) 数据保证矩形网格中至少有一个格点上生长着灌木丛，即 “.” 格点的数目一定大于 0。
Examples
standard input
standard output
3 III I.I I.*
2
4
I..I
.**.
.**.
I...
9
Note
为方便说明，我们假设左上角的点坐标为 (1, 1)，右下角坐标为 (n, n)。 Page 3 of 7
北京理工大学 2020 年计算机学院小学期程序设计方法与实践 - 现场赛 Beijing Institute of Technology, 26 September 2020
对于样例 1，如果不清理灌木丛，则无法搭起帐篷;如果清理 (2, 2) 处的灌木丛，可以得到两个 边长为 1 的正方形。如果清理 (3, 2) 处的灌木丛，则 (3, 2), (2, 3), (1, 2), (2, 1) 四个格点构成了边 长为 √2 的正方形，面积为 2。
对于样例 2，Tob 只需清理 (4, 4) 处的灌木丛，就能得到一个边长为 3 的正方形，面积为 9。
Page 4 of 7
北京理工大学 2020 年计算机学院小学期程序设计方法与实践 - 现场赛 Beijing Institute of Technology, 26 September 2020
Problem C. 西人保级路
Input file: Output file: Time limit: Memory limit:
standard input standard output 1 second
256 megabytes
2019-2020 赛季，西班牙足球甲级联赛的西班牙人队最终在 38 场比赛后仅获得了 25 分，因此遗 憾降级。现在，为了改变西班牙人队降级的结果，你决定让时光倒流，回到西班牙人还有 n 场 比赛要踢的时间节点。
已知在这剩余的 n 轮比赛中，西班牙人队需要再获得 m 分(大于等于)才不会降级。 联赛的规则是，赢一场(进球数大于对方)比赛得 3 分，输一场比赛(进球数小于对方)得 0
分，平局(进球数等于对方)得 1 分。
已知在接下来 n 轮比赛里西班牙人队一共进了 x 个球，而西班牙人的 n 个对手在和西班牙人队
的比赛中一共进了 y 个球。
求这 n 轮有多少种不同的比赛结果使得西班牙人不会降级。若 n 轮比赛中至少有一场的比分不
一样，就认为比赛结果不同。
例如，n = 2 时:比赛结果一可以是第一场比赛 2:0、第二场比赛 3:1;比赛结果二可以是第一场 比赛 2:0、第二场比赛 1:1。则结果一中西班牙人队获得了 6 分，结果二中西班牙人队获得了 4 分，且我们认为这是两种不同的比赛结果，因为第二场比赛的比分不同。
由于结果可能是很大的数字，为了便于编程，请将结果对 998244353 取模后输出。 Input
输入仅包含一行四个整数 n,m,x,y(1 ≤ n ≤ 38,0 ≤ m ≤ 114,0 ≤ x,y ≤ 50)，之间用空格分隔 开，
Output
输出一个数字，为答案对 998244353 取模的结果。 Examples
standard input
standard output
2343
20
3044
225
Page 5 of 7
北京理工大学 2020 年计算机学院小学期程序设计方法与实践 - 现场赛 Beijing Institute of Technology, 26 September 2020
Problem D. 虚假的树状数组
Input file: Output file: Time limit: Memory limit:
standard input standard output 1 second
256 megabytes
一年一度的数据结构发明大赛开始了，小张作为数据结构爱好者积极参加了这次比赛。他将自 己参与竞赛的数据结构命名为“虚假的树状数组”。有别于我们常说的树状数组，这个数据结构 没有什么实际作用，但还是比较有意思的，因此他光荣的获得了此次大赛的鼓励奖。
“虚假的树状数组”是一个 n 个结点的有向树，每个结点都有一个权值，编号为 i 的结点权值为 ai。树上的每一个结点可以生成一个数组，生成的方式为:[编号为 x 的结点的生成数组]=[ax]+[x 结点编号最小的儿子结点的生成数组]+...+[x 结点编号最大的儿子结点的生成数组]。式子中的 加号为数组的拼接，例如 [1,1,2,1]+[1,2,2,3]=[1,1,2,1,1,2,2,3]。
同时，有些结点拥有一个排序标记，拥有排序标记的结点的生成数组需要按照从小到大的顺序 排序。
现在，请你求出有向树的根节点的生成数组。
样例中“虚假的树状数组”如上图所示，圈内的数字为结点编号，圈外的红色数字为结点权值， 蓝色中括号的数为结点生成数组。
Input
第一行一个整数 n(1 ≤ n ≤ 1000)。
第二行 n 个整数，第 i 个整数 ai(1 ≤ ai ≤ 109) 表示编号为 i 的结点权值。
第三行 n 个整数，第 i 个整数 fi(0 ≤ fi ≤ 1)，0 表示编号为 i 的结点没有排序标记，1 表示编 号为 i 的结点有排序标记，保证最多有 20 个排序标记。
接下来 n − 1 行，每行两个数 x,y(1 ≤ x,y ≤ n)，表示编号为 x 的结点到编号为 y 的结点有一 条有向边。数据保证为一个有向树。
Output
用逗号隔开的 n 个整数，表示有向树的根节点的生成数组。用 [] 括起来。请注意输出行末回车。 Page 6 of 7
Example
北京理工大学 2020 年计算机学院小学期程序设计方法与实践 - 现场赛 Beijing Institute of Technology, 26 September 2020
standard input
standard output
7
12 1 10 8 8 11 2 0000100 23
24
25
31
36
57
[1,10,12,11,8,2,8]
Page 7 of 7