PTA|团体程序设计天梯赛-练习题库集_冠军魔术pta

关于爬取脚本的编写

在此前爬取其他题目集的程序上改进https://blog.csdn.net/a2272062968/article/details/117647849
原因： 之前的程序只能爬取文本信息，遇到次方，特殊符号，图片等信息导致格式混乱
史诗级修改方案： 直接爬取每个题目的网页源码，将所有题目的网页源码拼接生产一个新的html文件，自己仿照PTA写一下css样式，生成新的html文件，浏览器运行，Ctrl+P打印网页，然后选择另存为pdf（需要安装Acrobat），打开生成的pdf可以看到完美的一个所有题目集的pdf文件，再将pdf文件另存为docx格式，安装writage插件（https://www.writage.com/），使用office再将docx格式转为markdown格式即可得到markdown的题目列表集。

## 此程序用来爬取PTA至2021年团体程序设计天梯赛-题库集程序题

from selenium import webdriver
from selenium.webdriver.common.action_chains import ActionChains
from selenium.webdriver.chrome.service import Service
import requests
import time
import numpy
import cv2
import os
import json
import traceback


# 定义全局变量请求网页之前等待的时间，防止请求过快被拒绝
my_time = 3.5


def login_PTA(my_account, my_password):
    # 输入账号密码并点击登录
    account = web.find_element_by_xpath(
        '/html/body/div[1]/div[2]/div/div[2]/form/div[1]/div/div/div[1]/div/div/div/input')
    password = web.find_element_by_xpath(
        '/html/body/div[1]/div[2]/div/div[2]/form/div[1]/div/div/div[2]/div/div/div/input')
    account.send_keys(my_account)
    password.send_keys(my_password)
    web.find_element_by_xpath('/html/body/div[1]/div[2]/div/div[2]/form/div[2]/button').click()  # 找到登录按钮并点击
    web.find_element_by_xpath('/html/body/div[1]/div[2]/div/div[2]/form/div[2]/button/div/div').click()
    print("ok")
    for i in range(5):
        time.sleep(3)  # 等待验证码加载完成,时间间隔可根据网速调整，
        # print('当前url:' + web.current_url)
        # 如果当前url改变说明已经登录成功
        if web.current_url != login_url:
            break
        cracking_captcha()


def cracking_captcha():
    """破解验证码"""
    # bg背景图片
    bg_img_src = web.find_element_by_xpath(
        '/html/body/div[3]/div[2]/div/div/div[2]/div/div[1]/div/div[1]/img[1]').get_attribute('src')
    # front可拖动图片
    front_img_src = web.find_element_by_xpath(
        '/html/body/div[3]/div[2]/div/div/div[2]/div/div[1]/div/div[1]/img[2]').get_attribute('src')

    # 保存图片
    with open("bg.jpg", mode="wb") as f:
        f.write(requests.get(bg_img_src).content)
    with open("front.jpg", mode="wb") as f:
        f.write(requests.get(front_img_src).content)

    # 将图片加载至内存
    bg = cv2.imread("bg.jpg")
    front = cv2.imread("front.jpg")

    # 将背景图片转化为灰度图片，将三原色降维
    bg = cv2.cvtColor(bg, cv2.COLOR_BGR2GRAY)
    # 将可滑动图片转化为灰度图片，将三原色降维
    front = cv2.cvtColor(front, cv2.COLOR_BGR2GRAY)
    front = front[front.any(1)]
    # 用cv算法匹配精度最高的xy值
    result = cv2.matchTemplate(bg, front, cv2.TM_CCOEFF_NORMED)
    # numpy解析xy，注意xy与实际为相反，x=y,y=x
    x, y = numpy.unravel_index(numpy.argmax(result), result.shape)
    # 找到可拖动区域
    div = web.find_element_by_xpath('/html/body/div[3]/div[2]/div/div/div[2]/div/div[2]/div[2]')
    # 拖动滑块，以实际相反的y值代替x
    ActionChains(web).drag_and_drop_by_offset(div, xoffset=y // 0.946, yoffset=0).perform()
    # 至此成功破解验证码，由于算法问题，准确率不能达到100%，所以加了循环判断


def get_question_type_url(headers_collection_url):
    time.sleep(my_time)
    """获取当前章节题目类型的url"""
    web.get(headers_collection_url)
    single_choice_url = ""
    judgment_url = ""
    fill_in_the_blanks_url = ""
    program_fill_in_the_blanks_url = ""
    function_url = ""
    programming_url = ""

    questions_type_list_a = web.find_element_by_css_selector(
        "[class='pc-h container_3U5RB pc-gap-default']").find_elements_by_css_selector("a")
    for t in questions_type_list_a:
        questions_type_name = t.find_element_by_css_selector("[class='pc-text-raw']").text
        this_url = t.get_attribute('href')
        if questions_type_name == '单选题':
            single_choice_url = this_url
        elif questions_type_name == '判断题':
            judgment_url = this_url
        elif questions_type_name == '填空题':
            fill_in_the_blanks_url = this_url
        elif questions_type_name == '程序填空题':
            program_fill_in_the_blanks_url = this_url
        elif questions_type_name == '函数题':
            function_url = this_url
        elif questions_type_name == '编程题':
            programming_url = this_url

    # print(single_choice_url)
    # print(judgment_url)
    # print(fill_in_the_blanks)
    # print(program_fill_in_the_blanks)
    # print(function)
    # print(programming)

    question_type_dict = {
        "single_choice_url": single_choice_url,
        "judgment_url": judgment_url,
        "fill_in_the_blanks_url": fill_in_the_blanks_url,
        "program_fill_in_the_blanks_url": program_fill_in_the_blanks_url,
        "function_url": function_url,
        "programming_url": programming_url
    }

    return question_type_dict

def write_question_file(url_list, programming_name):
    """将题目分类并写入json文件"""
    for url in url_list:

        this_question_type_dict = get_question_type_url(url)
        questions_dict = {}

        def write_file(this_name):
            if not os.path.exists(os.getcwd() + "\\" + this_name):
                new_file = open(this_name, 'w')
                new_file.write("{}")
                new_file.close()
            f = open(this_name, 'r', encoding="utf-8")
            content = f.read()
            file_dict = json.loads(content)
            f.close()

            file_dict.update(questions_dict)

            judgment_file = open(this_name, mode='w', encoding="utf-8")
            judgment_file.write(json.dumps(file_dict, ensure_ascii=False))
            judgment_file.close()
            print("-----当前题记长度-----------------------------------------------------" + str(len(questions_dict)))
            print("-----写入文件--总长度-------------------------------------------------" + str(len(file_dict)))

        # # 编程题
        if this_question_type_dict['programming_url'] != "":
            questions_dict = get_function_or_programming(
                function_or_programming_url=this_question_type_dict['programming_url'])
            write_file(this_name=programming_name)




def get_function_or_programming(function_or_programming_url):
    """获取函数/编程题并返回题集字典"""
    time.sleep(my_time)
    web.get(function_or_programming_url)
    # 翻页没写，手动翻页吧~~
    time.sleep(10)
    questions_dict = {}

    # 获取所以题目行
    trp_problems = web.find_elements_by_xpath(
        '/html/body/div/div[2]/div[1]/div/div[2]/div[2]/div/div[1]/table//tbody/tr')
    # 存放所有题目的链接
    problems_href = []
    for tr in trp_problems:
        problems_href.append(tr.find_element_by_xpath('td[3]/a').get_attribute('href'))

    success_num = 0
    fail_num = 0
    for problem in problems_href:
        # 这里循环3次的目的是防止请求过快被限制，如果正常执行则退出，否则继续请求(3次还get不到跳过)
        for i in range(3):
            try:
                time.sleep(my_time)  # 根据网速设置时间间隔，访问太快也会被提示
                web.get(problem)
                # 获取题目和答案
                problem_title = web.find_element_by_css_selector(
                    "[class='text-center text-light text-base font-bold my-4']").text
                answer = web.find_element_by_css_selector(
                    "[class='codeEditor_2kCM6 grow shrink']").find_element_by_css_selector('textarea').get_attribute(
                    'value')
                problem_content = web.find_element_by_css_selector("[class='rendered-markdown']").get_attribute('outerHTML')
                author = web.find_element_by_css_selector("[class='problemInfo_24edr']").text

                questions_dict[problem_title] = [problem_content, answer]

                print("<h2>" + problem_title + "</h2>")
                print('<i style="font-size:12px">' + author + '</i>')
                print(problem_content)
                print("<hr>")

                # print(answer)

                success_num += 1
                break
            except:
                continue
            fail_num += 1  # 如果能执行到这说明当前题目获取失败

    print("函数/编程题--题集: " + function_or_programming_url + "获取题目数量--成功: " + str(success_num) + " 失败: " + str(fail_num))
    return questions_dict

if __name__ == '__main__':
    # 创建 WebDriver 对象，指明使用chrome浏览器驱动
    web = webdriver.Chrome(service=Service(r'C:\Users\Cat\AppData\Local\Google\Chrome\Application\chromedriver.exe'))
    web.implicitly_wait(5)
    login_url = 'https://pintia.cn/auth/login'
    # 调用WebDriver 对象的get方法 可以让浏览器打开 指定网址
    web.get('https://pintia.cn/auth/login')

    login_PTA('账号', '密码')

    java_url_list_lxf = [
        '存放题目集列表链接'
    ]


    write_question_file(java_url_list_lxf, "dataSql\\programming.json")
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221

L1-001 Hello World! (5 分)

作者 C课程组 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

本题要求编写程序，输出一个短句“Hello World!”。

输入格式:

本题目没有输入。

输出格式:

在一行中输出短句“Hello World!”。

L1-002 打印沙漏 (15 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

本题要求你写个程序把给定的符号打印成沙漏的形状。例如给定17个“*”，要求按下列格式打印

*****

***

*

***

*****

所谓“沙漏形状”，是指每行输出奇数个符号；各行符号中心对齐；相邻两行符号数差2；符号数先从大到小顺序递减到1，再从小到大顺序递增；首尾符号数相等。

给定任意N个符号，不一定能正好组成一个沙漏。要求打印出的沙漏能用掉尽可能多的符号。

输入格式:

输入在一行给出1个正整数N（≤1000）和一个符号，中间以空格分隔。

输出格式:

首先打印出由给定符号组成的最大的沙漏形状，最后在一行中输出剩下没用掉的符号数。

输入样例:

19 *

输出样例:

*****

***

*

***

***** 2

L1-003 个位数统计 (15 分)

作者 CHEN, Yue 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

给定一个 k 位整数 N = dk−110k−1 + ⋯ + d1101 + d0 (0 ≤ di ≤ 9, i
= 0, ⋯ , k − 1, dk−1 >
0)，请编写程序统计每种不同的个位数字出现的次数。例如：给定 N = 100311，则有 2
个 0，3 个 1，和 1 个 3。

输入格式：

每个输入包含 1 个测试用例，即一个不超过 1000 位的正整数 N 。

输出格式：

对 N 中每一种不同的个位数字，以 D:M 的格式在一行中输出该位数字 D 及其在 N
中出现的次数 M。要求按 D 的升序输出。

输入样例：

100311

输出样例：

0:2

1:3

3:1

L1-004 计算摄氏温度 (5 分)

作者 陈建海 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

给定一个华氏温度F ，本题要求编写程序，计算对应的摄氏温度C。计算公式：C = 5
× (F − 32)/9。题目保证输入与输出均在整型范围内。

输入格式:

输入在一行中给出一个华氏温度。

输出格式:

在一行中按照格式“Celsius = C”输出对应的摄氏温度C的整数值。

输入样例:

150

输出样例:

Celsius = 65

L1-005 考试座位号 (15 分)

作者 CHEN, Yue 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

每个 PAT
考生在参加考试时都会被分配两个座位号，一个是试机座位，一个是考试座位。正常情况下，考生在入场时先得到试机座位号码，入座进入试机状态后，系统会显示该考生的考试座位号码，考试时考生需要换到考试座位就座。但有些考生迟到了，试机已经结束，他们只能拿着领到的试机座位号码求助于你，从后台查出他们的考试座位号码。

输入格式：

输入第一行给出一个正整数 N （≤ 1000），随后 N
行，每行给出一个考生的信息：准考证号 试机座位号 考试座位号。其中准考证号由 16
位数字组成， 座位从 1 到 N
编号。输入保证每个人的准考证号都不同，并且任何时候都不会把两个人分配到同一个座位上。

考生信息之后，给出一个正整数 M （≤ N ），随后一行中给出 M
个待查询的试机座位号码，以空格分隔。

输出格式：

对应每个需要查询的试机座位号码，在一行中输出对应考生的准考证号和考试座位号码，中间用
1 个空格分隔。

输入样例：

4

3310120150912233 2 4

3310120150912119 4 1

3310120150912126 1 3

3310120150912002 3 2

2

3 4

输出样例：

3310120150912002 2

3310120150912119 1

L1-006 连续因子 (20 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

一个正整数 N 的因子中可能存在若干连续的数字。例如 630 可以分解为 3×5×6×7，其中
5、6、7 就是 3 个连续的数字。给定任一正整数 N
，要求编写程序求出最长连续因子的个数，并输出最小的连续因子序列。

输入格式：

输入在一行中给出一个正整数 N （1 < N < 231 ）。

输出格式：

首先在第 1 行输出最长连续因子的个数；然后在第 2 行中按 因子1*因子2*……*因子k
的格式输出最小的连续因子序列，其中因子按递增顺序输出，1 不算在内。

输入样例：

630

输出样例：

3

5*6*7

** 鸣谢用户** 漏穿雪 补充数据！

L1-007 念数字 (10 分)

作者 翁恺 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

输入一个整数，输出每个数字对应的拼音。当整数为负数时，先输出fu字。十个数字对应的拼音如下：

0: ling 1: yi 2: er 3: san 4: si 5: wu 6: liu 7: qi 8: ba 9: jiu

输入格式：

输入在一行中给出一个整数，如：1234。

** 提示：整**数包括负数、零和正数。

输出格式：

在一行中输出这个整数对应的拼音，每个数字的拼音之间用空格分开，行末没有最后的空格。如
yi er san si。

输入样例：

-600

输出样例：

fu liu ling ling

L1-008 求整数段和 (10 分)

作者 杨起帆 单位 浙大城市学院 代码长度限制 16 KB 时间限制 400 ms 内存限制 64
MB

给定两个整数A和B，输出从A到B的所有整数以及这些数的和。

输入格式：

输入在一行中给出2个整数A和B，其中−100 ≤ A ≤ B ≤ 100，其间以空格分隔。

输出格式：

首先顺序输出从A到B的所有整数，每5个数字占一行，每个数字占5个字符宽度，向右对齐。最后在一行中按Sum
= X的格式输出全部数字的和X。

输入样例：

-3 8

输出样例：

-3 -2 -1 0 1

2 3 4 5 6

7 8

Sum = 30

L1-009 N个数求和 (20 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

本题的要求很简单，就是求N个数字的和。麻烦的是，这些数字是以有理数分子/分母的形式给出的，你输出的和也必须是有理数的形式。

输入格式：

输入第一行给出一个正整数N（≤100）。随后一行按格式a1/b1 a2/b2
给出N个有理数。题目保证所有分子和分母都在长整型范围内。另外，负数的符

号一定出现在分子前面。

输出格式：

输出上述数字和的最简形式 —— 即将结果写成整数部分
分数部分，其中分数部分写成分子/分母，要求分子小于分母，且它们没有公因子。如果结果的整数部分为0，则只输出分数部分。

输入样例1：

5

2/5 4/15 1/30 -2/60 8/3

输出样例1：

3 1/3

输入样例2：

2

4/3 2/3

输出样例2：

2

输入样例3：

3

1/3 -1/6 1/8

输出样例3：

7/24

L1-010 比较大小 (10 分)

作者 杨起帆 单位 浙大城市学院 代码长度限制 16 KB 时间限制 400 ms 内存限制 64
MB

本题要求将输入的任意3个整数从小到大输出。

输入格式:

输入在一行中给出3个整数，其间以空格分隔。

输出格式:

在一行中将3个整数从小到大输出，其间以“->”相连。

输入样例:

4 2 8

输出样例:

2->4->8

L1-011 A-B (20 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 150 ms 内存限制 64 MB

本题要求你计算A − B。不过麻烦的是，A和B都是字符串 ——
即从字符串A中把字符串B所包含的字符全删掉，剩下的字符组成的就是字符串

A − B。

输入格式：

输入在2行中先后给出字符串A和B。两字符串的长度都不超过104
，并且保证每个字符串都是由可见的ASCII码和空白字符组成，最后以换行符结束。

输出格式：

在一行中打印出A − B的结果字符串。

输入样例：

I love GPLT! It’s a fun game! aeiou

输出样例：

I lv GPLT! It’s fn gm!

L1-012 计算指数 (5 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

真的没骗你，这道才是简单题 —— 对任意给定的不超过10的正整数n，要求你输出2n
。不难吧？

输入格式：

输入在一行中给出一个不超过10的正整数n。

输出格式：

在一行中按照格式 2^n = 计算结果 输出2n 的值。

输入样例：

5

输出样例：

2^5 = 32

L1-013 计算阶乘和 (10 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

对于给定的正整数N ，需要你计算 S = 1! + 2! + 3! + … + N !。

输入格式：

输入在一行中给出一个不超过10的正整数N 。

输出格式：

在一行中输出S的值。

输入样例：

3

输出样例：

9

L1-014 简单题 (5 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

这次真的没骗你 —— 这道超级简单的题目没有任何输入。

你只需要在一行中输出事实：This is a simple problem. 就可以了。

L1-015 跟奥巴马一起画方块 (15 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

美国总统奥巴马不仅呼吁所有人都学习编程，甚至以身作则编写代码，成为美国历史上首位编写计算机代码的总统。2014年底，为庆祝“计算机科学教育周”正式启动，奥巴马编写了很简单的计算机代码：在屏幕上画一个正方形。现在你也跟他一起画吧！

输入格式：

输入在一行中给出正方形边长N （3 ≤ N ≤
21）和组成正方形边的某种字符C，间隔一个空格。

输出格式：

输出由给定字符C画出的正方形。但是注意到行间距比列间距大，所以为了让结果看上去更像正方形，我们输出的行数实际上是列数的50%（四舍五入取整）。

输入样例：

10 a

输出样例：

aaaaaaaaaa aaaaaaaaaa aaaaaaaaaa aaaaaaaaaa aaaaaaaaaa

L1-016 查验身份证 (15 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

一个合法的身份证号码由17位地区、日期编号和顺序编号加1位校验码组成。校验码的计算规则如下：

首先对前17位数字加权求和，权重分配为：{7，9，10，5，8，4，2，1，6，3，7，9，10，5，8，4，2}；然后将计算的和对11取模得到值Z；最后按照以下关系对应Z值与校验码M的值：

Z：0 1 2 3 4 5 6 7 8 9 10 M：1 0 X 9 8 7 6 5 4 3 2

现在给定一些身份证号码，请你验证校验码的有效性，并输出有问题的号码。

输入格式：

输入第一行给出正整数N （≤ 100）是输入的身份证号码的个数。随后N
行，每行给出1个18位身份证号码。

输出格式：

按照输入的顺序每行输出1个有问题的身份证号码。这里并不检验前17位是否合理，只检查前17位是否全为数字且最后1位校验码计算准确。如果所有号码都正常，则输出All
passed。

输入样例1：

4

320124198808240056

12010X198901011234

110108196711301866

37070419881216001X

输出样例1：

12010X198901011234

110108196711301866

37070419881216001X

输入样例2：

2

320124198808240056

110108196711301862

输出样例2：

All passed

** 鸣谢阜阳**师范学院范建中老师补充数据

鸣谢浙江工业大学之江学院石洗凡老师纠正数据

L1-017 到底有多二 (15 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

一个整数“犯二的程度”定义为该数字中包含2的个数与其位数的比值。如果这个数是负数，则程度增加0.5倍；如果还是个偶数，则再增加1倍。例如数字-13142223336是个11位数，其中有3个2，并且是负数，也是偶数，则它的犯二程度计算为：3/11
× 1.5 × 2 × 100%，约为81.82%。本题就请你计算一个给定整数到底有多二。

输入格式：

输入第一行给出一个不超过50位的整数N。

输出格式：

在一行中输出N犯二的程度，保留小数点后两位。

输入样例：

-13142223336

输出样例：

81.82%

** 鸣谢安阳**师范学院段晓云老师和软件工程五班李富龙同学补充测试数据！

L1-018 大笨钟 (10 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

微博上有个自称“大笨钟V”的家伙，每天敲钟催促码农们爱惜身体早点睡觉。不过由于笨钟自己作息也不是很规律，所以敲钟并不定时。一般敲钟的点数是根据敲钟时间而定的，如果正好在某个整点敲，那么“当”数就等于那个整点数；如果过了整点，就敲下一个整点数。另外，虽然一天有24小时，钟却是只在后半天敲1~12下。例如在23:00敲钟，就是“当当当当当当当当当当当”，而到了23:01就会是“当当当当当当当当当当当当”。在午夜00:00到中午12:00期间（端点时间包括在内），笨钟是不敲的。

下面就请你写个程序，根据当前时间替大笨钟敲钟。

输入格式：

输入第一行按照hh:mm的格式给出当前时间。其中hh是小时，在00到23之间；mm是分钟，在00到59之间。

输出格式：

根据当前时间替大笨钟敲钟，即在一行中输出相应数量个Dang。如果不是敲钟期，则输出：

Only hh:mm. Too early to Dang.

其中hh:mm是输入的时间。

输入样例1：

19:05

输出样例1：

DangDangDangDangDangDangDangDang

输入样例2：

07:05

输出样例2：

Only 07:05. Too early to Dang.

L1-019 谁先倒 (15 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

划拳是古老中国酒文化的一个有趣的组成部分。酒桌上两人划拳的方法为：每人口中喊出一个数字，同时用手比划出一个数字。如果谁比划出的数字正好等于两人喊出的数字之和，谁就输了，输家罚一杯酒。两人同赢或两人同输则继续下一轮，直到唯一的赢家出现。

下面给出甲、乙两人的酒量（最多能喝多少杯不倒）和划拳记录，请你判断两个人谁先倒。

输入格式：

输入第一行先后给出甲、乙两人的酒量（不超过100的非负整数），以空格分隔。下一行给出一个正整数N（≤
100），随后N行，每行给出一轮划拳的记录，格式为：

甲喊 甲划 乙喊 乙划

其中喊是喊出的数字，划是划出的数字，均为不超过100的正整数（两只手一起划）。

输出格式：

在第一行中输出先倒下的那个人：A代表甲，B代表乙。第二行中输出没倒的那个人喝了多少杯。题目保证有一个人倒下。注意程序处理到有人倒下就终止，后面的数据不必处理。

输入样例：

1 1

6

8 10 9 12

5 10 5 10

3 8 5 12

12 18 1 13

4 16 12 15

15 1 1 16

输出样例：

A 1

L1-020 帅到没朋友 (20 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 300 ms 内存限制 64 MB

当芸芸众生忙着在朋友圈中发照片的时候，总有一些人因为太帅而没有朋友。本题就要求你找出那些帅到没有朋友的人。

输入格式：

输入第一行给出一个正整数N（≤
100），是已知朋友圈的个数；随后N行，每行首先给出一个正整数K（≤
1000），为朋友圈中的人数，然后列出一个朋友圈内的所有人——为方便起见，每人对应一个ID号，为5位数字（从00000到99999），ID间以空格分隔；之后给出一个正整数M（≤
10000）， 为待查询的人数；随后一行中列出M个待查询的ID，以空格分隔。

注意：没有朋友的人可以是根本没安装“朋友圈”，也可以是只有自己一个人在朋友圈的人。虽然有个别自恋狂会自己把自己反复加进朋友圈，但题目保证所有K超过1的朋友圈里都至少有2个不同的人。

输出格式：

按输入的顺序输出那些帅到没朋友的人。ID间用1个空格分隔，行的首尾不得有多余空格。如果没有人太帅，则输出No
one is handsome。注意：同一个人可以被查询多次，但只输出一次。

输入样例1：

3

3 11111 22222 55555

2 33333 44444

4 55555 66666 99999 77777

8

55555 44444 10000 88888 22222 11111 23333 88888

输出样例1：

10000 88888 23333

输入样例2：

3

3 11111 22222 55555

2 33333 44444

4 55555 66666 99999 77777

4

55555 44444 22222 11111

输出样例2：

No one is handsome

L1-021 重要的话说三遍 (5 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

这道超级简单的题目没有任何输入。

你只需要把这句很重要的话 —— “I’m gonna
WIN!”——连续输出三遍就可以了。注意每遍占一行，除了每行的回车不能有任何多余字符。

L1-022 奇偶分家 (10 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

给定N个正整数，请统计奇数和偶数各有多少个？

输入格式：

输入第一行给出一个正整N（≤ 1000）；第2行给出N个非负整数，以空格分隔。

输出格式：

在一行中先后输出奇数的个数、偶数的个数。中间以1个空格分隔。

输入样例：

9

88 74 101 26 15 0 34 22 77

输出样例：

3 6

L1-023 输出GPLT (20 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 200 ms 内存限制 64 MB

给定一个长度不超过10000的、仅由英文字母构成的字符串。请将字符重新调整顺序，按GPLTGPLT
这样的顺序输出，并忽略其它字符。当然，四种字

符（不区分大小写）的个数不一定是一样多的，若某种字符已经输出完，则余下的字符仍按GPLT的顺序打印，直到所有字符都被输出。

输入格式：

输入在一行中给出一个长度不超过10000的、仅由英文字母构成的非空字符串。

输出格式：

在一行中按题目要求输出排序后的字符串。题目保证输出非空。

输入样例：

pcTclnGloRgLrtLhgljkLhGFauPewSKgt

输出样例：

GPLTGPLTGLTGLGLL

L1-024 后天 (5 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

如果今天是星期三，后天就是星期五；如果今天是星期六，后天就是星期一。我们用数字1到7对应星期一到星期日。给定某一天，请你输出那天的“后天”是星期几。

输入格式：

输入第一行给出一个正整数D（1 ≤ D ≤ 7），代表星期里的某一天。

输出格式：

在一行中输出D天的后天是星期几。

输入样例：

3

输出样例：

5

L1-025 正整数A+B (15 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

题的目标很简单，就是求两个正整数A和B的和，其中A和B都在区间[1,1000]。稍微有点麻烦的是，输入并不保证是两个正整数。

输入格式：

输入在一行给出A和B，其间以空格分开。问题是A和B不一定是满足要求的正整数，有时候可能是超出范围的数字、负数、带小数点的实数、甚至是一堆乱码。

注意：我们把输入中出现的第1个空格认为是A和B的分隔。题目保证至少存在一个空格，并且B不是一个空字符串。

输出格式：

如果输入的确是两个正整数，则按格式A + B =
和输出。如果某个输入不合要求，则在相应位置输出?，显然此时和也是?。

输入样例1：

123 456

输出样例1：

123 + 456 = 579

输入样例2：

22. 18

输出样例2：

? + 18 = ?

输入样例3：

-100 blabla bla…33

输出样例3：

? + ? = ?

L1-026 I Love GPLT (5 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

这道超级简单的题目没有任何输入。

你只需要把这句很重要的话 —— I Love GPLT ——竖着输出就可以了。

所谓“竖着输出”，是指每个字符占一行（包括空格），即每行只能有1个字符和回车。

L1-027 出租 (20 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

下面是新浪微博上曾经很火的一张图：

一时间网上一片求救声，急问这个怎么破。其实这段代码很简单，index数组就是arr数组的下标，index[0]=2
对应 arr[2]=1，index[1]=0 对应 arr[0]=8，

index[2]=3 对应 arr[3]=0，以此类推…… 很容易得到电话号码是18013820100。

本题要求你编写一个程序，为任何一个电话号码生成这段代码 ——
事实上，只要生成最前面两行就可以了，后面内容是不变的。

输入格式：

输入在一行中给出一个由11位数字组成的手机号码。

输出格式：

为输入的号码生成代码的前两行，其中arr中的数字必须按递减顺序给出。

输入样例：

18013820100

输出样例：

int[] arr = new int[]{8,3,2,1,0};

int[] index = new int[]{3,0,4,3,1,0,2,4,3,4,4};

L1-028 判断素数 (10 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

本题的目标很简单，就是判断一个给定的正整数是否素数。

输入格式：

输入在第一行给出一个正整数N（≤ 10），随后N行，每行给出一个小于231
的需要判断的正整数。

输出格式：

对每个需要判断的正整数，如果它是素数，则在一行中输出Yes，否则输出No。

输入样例：

2

11

111

输出样例：

Yes No

L1-029 是不是太胖了 (5 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

据说一个人的标准体重应该是其身高（单位：厘米）减去100、再乘以0.9所得到的公斤数。已知市斤的数值是公斤数值的两倍。现给定某人身高，请你计算其标准体重应该是多少？（顺便也悄悄给自己算一下吧……）

输入格式：

输入第一行给出一个正整数H（100 < H ≤ 300），为某人身高。

输出格式：

在一行中输出对应的标准体重，单位为市斤，保留小数点后1位。

输入样例：

169

输出样例：

124.2

L1-030 一帮一 (15 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

“一帮一学习小组”是中小学中常见的学习组织方式，老师把学习成绩靠前的学生跟学习成绩靠后的学生排在一组。本题就请你编写程序帮助老师自动完成这个分配工作，即在得到全班学生的排名后，在当前尚未分组的学生中，将名次最靠前的学生与名次最靠后的异性学生分为一组。

输入格式：

输入第一行给出正偶数N（≤50），即全班学生的人数。此后N行，按照名次从高到低的顺序给出每个学生的性别（0代表女生，1代表男生）和姓名（不超过8个英文字母的非空字符串），其间以1个空格分隔。这里保证本班男女比例是1:1，并且没有并列名次。

输出格式：

每行输出一组两个学生的姓名，其间以1个空格分隔。名次高的学生在前，名次低的学生在后。小组的输出顺序按照前面学生的名次从高到低排列。

输入样例：

8

0 Amy 1 Tom 1 Bill

0 Cindy 0 Maya 1 John 1 Jack 0 Linda

输出样例：

Amy Jack Tom Linda Bill Maya Cindy John

L1-031 到底是不是太胖了 (10 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

据说一个人的标准体重应该是其身高（单位：厘米）减去100、再乘以0.9所得到的公斤数。真实体重与标准体重误差在10%以内都是完美身材（即
| 真实体重 − 标准体重 | <
标准体重×10%）。已知市斤是公斤的两倍。现给定一群人的身高和实际体重，请你告诉他们是否太胖或太瘦了。

输入格式：

输入第一行给出一个正整数N（≤
20）。随后N行，每行给出两个整数，分别是一个人的身高H（120 < H <
200；单位：厘米）和真实体重W（50 <

W ≤ 300；单位：市斤），其间以空格分隔。

输出格式：

为每个人输出一行结论：如果是完美身材，输出You are wan mei!；如果太胖了，输出You
are tai pang le!；否则输出You are tai shou le!。

输入样例：

3

169 136

150 81

178 155

输出样例：

You are wan mei!

You are tai shou le! You are tai pang le!

L1-032 Left-pad (20 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 250 ms 内存限制 64 MB

根据新浪微博上的消息，有一位开发者不满NPM（Node Package
Manager）的做法，收回了自己的开源代码，其中包括一个叫left-pad的模块，就是这个模块把javascript里面的React/Babel干瘫痪了。这是个什么样的模块？就是在字符串前填充一些东西到一定的长度。例如用*去填充字符串GPLT，使之长度为10，调用left-pad的结果就应该是******GPLT。Node社区曾经对left-pad紧急发布了一个替代，被严重吐槽。下面就请你来实现一下这个模块。

输入格式：

输入在第一行给出一个正整数N（≤ 104
）和一个字符，分别是填充结果字符串的长度和用于填充的字符，中间以1个空格分开。第二行给出原始的非空字符串，以回车结束。

输出格式：

在一行中输出结果字符串。

输入样例1：

15 _

I love GPLT

输出样例1：

____I love GPLT

输入样例2：

4 *

this is a sample for cut

输出样例2：

cut

L1-033 出生年 (15 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

以上是新浪微博中一奇葩贴：“我出生于1988年，直到25岁才遇到4个数字都不相同的年份。”也就是说，直到2013年才达到“4个数字都不相同”的要求。本题请你根据要求，自动填充“我出生于y年，直到x岁才遇到n个数字都不相同的年份”这句话。

输入格式：

输入在一行中给出出生年份y和目标年份中不同数字的个数n，其中y在[1,
3000]之间，n可以是2、或3、或4。注意不足4位的年份要在前面补零，例如公元1年被认为是0001年，有2个不同的数字0和1。

输出格式：

根据输入，输出x和能达到要求的年份。数字间以1个空格分隔，行首尾不得有多余空格。年份要按4位输出。注意：所谓“n个数字都不相同”是指不同的数字正好是n个。如“2013”被视为满足“4位数字都不同”的条件，但不被视为满足2位或3位数字不同的条件。

输入样例1：

1988 4

输出样例1：

25 2013

输入样例2：

1 2

输出样例2：

0 0001

L1-034 点赞 (20 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 200 ms 内存限制 64 MB

微博上有个“点赞”功能，你可以为你喜欢的博文点个赞表示支持。每篇博文都有一些刻画其特性的标签，而你点赞的博文的类型，也间接刻画了你的特性。本题就要求你写个程序，通过统计一个人点赞的纪录，分析这个人的特性。

输入格式：

输入在第一行给出一个正整数N （≤ 1000），是该用户点赞的博文数量。随后N
行，每行给出一篇被其点赞的博文的特性描述，格式为“K F1 ⋯ FK ”，其中1 ≤ K ≤
10，Fi（i = 1, ⋯ ,
K）是特性标签的编号，我们将所有特性标签从1到1000编号。数字间以空格分隔。

输出格式：

统计所有被点赞的博文中最常出现的那个特性标签，在一行中输出它的编号和出现次数，数字间隔1个空格。如果有并列，则输出编号最大的那个。

输入样例：

4

3 889 233 2

5 100 3 233 2 73

4 3 73 889 2

2 233 123

输出样例：

233 3

L1-035 情人节 (15 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

以上是朋友圈中一奇葩贴：“2月14情人节了，我决定造福大家。第2个赞和第14个赞的，我介绍你俩认识…
咱三吃饭…你俩请…”。现给出此贴

下点赞的朋友名单，请你找出那两位要请客的倒霉蛋。

输入格式：

输入按照点赞的先后顺序给出不知道多少个点赞的人名，每个人名占一行，为不超过10个英文字母的非空单词，以回车结束。一个英文句点.标志输入的结束，这个符号不算在点赞名单里。

输出格式：

根据点赞情况在一行中输出结论：若存在第2个人A和第14个人B，则输出“A and B are
inviting you to dinner ”；若只有A没有B，则输出“A is

the only one for you…”；若连A都没有，则输出“Momo… No one is for you ”。

输入样例1：

GaoXZh Magi Einst Quark LaoLao FatMouse ZhaShen fantacy latesum SenSen QuanQuan
whatever whenever Potaty hahaha

.

输出样例1：

Magi and Potaty are inviting you to dinner…

输入样例2：

LaoLao FatMouse whoever

.

输出样例2：

FatMouse is the only one for you…

输入样例3：

LaoLao

.

输出样例3：

Momo… No one is for you …

L1-036 A乘以B (5 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

看我没骗你吧 ——
这是一道你可以在10秒内完成的题：给定两个绝对值不超过100的整数A和B，输出A乘以B的值。

输入格式：

输入在第一行给出两个整数A和B（−100 ≤ A, B ≤ 100），数字间以空格分隔。

输出格式：

在一行中输出A乘以B的值。

输入样例：

-8 13

输出样例：

-104

L1-037 A除以B (10 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

真的是简单题哈 —— 给定两个绝对值不超过100的整数A和B，要求你按照“A/B
=商”的格式输出结果。

输入格式：

输入在第一行给出两个整数A和B（−100 ≤ A, B ≤ 100），数字间以空格分隔。

输出格式：

在一行中输出结果：如果分母是正数，则输出“A/B
=商”；如果分母是负数，则要用括号把分母括起来输出；如果分母为零，则输出的商应为

Error。输出的商应保留小数点后2位。

输入样例1：

-1 2

输出样例1：

-1/2=-0.50

输入样例2：

1 -3

输出样例2：

1/(-3)=-0.33

输入样例3：

5 0

输出样例3：

5/0=Error

L1-038 新世界 (5 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

这道超级简单的题目没有任何输入。

你只需要在第一行中输出程序员钦定名言“Hello
World”，并且在第二行中输出更新版的“Hello New World”就可以了。

L1-039 古风排版 (20 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

中国的古人写文字，是从右向左竖向排版的。本题就请你编写程序，把一段文字按古风排版。

输入格式：

输入在第一行给出一个正整数N （<
100），是每一列的字符数。第二行给出一个长度不超过1000的非空字符串，以回车结束。

输出格式：

按古风格式排版给定的字符串，每列N 个字符（除了最后一列可能不足N 个）。

输入样例：

4

This is a test case

输出样例：

asa T st ih e tsi

ce s

L1-040 最佳情侣身高差 (10 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

专家通过多组情侣研究数据发现，最佳的情侣身高差遵循着一个公式：（女方的身高）×1.09
=（男方的身高）。如果符合，你俩的身高差不管是牵手、拥抱、接吻，都是最和谐的差度。

下面就请你写个程序，为任意一位用户计算他/她的情侣的最佳身高。

输入格式：

输入第一行给出正整数N （≤ 10），为前来查询的用户数。随后N 行，每行按照“性别
身高”的格式给出前来查询的用户的性别和身高，其中“性别”为“F”表示女性、“M”表示男性；“身高”为区间
[1.0, 3.0] 之间的实数。

输出格式：

对每一个查询，在一行中为该用户计算出其情侣的最佳身高，保留小数点后2位。

输入样例：

2

M 1.75 F 1.8

输出样例：

1.61

1.96

L1-041 寻找250 (10 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

对方不想和你说话，并向你扔了一串数……
而你必须从这一串数字中找到“250”这个高大上的感人数字。

输入格式：

输入在一行中给出不知道多少个绝对值不超过1000的整数，其中保证至少存在一个“250”。

输出格式：

在一行中输出第一次出现的“250”是对方扔过来的第几个数字（计数从1开始）。题目保证输出的数字在整型范围内。

输入样例：

888 666 123 -233 250 13 250 -222

输出样例：

5

L1-042 日期格式化 (5 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

世界上不同国家有不同的写日期的习惯。比如美国人习惯写成“月-日-年”，而中国人习惯写成“年-月-日”。下面请你写个程序，自动把读入的美国格式的日期改写成中国习惯的日期。

输入格式：

输入在一行中按照“mm-dd-yyyy”的格式给出月、日、年。题目保证给出的日期是1900年元旦至今合法的日期。

输出格式：

在一行中按照“yyyy-mm-dd”的格式给出年、月、日。

输入样例：

03-15-2017

输出样例：

2017-03-15

L1-043 阅览室 (20 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

天梯图书阅览室请你编写一个简单的图书借阅统计程序。当读者借书时，管理员输入书号并按下S键，程序开始计时；当读者还书时，管理员输入书号并按下E键，程序结束计时。书号为不超过1000的正整数。当管理员将0作为书号输入时，表示一天工作结束，你的程序应输出当天的读者借书次数和平均阅读时间。

注意：由于线路偶尔会有故障，可能出现不完整的纪录，即只有S没有E，或者只有E没有S的纪录，系统应能自动忽略这种无效纪录。另外，题目保证书号是书的唯一标识，同一本书在任何时间区间内只可能被一位读者借阅。

输入格式：

输入在第一行给出一个正整数N （≤ 10），随后给出N
天的纪录。每天的纪录由若干次借阅操作组成，每次操作占一行，格式为：

书号（[1, 1000]内的整数） 键值（S或E）
发生时间（hh:mm，其中hh是[0,23]内的整数，mm是[0, 59]内整数）
每一天的纪录保证按时间递增的顺序给出。

输出格式：

对每天的纪录，在一行中输出当天的读者借书次数和平均阅读时间（以分钟为单位的精确到个位的整数时间）。

输入样例：

3

1 S 08:10

2 S 08:35

1 E 10:00

2 E 13:16

0 S 17:00

0 S 17:00

3 E 08:10

1 S 08:20

2 S 09:00

1 E 09:20

0 E 17:00

输出样例：

2 196

0 0

1 60

L1-044 稳赢 (15 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

大家应该都会玩“锤子剪刀布”的游戏：两人同时给出手势，胜负规则如图所示：

现要求你编写一个稳赢不输的程序，根据对方的出招，给出对应的赢招。但是！为了不让对方输得太惨，你需要每隔K次就让一个平局。

输入格式：

输入首先在第一行给出正整数K（≤
10），即平局间隔的次数。随后每行给出对方的一次出招：ChuiZi代表“锤子”、JianDao代表“剪刀”、Bu代表“布”。End代表输入结束，这一行不要作为出招处理。

输出格式：

对每一个输入的出招，按要求输出稳赢或平局的招式。每招占一行。

输入样例：

2

ChuiZi JianDao Bu JianDao Bu ChuiZi ChuiZi End

输出样例：

Bu ChuiZi Bu ChuiZi JianDao ChuiZi Bu

L1-045 宇宙无敌大招呼 (5 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

据说所有程序员学习的第一个程序都是在屏幕上输出一句“Hello
World”，跟这个世界打个招呼。作为天梯赛中的程序员，你写的程序得高级一点，
要能跟任意指定的星球打招呼。

输入格式：

输入在第一行给出一个星球的名字S，是一个由不超过7个英文字母组成的单词，以回车结束。

输出格式：

在一行中输出Hello S，跟输入的S星球打个招呼。

输入样例：

Mars

输出样例：

Hello Mars

L1-046 整除光棍 (20 分)

作者 翁恺 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

这里所谓的“光棍”，并不是指单身汪啦~
说的是全部由1组成的数字，比如1、11、111、1111等。传说任何一个光棍都能被一个不以5结尾的奇数整除。比如，111111就可以被13整除。
现在，你的程序要读入一个整数x，这个整数一定是奇数并且不以5结尾。然后，经过计算，输出两个数字：第一个数字s，表示x乘以s是一个光棍，第二个数字n是这个光棍的位数。这样的解当然不是唯一的,题目要求你输出最小的解。

提示：一个显然的办法是逐渐增加光棍的位数，直到可以整除x为止。但难点在于，s可能是个非常大的数
——
比如，程序输入31，那么就输出3584229390681和15，因为31乘以3584229390681的结果是111111111111111，一共15个1。

输入格式：

输入在一行中给出一个不以5结尾的正奇数x（< 1000）。

输出格式：

在一行中输出相应的最小的s和n，其间以1个空格分隔。

输入样例：

31

输出样例：

3584229390681 15

L1-047 装睡 (10 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

你永远叫不醒一个装睡的人 ——
但是通过分析一个人的呼吸频率和脉搏，你可以发现谁在装睡！医生告诉我们，正常人睡眠时的呼吸频率是每分钟15-20次，脉搏是每分钟50-70次。下面给定一系列人的呼吸频率与脉搏，请你找出他们中间有可能在装睡的人，即至少一项指标不在正常范围内的人。

输入格式：

输入在第一行给出一个正整数N （≤ 10）。随后N
行，每行给出一个人的名字（仅由英文字母组成的、长度不超过3个字符的串）、其呼吸频率和脉搏（均为不超过100的正整数）。

输出格式：

按照输入顺序检查每个人，如果其至少一项指标不在正常范围内，则输出其名字，每个名字占一行。

输入样例：

4

Amy 15 70 Tom 14 60 Joe 18 50 Zoe 21 71

输出样例：

Tom Zoe

L1-048 矩阵A乘以B (15 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

给定两个矩阵A和B，要求你计算它们的乘积矩阵AB。需要注意的是，只有规模匹配的矩阵才可以相乘。即若A有Ra行、Ca列，B有Rb行、Cb列，
则只有Ca与Rb相等时，两个矩阵才能相乘。

输入格式：

输入先后给出两个矩阵A和B。对于每个矩阵，首先在一行中给出其行数R和列数C，随后R行，每行给出C个整数，以1个空格分隔，且行首尾没有
多余的空格。输入保证两个矩阵的R和C都是正数，并且所有整数的绝对值不超过100。

输出格式：

若输入的两个矩阵的规模是匹配的，则按照输入的格式输出乘积矩阵AB，否则输出Error:
Ca != Rb，其中Ca是A的列数，Rb是B的行数。

输入样例1：

2 3

1 2 3

4 5 6

3 4

7 8 9 0

-1 -2 -3 -4

5 6 7 8

输出样例1：

2 4

20 22 24 16

53 58 63 28

输入样例2：

3 2

38 26

43 -5

0 17

3 2

-11 57 99 68

81 72

输出样例2：

Error: 2 != 3

L1-049 天梯赛座位分配 (20 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

天梯赛每年有大量参赛队员，要保证同一所学校的所有队员都不能相邻，分配座位就成为一件比较麻烦的事情。为此我们制定如下策略：假设某赛场有

N 所学校参赛，第 i 所学校有 M[i] 支队伍，每队 10
位参赛选手。令每校选手排成一列纵队，第 i+1 队的选手排在第 i 队选手之后。从第 1
所学校开始，各校的第 1 位队员顺次入座，然后是各校的第 2 位队员……
以此类推。如果最后只剩下 1 所学校的队伍还没有分配座位，则需要安排他们的队员

隔位就坐。本题就要求你编写程序，自动为各校生成队员的座位号，从 1 开始编号。

输入格式：

输入在一行中给出参赛的高校数 N （不超过100的正整数）；第二行给出 N
个不超过10的正整数，其中第 i 个数对应第 i 所高校的参赛队伍数，数字间以空格分隔。

输出格式：

从第 1 所高校的第 1 支队伍开始，顺次输出队员的座位号。每队占一行，座位号间以 1
个空格分隔，行首尾不得有多余空格。另外，每所高校的第一

行按“#X”输出该校的编号X，从 1 开始。

输入样例：

3

3 4 2

输出样例：

#1

1 4 7 10 13 16 19 22 25 28

31 34 37 40 43 46 49 52 55 58

61 63 65 67 69 71 73 75 77 79 #2

2 5 8 11 14 17 20 23 26 29

32 35 38 41 44 47 50 53 56 59

62 64 66 68 70 72 74 76 78 80

82 84 86 88 90 92 94 96 98 100 #3

3 6 9 12 15 18 21 24 27 30

33 36 39 42 45 48 51 54 57 60

L1-050 倒数第N个字符串 (15 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

给定一个完全由小写英文字母组成的字符串等差递增序列，该序列中的每个字符串的长度固定为
L，从 L 个 a 开始，以 1 为步长递增。例如当 L 为 3 时，序列为 { aaa, aab, aac,
…, aaz, aba, abb, …, abz, …, zzz }。这个序列的倒数第27个字符串就是
zyz。对于任意给定的 L，本题要求你给出对应序列倒数第 N 个字符串。

输入格式：

输入在一行中给出两个正整数 L（2 ≤ L ≤ 6）和 N（≤ 105 ）。

输出格式：

在一行中输出对应序列倒数第 N 个字符串。题目保证这个字符串是存在的。

输入样例：

3 7417

输出样例：

pat

L1-051 打折 (5 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

去商场淘打折商品时，计算打折以后的价钱是件颇费脑子的事情。例如原价 ￥988，标明打
7 折，则折扣价应该是 ￥988 x 70% =
￥691.60。本题就请你写个程序替客户计算折扣价。

输入格式：

输入在一行中给出商品的原价（不超过1万元的正整数）和折扣（为[1,
9]区间内的整数），其间以空格分隔。

输出格式：

在一行中输出商品的折扣价，保留小数点后 2 位。

输入样例：

988 7

输出样例：

691.60

L1-052 2018我们要赢 (5 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

2018年天梯赛的注册邀请码是“2018wmyy”，意思就是“2018我们要赢”。本题就请你用汉语拼音输出这句话。

输入格式： 本题没有输入。输出格式：

在第一行中输出：“2018”；第二行中输出：“wo3 men2 yao4 ying2 !”。

输入样例：

本题没有输入。

输出样例：

2018

wo3 men2 yao4 ying2 !

L1-053 电子汪 (10 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

据说汪星人的智商能达到人类 4
岁儿童的水平，更有些聪明汪会做加法计算。比如你在地上放两堆小球，分别有 1 只球和
2 只球，聪明汪就会

用“汪！汪！汪！”表示 1 加 2 的结果是 3。

本题要求你为电子宠物汪做一个模拟程序，根据电子眼识别出的两堆小球的个数，计算出和，并且用汪星人的叫声给出答案。

输入格式：

输入在一行中给出两个 [1, 9] 区间内的正整数 A 和 B，用空格分隔。

输出格式：

在一行中输出 A + B 个Wang!。

输入样例：

2 1

输出样例：

Wang!Wang!Wang!

L1-054 福到了 (15 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

“福”字倒着贴，寓意“福到”。不论到底算不算民俗，本题且请你编写程序，把各种汉字倒过来输出。这里要处理的每个汉字是由一个
N × N 的网格组成的，网格中的元素或者为字符 @
或者为空格。而倒过来的汉字所用的字符由裁判指定。

输入格式：

输入在第一行中给出倒过来的汉字所用的字符、以及网格的规模 N
（不超过100的正整数），其间以 1 个空格分隔；随后 N 行，每行给出 N 个字符，
或者为 @ 或者为空格。

输出格式：

输出倒置的网格，如样例所示。但是，如果这个字正过来倒过去是一样的，就先输出bu
yong dao le，然后再用输入指定的字符将其输出。

**输入样例 **1：

$ 9

@ @@@@@ @@@ @@@

@ @ @ @@@ @@@ @@@ @@@@@ @@@ @ @ @ @@@ @@@@@

@ @ @ @

@ @@@@@

**输出样例 **1：

$ $

$ $ $ $

$ $$$

$ $ $ $$$

$ $$$

$$$$$ $

$ $ $

$$$$$ $

$ $

**输入样例 **2：

& 3 @@@

@ @@@

**输出样例 **2：

bu yong dao le &&&

& &&&

L1-055 谁是赢家 (10 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

某电视台的娱乐节目有个表演评审环节，每次安排两位艺人表演，他们的胜负由观众投票和
3 名评委投票两部分共同决定。规则为：如果一位艺人的观

众票数高，且得到至少 1
名评委的认可，该艺人就胜出；或艺人的观众票数低，但得到全部评委的认可，也可以胜出。节目保证投票的观众人数为奇数，所以不存在平票的情况。本题就请你用程序判断谁是赢家。

输入格式：

输入第一行给出 2 个不超过 1000 的正整数 Pa 和 Pb，分别是艺人 a 和艺人 b
得到的观众票数。题目保证这两个数字不相等。随后第二行给出 3
名评委的投票结果。数字 0 代表投票给 a，数字 1 代表投票给 b，其间以一个空格分隔。

输出格式：

按以下格式输出赢家：

The winner is x: P1 + P2

其中 x 是代表赢家的字母，P1 是赢家得到的观众票数，P2 是赢家得到的评委票数。

输入样例：

327 129

1 0 1

输出样例：

The winner is a: 327 + 1

** 鸣谢安阳**师范学院软件学院李栋同学完善测试数据。

L1-056 猜数字 (20 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

一群人坐在一起，每人猜一个 100
以内的数，谁的数字最接近大家平均数的一半就赢。本题就要求你找出其中的赢家。

输入格式：

输入在第一行给出一个正整数N（≤ 104 ）。随后 N
行，每行给出一个玩家的名字（由不超过8个英文字母组成的字符串）和其猜的正整数（≤
100）。

输出格式：

在一行中顺序输出：大家平均数的一半（只输出整数部分）、赢家的名字，其间以空格分隔。题目保证赢家是唯一的。

输入样例：

7

Bob 35 Amy 28 James 98 Alice 11 Jack 45 Smith 33 Chris 62

输出样例：

22 Amy

L1-057 PTA使我精神焕发 (5 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

以上是湖北经济学院同学的大作。本题就请你用汉语拼音输出这句话。

输入格式： 本题没有输入。输出格式：

在一行中按照样例输出，以惊叹号结尾。

输入样例：

无

输出样例：

PTA shi3 wo3 jing1 shen2 huan4 fa1 !

L1-058 6翻了 (15 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

“666”是一种网络用语，大概是表示某人很厉害、我们很佩服的意思。最近又衍生出另一个数字“9”，意思是“6翻了”，实在太厉害的意思。如果你以为这就是厉害的最高境界，那就错啦
—— 目前的最高境界是数字“27”，因为这是 3 个 “9”！

本题就请你编写程序，将那些过时的、只会用一连串“6666……6”表达仰慕的句子，翻译成最新的高级表达。

输入格式：

输入在一行中给出一句话，即一个非空字符串，由不超过 1000
个英文字母、数字和空格组成，以回车结束。

输出格式：

从左到右扫描输入的句子：如果句子中有超过 3 个连续的 6，则将这串连续的 6 替换成
9；但如果有超过 9 个连续的 6，则将这串连续的 6
替换成27。其他内容不受影响，原样输出。

输入样例：

it is so 666 really 6666 what else can I say 6666666666

输出样例：

it is so 666 really 9 what else can I say 27

L1-059 敲笨钟 (20 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

微博上有个自称“大笨钟V”的家伙，每天敲钟催促码农们爱惜身体早点睡觉。为了增加敲钟的趣味性，还会糟改几句古诗词。其糟改的方法为：去网上搜寻压“ong”韵的古诗词，把句尾的三个字换成“敲笨钟”。例如唐代诗人李贺有名句曰：“寻章摘句老雕虫，晓月当帘挂玉弓”，其

中“虫”（chong）和“弓”（gong）都压了“ong”韵。于是这句诗就被糟改为“寻章摘句老雕虫，晓月当帘敲笨钟”。

现在给你一大堆古诗词句，要求你写个程序自动将压“ong”韵的句子糟改成“敲笨钟”。

输入格式：

输入首先在第一行给出一个不超过 20 的正整数 N。随后 N
行，每行用汉语拼音给出一句古诗词，分上下两半句，用逗号 , 分隔，句号 .
结尾。相邻两字的拼音之间用一个空格分隔。题目保证每个字的拼音不超过 6
个字符，每行字符的总长度不超过 100，并且下半句诗至少有 3 个字。

输出格式：

对每一行诗句，判断其是否压“ong”韵。即上下两句末尾的字都是“ong”结尾。如果是压此韵的，就按题面方法糟改之后输出，输出格式同输入；
否则输出 Skipped，即跳过此句。

输入样例：

5

xun zhang zhai ju lao diao chong, xiao yue dang lian gua yu gong. tian sheng wo
cai bi you yong, qian jin san jin huan fu lai.

xue zhui rou zhi leng wei rong, an xiao chen jing shu wei long. zuo ye xing chen
zuo ye feng, hua lou xi pan gui tang dong.

ren xian gui hua luo, ye jing chun shan kong.

输出样例：

xun zhang zhai ju lao diao chong, xiao yue dang lian qiao ben zhong.

Skipped

xue zhui rou zhi leng wei rong, an xiao chen jing qiao ben zhong. Skipped

Skipped

L1-060 心理阴影面积 (5 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

这是一幅心理阴影面积图。我们都以为自己可以匀速前进（图中蓝色直线），而拖延症晚期的我们往往执行的是最后时刻的疯狂赶工（图中的红色折线）。由红、蓝线围出的面积，就是我们在做作业时的心理阴影面积。

现给出红色拐点的坐标 (x, y)，要求你算出这个心理阴影面积。

输入格式：

输入在一行中给出 2 个不超过 100 的正整数 x 和 y，并且保证有 x >
y。这里假设横、纵坐标的最大值（即截止日和最终完成度）都是 100。

输出格式：

在一行中输出心理阴影面积。

友情提醒：三角形的面积 = 底边长 x 高 / 2；矩形面积 = 底边长 x
高。嫑想得太复杂，这是一道 5 分考减法的题……

输入样例：

90 10

输出样例：

4000

L1-061 新胖子公式 (10 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

根据钱江晚报官方微博的报导，最新的肥胖计算方法为：体重(kg) / 身高(m)
的平方。如果超过
25，你就是胖子。于是本题就请你编写程序自动判断一个人到底算不算胖子。

输入格式：

输入在一行中给出两个正数，依次为一个人的体重（以 kg 为单位）和身高（以 m
为单位），其间以空格分隔。其中体重不超过 1000 kg，身高不超过 3.0 m。

输出格式：

首先输出将该人的体重和身高代入肥胖公式的计算结果，保留小数点后 1
位。如果这个数值大于 25，就在第二行输出 PANG，否则输出 Hai Xing。

**输入样例 **1：

100.1 1.74

**输出样例 **1：

33.1

PANG

**输入样例 **2：

65 1.70

**输出样例 **2：

22.5

Hai Xing

L1-062 幸运彩票 (15 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

彩票的号码有 6 位数字，若一张彩票的前 3 位上的数之和等于后 3
位上的数之和，则称这张彩票是幸运的。本题就请你判断给定的彩票是不是幸运的。

输入格式：

输入在第一行中给出一个正整数 N（≤ 100）。随后 N 行，每行给出一张彩票的 6
位数字。

输出格式：

对每张彩票，如果它是幸运的，就在一行中输出 You are lucky!；否则输出 Wish you
good luck.。

输入样例：

2

233008

123456

输出样例：

You are lucky!

Wish you good luck.

L1-063 吃鱼还是吃肉 (10 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

国家给出了 8 岁男宝宝的标准身高为 130 厘米、标准体重为 27 公斤；8
岁女宝宝的标准身高为 129 厘米、标准体重为 25
公斤。现在你要根据小宝宝的身高体重，给出补充营养的建议。

输入格式：

输入在第一行给出一个不超过 10 的正整数 N ，随后 N
行，每行给出一位宝宝的身体数据：

性别 身高 体重

其中性别是 1 表示男生，0 表示女生。身高和体重都是不超过 200 的正整数。

输出格式：

对于每一位宝宝，在一行中给出你的建议：

如果太矮了，输出：duo chi yu!（多吃鱼）； 如果太瘦了，输出：duo chi
rou!（多吃肉）； 如果正标准，输出：wan mei!（完美）；

如果太高了，输出：ni li hai!（你厉害）；

如果太胖了，输出：shao chi rou!（少吃肉）。

先评价身高，再评价体重。两句话之间要有 1 个空格。

输入样例：

4

0 130 23

1 129 27

1 130 30

0 128 27

输出样例：

ni li hai! duo chi rou! duo chi yu! wan mei!

wan mei! shao chi rou! duo chi yu! shao chi rou!

L1-064 估值一亿的AI核心代码 (20 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

以上图片来自新浪微博。

本题要求你实现一个稍微更值钱一点的 AI 英文问答程序，规则是：

无论用户说什么，首先把对方说的话在一行中原样打印出来；

消除原文中多余空格：把相邻单词间的多个空格换成 1
个空格，把行首尾的空格全部删掉，把标点符号前面的空格删掉；
把原文中所有大写英文字母变成小写，除了 I；

把原文中所有独立的 can you、could you 对应地换成 I can、I could——
这里“独立”是指被空格或标点符号分隔开的单词； 把原文中所有独立的 I 和 me 换成
you；

把原文中所有的问号 ? 换成惊叹号 !；

在一行中输出替换后的句子作为 AI 的回答。

输入格式：

输入首先在第一行给出不超过 10 的正整数 N，随后 N 行，每行给出一句不超过 1000
个字符的、以回车结尾的用户的对话，对话为非空字符串，仅包括字母、数字、空格、可见的半角标点符号。

输出格式：

按题面要求输出，每个 AI 的回答前要加上 AI: 和一个空格。

输入样例：

6

Hello ?

Good to chat with you can you speak Chinese? Really?

Could you show me 5

What Is this prime? I,don 't know

输出样例：

Hello ? AI: hello!

Good to chat with you AI: good to chat with you can you speak Chinese? AI: I can
speak chinese! Really?

AI: really!

Could you show me 5 AI: I could show you 5

What Is this prime? I,don 't know

AI: what Is this prime! you,don’t know

L2-001 城市间紧急救援 (25 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

作为一个城市的应急救援队伍的负责人，你有一张特殊的全国地图。在地图上显示有多个分散的城市和一些连接城市的快速道路。每个城市的救援队数量和每一条连接两个城市的快速道路长度都标在地图上。当其他城市有紧急求助电话给你的时候，你的任务是带领你的救援队尽快赶往事发地，同时，
一路上召集尽可能多的救援队。

输入格式:

输入第一行给出4个正整数N 、M 、S、D，其中N （2 ≤ N ≤
500）是城市的个数，顺便假设城市的编号为0 ~ (N − 1)；M 是快速道路的条数；

S是出发地的城市编号；D是目的地的城市编号。

第二行给出N
个正整数，其中第i个数是第i个城市的救援队的数目，数字间以空格分隔。随后的M
行中，每行给出一条快速道路的信息，分别是：城市1、城市2、快速道路的长度，中间用空格分开，数字均为整数且不超过500。输入保证救援可行且最优解唯一。

输出格式:

第一行输出最短路径的条数和能够召集的最多的救援队数量。第二行输出从S到D的路径中经过的城市编号。数字间以空格分隔，输出结尾不能有多余空格。

输入样例:

4 5 0 3

20 30 40 10

0 1 1

1 3 2

0 3 3

0 2 2

2 3 2

输出样例:

2 60

0 1 3

L2-002 链表去重 (25 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

给定一个带整数键值的链表 L，你需要把其中绝对值重复的键值结点删掉。即对每个键值
K，只有第一个绝对值等于 K
的结点被保留。同时，所有被删除的结点须被保存在另一个链表上。例如给定 L 为
21→-15→-15→-7→15，你需要输出去重后的链表 21→-15→-7，还有被删除的链表 -15→15。

输入格式：

输入在第一行给出 L 的第一个结点的地址和一个正整数 N（≤ 105
，为结点总数）。一个结点的地址是非负的 5 位整数，空地址 NULL 用 -1 来表示。随后
N 行，每行按以下格式描述一个结点：

地址 键值 下一个结点

其中地址是该结点的地址，键值是绝对值不超过104
的整数，下一个结点是下个结点的地址。

输出格式：

首先输出去重后的链表，然后输出被删除的链表。每个结点占一行，按输入的格式输出。

输入样例：

00100 5

99999 -7 87654

23854 -15 00000

87654 15 -1

00000 -15 99999

00100 21 23854

输出样例：

00100 21 23854

23854 -15 99999

99999 -7 -1

00000 -15 87654

87654 15 -1

L2-003 月饼 (25 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 150 ms 内存限制 64 MB

月饼是中国人在中秋佳节时吃的一种传统食品，不同地区有许多不同风味的月饼。现给定所有种类月饼的库存量、总售价、以及市场的最大需求量，请你计算可以获得的最大收益是多少。

注意：销售时允许取出一部分库存。样例给出的情形是这样的：假如我们有 3
种月饼，其库存量分别为 18、15、10 万吨，总售价分别为 75、72、45
亿元。如果市场的最大需求量只有 20 万吨，那么我们最大收益策略应该是卖出全部 15
万吨第 2 种月饼、以及 5 万吨第 3 种月饼，获得 72 + 45/2 = 94.5（亿元）。

输入格式：

每个输入包含一个测试用例。每个测试用例先给出一个不超过 1000 的正整数 N
表示月饼的种类数、以及不超过 500（以万吨为单位）的正整数 D
表示市场最大需求量。随后一行给出 N
个正数表示每种月饼的库存量（以万吨为单位）；最后一行给出 N
个正数表示每种月饼的总售价（以亿元为单位）。数字间以空格分隔。

输出格式：

对每组测试用例，在一行中输出最大收益，以亿元为单位并精确到小数点后 2 位。

输入样例：

3 20

18 15 10

75 72 45

输出样例：

94.50

L2-004 搜索树判断 (25 分)

作者 DS课程组 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

对于二叉搜索树，我们规定任一结点的左子树仅包含严格小于该结点的键值，而其右子树包含大于或等于该结点的键值。如果我们交换每个节点的左子树和右子树，得到的树叫做镜像二叉搜索树。

现在我们给出一个整数键值序列，请编写程序判断该序列是否为某棵二叉搜索树或某镜像二叉搜索树的前序遍历序列，如果是，则输出对应二叉树的后序遍历序列。

输入格式:

输入的第一行包含一个正整数N（≤1000），第二行包含N个整数，为给出的整数键值序列，数字间以空格分隔。

输出格式:

输出的第一行首先给出判断结果，如果输入的序列是某棵二叉搜索树或某镜像二叉搜索树的前序遍历序列，则输出YES，否侧输出NO。如果判断结果是

YES，下一行输出对应二叉树的后序遍历序列。数字间以空格分隔，但行尾不能有多余的空格。

输入样例1:

7

8 6 5 7 10 8 11

输出样例1:

YES

5 7 6 8 11 10 8

输入样例2:

7

8 6 8 5 10 9 11

输出样例2:

NO

L2-005 集合相似度 (25 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 500 ms 内存限制 64 MB

给定两个整数集合，它们的相似度定义为：Nc/Nt ×
100%。其中Nc是两个集合都有的不相等整数的个数，Nt是两个集合一共有的不相等整数的个数。你的任务就是计算任意一对给定集合的相似度。

输入格式：

输入第一行给出一个正整数N （≤ 50），是集合的个数。随后N
行，每行对应一个集合。每个集合首先给出一个正整数M （≤ 104
），是集合中元素的个数；然后跟M 个[0, 109 ]区间内的整数。

之后一行给出一个正整数K（≤
2000），随后K行，每行对应一对需要计算相似度的集合的编号（集合从1到N
编号）。数字间以空格分隔。

输出格式：

对每一对需要计算的集合，在一行中输出它们的相似度，为保留小数点后2位的百分比数字。

输入样例：

3

3 99 87 101

4 87 101 5 87

7 99 101 18 5 135 18 99

2

1 2

1 3

输出样例：

50.00%

33.33%

L2-006 树的遍历 (25 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

给定一棵二叉树的后序遍历和中序遍历，请你输出其层序遍历的序列。这里假设键值都是互不相等的正整数。

输入格式：

输入第一行给出一个正整数N （≤
30），是二叉树中结点的个数。第二行给出其后序遍历序列。第三行给出其中序遍历序列。数字间以空格分隔。

输出格式：

在一行中输出该树的层序遍历的序列。数字间以1个空格分隔，行首尾不得有多余空格。

输入样例：

7

2 3 1 5 7 6 4

1 2 3 4 5 6 7

输出样例：

4 1 6 3 5 7 2

L2-007 家庭房产 (25 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

给定每个人的家庭成员和其自己名下的房产，请你统计出每个家庭的人口数、人均房产面积及房产套数。

输入格式：

输入第一行给出一个正整数N （≤ 1000），随后N
行，每行按下列格式给出一个人的房产：

编号 父 母 k 孩子1 孩子k 房产套数 总面积

其中编号是每个人独有的一个4位数的编号；父和母分别是该编号对应的这个人的父母的编号（如果已经过世，则显示-1）；k（0
≤k≤ 5）是该人的子女的个数；孩子i是其子女的编号。

输出格式：

首先在第一行输出家庭个数（所有有亲属关系的人都属于同一个家庭）。随后按下列格式输出每个家庭的信息：

家庭成员的最小编号 家庭人口数 人均房产套数 人均房产面积

其中人均值要求保留小数点后3位。家庭信息首先按人均面积降序输出，若有并列，则按成员编号的升序输出。

输入样例：

10

6666 5551 5552 1 7777 1 100

1234 5678 9012 1 0002 2 300

8888 -1 -1 0 1 1000

2468 0001 0004 1 2222 1 500

7777 6666 -1 0 2 300

3721 -1 -1 1 2333 2 150

9012 -1 -1 3 1236 1235 1234 1 100

1235 5678 9012 0 1 50

2222 1236 2468 2 6661 6662 1 300

2333 -1 3721 3 6661 6662 6663 1 100

输出样例：

3

8888 1 1.000 1000.000

0001 15 0.600 100.000

5551 4 0.750 100.000

L2-008 最长对称子串 (25 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

对给定的字符串，本题要求你输出最长对称子串的长度。例如，给定Is PAT&TAP
symmetric?，最长对称子串为s PAT&TAP s，于是你应该输出11。

输入格式：

输入在一行中给出长度不超过1000的非空字符串。

输出格式：

在一行中输出最长对称子串的长度。

输入样例：

Is PAT&TAP symmetric?

输出样例：

11

L2-009 抢红包 (25 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 600 ms 内存限制 64 MB

没有人没抢过红包吧…… 这里给出N
个人之间互相发红包、抢红包的记录，请你统计一下他们抢红包的收获。

输入格式：

输入第一行给出一个正整数N （≤ 104
），即参与发红包和抢红包的总人数，则这些人从1到N 编号。随后N
行，第i行给出编号为i的人发红包的记录，格式如下：

K N1 P1 ⋯ NK PK

其中K（0 ≤ K ≤ 20）是发出去的红包个数，Ni是抢到红包的人的编号，Pi（>
0）是其抢到的红包金额（以分为单位）。注意：对于同一个人发出的红包，每人最多只能抢1次，不能重复抢。

输出格式：

按照收入金额从高到低的递减顺序输出每个人的编号和收入金额（以元为单位，输出小数点后2位）。每个人的信息占一行，两数字间有1个空格。如果收入金额有并列，则按抢到红包的个数递减输出；如果还有并列，则按个人编号递增输出。

输入样例：

10

3 2 22 10 58 8 125

5 1 345 3 211 5 233 7 13 8 101

1 7 8800

2 1 1000 2 1000

2 4 250 10 320

6 5 11 9 22 8 33 7 44 10 55 4 2

1 3 8800

2 1 23 2 123

1 8 250

4 2 121 4 516 7 112 9 10

输出样例：

1 11.63

2 3.63

8 3.63

3 2.11

7 1.69

6 -1.67

9 -2.18

10 -3.26

5 -3.26

4 -12.32

L2-010 排座位 (25 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 200 ms 内存限制 64 MB

布置宴席最微妙的事情，就是给前来参宴的各位宾客安排座位。无论如何，总不能把两个死对头排到同一张宴会桌旁！这个艰巨任务现在就交给你，对任何一对客人，请编写程序告诉主人他们是否能被安排同席。

输入格式：

输入第一行给出3个正整数：N（≤100），即前来参宴的宾客总人数，则这些人从1到N编号；M为已知两两宾客之间的关系数；K为查询的条数。随后M
行，每行给出一对宾客之间的关系，格式为：宾客1 宾客2
关系，其中关系为1表示是朋友，-1表示是死对头。注意两个人不可能既是朋友又是敌人。最后K行，每行给出一对需要查询的宾客编号。

这里假设朋友的朋友也是朋友。但敌人的敌人并不一定就是朋友，朋友的敌人也不一定是敌人。只有单纯直接的敌对关系才是绝对不能同席的。

输出格式：

对每个查询输出一行结果：如果两位宾客之间是朋友，且没有敌对关系，则输出No
problem；如果他们之间并不是朋友，但也不敌对，则输出OK；如果他们之间有敌对，然而也有共同的朋友，则输出OK
but…；如果他们之间只有敌对关系，则输出No way。

输入样例：

7 8 4

5 6 1

2 7 -1

1 3 1

3 4 1

6 7 -1

1 2 1

1 4 1

2 3 -1

3 4

5 7

2 3

7 2

输出样例：

No problem OK

OK but… No way

L2-011 玩转二叉树 (25 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

给定一棵二叉树的中序遍历和前序遍历，请你先将树做个镜面反转，再输出反转后的层序遍历的序列。所谓镜面反转，是指将所有非叶结点的左右孩子对换。这里假设键值都是互不相等的正整数。

输入格式：

输入第一行给出一个正整数N（≤30），是二叉树中结点的个数。第二行给出其中序遍历序列。第三行给出其前序遍历序列。数字间以空格分隔。

输出格式：

在一行中输出该树反转后的层序遍历的序列。数字间以1个空格分隔，行首尾不得有多余空格。

输入样例：

7

1 2 3 4 5 6 7

4 1 3 2 6 5 7

输出样例：

4 6 1 7 5 3 2

L2-012 关于堆的判断 (25 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

将一系列给定数字顺序插入一个初始为空的小顶堆H[]。随后判断一系列相关命题是否为真。命题分下列几种：

x is the root：x是根结点；

x and y are siblings：x和y是兄弟结点； x is the parent of y：x是y的父结点；

x is a child of y：x是y的一个子结点。

输入格式：

每组测试第1行包含2个正整数N（≤ 1000）和M（≤
20），分别是插入元素的个数、以及需要判断的命题数。下一行给出区间[−10000,
10000]内的N
个要被插入一个初始为空的小顶堆的整数。之后M行，每行给出一个命题。题目保证命题中的结点键值都是存在的。

输出格式：

对输入的每个命题，如果其为真，则在一行中输出T，否则输出F。

输入样例：

5 4

46 23 26 24 10

24 is the root

26 and 23 are siblings 46 is the parent of 23 23 is a child of 10

输出样例：

F T F T

L2-013 红色警报 (25 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

战争中保持各个城市间的连通性非常重要。本题要求你编写一个报警程序，当失去一个城市导致国家被分裂为多个无法连通的区域时，就发出红色警报。注意：若该国本来就不完全连通，是分裂的k个区域，而失去一个城市并不改变其他城市之间的连通性，则不要发出警报。

输入格式：

输入在第一行给出两个整数N（0 < N ≤ 500）和M（≤
5000），分别为城市个数（于是默认城市从0到N-1编号）和连接两城市的通路条数。随后M行，
每行给出一条通路所连接的两个城市的编号，其间以1个空格分隔。在城市信息之后给出被攻占的信息，即一个正整数K和随后的K个被攻占的城市的编号。

注意：输入保证给出的被攻占的城市编号都是合法的且无重复，但并不保证给出的通路没有重复。

输出格式：

对每个被攻占的城市，如果它会改变整个国家的连通性，则输出Red Alert: City k is
lost!，其中k是该城市的编号；否则只输出City k is
lost.即可。如果该国失去了最后一个城市，则增加一行输出Game Over.。

输入样例：

5 4

0 1

1 3

3 0

0 4

5

1 2 0 4 3

输出样例：

City 1 is lost. City 2 is lost.

Red Alert: City 0 is lost! City 4 is lost.

City 3 is lost. Game Over.

L2-014 列车调度 (25 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 300 ms 内存限制 64 MB

火车站的列车调度铁轨的结构如下图所示。

两端分别是一条入口（Entrance）轨道和一条出口（Exit）轨道，它们之间有N条平行的轨道。每趟列车从入口可以选择任意一条轨道进入，最后从出口离开。在图中有9趟列车，在入口处按照{8，4，2，5，3，9，1，6，7}的顺序排队等待进入。如果要求它们必须按序号递减的顺序从出口离开，则至少需要多少条平行铁轨用于调度？

输入格式：

输入第一行给出一个整数N (2 ≤ N ≤ 105
)，下一行给出从1到N的整数序号的一个重排列。数字间以空格分隔。

输出格式：

在一行中输出可以将输入的列车按序号递减的顺序调离所需要的最少的铁轨条数。

输入样例：

9

8 4 2 5 3 9 1 6 7

输出样例：

4

L2-015 互评成绩 (25 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 300 ms 内存限制 64 MB

学生互评作业的简单规则是这样定的：每个人的作业会被k个同学评审，得到k个成绩。系统需要去掉一个最高分和一个最低分，将剩下的分数取平均，
就得到这个学生的最后成绩。本题就要求你编写这个互评系统的算分模块。

输入格式：

输入第一行给出3个正整数N（3 < N ≤ 104 ，学生总数）、k（3 ≤ k ≤
10，每份作业的评审数）、M（≤
20，需要输出的学生数）。随后N行，每行给出一份作业得到的k个评审成绩（在区间[0,
100]内），其间以空格分隔。

输出格式：

按非递减顺序输出最后得分最高的M个成绩，保留小数点后3位。分数间有1个空格，行首尾不得有多余空格。

输入样例：

6 5 3

88 90 85 99 60

67 60 80 76 70

90 93 96 99 99

78 65 77 70 72

88 88 88 88 88

55 55 55 55 55

输出样例：

87.667 88.000 96.000

L2-016 愿天下有情人都是失散多年的兄妹 (25 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 200 ms 内存限制 64 MB

呵呵。大家都知道五服以内不得通婚，即两个人最近的共同祖先如果在五代以内（即本人、父母、祖父母、曾祖父母、高祖父母）则不可通婚。本题就请你帮助一对有情人判断一下，他们究竟是否可以成婚？

输入格式：

输入第一行给出一个正整数N（2 ≤ N ≤ 104
），随后N行，每行按以下格式给出一个人的信息：

本人ID 性别 父亲ID 母亲ID

其中ID是5位数字，每人不同；性别M代表男性、F代表女性。如果某人的父亲或母亲已经不可考，则相应的ID位置上标记为-1。接下来给出一个正整数K，随后K行，每行给出一对有情人的ID，其间以空格分隔。

注意：题目保证两个人是同辈，每人只有一个性别，并且血缘关系网中没有乱伦或隔辈成婚的情况。

输出格式：

对每一对有情人，判断他们的关系是否可以通婚：如果两人是同性，输出Never
Mind；如果是异性并且关系出了五服，输出Yes；如果异性关系未出五服，输出No。

输入样例：

24

00001 M 01111 -1

00002 F 02222 03333

00003 M 02222 03333

00004 F 04444 03333

00005 M 04444 05555

00006 F 04444 05555

00007 F 06666 07777

00008 M 06666 07777

00009 M 00001 00002

00010 M 00003 00006

00011 F 00005 00007

00012 F 00008 08888

00013 F 00009 00011

00014 M 00010 09999

00015 M 00010 09999

00016 M 10000 00012

00017 F -1 00012

00018 F 11000 00013

00019 F 11100 00018

00020 F 00015 11110

00021 M 11100 00020

00022 M 00016 -1

00023 M 10012 00017

00024 M 00022 10013

9

00021 00024

00019 00024

00011 00012

00022 00018

00001 00004

00013 00016

00017 00015

00019 00021

00010 00011

输出样例：

Never Mind Yes

Never Mind No

Yes No Yes No No

** 鸣谢用户** 徐校波 修正数据！

L2-017 人以群分 (25 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 200 ms 内存限制 64 MB

社交网络中我们给每个人定义了一个“活跃度”，现希望根据这个指标把人群分为两大类，即外向型（outgoing，即活跃度高的）和内向型

（introverted，即活跃度低的）。要求两类人群的规模尽可能接近，而他们的总活跃度差距尽可能拉开。

输入格式：

输入第一行给出一个正整数N （2 ≤ N ≤ 105 ）。随后一行给出N
个正整数，分别是每个人的活跃度，其间以空格分隔。题目保证这些数字以及它们的和都不会超过231
。

输出格式：

按下列格式输出：

Outgoing #: N1 Introverted #: N2 Diff = N3

其中N1是外向型人的个数；N2是内向型人的个数；N3是两群人总活跃度之差的绝对值。

输入样例1：

10

23 8 10 99 46 2333 46 1 666 555

输出样例1：

Outgoing #: 5 Introverted #: 5 Diff = 3611

输入样例2：

13

110 79 218 69 3721 100 29 135 2 6 13 5188 85

输出样例2：

Outgoing #: 7 Introverted #: 6 Diff = 9359

L2-018 多项式A除以B (25 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

这仍然是一道关于A/B的题，只不过A和B都换成了多项式。你需要计算两个多项式相除的商Q和余R，其中R的阶数必须小于B的阶数。

输入格式：

输入分两行，每行给出一个非零多项式，先给出A，再给出B。每行的格式如下：

N e[1] c[1] e[N] c[N]

其中N是该多项式非零项的个数，e[i]是第i个非零项的指数，c[i]是第i个非零项的系数。各项按照指数递减的顺序给出，保证所有指数是各不相同的非负整数，所有系数是非零整数，所有整数在整型范围内。

输出格式：

分两行先后输出商和余，输出格式与输入格式相同，输出的系数保留小数点后1位。同行数字间以1个空格分隔，行首尾不得有多余空格。注意：零多项式是一个特殊多项式，对应输出为0
0
0.0。但非零多项式不能输出零系数（包括舍入后为0.0）的项。在样例中，余多项式其实有常数项-1/27，但因其

舍入后为0.0，故不输出。

输入样例：

4 4 1 2 -3 1 -1 0 -1

3 2 3 1 -2 0 1

输出样例：

3 2 0.3 1 0.2 0 -1.0

1 1 -3.1

L2-019 悄悄关注 (25 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 200 ms 内存限制 64 MB

新浪微博上有个“悄悄关注”，一个用户悄悄关注的人，不出现在这个用户的关注列表上，但系统会推送其悄悄关注的人发表的微博给该用户。现在我们来做一回网络侦探，根据某人的关注列表和其对其他用户的点赞情况，扒出有可能被其悄悄关注的人。

输入格式：

输入首先在第一行给出某用户的关注列表，格式如下：

人数N 用户1 用户2 …… 用户N

其中N是不超过5000的正整数，每个用户i（i=1, …,
N）是被其关注的用户的ID，是长度为4位的由数字和英文字母组成的字符串，各项间以空格分隔。

之后给出该用户点赞的信息：首先给出一个不超过10000的正整数M，随后M行，每行给出一个被其点赞的用户ID和对该用户的点赞次数（不超过1000），以空格分隔。注意：用户ID是一个用户的唯一身份标识。题目保证在关注列表中没有重复用户，在点赞信息中也没有重复用户。

输出格式：

我们认为被该用户点赞次数大于其点赞平均数、且不在其关注列表上的人，很可能是其悄悄关注的人。根据这个假设，请你按用户ID字母序的升序输出可能是其悄悄关注的人，每行1个ID。如果其实并没有这样的人，则输出“Bing
Mei You”。

输入样例1：

10 GAO3 Magi Zha1 Sen1 Quan FaMK LSum Eins FatM LLao 8

Magi 50 Pota 30 LLao 3 Ammy 48 Dave 15 GAO3 31

Zoro 1 Cath 60

输出样例1：

Ammy Cath Pota

输入样例2：

11 GAO3 Magi Zha1 Sen1 Quan FaMK LSum Eins FatM LLao Pota 7

Magi 50 Pota 30 LLao 48 Ammy 3 Dave 15 GAO3 31

Zoro 29

输出样例2：

Bing Mei You

L2-020 功夫传人 (25 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 500 ms 内存限制 64 MB

一门武功能否传承久远并被发扬光大，是要看缘分的。一般来说，师傅传授给徒弟的武功总要打个折扣，于是越往后传，弟子们的功夫就越弱……
直到某一支的某一代突然出现一个天分特别高的弟子（或者是吃到了灵丹、挖到了特别的秘笈），会将功夫的威力一下子放大N倍
—— 我们称这种弟子

为“得道者”。

这里我们来考察某一位祖师爷门下的徒子徒孙家谱：假设家谱中的每个人只有1位师傅（除了祖师爷没有师傅）；每位师傅可以带很多徒弟；并且假设辈分严格有序，即祖师爷这门武功的每个第i代传人只能在第i-1代传人中拜1个师傅。我们假设已知祖师爷的功力值为Z，每向下传承一代，就会减弱r%，除非某一代弟子得道。现给出师门谱系关系，要求你算出所有得道者的功力总值。

输入格式：

输入在第一行给出3个正整数，分别是：N （≤ 105
）——整个师门的总人数（于是每个人从0到N −
1编号，祖师爷的编号为0）；Z——祖师爷的功力值（不一定是整数，但起码是正数）；r
——每传一代功夫所打的折扣百分比值（不超过100的正数）。接下来有N
行，第i行（i =

0, ⋯ , N − 1）描述编号为i的人所传的徒弟，格式为：

Ki ID[1] ID[2] ⋯ ID[Ki]

其中Ki是徒弟的个数，后面跟的是各位徒弟的编号，数字间以空格间隔。Ki为零表示这是一位得道者，这时后面跟的一个数字表示其武功被放大的倍数。

输出格式：

在一行中输出所有得道者的功力总值，只保留其整数部分。题目保证输入和正确的输出都不超过1010
。

输入样例：

10 18.0 1.00

3 2 3 5

1 9

1 4

1 7

0 7

2 6 1

1 8

0 9

0 4

0 3

输出样例：

404

L2-021 点赞狂魔 (25 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 200 ms 内存限制 64 MB

微博上有个“点赞”功能，你可以为你喜欢的博文点个赞表示支持。每篇博文都有一些刻画其特性的标签，而你点赞的博文的类型，也间接刻画了你的特性。然而有这么一种人，他们会通过给自己看到的一切内容点赞来狂刷存在感，这种人就被称为“点赞狂魔”。他们点赞的标签非常分散，无法体现出明显的特性。本题就要求你写个程序，通过统计每个人点赞的不同标签的数量，找出前3名点赞狂魔。

输入格式：

输入在第一行给出一个正整数N （≤ 100），是待统计的用户数。随后N
行，每行列出一位用户的点赞标签。格式为“Name K F1 ⋯ FK ”，其中

Name是不超过8个英文小写字母的非空用户名，1 ≤ K ≤ 1000，Fi（i = 1, ⋯ ,
K）是特性标签的编号，我们将所有特性标签从 1 到 107 编号。数字间以空格分隔。

输出格式：

统计每个人点赞的不同标签的数量，找出数量最大的前3名，在一行中顺序输出他们的用户名,其间以1个空格分隔,且行末不得有多余空格。如果有并列，则输出标签出现次数平均值最小的那个，题目保证这样的用户没有并列。若不足3人，则用-补齐缺失，例如mike
jenny -就表示只有2人。

输入样例：

5

bob 11 101 102 103 104 105 106 107 108 108 107 107 peter 8 1 2 3 4 3 2 5 1

chris 12 1 2 3 4 5 6 7 8 9 1 2 3 john 10 8 7 6 5 4 3 2 1 7 5

jack 9 6 7 8 9 10 11 12 13 14

输出样例：

jack chris john

L2-022 重排链表 (25 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 500 ms 内存限制 64 MB

给定一个单链表 L1→L2→⋯→Ln−1→Ln，请编写程序将链表重新排列为
Ln→L1→Ln−1→L2→⋯。例如：给定L为1→2→3→4→5→6，则输出应该为6→1→5→2→4→3。

输入格式：

每个输入包含1个测试用例。每个测试用例第1行给出第1个结点的地址和结点总个数，即正整数N
(≤ 105 )。结点的地址是5位非负整数，NULL地址用

−1表示。

接下来有N 行，每行格式为：

Address Data Next

其中Address是结点地址；Data是该结点保存的数据，为不超过105
的正整数；Next是下一结点的地址。题目保证给出的链表上至少有两个结点。

输出格式：

对每个测试用例，顺序输出重排后的结果链表，其上每个结点占一行，格式与输入相同。

输入样例：

00100 6

00000 4 99999

00100 1 12309

68237 6 -1

33218 3 00000

99999 5 68237

12309 2 33218

输出样例：

68237 6 00100

00100 1 99999

99999 5 12309

12309 2 00000

00000 4 33218

33218 3 -1

L2-023 图着色问题 (25 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 300 ms 内存限制 64 MB

图着色问题是一个著名的NP完全问题。给定无向图G = (V ,
E)，问可否用K种颜色为V
中的每一个顶点分配一种颜色，使得不会有两个相邻顶点具有同一种颜色？

但本题并不是要你解决这个着色问题，而是对给定的一种颜色分配，请你判断这是否是图着色问题的一个解。

输入格式：

输入在第一行给出3个整数V （0 < V ≤ 500）、E（≥ 0）和K（0 < K ≤ V
），分别是无向图的顶点数、边数、以及颜色数。顶点和颜色都从1 到V
编号。随后E行，每行给出一条边的两个端点的编号。在图的信息给出之后，给出了一个正整数N
（≤ 20），是待检查的颜色分配方案的个数。随后N 行，每行顺次给出V
个顶点的颜色（第i个数字表示第i个顶点的颜色），数字间以空格分隔。题目保证给定的无向图是合法的（即不存在自回路和重边）。

输出格式：

对每种颜色分配方案，如果是图着色问题的一个解则输出Yes，否则输出No，每句占一行。

输入样例：

6 8 3

2 1

1 3

4 6

2 5

2 4

5 4

5 6

3 6

4

1 2 3 3 1 2

4 5 6 6 4 5

1 2 3 4 5 6

2 3 4 2 3 4

输出样例：

Yes Yes No No

L2-024 部落 (25 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 150 ms 内存限制 64 MB

在一个社区里，每个人都有自己的小圈子，还可能同时属于很多不同的朋友圈。我们认为朋友的朋友都算在一个部落里，于是要请你统计一下，在一个给定社区中，到底有多少个互不相交的部落？并且检查任意两个人是否属于同一个部落。

输入格式：

输入在第一行给出一个正整数N （≤ 104 ），是已知小圈子的个数。随后N
行，每行按下列格式给出一个小圈子里的人：

K P [1] P [2] ⋯ P [K]

其中K是小圈子里的人数，P [i]（i = 1, ⋯ ,
K）是小圈子里每个人的编号。这里所有人的编号从1开始连续编号，最大编号不会超过104
。之后一行给出一个非负整数Q（≤ 104
），是查询次数。随后Q行，每行给出一对被查询的人的编号。

输出格式：

首先在一行中输出这个社区的总人数、以及互不相交的部落的个数。随后对每一次查询，如果他们属于同一个部落，则在一行中输出Y，否则输出N。

输入样例：

4

3 10 1 2

2 3 4

4 1 5 7 8

3 9 6 4

2

10 5

3 7

输出样例：

10 2

Y N

L2-025 分而治之 (25 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 600 ms 内存限制 64 MB

分而治之，各个击破是兵家常用的策略之一。在战争中，我们希望首先攻下敌方的部分城市，使其剩余的城市变成孤立无援，然后再分头各个击破。为此参谋部提供了若干打击方案。本题就请你编写程序，判断每个方案的可行性。

输入格式：

输入在第一行给出两个正整数 N 和 M（均不超过10
000），分别为敌方城市个数（于是默认城市从 1 到 N
编号）和连接两城市的通路条数。随后 M
行，每行给出一条通路所连接的两个城市的编号，其间以一个空格分隔。在城市信息之后给出参谋部的系列方案，即一个正整数
K （≤ 100）和随后的 K 行方案，每行按以下格式给出：

Np v[1] v[2] v[Np]

其中 Np 是该方案中计划攻下的城市数量，后面的系列 v[i] 是计划攻下的城市编号。

输出格式：

对每一套方案，如果可行就输出YES，否则输出NO。

输入样例：

10 11

8 7

6 8

4 5

8 4

8 1

1 2

1 4

9 8

9 1

1 10

2 4

5

4 10 3 8 4

6 6 1 7 5 4 9

3 1 8 4

2 2 8

7 9 8 7 6 5 4 2

输出样例：

NO YES YES NO NO

L2-026 小字辈 (25 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

本题给定一个庞大家族的家谱，要请你给出最小一辈的名单。

输入格式：

输入在第一行给出家族人口总数 N（不超过 100 000 的正整数） ——
简单起见，我们把家族成员从 1 到 N 编号。随后第二行给出 N 个编号，其中第 i
个编号对应第 i 位成员的父/母。家谱中辈分最高的老祖宗对应的父/母编号为
-1。一行中的数字间以空格分隔。

输出格式：

首先输出最小的辈分（老祖宗的辈分为
1，以下逐级递增）。然后在第二行按递增顺序输出辈分最小的成员的编号。编号间以一个空格分隔，行首尾不得有多余空格。

输入样例：

9

2 6 5 5 -1 5 6 4 7

输出样例：

4

1 9

L2-027 名人堂与代金券 (25 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 250 ms 内存限制 64 MB

对于在中国大学MOOC（http://www.icourse163.org/
）学习“数据结构”课程的学生，想要获得一张合格证书，总评成绩必须达到 60 分及以上，
并且有另加福利：总评分在 [G, 100] 区间内者，可以得到 50 元 PAT 代金券；在 [60,
G) 区间内者，可以得到 20
元PAT代金券。全国考点通用，一年有效。同时任课老师还会把总评成绩前 K
名的学生列入课程“名人堂”。本题就请你编写程序，帮助老师列出名人堂的学生，并统计一共发出了面值多少元的
PAT 代金券。

输入格式：

输入在第一行给出 3 个整数，分别是 N（不超过 10 000 的正整数，为学生总数）、G（在
(60,100) 区间内的整数，为题面中描述的代金券等级分界线）、K（不超过 100 且不超过
N 的正整数，为进入名人堂的最低名次）。接下来 N
行，每行给出一位学生的账号（长度不超过15位、不带空格的字符串）和总评成绩（区间
[0, 100] 内的整数），其间以空格分隔。题目保证没有重复的账号。

输出格式：

首先在一行中输出发出的 PAT
代金券的总面值。然后按总评成绩非升序输出进入名人堂的学生的名次、账号和成绩，其间以
1
个空格分隔。需要注意的是：成绩相同的学生享有并列的排名，排名并列时，按账号的字母序升序输出。

输入样例：

10 80 5

cy@zju.edu.cn 78 cy@pat-edu.com 87
1001@qq.com 65

uh-oh@163.com 96 test@126.com 39
anyone@qq.com 87 zoe@mit.edu 80
jack@ucla.edu 88 bob@cmu.edu 80
ken@163.com 70

输出样例：

360

1 uh-oh@163.com 96 2
jack@ucla.edu 88 3 anyone@qq.com
87 3 cy@pat-edu.com 87 5
bob@cmu.edu 80

5 zoe@mit.edu 80

L2-028 秀恩爱分得快 (25 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 500 ms 内存限制 64 MB

古人云：秀恩爱，分得快。

互联网上每天都有大量人发布大量照片，我们通过分析这些照片，可以分析人与人之间的亲密度。如果一张照片上出现了
K 个人，这些人两两间的亲密度就被定义为
1/K。任意两个人如果同时出现在若干张照片里，他们之间的亲密度就是所有这些同框照片对应的亲密度之和。下面给定一批照片，请你分析一对给定的情侣，看看他们分别有没有亲密度更高的异性朋友？

输入格式：

输入在第一行给出 2 个正整数：N（不超过1000，为总人数——简单起见，我们把所有人从 0
到 N-1 编号。为了区分性别，我们用编号前的负号表示女性）和
M（不超过1000，为照片总数）。随后 M 行，每行给出一张照片的信息，格式如下：

K P[1] P[K]

其中 K（≤ 500）是该照片中出现的人数，P[1] ~ P[K]
就是这些人的编号。最后一行给出一对异性情侣的编号 A 和
B。同行数字以空格分隔。题目保证每个人只有一个性别，并且不会在同一张照片里出现多次。

输出格式：

首先输出 A PA，其中 PA 是与 A 最亲密的异性。如果 PA
不唯一，则按他们编号的绝对值递增输出；然后类似地输出 B PB。但如果 A 和 B
正是彼此亲密度最高的一对，则只输出他们的编号，无论是否还有其他人并列。

**输入样例 **1：

10 4

4 -1 2 -3 4

4 2 -3 -5 -6

3 2 4 -5

3 -6 0 2

-3 2

**输出样例 **1：

-3 2 2 -5

2 -6

**输入样例 **2：

4 4

4 -1 2 -3 0

2 0 -3

2 2 -3

2 -1 2

-3 2

**输出样例 **2：

-3 2

L2-029 特立独行的幸福 (25 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

对一个十进制数的各位数字做一次平方和，称作一次迭代。如果一个十进制数能通过若干次迭代得到
1，就称该数为幸福数。1 是一个幸福数。此外， 例如 19 经过 1 次迭代得到 82，2
次迭代后得到 68，3 次迭代后得到 100，最后得到 1。则 19
就是幸福数。显然，在一个幸福数迭代到 1
的过程中经过的数字都是幸福数，它们的幸福是依附于初始数字的。例如 82、68、100
的幸福是依附于 19
的。而一个特立独行的幸福数，是在一个有限的区间内不依附于任何其它数字的；其独立性就是依附于它的的幸福数的个数。如果这个数还是个素数，则其独立性加倍。例如
19 在区间[1, 100] 内就是

一个特立独行的幸福数，其独立性为 2 × 4 = 8。

另一方面，如果一个大于1的数字经过数次迭代后进入了死循环，那这个数就不幸福。例如
29 迭代得到 85、89、145、42、20、4、16、37、58、

89、…… 可见 89 到 58 形成了死循环，所以 29 就不幸福。

本题就要求你编写程序，列出给定区间内的所有特立独行的幸福数和它的独立性。

输入格式：

输入在第一行给出闭区间的两个端点：1 < A < B ≤ 104 。

输出格式：

按递增顺序列出给定闭区间 [A, B]
内的所有特立独行的幸福数和它的独立性。每对数字占一行，数字间以 1
个空格分隔。如果区间内没有幸福数，则在一行中输出 SAD。

**输入样例 **1：

10 40

**输出样例 **1：

19 8

23 6

28 3

31 4

32 3

**注意：**样例中，10、13 也都是幸福数，但它们分别依附于其他数字（如 23、31
等等），所以不输出。其它数字虽然其实也依附于其它幸福数，但因为那些数字不在给定区间
[10, 40] 内，所以它们在给定区间内是特立独行的幸福数。

**输入样例 **2：

110 120

**输出样例 **2：

SAD

L2-030 冰岛人 (25 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

2018年世界杯，冰岛队因1:1平了强大的阿根廷队而一战成名。好事者发现冰岛人的名字后面似乎都有个“松”（son），于是有网友科普如下：

冰岛人沿用的是维京人古老的父系姓制，孩子的姓等于父亲的名加后缀，如果是儿子就加
sson，女儿则加 sdottir。因为冰岛人口较少，为避免近亲繁衍，本地人交往前先用个 App
查一下两人祖宗若干代有无联系。本题就请你实现这个 App 的功能。

输入格式：

输入首先在第一行给出一个正整数 N （1 < N ≤ 105 ），为当地人口数。随后 N
行，每行给出一个人名，格式为：名 姓（带性别后缀），两个字符串均由不超过 20
个小写的英文字母组成。维京人后裔是可以通过姓的后缀判断其性别的，其他人则是在姓的后面加
m 表示男性、f 表示女性。题目保证给出的每个维京家族的起源人都是男性。

随后一行给出正整数 M ，为查询数量。随后 M 行，每行给出一对人名，格式为：名1
姓1 名2 姓2。注意：这里的姓是不带后缀的。四个字符串均由不超过 20
个小写的英文字母组成。

题目保证不存在两个人是同名的。

输出格式：

对每一个查询，根据结果在一行内显示以下信息：

若两人为异性，且五代以内无公共祖先，则输出 Yes；

若两人为异性，但五代以内（不包括第五代）有公共祖先，则输出 No；
若两人为同性，则输出 Whatever；

若有一人不在名单内，则输出 NA。

所谓“五代以内无公共祖先”是指两人的公共祖先（如果存在的话）必须比任何一方的曾祖父辈分高。

输入样例：

15

chris smithm adam smithm bob adamsson jack chrissson bill chrissson mike
jacksson steve billsson tim mikesson

april mikesdottir eric stevesson tracy timsdottir james ericsson patrick
jacksson robin patricksson will robinsson

6

tracy tim james eric will robin tracy tim april mike steve bill bob adam eric
steve tracy tim tracy tim

x man april mikes

输出样例：

Yes No No

Whatever Whatever NA

L2-031 深入虎穴 (25 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

著名的王牌间谍 007
需要执行一次任务，获取敌方的机密情报。已知情报藏在一个地下迷宫里，迷宫只有一个入口，里面有很多条通路，每条路通向一扇门。每一扇门背后或者是一个房间，或者又有很多条路，同样是每条路通向一扇门……
他的手里有一张表格，是其他间谍帮他收集到的情报，他们记下了每扇门的编号，以及这扇门背后的每一条通路所到达的门的编号。007
发现不存在两条路通向同一扇门。

内线告诉他，情报就藏在迷宫的最深处。但是这个迷宫太大了，他需要你的帮助 ——
请编程帮他找出距离入口最远的那扇门。

输入格式：

输入首先在一行中给出正整数 N （< 105 ），是门的数量。最后 N 行，第 i
行（1 ≤ i ≤ N ）按以下格式描述编号为 i 的那扇门背后能通向的门：

K D[1] D[2] D[K]

其中 K 是通道的数量，其后是每扇门的编号。

输出格式：

在一行中输出距离入口最远的那扇门的编号。题目保证这样的结果是唯一的。

输入样例：

13

3 2 3 4

2 5 6

1 7

1 8

1 9

0

2 11 10

1 13

0

0

1 12

0

0

输出样例：

12

L2-032 彩虹瓶 (25 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

彩虹瓶的制作过程（并不）是这样的：先把一大批空瓶铺放在装填场地上，然后按照一定的顺序将每种颜色的小球均匀撒到这批瓶子里。

假设彩虹瓶里要按顺序装 N 种颜色的小球（不妨将顺序就编号为 1 到
N）。现在工厂里有每种颜色的小球各一箱，工人需要一箱一箱地将小球从工厂里搬到装填场地。如果搬来的这箱小球正好是可以装填的颜色，就直接拆箱装填；如果不是，就把箱子先码放在一个临时货架上，码放的方法就是一箱一箱堆上去。当一种颜色装填完以后，先看看货架顶端的一箱是不是下一个要装填的颜色，如果是就取下来装填，否则去工厂里再搬一箱过来。

如果工厂里发货的顺序比较好，工人就可以顺利地完成装填。例如要按顺序装填 7
种颜色，工厂按照 7、6、1、3、2、5、4 这个顺序发货，则工人先拿到 7、6
两种不能装填的颜色，将其按照 7 在下、6 在上的顺序堆在货架上；拿到 1
时可以直接装填；拿到 3 时又得临时码放在 6 号颜色箱上；拿

到 2 时可以直接装填；随后从货架顶取下 3 进行装填；然后拿到 5，临时码放到 6
上面；最后取了 4 号颜色直接装填；剩下的工作就是顺序从货架上取下 5、6、7
依次装填。

但如果工厂按照 3、1、5、4、2、6、7
这个顺序发货，工人就必须要愤怒地折腾货架了，因为装填完 2
号颜色以后，不把货架上的多个箱子搬下来就拿不到 3 号箱，就不可能顺利完成任务。

另外，货架的容量有限，如果要堆积的货物超过容量，工人也没办法顺利完成任务。例如工厂按照
7、6、5、4、3、2、1 这个顺序发货，如果货架够高，能码放 6
只箱子，那还是可以顺利完工的；但如果货架只能码放 5 只箱子，工人就又要愤怒了……

本题就请你判断一下，工厂的发货顺序能否让工人顺利完成任务。

输入格式：

输入首先在第一行给出 3 个正整数，分别是彩虹瓶的颜色数量 N （1 < N ≤ 103
）、临时货架的容量 M （< N ）、以及需要判断的发货顺序的数量 K。

随后 K 行，每行给出 N 个数字，是 1 到N
的一个排列，对应工厂的发货顺序。一行中的数字都以空格分隔。

输出格式：

对每个发货顺序，如果工人可以愉快完工，就在一行中输出 YES；否则输出 NO。

输入样例：

7 5 3

7 6 1 3 2 5 4

3 1 5 4 2 6 7

7 6 5 4 3 2 1

输出样例：

YES NO NO

L3-001 凑零钱 (30 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 300 ms 内存限制 64 MB

韩梅梅喜欢满宇宙到处逛街。现在她逛到了一家火星店里，发现这家店有个特别的规矩：你可以用任何星球的硬币付钱，但是绝不找零，当然也不能欠债。韩梅梅手边有
104 枚来自各个星球的硬币，需要请你帮她盘算一下，是否可能精确凑出要付的款额。

输入格式：

输入第一行给出两个正整数：N （≤ 104 ）是硬币的总个数，M （≤ 102
）是韩梅梅要付的款额。第二行给出 N 枚硬币的正整数面值。数字间以空格分隔。

输出格式：

在一行中输出硬币的面值 V1 ≤ V2 ≤ ⋯ ≤ Vk ，满足条件 V1 + V2 + … +
Vk = M 。数字间以 1
个空格分隔，行首尾不得有多余空格。若解不唯一，则输出最小序列。若无解，则输出 No
Solution。

注：我们说序列{ A[1], A[2], ⋯ }比{ B[1], B[2], ⋯ }“小”，是指存在 k ≥ 1
使得 A[i] = B[i] 对所有 i < k 成立，并且 A[k] < B[k]。

**输入样例 **1：

8 9

5 9 8 7 2 3 4 1

**输出样例 **1：

1 3 5

**输入样例 **2：

4 8

7 2 4 3

**输出样例 **2：

No Solution

L3-002 特殊堆栈 (30 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

堆栈是一种经典的后进先出的线性结构，相关的操作主要有“入栈”（在堆栈顶插入一个元素）和“出栈”（将栈顶元素返回并从堆栈中删除）。本题要求你实现另一个附加的操作：“取中值”——即返回所有堆栈中元素键值的中值。给定
N 个元素，如果 N 是偶数，则中值定义为第 N/2 小元；若是奇数，则为第 (N+1)/2
小元。

输入格式：

输入的第一行是正整数 N（≤ 105 ）。随后 N 行，每行给出一句指令，为以下 3 种之一：

Push key Pop PeekMedian

其中 key 是不超过 105 的正整数；Push 表示“入栈”；Pop 表示“出栈”；PeekMedian
表示“取中值”。

输出格式：

对每个 Push 操作，将 key 插入堆栈，无需输出；对每个 Pop 或 PeekMedian
操作，在一行中输出相应的返回值。若操作非法，则对应输出 Invalid。

输入样例：

17

Pop PeekMedian Push 3 PeekMedian Push 2 PeekMedian Push 1 PeekMedian Pop

Pop Push 5 Push 4

PeekMedian Pop

Pop Pop Pop

输出样例：

Invalid Invalid 3

2

2

1

2

4

4

5

3

Invalid

L3-003 社交集群 (30 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 3000 ms 内存限制 64 MB

当你在社交网络平台注册时，一般总是被要求填写你的个人兴趣爱好，以便找到具有相同兴趣爱好的潜在的朋友。一个“社交集群”是指部分兴趣爱好相同的人的集合。你需要找出所有的社交集群。

输入格式：

输入在第一行给出一个正整数 N（≤
1000），为社交网络平台注册的所有用户的人数。于是这些人从 1 到 N 编号。随后 N
行，每行按以下格式给出一个人的兴趣爱好列表：

Ki: hi[1] hi[2] … hi[Ki]

其中Ki(> 0)是兴趣爱好的个数，hi[j]是第j个兴趣爱好的编号，为区间 [1,
1000] 内的整数。

输出格式：

首先在一行中输出不同的社交集群的个数。随后第二行按非增序输出每个集群中的人数。数字间以一个空格分隔，行末不得有多余空格。

输入样例：

8

3: 2 7 10

1: 4

2: 5 3

1: 4

1: 3

1: 4

4: 6 8 1 5

1: 4

输出样例：

3

4 3 1

L3-004 肿瘤诊断 (30 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 1000 ms 内存限制 64 MB

在诊断肿瘤疾病时，计算肿瘤体积是很重要的一环。给定病灶扫描切片中标注出的疑似肿瘤区域，请你计算肿瘤的体积。

输入格式：

输入第一行给出4个正整数：M 、N 、L、T ，其中M 和N
是每张切片的尺寸（即每张切片是一个M × N 的像素矩阵。最大分辨率是1286 × 128

）；L（≤ 60）是切片的张数；T 是一个整数阈值（若疑似肿瘤的连通体体积小于T
，则该小块忽略不计）。

最后给出L张切片。每张用一个由0和1组成的M × N
的矩阵表示，其中1表示疑似肿瘤的像素，0表示正常像素。由于切片厚度可以认为是一个常数，
于是我们只要数连通体中1的个数就可以得到体积了。麻烦的是，可能存在多个肿瘤，这时我们只统计那些体积不小于T
的。两个像素被认为是“连通的”，如果它们有一个共同的切面，如下图所示，所有6个红色的像素都与蓝色的像素连通。

输出格式：

在一行中输出肿瘤的总体积。

输入样例：

3 4 5 2

1 1 1 1

1 1 1 1

1 1 1 1

0 0 1 1

0 0 1 1

0 0 1 1

1 0 1 1

0 1 0 0

0 0 0 0

1 0 1 1

0 0 0 0

0 0 0 0

0 0 0 1

0 0 0 1

1 0 0 0

输出样例：

26

L3-005 垃圾箱分布 (30 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 200 ms 内存限制 64 MB

大家倒垃圾的时候，都希望垃圾箱距离自己比较近，但是谁都不愿意守着垃圾箱住。所以垃圾箱的位置必须选在到所有居民点的最短距离最长的地方，
同时还要保证每个居民点都在距离它一个不太远的范围内。

现给定一个居民区的地图，以及若干垃圾箱的候选地点，请你推荐最合适的地点。如果解不唯一，则输出到所有居民点的平均距离最短的那个解。如果这样的解还是不唯一，则输出编号最小的地点。

输入格式：

输入第一行给出4个正整数：N （≤ 103 ）是居民点的个数；M （≤
10）是垃圾箱候选地点的个数；K（≤ 104
）是居民点和垃圾箱候选地点之间的道路的条数；DS
是居民点与垃圾箱之间不能超过的最大距离。所有的居民点从1到N
编号，所有的垃圾箱候选地点从G1到GM 编号。

随后K行，每行按下列格式描述一条道路：

P1 P2 Dist

其中P1和P2是道路两端点的编号，端点可以是居民点，也可以是垃圾箱候选点。Dist是道路的长度，是一个正整数。

输出格式：

首先在第一行输出最佳候选地点的编号。然后在第二行输出该地点到所有居民点的最小距离和平均距离。数字间以空格分隔，保留小数点后1位。如果解不存在，则输出No
Solution。

输入样例1：

4 3 11 5

1 2 2

1 4 2

1 G1 4

1 G2 3

2 3 2

2 G2 1

3 4 2

3 G3 2

4 G1 3

G2 G1 1 G3 G2 2

输出样例1：

G1

2.0 3.3

输入样例2：

2 1 2 10

1 G1 9

2 G1 20

输出样例2：

No Solution

L3-006 迎风一刀斩 (30 分)

作者 刘汝佳 单位 北京尔宜居科技有限责任公司 代码长度限制 16 KB 时间限制 150 ms
内存限制 64 MB

迎着一面矩形的大旗一刀斩下，如果你的刀够快的话，这笔直一刀可以切出两块多边形的残片。反过来说，如果有人拿着两块残片来吹牛，说这是自己迎风一刀斩落的，你能检查一下这是不是真的吗？

注意摆在你面前的两个多边形可不一定是端端正正摆好的，它们可能被平移、被旋转（逆时针90度、180度、或270度），或者被（镜像）翻面。这里假设原始大旗的四边都与坐标轴是平行的。

输入格式：

输入第一行给出一个正整数N （≤ 20），随后给出N
对多边形。每个多边形按下列格式给出：

k x1

y1 ⋯ xk yk

其中k（2 < k ≤ 10）是多边形顶点个数；(xi, yi)（0 ≤ xi, yi ≤ 108
）是顶点坐标，按照顺时针或逆时针的顺序给出。注意：题目保证没有多余顶点。即每个多边形的顶点都是不重复的，任意3个相邻顶点不共线。

输出格式：

对每一对多边形，输出YES或者NO。

输入样例：

8

3 0 0 1 0 1 1

3 0 0 1 1 0 1

3 0 0 1 0 1 1

3 0 0 1 1 0 2

4 0 4 1 4 1 0 0 0

4 4 0 4 1 0 1 0 0

3 0 0 1 1 0 1

4 2 3 1 4 1 7 2 7

5 10 10 10 12 12 12 14 11 14 10

3 28 35 29 35 29 37

3 7 9 8 11 8 9

5 87 26 92 26 92 23 90 22 87 22

5 0 0 2 0 1 1 1 2 0 2

4 0 0 1 1 2 1 2 0

4 0 0 0 1 1 1 2 0

4 0 0 0 1 1 1 2 0

输出样例：

YES NO YES YES YES YES NO YES

L3-007 天梯地图 (30 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 300 ms 内存限制 64 MB

本题要求你实现一个天梯赛专属在线地图，队员输入自己学校所在地和赛场地点后，该地图应该推荐两条路线：一条是最快到达路线；一条是最短距离的路线。题目保证对任意的查询请求，地图上都至少存在一条可达路线。

输入格式：

输入在第一行给出两个正整数N（2 ≤ N ≤
500）和M，分别为地图中所有标记地点的个数和连接地点的道路条数。随后M行，每行按如下格式给出一条道路的信息：

V1 V2 one-way length time

其中V1和V2是道路的两个端点的编号（从0到N-1）；如果该道路是从V1到V2的单行线，则one-way为1，否则为0；length是道路的长度；time是通过该路所需要的时间。最后给出一对起点和终点的编号。

输出格式：

首先按下列格式输出最快到达的时间T和用节点编号表示的路线：

Time = T: 起点 => 节点1 => => 终点

然后在下一行按下列格式输出最短距离D和用节点编号表示的路线：

Distance = D: 起点 => 节点1 => => 终点

如果最快到达路线不唯一，则输出几条最快路线中最短的那条，题目保证这条路线是唯一的。而如果最短距离的路线不唯一，则输出途径节点数最少的那条，题目保证这条路线是唯一的。

如果这两条路线是完全一样的，则按下列格式输出：

Time = T; Distance = D: 起点 => 节点1 => => 终点

输入样例1：

10 15

0 1 0 1 1

8 0 0 1 1

4 8 1 1 1

5 4 0 2 3

5 9 1 1 4

0 6 0 1 1

7 3 1 1 2

8 3 1 1 2

2 5 0 2 2

2 1 1 1 1

1 5 0 1 3

1 4 0 1 1

9 7 1 1 3

3 1 0 2 5

6 3 1 2 1

5 3

输出样例1：

Time = 6: 5 => 4 => 8 => 3 Distance = 3: 5 => 1 => 3

输入样例2：

7 9

0 4 1 1 1

1 6 1 3 1

2 6 1 1 1

2 5 1 2 2

3 0 0 1 1

3 1 1 3 1

3 2 1 2 1

4 5 0 2 2

6 5 1 2 1

3 5

输出样例2：

Time = 3; Distance = 4: 3 => 2 => 5

L3-008 喊山 (30 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 150 ms 内存限制 64 MB

喊山，是人双手围在嘴边成喇叭状，对着远方高山发出“喂—喂喂—喂喂喂……”的呼唤。呼唤声通过空气的传递，回荡于深谷之间，传送到人们耳中，发出约定俗成的“讯号”，达到声讯传递交流的目的。原来它是彝族先民用来求援呼救的“讯号”，慢慢地人们在生活实践中发现了它的实用价值，便把它作为一种交流工具世代传袭使用。（图文摘自：http://news.xrxxw.com/newsshow-8018.html）

一个山头呼喊的声音可以被临近的山头同时听到。题目假设每个山头最多有两个能听到它的临近山头。给定任意一个发出原始信号的山头，本题请你找出这个信号最远能传达到的地方。

输入格式：

输入第一行给出3个正整数n、m和k，其中n（≤10000）是总的山头数（于是假设每个山头从1到n编号）。接下来的m行，每行给出2个不超过n的正整数，数字间用空格分开，分别代表可以听到彼此的两个山头的编号。这里保证每一对山头只被输入一次，不会有重复的关系输入。最后一行给出k（≤10）个不超过n的正整数，数字间用空格分开，代表需要查询的山头的编号。

输出格式：

依次对于输入中的每个被查询的山头，在一行中输出其发出的呼喊能够连锁传达到的最远的那个山头。注意：被输出的首先必须是被查询的个山头能连锁传到的。若这样的山头不只一个，则输出编号最小的那个。若此山头的呼喊无法传到任何其他山头，则输出0。

输入样例：

7 5 4

1 2

2 3

3 1

4 5

5 6

1 4 5 7

输出样例：

2

6

4

0

L3-009 长城 (30 分)

作者 邓俊辉 单位 清华大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

正如我们所知，中国古代长城的建造是为了抵御外敌入侵。在长城上，建造了许多烽火台。每个烽火台都监视着一个特定的地区范围。一旦某个地区有外敌入侵，值守在对应烽火台上的士兵就会将敌情通报给周围的烽火台，并迅速接力地传递到总部。

现在如图1所示，若水平为南北方向、垂直为海拔高度方向，假设长城就是依次相联的一系列线段，而且在此范围内的任一垂直线与这些线段有且仅有唯一的交点。

** 图 1
**
进一步地，假设烽火台只能建造在线段的端点处。我们认为烽火台本身是没有高度的，每个烽火台只负责向北方（图1中向左）瞭望，而且一旦有外敌入侵，只要敌人与烽火台之间未被山体遮挡，哨兵就会立即察觉。当然，按照这一军规，对于南侧的敌情各烽火台并不负责任。一旦哨兵发现敌情，他就会立即以狼烟或烽火的形式，向其南方的烽火台传递警报，直到位于最南侧的总部。

以图2中的长城为例，负责守卫的四个烽火台用蓝白圆点示意，最南侧的总部用红色圆点示意。如果红色星形标示的地方出现敌情，将被哨兵们发现并沿红色折线将警报传递到总部。当然，就这个例子而言只需两个烽火台的协作，但其他位置的敌情可能需要更多。

然而反过来，即便这里的4个烽火台全部参与，依然有不能覆盖的（黄色）区域。

** 图 2
**
另外，为避免歧义，我们在这里约定，与某个烽火台的视线刚好相切的区域都认为可以被该烽火台所监视。以图3中的长城为例，若A、B、C、D点均共线，且在D点设置一处烽火台，则A、B、C以及线段BC上的任何一点都在该烽火台的监视范围之内。

** 图 3
**
好了，倘若你是秦始皇的太尉，为不致出现更多孟姜女式的悲剧，如何在保证长城安全的前提下，使消耗的民力（建造的烽火台）最少呢？

输入格式：

输入在第一行给出一个正整数N（3 ≤ N ≤ 105
），即刻画长城边缘的折线顶点（含起点和终点）数。随后N行，每行给出一个顶点的x和y坐标，其间以空格分隔。注意顶点从南到北依次给出，第一个顶点为总部所在位置。坐标为区间[−109
, 109 )内的整数，且没有重合点。

输出格式：

在一行中输出所需建造烽火台（不含总部）的最少数目。

输入样例：

10

67 32

48 -49

32 53

22 -44

19 22

11 40

10 -65

-1 -23

-3 31

-7 59

输出样例：

2

L3-010 是否完全二叉搜索树 (30 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

将一系列给定数字顺序插入一个初始为空的二叉搜索树（定义为左子树键值大，右子树键值小），你需要判断最后的树是否一棵完全二叉树，并且给出其层序遍历的结果。

输入格式：

输入第一行给出一个不超过20的正整数N；第二行给出N个互不相同的正整数，其间以空格分隔。

输出格式：

将输入的N个正整数顺序插入一个初始为空的二叉搜索树。在第一行中输出结果树的层序遍历结果，数字间以1个空格分隔，行的首尾不得有多余空格。第二行输出YES，如果该树是完全二叉树；否则输出NO。

输入样例1：

9

38 45 42 24 58 30 67 12 51

输出样例1：

38 45 24 58 42 30 12 67 51

YES

输入样例2：

8

38 24 12 45 58 67 42 51

输出样例2：

38 45 24 58 42 12 67 51

NO

L3-011 直捣黄龙 (30 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 150 ms 内存限制 64 MB

本题是一部战争大片 ——
你需要从己方大本营出发，一路攻城略地杀到敌方大本营。首先时间就是生命，所以你必须选择合适的路径，以最快的速度占领敌方大本营。当这样的路径不唯一时，要求选择可以沿途解放最多城镇的路径。若这样的路径也不唯一，则选择可以有效杀伤最多敌军的路径。

输入格式：

输入第一行给出2个正整数N（2 ≤ N ≤
200，城镇总数）和K（城镇间道路条数），以及己方大本营和敌方大本营的代号。随后N-1行，每行给出除了己方大本营外的一个城镇的代号和驻守的敌军数量，其间以空格分隔。再后面有K行，每行按格式城镇1
城镇2
距离给出两个城镇之间道路的长度。这里设每个城镇（包括双方大本营）的代号是由3个大写英文字母组成的字符串。

输出格式：

按照题目要求找到最合适的进攻路径（题目保证速度最快、解放最多、杀伤最强的路径是唯一的），并在第一行按照格式己方大本营->城镇1->…->敌方大本营输出。第二行顺序输出最快进攻路径的条数、最短进攻距离、歼敌总数，其间以1个空格分隔，行首尾不得有多余空格。

输入样例：

10 12 PAT DBY DBY 100

PTA 20 PDS 90 PMS 40 TAP 50 ATP 200 LNN 80 LAO 30 LON 70

PAT PTA 10 PAT PMS 10 PAT ATP 20 PAT LNN 10 LNN LAO 10 LAO LON 10 LON DBY 10 PMS
TAP 10 TAP DBY 10 DBY PDS 10 PDS PTA 10 DBY ATP 10

输出样例：

PAT->PTA->PDS->DBY 3 30 210

L3-012 水果忍者 (30 分)

作者 邓俊辉、罗必成 单位 清华大学 代码长度限制 16 KB 时间限制 250 ms 内存限制
64 MB

2010年风靡全球的“水果忍者”游戏，想必大家肯定都玩过吧？（没玩过也没关系啦~）在游戏当中，画面里会随机地弹射出一系列的水果与炸弹，玩家尽可能砍掉所有的水果而避免砍中炸弹，就可以完成游戏规定的任务。如果玩家可以一刀砍下画面当中一连串的水果，则会有额外的奖励，如图1所示。

** 图 1
**
现在假如你是“水果忍者”游戏的玩家，你要做的一件事情就是，将画面当中的水果一刀砍下。这个问题看上去有些复杂，让我们把问题简化一些。我们将游戏世界想象成一个二维的平面。游戏当中的每个水果被简化成一条一条的垂直于水平线的竖直线段。而一刀砍下我们也仅考虑成能否找到一条直线，使之可以穿过所有代表水果的线段。

** 图 2
**
如图2所示，其中绿色的垂直线段表示的就是一个一个的水果；灰色的虚线即表示穿过所有线段的某一条直线。可以从上图当中看出，对于这样一组线段的排列，我们是可以找到一刀切开所有水果的方案的。

另外，我们约定，如果某条直线恰好穿过了线段的端点也表示它砍中了这个线段所表示的水果。假如你是这样一个功能的开发者，你要如何来找到一条穿过它们的直线呢？

输入格式：

输入在第一行给出一个正整数N（≤ 104
），表示水果的个数。随后N行，每行给出三个整数x、y1 、y2
，其间以空格分隔，表示一条端点为(x, y1 )和

(x, y2 )的水果，其中y1 > y2
。注意：给出的水果输入集合一定存在一条可以将其全部穿过的直线，不需考虑不存在的情况。坐标为区间

[−106 , 106 ) 内的整数。

输出格式：

在一行中输出穿过所有线段的直线上具有整数坐标的任意两点p1(x1, y1
)和p2(x2, y2 )，格式为 x1 y1

裁判程序判定，但一定存在四个坐标全是整数的解。

输入样例：

5

-30 -52 -84 38 22 -49

-99 -22 -99 48 59 -18

-36 -50 -72

输出样例：

-99 -99 -30 -52

L3-013 非常弹的球 (30 分)

x2 y2 。注意：本题答案不唯一，由特殊

作者 俞勇 单位 上海交通大学 代码长度限制 16 KB 时间限制 150 ms 内存限制 64 MB

刚上高一的森森为了学好物理，买了一个“非常弹”的球。虽然说是非常弹的球，其实也就是一般的弹力球而已。森森玩了一会儿弹力球后突然想到，
假如他在地上用力弹球，球最远能弹到多远去呢？他不太会，你能帮他解决吗？当然为了刚学习物理的森森，我们对环境做一些简化：

假设森森是一个质点，以森森为原点设立坐标轴，则森森位于(0,
0)点。小球质量为w/100 千克（kg），重力加速度为9.8米/秒平方（m/s2）。

森森在地上用力弹球的过程可简化为球从(0, 0)点以某个森森选择的角度ang (0 <
ang < π/2) 向第一象限抛出，抛出时假设动能为1000 焦耳

（J）。

小球在空中仅受重力作用，球纵坐标为0时可视作落地，落地时损失p%动能并反弹。地面可视为刚体，忽略小球形状、空气阻力及摩擦阻力等。

森森为你准备的公式：

动能公式：E = m × v2/2 牛顿力学公式：F = m × a 重力：G = m × g

其中：

E - 动能，单位为“焦耳” m - 质量，单位为“千克” v - 速度，单位为“米/秒”

a - 加速度，单位为“米/秒平方”

g - 重力加速度

输入格式：

输入在一行中给出两个整数：1 ≤ w ≤ 1000 和 1 ≤ p ≤
100，分别表示放大100倍的小球质量、以及损失动力的百分比p。

输出格式：

在一行输出最远的投掷距离，保留3位小数。

输入样例：

100 90

输出样例：

226.757

L3-014 周游世界 (30 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 200 ms 内存限制 64 MB

周游世界是件浪漫事，但规划旅行路线就不一定了……
全世界有成千上万条航线、铁路线、大巴线，令人眼花缭乱。所以旅行社会选择部分运输公司组成联盟，每家公司提供一条线路，然后帮助客户规划由联盟内企业支持的旅行路线。本题就要求你帮旅行社实现一个自动规划路线的程序，使得对任何给定的起点和终点，可以找出最顺畅的路线。所谓“最顺畅”，首先是指中途经停站最少；如果经停站一样多，则取需要换乘线路次数最少的路线。

输入格式：

输入在第一行给出一个正整数N （≤ 100），即联盟公司的数量。接下来有N
行，第i行（i = 1, ⋯ , N ）描述了第i家公司所提供的线路。格式为：

M S[1] S[2] ⋯ S[M ]

其中M （≤ 100）是经停站的数量，S[i]（i = 1, ⋯ , M
）是经停站的编号（由4位0-9的数字组成）。这里假设每条线路都是简单的一条可以双向运行的链路，并且输入保证是按照正确的经停顺序给出的
—— 也就是说，任意一对相邻的S[i]和S[i + 1]（i = 1, ⋯ , M −
1）之间都不存在其他经停站点。我们称相邻站点之间的线路为一个运营区间，每个运营区间只承包给一家公司。环线是有可能存在的，但不会不经停任何中间站点就从出发地回到出发地。当然，不同公司的线路是可能在某些站点有交叉的，这些站点就是客户的换乘点，我们假设任意换乘点涉及的不同公司的线路都不超过5

条。

在描述了联盟线路之后，题目将给出一个正整数K（≤
10），随后K行，每行给出一位客户的需求，即始发地的编号和目的地的编号，中间以一空格分隔。

输出格式：

处理每一位客户的需求。如果没有现成的线路可以使其到达目的地，就在一行中输出“Sorry,
no line is
available.”；如果目的地可达，则首先在一行中输出最顺畅路线的经停站数量（始发地和目的地不包括在内），然后按下列格式给出旅行路线：

Go by the line of company #X1 from S1 to S2. Go by the line of company #X2
from S2 to S3.

…

其中Xi是线路承包公司的编号，Si是经停站的编号。但必须只输出始发地、换乘点和目的地，不能输出中间的经停站。题目保证满足要求的路线是唯一的。

输入样例：

4

7 1001 3212 1003 1204 1005 1306 7797

9 9988 2333 1204 2006 2005 2004 2003 2302 2001

13 3011 3812 3013 3001 1306 3003 2333 3066 3212 3008 2302 3010 3011

4 6666 8432 4011 1306

4

3011 3013

6666 2001

2004 3001

2222 6666

输出样例：

2

Go by the line of company #3 from 3011 to 3013. 10

Go by the line of company #4 from 6666 to 1306. Go by the line of company #3
from 1306 to 2302. Go by the line of company #2 from 2302 to 2001. 6

Go by the line of company #2 from 2004 to 1204. Go by the line of company #1
from 1204 to 1306. Go by the line of company #3 from 1306 to 3001. Sorry, no
line is available.

L3-015 球队“食物链” (30 分)

作者 李文新 单位 北京大学 代码长度限制 16 KB 时间限制 2000 ms 内存限制 128 MB

某国的足球联赛中有N 支参赛球队，编号从1至N
。联赛采用主客场双循环赛制，参赛球队两两之间在双方主场各赛一场。

联赛战罢，结果已经尘埃落定。此时，联赛主席突发奇想，希望从中找出一条包含所有球队的“食物链”，来说明联赛的精彩程度。“食物链”为一个

1至N 的排列{ T1 T2 ⋯ TN }，满足：球队T1 战胜过球队T2 ，球队T2
战胜过球队T3 ，⋯，球队T(N −1) 战胜过球队TN ，球队TN 战胜过球队T1 。

现在主席请你从联赛结果中找出“食物链”。若存在多条“食物链”，请找出字典序最小的。

注：排列{ a1 a2 ⋯ aN }在字典序上小于排列{ b1 b2 ⋯ bN
}，当且仅当存在整数K（1 ≤ K ≤ N ），满足：aK < bK
且对于任意小于K的正整数

i，ai = bi。

输入格式：

输入第一行给出一个整数N （2 ≤ N ≤ 20），为参赛球队数。随后N 行，每行N
个字符，给出了N × N
的联赛结果表，其中第i行第j列的字符为球队i在主场对阵球队j的比赛结果：W表示球队i战胜球队j，L表示球队i负于球队j，D表示两队打平，-表示无效（当i
= j时）。输入中无多余空格。

输出格式：

按题目要求找到“食物链”T1 T2 ⋯ TN ，将这N
个数依次输出在一行上，数字间以1个空格分隔，行的首尾不得有多余空格。若不存在“食物链”，
输出“No Solution”。

输入样例1：

5

-LWDW W-LDW WW-LW DWW-W DDLW-

输出样例1：

1 3 5 4 2

输入样例2：

5

-WDDW D-DWL DD-DW DDW-D DDDD-

输出样例2：

No Solution

L3-016 二叉搜索树的结构 (30 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

二叉搜索树或者是一棵空树，或者是具有下列性质的二叉树：
若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉搜索树。（摘自百度百科）

给定一系列互不相等的整数，将它们顺次插入一棵初始为空的二叉搜索树，然后对结果树的结构进行描述。你需要能判断给定的描述是否正确。例如将

{ 2 4 1 3 0
}插入后，得到一棵二叉搜索树，则陈述句如“2是树的根”、“1和4是兄弟结点”、“3和0在同一层上”（指自顶向下的深度相同）、“2
是4的双亲结点”、“3是4的左孩子”都是正确的；而“4是2的左孩子”、“1和3是兄弟结点”都是不正确的。

输入格式：

输入在第一行给出一个正整数N （≤ 100），随后一行给出N
个互不相同的整数，数字间以空格分隔，要求将之顺次插入一棵初始为空的二叉搜索树。之后给出一个正整数M
（≤ 100），随后M 行，每行给出一句待判断的陈述句。陈述句有以下6种：

A is the root，即"A是树的根"；

A and B are siblings，即"A和B是兄弟结点"； A is the parent of
B，即"A是B的双亲结点"；

A is the left child of B，即"A是B的左孩子"； A is the right child of
B，即"A是B的右孩子"；

A and B are on the same level，即"A和B在同一层上"。

题目保证所有给定的整数都在整型范围内。

输出格式：

对每句陈述，如果正确则输出Yes，否则输出No，每句占一行。

输入样例：

5

2 4 1 3 0

8

2 is the root

1 and 4 are siblings

3 and 0 are on the same level 2 is the parent of 4

3 is the left child of 4 1 is the right child of 2

4 and 0 are on the same level 100 is the right child of 3

输出样例：

Yes Yes Yes Yes Yes No No No

L3-017 森森快递 (30 分)

作者 俞勇 单位 上海交通大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

森森开了一家快递公司，叫森森快递。因为公司刚刚开张，所以业务路线很简单，可以认为是一条直线上的N
个城市，这些城市从左到右依次从0到

(N − 1)编号。由于道路限制，第i号城市（i = 0, ⋯ , N − 2）与第(i +
1)号城市中间往返的运输货物重量在同一时刻不能超过Ci公斤。

公司开张后很快接到了Q张订单，其中j张订单描述了某些指定的货物要从Sj
号城市运输到Tj
号城市。这里我们简单地假设所有货物都有无限货源，森森会不定时地挑选其中一部分货物进行运输。安全起见，这些货物不会在中途卸货。

为了让公司整体效益更佳，森森想知道如何安排订单的运输，能使得运输的货物重量最大且符合道路的限制？要注意的是，发货时间有可能是任何时刻，所以我们安排订单的时候，必须保证共用同一条道路的所有货车的总重量不超载。例如我们安排1号城市到4号城市以及2号城市到4号城市两张订单的运输，则这两张订单的运输同时受2-3以及3-4两条道路的限制，因为两张订单的货物可能会同时在这些道路上运输。

输入格式：

输入在第一行给出两个正整数N 和Q（2 ≤ N ≤ 105 , 1 ≤ Q ≤ 105
），表示总共的城市数以及订单数量。

第二行给出(N − 1)个数，顺次表示相邻两城市间的道路允许的最大运货重量Ci（i =
0, ⋯ , N − 2）。题目保证每个Ci是不超过231
的非负整数。接下来Q行，每行给出一张订单的起始及终止运输城市编号。题目保证所有编号合法，并且不存在起点和终点重合的情况。

输出格式：

在一行中输出可运输货物的最大重量。

输入样例：

10 6

0 7 8 5 2 3 1 9 10

0 9

1 8

2 7

6 3

4 5

4 2

输出样例：

7

**样例提示：**我们选择执行最后两张订单，即把5公斤货从城市4运到城市2，并且把2公斤货从城市4运到城市5，就可以得到最大 运输量7公斤。

L3-018 森森美图 (30 分)

作者 戴龙翱、朱建科 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制
64 MB

森森最近想让自己的朋友圈熠熠生辉，所以他决定自己写个美化照片的软件，并起名为森森美图。众所周知，在合照中美化自己的面部而不美化合照者的面部是让自己占据朋友圈高点的绝好方法，因此森森美图里当然得有这个功能。
这个功能的第一步是将自己的面部选中。森森首先计算出了一个图像中所有像素点与周围点的相似程度的分数，分数越低表示某个像素点越“像”一个轮廓边缘上的点。
森森认为，任意连续像素点的得分之和越低，
表示它们组成的曲线和轮廓边缘的重合程度越高。为了选择出一个完整的面部，森森决定让用户选择面部上的两个像素点A和B，则连接这两个点的直线就将图像分为两部分，然后在这两部分中分别寻找一条从A到B且与轮廓重合程度最高的曲线，就可以拼出用户的面部了。
然而森森计算出来得分矩阵后，突然发现自己不知道怎么找到这两条曲线了，你能帮森森当上朋友圈的小王子吗？

为了解题方便，我们做出以下补充说明：

图像的左上角是坐标原点(0,0)，我们假设所有像素按矩阵格式排列，其坐标均为非负整数（即横轴向右为正，纵轴向下为正）。

忽略正好位于连接A和B的直线（注意不是线段）上的像素点，即不认为这部分像素点在任何一个划分部分上，因此曲线也不能经过这部分像素点。

曲线是八连通的（即任一像素点可与其周围的8个像素连通），但为了计算准确，某像素连接对角相邻的斜向像素时，得分额外增加两个像素分数和的$\sqrt{2}$倍减一。例如样例中，经过坐标为(3,1)和(4,2)的两个像素点的曲线，其得分应该是这两个像素点的分数和(2+2)，再加上额外的(2+2)乘以( − 1)，即约为5.66。

输入格式：

输入在第一行给出两个正整数N 和M （5 ≤ N , M ≤
100），表示像素得分矩阵的行数和列数。接下来N 行，每行M
个不大于1000的非负整数，即为像素点的分值。

最后一行给出用户选择的起始和结束像素点的坐标(Xstart, Ystart)和(Xend,
Yend )。4个整数用空格分隔。

输出格式：

在一行中输出划分图片后找到的轮廓曲线的得分和，保留小数点后两位。注意起点和终点的得分不要重复计算。

输入样例：

6 6

9 0 1 9 9 9

9 9 1 2 2 9

9 9 2 0 2 9

9 9 1 1 2 9

9 9 3 3 1 1

9 9 9 9 9 9

2 1 5 4

输出样例：

27.04

L3-019 代码排版 (30 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 150 ms 内存限制 64 MB

某编程大赛中设计有一个挑战环节，选手可以查看其他选手的代码，发现错误后，提交一组测试数据将对手挑落马下。为了减小被挑战的几率，有些选手会故意将代码写得很难看懂，比如把所有回车去掉，提交所有内容都在一行的程序，令挑战者望而生畏。

为了对付这种选手，现请你编写一个代码排版程序，将写成一行的程序重新排版。当然要写一个完美的排版程序可太难了，这里只简单地要求处理C语言里的for、while、if-else这三种特殊结构，而将其他所有句子都当成顺序执行的语句处理。输出的要求如下：

默认程序起始没有缩进；每一级缩进是 2 个空格；

每行开头除了规定的缩进空格外，不输出多余的空格；

顺序执行的程序体是以分号“;”结尾的，遇到分号就换行；

在一对大括号“{”和“}”中的程序体输出时，两端的大括号单独占一行，内部程序体每行加一级缩进，即：

{

程序体

}

for的格式为：

for (条件) {

程序体

}

while的格式为：

while (条件) {

程序体

}

if-else的格式为：

if (条件) {

程序体

}

else {

程序体

}

输入格式：

输入在一行中给出不超过 331
个字符的非空字符串，以回车结束。题目保证输入的是一个语法正确、可以正常编译运行的
main 函数模块。

输出格式：

按题面要求的格式，输出排版后的程序。

输入样例：

int main() {int n, i; scanf(“%d”, &n);if( n>0)n++;else if (n<0) n–; else
while(n<10)n++; for(i=0; i<n; i++ ){ printf(“n=%d\n”, n);}return 0; }

输出样例：

int main()

{

int n, i;

scanf(“%d”, &n);

if ( n>0) {

n++;

}

else {

if (n<0) {

n–;

}

else {

while (n<10) {

n++;

}

}

}

for (i=0; i<n; i++ ) {

printf(“n=%d\n”, n);

}

return 0;

}

L3-020 至多删三个字符 (30 分)

作者 曹鹏 单位 Google 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

给定一个全部由小写英文字母组成的字符串，允许你至多删掉其中 3
个字符，结果可能有多少种不同的字符串？

输入格式：

输入在一行中给出全部由小写英文字母组成的、长度在区间 [4, 106 ] 内的字符串。

输出格式：

在一行中输出至多删掉其中 3 个字符后不同字符串的个数。

输入样例：

ababcc

输出样例：

25

** 提示：
**
删掉 0 个字符得到 “ababcc”。

删掉 1 个字符得到 “babcc”, “aabcc”, “abbcc”, “abacc” 和 “ababc”。

删掉 2 个字符得到 “abcc”, “bbcc”, “bacc”, “babc”, “aacc”, “aabc”, “abbc”, “abac”
和 “abab”。

删掉 3 个字符得到 “abc”, “bcc”, “acc”, “bbc”, “bac”, “bab”, “aac”, “aab”, “abb”
和 “aba”。

L3-021 神坛 (30 分)

作者 邓俊辉 单位 清华大学 代码长度限制 16 KB 时间限制 8000 ms 内存限制 64 MB

在古老的迈瑞城，巍然屹立着 n 块神石。长老们商议，选取 3
块神石围成一个神坛。因为神坛的能量强度与它的面积成反比，因此神坛的面积越小越好。特殊地，如果有两块神石坐标相同，或者三块神石共线，神坛的面积为
0.000。

长老们发现这个问题没有那么简单，于是委托你编程解决这个难题。

输入格式：

输入在第一行给出一个正整数 n（3 ≤ n ≤ 5000）。随后 n
行，每行有两个整数，分别表示神石的横坐标、纵坐标（−109 ≤ 横坐标、纵坐标 < 109
）。

输出格式：

在一行中输出神坛的最小面积，四舍五入保留 3 位小数。

输入样例：

8

3 4

2 4

1 1

4 1

0 3

3 0

1 3

4 2

输出样例：

0.500

**样例解释
**
输出的数值等于图中红色或紫色框线的三角形的面积。

** 鸣谢浙江**师范大学伍泰炜补充测试数据！

L3-022 地铁一日游 (30 分)

作者 戴龙翱 单位 杭州百腾教育科技有限公司 代码长度限制 16 KB 时间限制 550 ms
内存限制 64 MB

森森喜欢坐地铁。这个假期，他终于来到了传说中的地铁之城——魔都，打算好好过一把坐地铁的瘾！

魔都地铁的计价规则是：起步价 2 元，出发站与到达站的最短距离（即计费距离）每
K 公里增加 1 元车费。例如取 K = 10，动安寺站离魔都绿桥站为 40 公里，则车费为
2 + 4 = 6 元。

为了获得最大的满足感，森森决定用以下的方式坐地铁：在某一站上车（不妨设为地铁站
A），则对于所有车费相同的到达站，森森只会在计费距离最远的站或线路末端站点出站，然后用森森美图
App 在站点外拍一张认证照，再按同样的方式前往下一个站点。

坐着坐着，森森突然好奇起来：在给定出发站的情况下（在出发时森森也会拍一张照），他的整个旅程中能够留下哪些站点的认证照？

地铁是铁路运输的一种形式，指在地下运行为主的城市轨道交通系统。一般来说，地铁由若干个站点组成，并有多条不同的线路双向行驶，可类比公交车，当两条或更多条线路经过同一个站点时，可进行换乘，更换自己所乘坐的线路。举例来说，魔都
1 号线和 2 号线都经过人民广场站，则乘坐 1 号

线到达人民广场时就可以换乘到 2 号线前往 2
号线的各个站点。换乘不需出站（也拍不到认证照），因此森森乘坐地铁时换乘不受限制。

输入格式:

输入第一行是三个正整数 N、M 和 K，表示魔都地铁有 N 个车站 (1 ≤
N ≤ 200)，M 条线路 (1 ≤ M ≤ 1500)，最短距离每超过 K 公里 (1 ≤
K ≤ 106)，加 1 元车费。

接下来 M 行，每行由以下格式组成：

<站点1><空格><距离><空格><站点2><空格><距离><空格><站点3> …
<站点X-1><空格><距离><空格><站点X>

其中站点是一个 1 到 N
的编号；两个站点编号之间的距离指两个站在该线路上的距离。两站之间距离是一个不大于
106 的正整数。一条线路上的站点互不相同。

注意：两个站之间可能有多条直接连接的线路，且距离不一定相等。

再接下来有一个正整数 Q (1 ≤ Q ≤ 200)，表示森森尝试从 Q 个站点出发。

最后有 Q 行，每行一个正整数 **Xi**，表示森森尝试从编号为 Xi
的站点出发。

输出格式:

对于森森每个尝试的站点，输出一行若干个整数，表示能够到达的站点编号。站点编号从小到大排序。

输入样例:

6 2 6

1 6 2 4 3 1 4

5 6 2 6 6

4

2

3

4

5

输出样例:

1 2 4 5 6

1 2 3 4 5 6

1 2 4 5 6

1 2 4 5 6

L3-023 计算图 (30 分)

作者 陈翔 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

“计算图”（computationalgraph）是现代深度学习系统的基础执行引擎，提供了一种表示任意数学表达式的方法，例如用有向无环图表示的神经网络。
图中的节点表示基本操作或输入变量，边表示节点之间的中间值的依赖性。
例如，下图就是一个函数 f (x1, x2) = ln x1 + x1x2 − sin x2
的计算图。

现在给定一个计算图，请你根据所有输入变量计算函数值及其偏导数（即梯度）。
例如，给定输入x1 = 2, x2 = 5，上述计算图获得函数值f (2, 5) = ln(2) + 2 × 5
− sin(5) = 11.652；并且根据微分链式法则，上图得到的梯度 ∇f = [∂f /∂x1,
∂f /∂x2] = [1/x1 + x2, x1 − cos x2] = [5.500, 1.716]。

知道你已经把微积分忘了，所以这里只要求你处理几个简单的算子：加法、减法、乘法、指数（ex，即编程语言中的
exp(x) 函数）、对数（ln x，即编程语言中的 log(x) 函数）和正弦函数（sin
x，即编程语言中的 sin(x) 函数）。

友情提醒：

常数的导数是 0；x 的导数是 1；ex 的导数还是 ex；ln x 的导数是 1/x；sin
x 的导数是 cos x。

回顾一下什么是偏导数：在数学中，一个多变量的函数的偏导数，就是它关于其中一个变量的导数而保持其他变量恒定。在上面的例子中，当我们对
x1 求偏导数 ∂f /∂x1 时，就将 x2 当成常数，所以得到 ln x1 的导数是
1/x1，x1x2 的导数是 x2，sin x2 的导数是 0。

回顾一下链式法则：复合函数的导数是构成复合这有限个函数在相应点的导数的乘积，即若有
u = f (y)，y = g(x)，则 du/dx = du/dy ⋅

dy/dx。例如对 sin(ln x) 求导，就得到 cos(ln x) ⋅ (1/x)。

如果你注意观察，可以发现在计算图中，计算函数值是一个从左向右进行的计算，而计算偏导数则正好相反。

输入格式：

输入在第一行给出正整数 N （≤ 5 × 104 ），为计算图中的顶点数。

以下 N 行，第 i 行给出第 i 个顶点的信息，其中 i = 0, 1, ⋯ , N −
1。第一个值是顶点的类型编号，分别为：

1. 代表输入变量

   1. 代表加法，对应 x1 + x2

   2. 代表减法，对应 x1 − x2

   3. 代表乘法，对应 x1 × x2

   4. 代表指数，对应 ex

   5. 代表对数，对应 ln x

   6. 代表正弦函数，对应 sin x

对于输入变量，后面会跟它的双精度浮点数值；对于单目算子，后面会跟它对应的单个变量的顶点编号（编号从
0 开始）；对于双目算子，后面会跟它对应两个变量的顶点编号。

题目保证只有一个输出顶点（即没有出边的顶点，例如上图最右边的
-），且计算过程不会超过双精度浮点数的计算精度范围。

输出格式：

首先在第一行输出给定计算图的函数值。在第二行顺序输出函数对于每个变量的偏导数的值，其间以一个空格分隔，行首尾不得有多余空格。偏导数的输出顺序与输入变量的出现顺序相同。输出小数点后
3 位。

输入样例：

7

0 2.0

0 5.0

5 0

3 0 1

6 1

1 2 3

2 5 4

输出样例：

11.652

5.500 1.716

L3-024 Oriol和David (30 分)

作者 李文新 单位 北京大学 代码长度限制 16 KB 时间限制 2000 ms 内存限制 256 MB

Oriol 和 David 在一个边长为 16 单位长度的正方形区域内，初始位置分别为（7,
7）和（8, 8）。现在有 20 组、每组包含 20 个位置需要他们访问， 位置以坐标（x,
y）的形式给出，要求在时间 120 秒内访问尽可能多的点。（x和y均为正整数，且0 ≤ x <
16，0 ≤ y < 16）

注意事项：

针对任意一个位置，Oriol或David中的一人到达即视为访问成功；

Oriol和David必须从第 1 组位置开始访问，且必须访问完第 i
组全部20个位置之后，才可以开始第 i + 1 组 20
个位置的访问。同组间各位置的访问顺序可自由决定；

Oriol和David在完成当前组位置的访问后，无需返回开始位置、可以立即开始下一组位置的访问；
Oriol和David可以向任意方向移动，移动时速率为 2
单位长度/秒；移动过程中，无任何障碍物阻拦。

输入格式:

输入第一行是一个正整数 T (T ≤ 10)，表示数据组数。接下来给出 T 组数据。

对于每组数据，输入包含 20 组，每组 1 行，每行由 20 个坐标组成，每个坐标由 2
个整数 x 和 y 组成，代表 Oriol 和 David 要访问的 20 组 20 个位置的坐标；0 ≤ x <
16，0 ≤ y < 16，均用一个空格隔开。

输出格式:

每组数据输出的第一行是一个整数N，代表分配方案访问过的位置组数；

接下来的N组每组的第一行包含两个整数 Ba 和 Bb，分别代表每组分配方案中 Oriol 和
David 负责访问的位置数，第二行和第三行分别包含 Ba 和 Bb 个整数 i，分别代表 Oriol
和 David 负责访问的位置在组内的序号（从0开始计数）。

0 ≤ N ≤ 20，0 ≤ Ba ≤ 20，0 ≤ Bb ≤ 20，0 ≤ i ≤ 19。

输入样例:

1

5 5 3 13 8 7 13 6 6 11 2 0 1 14 9 15 8 9 3 12 4 6 2 10 2 5 4 9 4 1 15 0 11 4 10
0 15 5 10 14

1 0 14 8 0 7 6 8 4 12 12 8 9 8 10 14 9 4 13 4 9 1 2 1 0 2 11 10 7 15 9 6 13 11 3
5 4 5 10 7

7 3 8 13 15 0 5 4 2 8 7 14 4 13 11 1 8 15 4 5 4 7 7 10 6 7 13 4 6 2 9 13 1 12 10
7 10 5 5 11

5 8 12 12 11 5 12 9 2 2 11 15 5 14 0 0 14 0 2 5 7 3 10 1 2 8 4 2 4 8 9 14 1 11 1
9 15 7 3 3

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

3 11 9 8 12 9 14 10 11 13 5 5 4 11 1 12 13 2 10 14 5 15 10 15 11 0 3 6 7 11 4 9
15 0 12 14 10 10 13 11

10 4 9 12 0 13 6 6 7 10 11 15 6 14 1 2 4 9 8 5 4 0 13 11 5 3 13 3 9 8 2 4 13 14
12 12 14 2 8 15

2 8 4 9 13 10 8 5 2 13 12 6 4 4 10 6 14 13 11 5 12 1 6 0 11 2 8 15 12 4 13 8 8 2
9 7 7 13 0 9

0 0 4 0 2 3 10 2 7 3 9 4 2 13 11 11 1 8 11 15 11 2 8 11 10 15 7 9 13 15 15 10 1
2 11 9 14 6 5 5

2 13 6 8 7 14 8 5 15 14 5 6 4 10 14 12 3 14 0 5 4 1 0 14 13 14 12 5 5 9 1 2 2 12
4 8 1 15 7 11

10 5 15 7 6 8 11 10 7 13 14 0 12 2 9 12 4 5 3 8 8 13 7 12 15 15 12 9 15 6 14 3 9
6 15 12 7 9 4 15

0 10 6 2 3 2 6 3 14 6 10 13 3 10 15 9 10 0 7 0 14 15 1 2 13 9 11 11 10 3 6 13 0
14 11 2 9 8 15 5

3 9 13 11 1 1 0 9 5 4 4 9 4 13 10 1 12 11 4 2 0 4 1 7 4 10 4 0 2 1 2 0 13 2 11
10 0 5 15 3

15 11 8 1 12 5 8 5 7 5 7 7 2 4 0 4 7 3 12 6 9 15 5 12 14 11 15 10 8 11 4 10 4 14
13 10 4 4 2 12

9 12 15 13 0 12 0 14 3 1 10 15 15 11 1 12 3 0 5 2 15 10 8 4 9 1 8 0 1 13 2 7 12
13 14 10 6 0 13 15

13 7 14 15 9 4 8 2 7 3 7 11 2 13 5 0 13 5 4 0 12 2 3 2 11 15 9 2 9 7 3 7 4 5 14
5 14 12 9 13

12 11 2 14 2 6 6 12 5 15 13 11 2 0 9 13 7 1 7 11 4 4 2 10 0 8 5 3 6 13 2 7 2 15
6 8 3 5 8 11

12 5 9 9 4 14 3 2 14 2 2 1 9 11 8 10 2 14 12 15 0 13 4 7 0 0 0 6 0 1 4 13 4 3 3
10 15 2 10 10

11 15 8 5 6 15 9 8 2 7 15 14 1 10 14 6 13 6 0 15 4 1 3 12 7 8 12 4 0 10 7 10 0
14 13 5 11 1 15 6

1 12 13 14 6 12 9 0 6 8 3 15 5 4 4 2 15 10 3 6 13 12 8 4 15 3 1 5 7 1 6 14 8 6 2
6 11 3 4 4

输出样例:

2

10 10

1 2 3 4 5 6 7 8 9 0

11 12 13 14 15 16 17 18 19 10

1 19

1

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

注意：样例只代表格式，不具有特别含义。

评分方式：

本题按照你给出的方案的优良程度评定分数。具体评分规则如下：

本题所有数据点输入均为一样的数据；

评分时，假定输入有 X 组数据，则你的评分答案为你的程序在所有 X
组数据中答案的平均值； 例如，你对 3 组数据，分别访问了 3 个、5 个、8
个点，则你的评分答案为 5.33333…

特别的，如果你输出的答案中有任意一组不合法，则你的评分答案恒定为 0；
输出方案行走超过 120 秒仍然合法，答案计算时只计算 120 秒内的部分；

评测时，从 0
开始的测试点的标准答案依次增大，只有评分答案超过标准答案时，你才可以得到对应测试点的分数。

不合法的情况如下：

输出格式不正确；

重复访问自己已访问的点；（但可以经过） 访问不存在的点。

部分评分标准答案如下：

第 0 号点：20；（即需要访问平均 20 个点才可以获得该点分数）

第 1 号点：70；（同上）

第 2 号点：90；

第 7 号点：150。

L1-4 冠军魔术 (10 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

2018年FISM（世界魔术大会）近景总冠军简纶廷的表演中有一个情节：以桌面上一根带子为界，当他将纸牌从带子的一边推到另一边时，纸牌会变成硬币；把硬币推回另一边会变成纸牌。

这里我们假设纸牌会变成等量的硬币，而硬币变成纸牌时，纸牌的数量会加倍。那么给定纸牌的初始数量，当他来回推了
N 次（来/回各算一次）后， 手里拿的是纸牌还是硬币？数量是多少？

输入格式：

输入在一行里给出两个正整数，分别是纸牌的初始数量和魔术师推送的次数。这里假设初始状态下魔术师手里全是纸牌。

输出格式：

如果最后魔术师手里是纸牌，输出 0 和纸牌数量；如果是硬币，则输出 1
和硬币数量。数字间须有 1 个空格。题目保证结果数值不超出整型范围（即

231 − 1）。

**输入样例 **1：

3 7

**输出样例 **1：

1 24

**输入样例 **2：

8 4

**输出样例 **2：

0 32

L1-5 判断题 (15 分)

作者 CHEN, Yue 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

判断题的评判很简单，本题就要求你写个简单的程序帮助老师判题并统计学生们判断题的得分。

输入格式：

输入在第一行给出两个不超过 100 的正整数 N 和
M，分别是学生人数和判断题数量。第二行给出 M 个不超过 5
的正整数，是每道题的满分值。第三行给出每道题对应的正确答案，0 代表“非”，1
代表“是”。随后 N 行，每行给出一个学生的解答。数字间均以空格分隔。

输出格式：

按照输入的顺序输出每个学生的得分，每个分数占一行。

输入样例：

3 6

2 1 3 3 4 5

0 0 1 0 1 1

0 1 1 0 0 1

1 0 1 0 1 0

1 1 0 0 1 1

输出样例：

13

11

12

L1-6 检查密码 (15 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

本题要求你帮助某网站的用户注册模块写一个密码合法性检查的小功能。该网站要求用户设置的密码必须由不少于6个字符组成，并且只能有英文字母、数字和小数点
.，还必须既有字母也有数字。

输入格式：

输入第一行给出一个正整数 N（≤ 100），随后 N
行，每行给出一个用户设置的密码，为不超过 80 个字符的非空字符串，以回车结束。

注意： 题目保证不存在只有小数点的输入。

输出格式：

对每个用户的密码，在一行中输出系统反馈信息，分以下5种： 如果密码合法，输出Your
password is wan mei.；

如果密码太短，不论合法与否，都输出Your password is tai duan le.；

如果密码长度合法，但存在不合法字符，则输出Your password is tai luan le.；
如果密码长度合法，但只有字母没有数字，则输出Your password needs shu zi.；
如果密码长度合法，但只有数字没有字母，则输出Your password needs zi mu.。

输入样例：

5

123s

zheshi.wodepw 1234.5678

WanMei23333 pass*word.6

输出样例：

Your password is tai duan le. Your password needs shu zi. Your password needs zi
mu.

Your password is wan mei. Your password is tai luan le.

L1-7 谷歌的招聘 (20 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 200 ms 内存限制 64 MB

2004 年 7 月，谷歌在硅谷的 101
号公路边竖立了一块巨大的广告牌（如下图）用于招聘。内容超级简单，就是一个以 .com
结尾的网址，而前面的网址是一个 10 位素数，这个素数是自然常数 e 中最早出现的 10
位连续数字。能找出这个素数的人，就可以通过访问谷歌的这个网站进入招聘流程的下一步。

自 然 常 数 e 是 一 个 著 名 的 超 越 数 ， 前 面 若 干 位 写 出 来 是 这 样 的：e =
2.7182818284590452353602874713526624977572470936999595749669676277240766303535475945713821785251664274274663919320

其中粗体标出的 10 位数就是答案。

本题要求你编程解决一个更通用的问题：从任一给定的长度为 L
的数字中，找出最早出现的 K 位连续数字所组成的素数。

输入格式：

输入在第一行给出 2 个正整数，分别是 L（不超过 1000 的正整数，为数字长度）和
K（小于 10 的正整数）。接下来一行给出一个长度为 L 的正整数N。

输出格式：

在一行中输出 N 中最早出现的 K
位连续数字所组成的素数。如果这样的素数不存在，则输出
404。注意，原始数字中的前导零也计算在位数之内。例如在 200236 中找 4 位素数，0023
算是解；但第一位 2 不能被当成 0002 输出，因为在原始数字中不存在这个 2 的前导零。

**输入样例 **1：

20 5

23654987725541023819

**输出样例 **1：

49877

**输入样例 **2：

10 3

2468001680

**输出样例 **2：

404

** 鸣谢用户** 大冰 补充数据！

L2-1 出栈序列的合法性 (25 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

给定一个最大容量为 M 的堆栈，将 N 个数字按 1, 2, 3, …, N
的顺序入栈，允许按任何顺序出栈，则哪些数字序列是不可能得到的？例如给定 M =

5、N = 7，则我们有可能得到{ 1, 2, 3, 4, 5, 6, 7 }，但不可能得到{ 3, 2, 1, 7,
5, 6, 4 }。

输入格式：

输入第一行给出 3 个不超过 1000 的正整数：M （堆栈最大容量）、N
（入栈元素个数）、K（待检查的出栈序列个数）。最后 K 行，每行给出 N

个数字的出栈序列。所有同行数字以空格间隔。

输出格式：

对每一行出栈序列，如果其的确是有可能得到的合法序列，就在一行中输出YES，否则输出NO。

输入样例：

5 7 5

1 2 3 4 5 6 7

3 2 1 7 5 6 4

7 6 5 4 3 2 1

5 6 4 3 7 2 1

1 7 6 5 4 3 2

输出样例：

YES NO NO YES NO

L2-3 二叉搜索树的2层结点统计 (25 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

二叉搜索树或者是一棵空树，或者是具有下列性质的二叉树：若它的左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也分别为二叉搜索树。

将一系列数字按给定顺序插入一棵初始为空的二叉搜索树，你的任务是统计结果树中最下面
2 层的结点数。

输入格式：输入在第一行给出一个正整数 N (≤ 1000)，为插入数字的个数。第二行给出
N 个 [−1000, 1000]
区间内的整数。数字间以空格分隔。输出格式：在一行中输出最下面 2 层的结点总数。

输入样例：9 25 30 42 16 20 20 35 -5 28 输出样例：6

L1-1 嫑废话上代码 (5 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

Linux 之父 Linus Torvalds 的名言是：“Talk is cheap. Show me the
code.”（嫑废话，上代码）。本题就请你直接在屏幕上输出这句话。

输入格式： 本题没有输入。输出格式：

在一行中输出 Talk is cheap. Show me the code.。

输入样例：

无

输出样例：

Talk is cheap. Show me the code.

L1-2 猫是液体 (5 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

测量一个人的体积是很难的，但猫就不一样了。因为猫是液体，所以可以很容易地通过测量一个长方体容器的容积来得到容器里猫的体积。本题就请你完成这个计算。

输入格式：

输入在第一行中给出 3 个不超过 100 的正整数，分别对应容器的长、宽、高。

输出格式：

在一行中输出猫的体积。

输入样例：

23 15 20

输出样例：

6900

L1-3 洛希极限 (10 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

科幻电影《流浪地球》中一个重要的情节是地球距离木星太近时，大气开始被木星吸走，而随着不断接近地木“刚体洛希极限”，地球面临被彻底撕碎的危险。但实际上，这个计算是错误的。

洛希极限（Roche
limit）是一个天体自身的引力与第二个天体造成的潮汐力相等时的距离。当两个天体的距离少于洛希极限，天体就会倾向碎散，继而成为第二个天体的环。它以首位计算这个极限的人爱德华·洛希命名。（摘自百度百科）

大天体密度与小天体的密度的比值开 3
次方后，再乘以大天体的半径以及一个倍数（流体对应的倍数是 2.455，刚体对应的倍数是
1.26），就是洛希极限的值。例如木星与地球的密度比值开 3 次方是
0.622，如果假设地球是流体，那么洛希极限就是 0.622 × 2.455 = 1.52701
倍木星半径；但地

球是刚体，对应的洛希极限是 0.622 × 1.26 = 0.78372
倍木星半径，这个距离比木星半径小，即只有当地球位于木星内部的时候才会被撕碎，换言之，就是地球不可能被撕碎。

本题就请你判断一个小天体会不会被一个大天体撕碎。

输入格式：

输入在一行中给出 3 个数字，依次为：大天体密度与小天体的密度的比值开 3
次方后计算出的值（≤ 1）、小天体的属性（0 表示流体、1
表示刚体）、两个天体的距离与大天体半径的比值（> 1 但不超过 10）。

输出格式：

在一行中首先输出小天体的洛希极限与大天体半径的比值（输出小数点后2位）；随后空一格；最后输出
^_^ 如果小天体不会被撕碎，否则输出 T_T。

**输入样例 **1：

0.622 0 1.4

**输出样例 **1：

1.53 T_T

**输入样例 **2：

0.622 1 1.4

**输出样例 **2：

0.78 ^_^

调和平均 (10 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

N 个正数的算数平均是这些数的和除以 N
，它们的调和平均是它们倒数的算数平均的倒数。本题就请你计算给定的一系列正数的调和平均值。

输入格式：

每个输入包含 1 个测试用例。每个测试用例第 1 行给出正整数 N (≤ 1000)；第 2
行给出 N 个正数，都在区间 [0.1, 100] 内。

输出格式：

在一行中输出给定数列的调和平均值，输出小数点后2位。

输入样例：

8

10 15 12.7 0.3 4 13 1 15.6

输出样例：

1.61

胎压监测 (15 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

小轿车中有一个系统随时监测四个车轮的胎压，如果四轮胎压不是很平衡，则可能对行车造成严重的影响。

让我们把四个车轮 —— 左前轮、右前轮、右后轮、左后轮 —— 顺次编号为
1、2、3、4。本题就请你编写一个监测程序，随时监测四轮的胎压，并给出正确的报警信息。报警规则如下：

如果所有轮胎的压力值与它们中的最大值误差在一个给定阈值内，并且都不低于系统设定的最低报警胎压，则说明情况正常，不报警；

如果存在一个轮胎的压力值与它们中的最大值误差超过了阈值，或者低于系统设定的最低报警胎压，则不仅要报警，而且要给出可能漏气的轮胎的准确位置；

如果存在两个或两个以上轮胎的压力值与它们中的最大值误差超过了阈值，或者低于系统设定的最低报警胎压，则报警要求检查所有轮胎。

输入格式：

输入在一行中给出 6 个 [0, 400] 范围内的整数，依次为 1~4
号轮胎的胎压、最低报警胎压、以及胎压差的阈值。

输出格式：

根据输入的胎压值给出对应信息： 如果不用报警，输出 Normal；

如果有一个轮胎需要报警，输出 Warning: please check #X!，其中 X
是出问题的轮胎的编号；

如果需要检查所有轮胎，输出 Warning: please check all the tires!。

**输入样例 **1：

242 251 231 248 230 20

**输出样例 **1：

Normal

**输入样例 **2：

242 251 232 248 230 10

**输出样例 **2：

Warning: please check #3!

**输入样例 **3：

240 251 232 248 240 10

**输出样例 **3：

Warning: please check all the tires!

吃火锅 (15 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

以上图片来自微信朋友圈：这种天气你有什么破事打电话给我基本没用。但是如果你说“吃火锅”，那就厉害了，我们的故事就开始了。本题要求你实现一个程序，自动检查你朋友给你发来的信息里有没有
chi1 huo3 guo1。

输入格式：

输入每行给出一句不超过 80
个字符的、以回车结尾的朋友信息，信息为非空字符串，仅包括字母、数字、空格、可见的半角标点符号。当读到某一行只有一个英文句点
. 时，输入结束，此行不算在朋友信息里。

输出格式：

首先在一行中输出朋友信息的总条数。然后对朋友的每一行信息，检查其中是否包含 chi1
huo3 guo1，并且统计这样厉害的信息有多少条。在第二行中首先输出第一次出现 chi1
huo3 guo1 的信息是第几条（从 1
开始计数），然后输出这类信息的总条数，其间以一个空格分隔。题目保证输出的所有数字不超过
100。

如果朋友从头到尾都没提 chi1 huo3 guo1 这个关键词，则在第二行输出一个表情 -_-#。

**输入样例 **1：

Hello!

are you there?

wantta chi1 huo3 guo1? that’s so li hai le

our story begins from chi1 huo3 guo1 le

.

**输出样例 **1：

5

3 2

**输入样例 **2：

Hello!

are you there?

wantta qi huo3 guo1 chi1huo3guo1? that’s so li hai le

our story begins from ci1 huo4 guo2 le

.

**输出样例 **2：

5

-_-#

前世档案 (20 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

网络世界中时常会遇到这类滑稽的算命小程序，实现原理很简单，随便设计几个问题，根据玩家对每个问题的回答选择一条判断树中的路径（如下图所示），结论就是路径终点对应的那个结点。

现在我们把结论从左到右顺序编号，编号从 1
开始。这里假设回答都是简单的“是”或“否”，又假设回答“是”对应向左的路径，回答“否”对应向右的路径。给定玩家的一系列回答，请你返回其得到的结论的编号。

输入格式：

输入第一行给出两个正整数：N （≤ 30）为玩家做一次测试要回答的问题数量；M （≤
100）为玩家人数。随后 M 行，每行顺次给出玩家的 N 个回答。这里用 y
代表“是”，用 n 代表“否”。

输出格式：

对每个玩家，在一行中输出其对应的结论的编号。

输入样例：

3 4 yny nyy nyn yyn

输出样例：

3

5

6

2

L1-8 刮刮彩票 (20 分)

作者 DAI, Longao 单位 杭州百腾教育科技有限公司 代码长度限制 16 KB 时间限制 400
ms 内存限制 64 MB

“刮刮彩票”是一款网络游戏里面的一个小游戏。如图所示：

每次游戏玩家会拿到一张彩票，上面会有 9 个数字，分别为数字 1 到数字
9，数字各不重复，并以 3 × 3 的“九宫格”形式排布在彩票上。

在游戏开始时能看见一个位置上的数字，其他位置上的数字均不可见。你可以选择三个位置的数字刮开，这样玩家就能看见四个位置上的数字了。最后玩家再从
3 横、3 竖、2 斜共 8
个方向中挑选一个方向，方向上三个数字的和可根据下列表格进行兑奖，获得对应数额的金币。

** 数字合计** 获得金币 数字合计 获得金币

现在请你写出一个模拟程序，模拟玩家的游戏过程。

输入格式:

输入第一部分给出一张合法的彩票，即用 3 行 3 列给出 0 至 9 的数字。0
表示的是这个位置上的数字初始时就能看见了，而不是彩票上的数字为 0。

第二部给出玩家刮开的三个位置，分为三行，每行按格式 x y
给出玩家刮开的位置的行号和列号（题目中定义左上角的位置为第 1 行、第 1
列。）。数据保证玩家不会重复刮开已刮开的数字。

最后一部分给出玩家选择的方向，即一个整数： 1 至 3
表示选择横向的第一行、第二行、第三行，4 至 6
表示纵向的第一列、第二列、第三列，7、8
分别表示左上到右下的主对角线和右上到左下的副对角线。

输出格式:

对于每一个刮开的操作，在一行中输出玩家能看到的数字。最后对于选择的方向，在一行中输出玩家获得的金币数量。

输入样例:

1 2 3

4 5 6

7 8 0

1 1

2 2

2 3

7

输出样例:

1

5

6

180

简单计算器 (25 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

本题要求你为初学数据结构的小伙伴设计一款简单的利用堆栈执行的计算器。如上图所示，计算器由两个堆栈组成，一个堆栈
S1 存放数字，另一个堆栈 S2
存放运算符。计算器的最下方有一个等号键，每次按下这个键，计算器就执行以下操作：

1. 从 S1 中弹出两个数字，顺序为 n1 和 n2；

   1. 从 S2 中弹出一个运算符 op；

   2. 执行计算 n2 op n1；

   3. 将得到的结果压回 S1。

      直到两个堆栈都为空时，计算结束，最后的结果将显示在屏幕上。

输入格式：

输入首先在第一行给出正整数 N （1 < N ≤ 103 ），为 S1 中数字的个数。

第二行给出 N 个绝对值不超过 100 的整数；第三行给出 N − 1 个运算符 ——
这里仅考虑 +、-、*、/ 这四种运算。一行中的数字和符号都以空格分隔。

输出格式：

将输入的数字和运算符按给定顺序分别压入堆栈 S1 和
S2，将执行计算的最后结果输出。注意所有的计算都只取结果的整数部分。题目保证计算的中间和最后结果的绝对值都不超过
109 。

如果执行除法时出现分母为零的非法操作，则在一行中输出：ERROR: X/0，其中 X
是当时的分子。然后结束程序。

**输入样例 **1：

5

40 5 8 3 2

/ * - +

**输出样例 **1：

2

**输入样例 **2：

5

2 5 8 4 4

* / - +

**输出样例 **2：

ERROR: 5/0

L2-2 口罩发放 (25 分)

作者 DAI, Longao 单位 杭州百腾教育科技有限公司 代码长度限制 16 KB 时间限制 400
ms 内存限制 64 MB

为了抗击来势汹汹的 COVID19
新型冠状病毒，全国各地均启动了各项措施控制疫情发展，其中一个重要的环节是口罩的发放。

某市出于给市民发放口罩的需要，推出了一款小程序让市民填写信息，方便工作的开展。小程序收集了各种信息，包括市民的姓名、身份证、身体情况、提交时间等，但因为数据量太大，需要根据一定规则进行筛选和处理，请你编写程序，按照给定规则输出口罩的寄送名单。

输入格式:

输入第一行是两个正整数 D 和 P （1 ≤ D, P ≤ 30），表示有 D
天的数据，市民两次获得口罩的时间至少需要间隔 P 天。

接下来 D 块数据，每块给出一天的申请信息。第 i 块数据（i = 1, ⋯ ,
D）的第一行是两个整数 Ti 和 Si（1 ≤ Ti, Si ≤ 1000），表示在第 i 天有
Ti 条申请，总共有 Si 个口罩发放名额。随后 Ti
行，每行给出一条申请信息，格式如下：

姓名 身份证号 身体情况 提交时间

给定数据约束如下：

姓名 是一个长度不超过 10 的不包含空格的非空字符串；

身份证号 是一个长度不超过 20 的非空字符串；

身体情况 是 0 或者 1，0 表示自觉良好，1 表示有相关症状；

提交时间 是 hh:mm，为24小时时间（由 00:00 到 23:59。例如
09:08。）。注意，给定的记录的提交时间不一定有序；

身份证号
各不相同，同一个身份证号被认为是同一个人，数据保证同一个身份证号姓名是相同的。

能发放口罩的记录要求如下：

身份证号 必须是 18 位的数字（可以包含前导0）；

同一个身份证号若在第 i 天申请成功，则接下来的 P
天不能再次申请。也就是说，若第 i 天申请成功，则等到第 i + P + 1
天才能再次申请；
在上面两条都符合的情况下，按照提交时间的先后顺序发放，直至全部记录处理完毕或
Si 个名额用完。如果提交时间相同，则按照在列表中出现的先后顺序决定。

输出格式:

对于每一天的申请记录，每行输出一位得到口罩的人的姓名及身份证号，用一个空格隔开。顺序按照发放顺序确定。

在输出完发放记录后，你还需要输出有合法记录的、身体状况为 1
的申请人的姓名及身份证号，用空格隔开。顺序按照申请记录中出现的顺序确定，同一个人只需要输出一次。

输入样例:

4 2

5 3

A 123456789012345670 1 13:58 B 123456789012345671 0 13:58 C 12345678901234567 0
13:22 D 123456789012345672 0 03:24 C 123456789012345673 0 13:59

4 3

A 123456789012345670 1 13:58 E 123456789012345674 0 13:59 C 123456789012345673 0
13:59 F F 0 14:00

1 3

E 123456789012345674 1 13:58

1 1

A 123456789012345670 0 14:11

输出样例:

D 123456789012345672 A 123456789012345670 B 123456789012345671 E
123456789012345674 C 123456789012345673 A 123456789012345670 A
123456789012345670 E 123456789012345674

样例解释：

输出中，第一行到第三行是第一天的部分；第四、五行是第二天的部分；第三天没有符合要求的市民；第六行是第四天的部分。最后两行按照出现顺序输出了可能存在身体不适的人员。

完全二叉树的层序遍历 (25 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是完美二叉树。对于深度为
D 的，有 N 个结点的二叉树，若其结点对应于相同深度完美二叉树的层序遍历的前
N 个结点，这样的树就是完全二叉树。

给定一棵完全二叉树的后序遍历，请你给出这棵树的层序遍历结果。

输入格式：

输入在第一行中给出正整数 N （≤
30），即树中结点个数。第二行给出后序遍历序列，为 N 个不超过 100
的正整数。同一行中所有数字都以空格分隔。

输出格式：

在一行中输出该树的层序遍历序列。所有数字都以 1
个空格分隔，行首尾不得有多余空格。

输入样例：

8

91 71 2 34 10 15 55 18

输出样例：

18 34 55 71 2 10 15 91

L2-4 网红点打卡攻略 (25 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

一个旅游景点，如果被带火了的话，就被称为“网红点”。大家来网红点游玩，俗称“打卡”。在各个网红点打卡的快（省）乐（钱）方法称为“攻略”。你的任务就是从一大堆攻略中，找出那个能在每个网红点打卡仅一次、并且路上花费最少的攻略。

输入格式：

首先第一行给出两个正整数：网红点的个数 N （1 < N ≤
200）和网红点之间通路的条数 M 。随后 M
行，每行给出有通路的两个网红点、以及这条路上的旅行花费（为正整数），格式为“网红点1
网红点2 费用”，其中网红点从 1 到 N
编号；同时也给出你家到某些网红点的花费，格式相同， 其中你家的编号固定为 0。

再下一行给出一个正整数 K，是待检验的攻略的数量。随后 K
行，每行给出一条待检攻略，格式为：

n V1 V2 ⋯ Vn

其中 n(≤ 200) 是攻略中的网红点数，Vi
是路径上的网红点编号。这里假设你从家里出发，从 V1 开始打卡，最后从 Vn 回家。

输出格式：

在第一行输出满足要求的攻略的个数。

在第二行中，首先输出那个能在每个网红点打卡仅一次、并且路上花费最少的攻略的序号（从
1
开始），然后输出这个攻略的总路费，其间以一个空格分隔。如果这样的攻略不唯一，则输出序号最小的那个。

题目保证至少存在一个有效攻略，并且总路费不超过 109 。

输入样例：

6 13

0 5 2

6 2 2

6 0 1

3 4 2

1 5 2

2 5 1

3 1 1

4 1 2

1 6 1

6 3 2

1 2 1

4 5 3

2 0 2

7

6 5 1 4 3 6 2

6 5 2 1 6 3 4

8 6 2 1 6 3 4 5 2

3 2 1 5

6 6 1 3 4 5 2

7 6 2 1 3 4 5 2

6 5 2 1 4 3 6

输出样例：

3

5 11

样例说明：

第 2、3、4、6
条都不满足攻略的基本要求，即不能做到从家里出发，在每个网红点打卡仅一次，且能回到家里。所以满足条件的攻略有
3 条。第 1 条攻略的总路费是：(0->5) 2 + (5->1) 2 + (1->4) 2 + (4->3) 2 +
(3->6) 2 + (6->2) 2 + (2->0) 2 = 14；

第 5 条攻略的总路费同理可算得：1 + 1 + 1 + 2 + 3 + 1 + 2 =
11，是一条更省钱的攻略；

第 7 条攻略的总路费同理可算得：2 + 1 + 1 + 2 + 2 + 2 + 1 = 11，与第 5
条花费相同，但序号较大，所以不输出。

L3-1 那就别担心了 (30 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

下图转自“英式没品笑话百科”的新浪微博 —— 所以无论有没有遇到难题，其实都不用担心。

. I 」V型 工 " 比卜

是的

你能做点

什么吗？

不斛

可以

博主将这种逻辑推演称为“逻辑自洽”，即从某个命题出发的所有推理路径都会将结论引导到同一个最终命题（开玩笑的，千万别以为这是真正的逻辑自洽的定义……）。现给定一个更为复杂的逻辑推理图，本题就请你检查从一个给定命题到另一个命题的推理是否是“逻辑自洽”的，以及存在多少种不同的推理路径。例如上图，从“你遇到难题了吗？”到“那就别担心了”就是一种“逻辑自洽”的推理，一共有
3 条不同的推理路径。

输入格式：

输入首先在一行中给出两个正整数 N （1 < N ≤ 500）和 M
，分别为命题个数和推理个数。这里我们假设命题从 1 到 N 编号。

接下来 M 行，每行给出一对命题之间的推理关系，即两个命题的编号 S1
S2，表示可以从 S1 推出
S2。题目保证任意两命题之间只存在最多一种推理关系，且任一命题不能循环自证（即从该命题出发推出该命题自己）。

最后一行给出待检验的两个命题的编号 A B。

输出格式：

在一行中首先输出从 A 到 B 有多少种不同的推理路径，然后输出 Yes
如果推理是“逻辑自洽”的，或 No 如果不是。题目保证输出数据不超过 109 。

**输入样例 **1：

7 8

7 6

7 4

6 5

4 1

5 2

5 3

2 1

3 1

7 1

**输出样例 **1：

3 Yes

**输入样例 **2：

7 8

7 6

7 4

6 5

4 1

5 2

5 3

6 1

3 1

7 1

**输出样例 **2：

3 No

L3-2 传送门 (30 分)

作者 WENG, Caizhi 单位 浙江大学 代码长度限制 16 KB 时间限制 3500 ms 内存限制
512 MB

平面上有 2n 个点，它们的坐标分别是 (1, 0), (2, 0), ⋯ (n, 0) 和 (1, 109 ),
(2, 109 ), ⋯ , (n, 109 )。我们称这些点中所有 y 坐标为 0 的点为“起点”，所有
y 坐标为 109 的点为终点。一个机器人将从坐标为 (x, 0) 的起点出发向 y
轴正方向移动。显然，该机器人最后会到达某个终点，我们设该终点的 x 坐标为 f
(x)。

在上述条件下，显然有 f (x) =
x。不过这样的数学模型就太无趣了，因此我们对上述数学模型做一些小小的改变。我们将会对模型进行
q 次修改，每一次修改都是以下两种操作之一：

+ x′ x′′ y: 在 (x′, y) 与 (x′′, y)
处增加一对传送门。当机器人碰到其中一个传送门时，它会立刻被传送到另一个传送门处。数据保证进行该操作时，(x′,
y) 与 (x′′, y) 处当前不存在传送门。

- x′ x′′ y: 移除 (x′, y) 与 (x′′, y)
处的一对传送门。数据保证这对传送门存在。

n

求每次修改后 ∑ xf (x) 的值。

x=1

输入格式：

第一行输入两个整数 n 与 q (2 ≤ n ≤ 105 , 1 ≤ q ≤ 105
)，代表起点和终点的数量以及修改的次数。

接下来 q 行中，第 i 行输入一个字符 opi 以及三个整数 x′ , x′′ and yi
(opi ∈ {‘+’ (ascii: 43), ‘-’ (ascii: 45)}, 1 ≤ x′ < x′′ ≤ n, 1 ≤ yi
< 109

i i i i

)，代表第 i 次修改的内容。修改顺序与输入顺序相同。

输出格式：

输出 q 行，其中第 i 行包含一个整数代表第 i 次修改后的答案。

输入样例：

5 4

+ 1 3 1

+ 1 4 3

+ 2 5 2

- 1 4 3

输出样例：

51

48

39

42

样例解释：

修改 f (1) f (2) f (3) f (4) f (5) 结果

L3-3 可怜的复杂度 (30 分)

作者 吉如一 单位 北京大学 代码长度限制 16 KB 时间限制 8000 ms 内存限制 256 MB

可怜有一个数组 A，定义它的复杂度 c(A)
等于它本质不同的子区间个数。举例来说，c([1, 1, 1]) = 3，因为 [1, 1, 1] 只有 3
个本质不同的子区间

[1]、[1, 1] 和 [1, 1, 1]；而 c([1, 2, 1]) = 5，它包含 5 个本质不同的子区间
[1]、[2]、[1, 2]、[2, 1]、[1, 2, 1]。

可怜打算出一道和复杂度相关的题目。众所周知，引入随机性往往可以让一个简单的题目脱胎换骨。现在，可怜手上有一个长度为
n 的正整数数组 x

和一个正整数 m。接着，可怜会独立地随机产生 n 个 [1, m] 中的随机整数
yi，并把 xi 修改为 mxi + yi。

显然，一共有 N = mn 种可能的结果数组。现在，可怜想让你求出这 N
个数组的复杂度的和。

输入格式：

第一行给出一个整数 t (1 ≤ t ≤ 5) 表示数据组数。

对于每组数据，第一行输入两个整数 n 和 m (1 ≤ n ≤ 100, 1 ≤ m ≤ 109
)，第二行是 n 个空格隔开的整数表示数组 x 的初始值 (1 ≤ xi ≤ 109

)。

输出格式：

对于每组数据，输出一行一个整数表示答案。答案可能很大，你只需要输出对 998244353
取模后的结果。

输入样例：

4

3 2

1 1 1

3 2

1 2 1

5 2

1 2 1 2 1

10 2

80582987 187267045 80582987 187267045 80582987 187267045 80582987 187267045
80582987 187267045

输出样例：

36

44

404

44616

考试周 (5 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

考试周快到了，浙江大学的电子屏又调皮了……
本题请你帮小编写一个自动倒计时的程序，对给定的日期（例如“腊八”就对应
8）和倒计时天数（例如电子屏上的“四天之后”就对应 4），自动调整公式里的分母（例如
8/2=4 里面的那个 2）。

输入格式：

输入在一行中给出两个正整数：A 是给定的日期，不超过 30；B
是倒计时天数，不超过 10。

输出格式：

在一行中输出公式 A/X = B，其中 X 是满足等式的数字，输出时保留小数点后 1
位即可。

输入样例：

8 3

输出样例：

8/2.7=3

真的恭喜你 (10 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

当别人告诉你自己考了 x 分的时候，你要回答说：“恭喜你考了 x
分！”比如小明告诉你他考了90分，你就用汉语拼音打出来 gong xi ni kao le 90

fen!。

但是如果小明没考好，比如只考了 20
分，你也“恭喜”人家就不对了。这时候你应该安慰他说：“考了 20
分别泄气！”用汉语拼音写出来就是 kao le 20 fen bie xie qi!。

输入格式：

输入在一行里给出一位小朋友的分数。这个分数是一个 0 到 100 之间的整数。

输出格式：

在一行中输出你对这位小朋友说的话。如果人家考到不低于 90 分，就说 gong xi ni kao
le X fen!；如果不到 90 分，就说 kao le X fen bie xie qi!。其中 X
是小朋友输入的分数。

**输入样例 **1：

95

**输出样例 **1：

gong xi ni kao le 95 fen!

**输入样例 **2：

89

**输出样例 **2：

kao le 89 fen bie xie qi!

Cassels方程 (10 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

Cassels方程是一个在数论界产生了巨大影响的不定方程：x2 + y2 + z2 =
3xyz。该方程有无穷多自然数解。本题并不是要你求解这个方程，只是判断给定的一组
(x, y, z) 是不是这个方程的解。

输入格式：

输入在第一行给出一个不超过 10 的正整数 N ，随后 N 行，每行给出 3 个正整数 0
< x ≤ y ≤ z ≤ 1000。

输出格式：

对于每一组输入，如果是一组解，就在一行中输出 Yes，否则输出 No。

输入样例：

2

1 1 1

5 6 7

输出样例：

Yes No

不变初心数 (15 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

不变初心数是指这样一种特别的数，它分别乘 2、3、4、5、6、7、8、9
时，所得乘积各位数之和却不变。例如 18 就是这样的数：18 的 2 倍是 36，

3+6=9；18 的 3 倍是 54，5+4=9；…… 18 的 9 倍是 162，1+6+2=9。对于 18 而言，9
就是它的初心。本题要求你判断任一个给定的数是否有不变的初心。

输入格式：

输入在第一行中给出一个正整数 N（≤ 100）。随后 N 行，每行给出一个不超过 105
的正整数。

输出格式：

对每个给定的数字，如果它有不变的初心，就在一行中输出它的初心；否则输出 NO。

输入样例：

4

18

256

99792

88672

输出样例：

9

NO 36 NO

编程团体赛 (20 分)

作者 CHEN, Yue 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

编程团体赛的规则为：每个参赛队由若干队员组成；所有队员独立比赛；参赛队的成绩为所有队员的成绩和；成绩最高的队获胜。

现给定所有队员的比赛成绩，请你编写程序找出冠军队。

输入格式：

输入第一行给出一个正整数 N （≤ 104 ），即所有参赛队员总数。随后 N
行，每行给出一位队员的成绩，格式为：队伍编号-队员编号 成绩，其中队伍编号为 1 到
1000 的正整数，队员编号为 1 到 10 的正整数，成绩为 0 到 100 的整数。

输出格式：

在一行中输出冠军队的编号和总成绩，其间以一个空格分隔。注意：题目保证冠军队是唯一的。

输入样例：

6

3-10 99

11-5 87

102-1 0

102-3 100

11-9 89

3-2 61

输出样例：

11 176

三足鼎立 (25 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

当三个国家中的任何两国实力之和都大于第三国的时候，这三个国家互相结盟就呈“三足鼎立”之势，这种状态是最稳定的。

现已知本国的实力值，又给出 n 个其他国家的实力值。我们需要从这 n 个国家中找 2
个结盟，以成三足鼎立。有多少种选择呢？

输入格式：

输入首先在第一行给出 2 个正整数 n（2 ≤ n ≤ 105 ）和 P （≤ 109
），分别为其他国家的个数、以及本国的实力值。随后一行给出 n 个正整数，表示n
个其他国家的实力值。每个数值不超过 109 ，数字间以空格分隔。

输出格式：

在一行中输出本国结盟选择的个数。

输入样例：

7 30

42 16 2 51 92 27 35

输出样例：

9

样例解释：

能联合的另外 2 个国家的 9 种选择分别为：

{16, 27}, {16, 35}, {16, 42}, {27, 35}, {27, 42}, {27, 51}, {35, 42}, {35, 51},
{42, 51}。

这是二叉搜索树吗？ (25 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

一棵二叉搜索树可被递归地定义为具有下列性质的二叉树：对于任一结点，
其左子树中所有结点的键值小于该结点的键值；

其右子树中所有结点的键值大于等于该结点的键值；

其左右子树都是二叉搜索树。

所谓二叉搜索树的“镜像”，即将所有结点的左右子树对换位置后所得到的树。

给定一个整数键值序列，现请你编写程序，判断这是否是对一棵二叉搜索树或其镜像进行前序遍历的结果。

输入格式：

输入的第一行给出正整数 N （≤ 1000）。随后一行给出 N
个整数键值，其间以空格分隔。

输出格式：

如果输入序列是对一棵二叉搜索树或其镜像进行前序遍历的结果，则首先在一行中输出 YES
，然后在下一行输出该树后序遍历的结果。数字间有 1
个空格，一行的首尾不得有多余空格。若答案是否，则输出 NO。

**输入样例 **1：

7

8 6 5 7 10 8 11

**输出样例 **1：

YES

5 7 6 8 11 10 8

**输入样例 **2：

7

8 10 11 8 6 7 5

**输出样例 **2：

YES

11 8 10 7 5 6 8

**输入样例 **3：

7

8 6 8 5 10 9 11

**输出样例 **3：

NO

狼人杀 (30 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 200 ms 内存限制 64 MB

以下文字摘自《灵机一动·好玩的数学》：“狼人杀”游戏分为狼人、好人两大阵营。在一局“狼人杀”游戏中，1号玩家说：“2号是狼人”，2号玩家说：“3号是好人”，3号玩家说：“4号是狼人”，4号玩家说：“5号是好人”，5号玩家说：“4号是好人”。已知这5名玩家中有2人扮演狼人角

色，有2人说的不是实话，有狼人撒谎但并不是所有狼人都在撒谎。扮演狼人角色的是哪两号玩家？

本题是这个问题的升级版：已知 N 名玩家中有 M 人扮演狼人角色，有 L
人说的不是实话，有狼人撒谎但并不是所有狼人都在撒谎。要求你找出扮演狼人角色的是哪几号玩家？

输入格式:

输入在第一行中给出三个正整数 N、M、L，其中 5 ≤ N ≤ 100，2 ≤ M，L < N。随后 N
行，第 i 行给出第 i 号玩家说的话（1 ≤ i ≤
N），即一个玩家编号，用正号表示好人，负号表示狼人。

输出格式:

如果有解，在一行中按递减顺序输出 M
个狼人的编号，其间以空格分隔，行首尾不得有多余空格。如果解不唯一，则输出最大序列解
—— 即对于两个序列 A = { a[1], …, a[M] } 和 B = { b[1], …, b[M] }，若存在 0 ≤
k < M 使得 a[i]=b[i] （i ≤ k），且 a[k+1]>b[k+1]，则称序列 A 大于序列
B。若无解则输出 No Solution。

**输入样例 **1:

5 2 2

-2

+3

-4

+5

+4

**输出样例 **1:

4 1

**输入样例 **2:

6 2 3

-2

+3

-4

+5

+4

-3

**输出样例 **2（解不唯一）:

6 4

**输入样例 **3:

6 2 5

-2

+3

-4

+5

+4

+6

**输出样例 **3:

No Solution

人与神 (5 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

跨界大神 L. Peter Deutsch 有一句名言：“To iterate is human, to recurse
divine.”（迭代的是人，递归的是神）。本题就请你直接在屏幕上输出这句话。

输入格式： 本题没有输入。输出格式：

在一行中输出 To iterate is human, to recurse divine.。

输入样例：

无

输出样例：

To iterate is human, to recurse divine.

两小时学完C语言 (5 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

知乎上有个宝宝问：“两个小时内如何学完 C 语言？”当然，问的是“学完”并不是“学会”。

假设一本 C 语言教科书有 N 个字，这个宝宝每分钟能看 K 个字，看了 M
分钟。还剩多少字没有看？

输入格式：

输入在一行中给出 3 个正整数，分别是 N（不超过 400
000），教科书的总字数；K（不超过 3
000），是宝宝每分钟能看的字数；M（不超过120），是宝宝看书的分钟数。

题目保证宝宝看完的字数不超过 N。

输出格式：

在一行中输出宝宝还没有看的字数。

输入样例：

100000 1000 72

输出样例：

28000

强迫症 (10 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

小强在统计一个小区里居民的出生年月，但是发现大家填写的生日格式不统一，例如有的人写
199808，有的人只写 9808。有强迫症的小强请你写个程序，把所有人的出生年月都整理成
年年年年-月月 格式。对于那些只写了年份后两位的信息，我们默认小于 22 都是 20
开头的，其他都是 19 开头的。

输入格式：

输入在一行中给出一个出生年月，为一个 6 位或者 4 位数，题目保证是 1000 年 1 月到
2021 年 12 月之间的合法年月。

输出格式：

在一行中按标准格式 年年年年-月月 将输入的信息整理输出。

**输入样例 **1：

9808

**输出样例 **1：

1998-08

**输入样例 **2：

0510

**输出样例 **2：

2005-10

**输入样例 **3：

196711

**输出样例 **3：

1967-11

降价提醒机器人 (10 分)

作者 DAI, Longao 单位 杭州百腾教育科技有限公司 代码长度限制 16 KB Java ( javac)
时间限制 600 ms 内存限制 64 MB 其他编译器 时间限制 400 ms 内存限制 64 MB

小 T
想买一个玩具很久了，但价格有些高，他打算等便宜些再买。但天天盯着购物网站很麻烦，请你帮小
T 写一个降价提醒机器人，当玩具的当前价格比他设定的价格便宜时发出提醒。

输入格式：

输入第一行是两个正整数 N 和 M (1 ≤ N ≤ 100, 0 ≤ M ≤ 1000)，表示有 N
条价格记录，小 T 设置的价格为 M 。接下来 N 行，每行有一个实数 Pi（−1000.0
< Pi < 1000.0），表示一条价格记录。

输出格式：

对每一条比设定价格 M 便宜的价格记录 P，在一行中输出 On Sale! P，其中 P
输出到小数点后 1 位。

输入样例：

4 99

98.0

97.0

100.2

98.9

输出样例：

On Sale! 98.0 On Sale! 97.0 On Sale! 98.9

大笨钟的心情 (15 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB Java ( javac) 时间限制 600 ms
内存限制 64 MB 其他编译器 时间限制 400 ms 内存限制 64 MB

有网友问：未来还会有更多大笨钟题吗？笨钟回复说：看心情……
本题就请你替大笨钟写一个程序，根据心情自动输出回答。

输入格式：

输入在一行中给出 24 个 [0, 100] 区间内的整数，依次代表大笨钟在一天 24
小时中，每个小时的心情指数。

随后若干行，每行给出一个 [0, 23]
之间的整数，代表网友询问笨钟这个问题的时间点。当出现非法的时间点时，表示输入结束，这个非法输入不要处

理。题目保证至少有 1 次询问。

输出格式：

对每一次提问，如果当时笨钟的心情指数大于 50，就在一行中输出 心情指数
Yes，否则输出 心情指数 No。

输入样例：

80 75 60 50 20 20 20 20 55 62 66 51 42 33 47 58 67 52 41 20 35 49 50 63

17

7

3

15

-1

输出样例：

52 Yes 20 No

50 No 58 Yes

吉老师的回归 (15 分)

作者 DAI, Longao 单位 杭州百腾教育科技有限公司 代码长度限制 16 KB 时间限制 400
ms 内存限制 64 MB

曾经在天梯赛大杀四方的吉老师决定回归天梯赛赛场啦！

为了简化题目，我们不妨假设天梯赛的每道题目可以用一个不超过 500
的、只包括可打印符号的字符串描述出来，如：Problem A: Print "Hello

world!"。

众所周知，吉老师的竞赛水平非常高超，你可以认为他每道题目都会做（事实上也是……）。因此，吉老师会按照顺序看题并做题。但吉老师水平太高了，所以签到题他就懒得做了（浪费时间），具体来说，假如题目的字符串里有
qiandao 或者 easy（区分大小写）的话，吉老师看完题目就会跳过这道题目不做。

现在给定这次天梯赛总共有几道题目以及吉老师已经做完了几道题目，请你告诉大家吉老师现在正在做哪个题，或者吉老师已经把所有他打算做的题目做完了。

提醒：天梯赛有分数升级的规则，如果不做签到题可能导致团队总分不足以升级，一般的选手请千万不要学习吉老师的酷炫行为！

输入格式：

输入第一行是两个正整数 N , M (1 ≤ M ≤ N ≤ 30)，表示本次天梯赛有 N
道题目，吉老师现在做完了 M 道。

接下来 N
行，每行是一个符合题目描述的字符串，表示天梯赛的题目内容。吉老师会按照给出的顺序看题——第一行就是吉老师看的第一道题，第二行就是第二道，以此类推。

输出格式：

在一行中输出吉老师当前正在做的题目对应的题面（即做完了 M
道题目后，吉老师正在做哪个题）。如果吉老师已经把所有他打算做的题目做完了，
输出一行 Wo AK le。

**输入样例 **1：

5 1

L1-1 is a qiandao problem. L1-2 is so…easy.

L1-3 is Easy.

L1-4 is qianDao.

Wow, such L1-5, so easy.

**输出样例 **1：

L1-4 is qianDao.

**输入样例 **2：

5 4

L1-1 is a-qiandao problem. L1-2 is so easy.

L1-3 is Easy.

L1-4 is qianDao.

Wow, such L1-5, so!!easy.

**输出样例 **2：

Wo AK le

天梯赛的善良 (20 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 200 ms 内存限制 64 MB

天梯赛是个善良的比赛。善良的命题组希望将题目难度控制在一个范围内，使得每个参赛的学生都有能做出来的题目，并且最厉害的学生也要非常努力才有可能得到高分。

于是命题组首先将编程能力划分成了 106
个等级（太疯狂了，这是假的），然后调查了每个参赛学生的编程能力。现在请你写个程序找出所有参赛学生的最小和最大能力值，给命题组作为出题的参考。

输入格式：

输入在第一行中给出一个正整数 N （≤ 2 × 104 ），即参赛学生的总数。随后一行给出
N 个不超过 106 的正整数，是参赛学生的能力值。

输出格式：

第一行输出所有参赛学生的最小能力值，以及具有这个能力值的学生人数。第二行输出所有参赛学生的最大能力值，以及具有这个能力值的学生人数。同行数字间以
1 个空格分隔，行首尾不得有多余空格。

输入样例：

10

86 75 233 888 666 75 886 888 75 666

输出样例：

75 3

888 2

乘法口诀数列 (20 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

本题要求你从任意给定的两个 1 位数字 a1 和 a2 开始，用乘法口诀生成一个数列
{an}，规则为从 a1
开始顺次进行，每次将当前数字与后面一个数字相乘，将结果贴在数列末尾。如果结果不是
1 位数，则其每一位都应成为数列的一项。

输入格式：

输入在一行中给出 3 个整数，依次为 a1、a2 和 n，满足 0 ≤ a1, a2 ≤ 9，0
< n ≤ 103 。

输出格式：

在一行中输出数列的前 n 项。数字间以 1 个空格分隔，行首尾不得有多余空格。

输入样例：

2 3 10

输出样例：

2 3 6 1 8 6 8 4 8 4

样例解释：

数列前 2 项为 2 和 3。从 2 开始，因为 2 × 3 = 6，所以第 3 项是 6。因为 3 × 6 =
18，所以第 4、5 项分别是 1、8。依次类推…… 最后因为第 6

项有 6 × 8 = 48，对应第 10、11 项应该是 4、8。而因为只要求输出前 10
项，所以在输出 4 后结束。

包装机 (25 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

一种自动包装机的结构如图 1 所示。首先机器中有 N
条轨道，放置了一些物品。轨道下面有一个筐。当某条轨道的按钮被按下时，活塞向左推动，将轨道尽头的一件物品推落筐中。当
0 号按钮被按下时，机械手将抓取筐顶部的一件物品，放到流水线上。图 2
显示了顺序按下按钮 3、2、3、0、1、2、0 后包装机的状态。

图1 自动包装机的结构

图 2 顺序按下按钮 3、2、3、0、1、2、0 后包装机的状态

一种特殊情况是，因为筐的容量是有限的，当筐已经满了，但仍然有某条轨道的按钮被按下时，系统应强制启动
0 号键，先从筐里抓出一件物品，再将

对应轨道的物品推落。此外，如果轨道已经空了，再按对应的按钮不会发生任何事；同样的，如果筐是空的，按
0 号按钮也不会发生任何事。

现给定一系列按钮操作，请你依次列出流水线上的物品。

输入格式：

输入第一行给出 3 个正整数 N （≤ 100）、M （≤ 1000）和 Smax（≤
100），分别为轨道的条数（于是轨道从 1 到 N
编号）、每条轨道初始放置的物品数量、以及筐的最大容量。随后 N 行，每行给出 M
个英文大写字母，表示每条轨道的初始物品摆放。

最后一行给出一系列数字，顺序对应被按下的按钮编号，直到 −1
标志输入结束，这个数字不要处理。数字间以空格分隔。题目保证至少会取出一件物品放在流水线上。

输出格式：

在一行中顺序输出流水线上的物品，不得有任何空格。

输入样例：

3 4 4

GPLT PATA

OMSA

3 2 3 0 1 2 0 2 2 0 -1

输出样例：

MATA

病毒溯源 (25 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

病毒容易发生变异。某种病毒可以通过突变产生若干变异的毒株，而这些变异的病毒又可能被诱发突变产生第二代变异，如此继续不断变化。现给定一些病毒之间的变异关系，要求你找出其中最长的一条变异链。

在此假设给出的变异都是由突变引起的，不考虑复杂的基因重组变异问题 ——
即每一种病毒都是由唯一的一种病毒突变而来，并且不存在循环变异的情况。

输入格式：

输入在第一行中给出一个正整数 N （≤ 104
），即病毒种类的总数。于是我们将所有病毒从 0 到 N − 1 进行编号。随后 N
行，每行按以下格式描述一种病毒的变异情况：

k 变异株1 …… 变异株k

其中 k 是该病毒产生的变异毒株的种类数，后面跟着每种变异株的编号。第 i
行对应编号为 i 的病毒（0 ≤ i < N ）。题目保证病毒源头有且仅有一个。

输出格式：

首先输出从源头开始最长变异链的长度。

在第二行中输出从源头开始最长的一条变异链，编号间以 1
个空格分隔，行首尾不得有多余空格。如果最长链不唯一，则输出最小序列。注：我们称序列
{ a1, ⋯ , an } 比序列 { b1, ⋯ , bn } “小”，如果存在 1 ≤ k ≤ n 满足
ai = bi 对所有 i < k 成立，且 ak < bk 。

输入样例：

10

3 6 4 8

0

0

0

2 5 9

0

1 7

1 2

0

2 3 1

输出样例：

4

0 4 9 1

清点代码库 (25 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB Java ( javac) 时间限制 1500 ms
内存限制 128 MB Python (python3) 时间限制 1500 ms 内存限制 64 MB 其他编译器 时间限制 500 ms 内存限制 64 MB

上图转自新浪微博：“阿里代码库有几亿行代码，但其中有很多功能重复的代码，比如单单快排就被重写了几百遍。请设计一个程序，能够将代码库中所有功能重复的代码找出。各位大佬有啥想法，我当时就懵了，然后就挂了。。。”

这里我们把问题简化一下：首先假设两个功能模块如果接受同样的输入，总是给出同样的输出，则它们就是功能重复的；其次我们把每个模块的输出都简化为一个整数（在
int
范围内）。于是我们可以设计一系列输入，检查所有功能模块的对应输出，从而查出功能重复的代码。你的任务就是设计并实现这个简化问题的解决方案。

输入格式：

输入在第一行中给出 2 个正整数，依次为 N （≤ 104 ）和 M （≤ 102
），对应功能模块的个数和系列测试输入的个数。随后 N 行，每行给出一个功能模块的
M 个对应输出，数字间以空格分隔。

输出格式：

首先在第一行输出不同功能的个数 K。随后 K
行，每行给出具有这个功能的模块的个数，以及这个功能的对应输出。数字间以 1
个空格分隔，行首尾不得有多余空格。输出首先按模块个数非递增顺序，如果有并列，则按输出序列的递增序给出。

注：所谓数列 { A1, …, AM } 比 { B1, …, BM } 大，是指存在 1 ≤ i <
M ，使得 A1 = B1，…，Ai = Bi 成立，且 Ai+1 > Bi+1。

输入样例：

7 3

35 28 74

-1 -1 22 28 74 35

-1 -1 22 11 66 0

35 28 74

35 28 74

输出样例：

4

3 35 28 74

2 -1 -1 22

1 11 66 0

1 28 74 35

哲哲打游戏 (25 分)

作者 DAI, Longao 单位 杭州百腾教育科技有限公司 代码长度限制 16 KB Java ( javac)
时间限制 800 ms 内存限制 64 MB Python (python3) 时间限制 1000 ms 内存限制 64 MB
其他编译器 时间限制400 ms 内存限制 64 MB

哲哲是一位硬核游戏玩家。最近一款名叫《达诺达诺》的新游戏刚刚上市，哲哲自然要快速攻略游戏，守护硬核游戏玩家的一切！

为简化模型，我们不妨假设游戏有 N
个剧情点，通过游戏里不同的操作或选择可以从某个剧情点去往另外一个剧情点。此外，游戏还设置了一些存档，在某个剧情点可以将玩家的游戏进度保存在一个档位上，读取存档后可以回到剧情点，重新进行操作或者选择，到达不同的剧情点。

为了追踪硬核游戏玩家哲哲的攻略进度，你打算写一个程序来完成这个工作。假设你已经知道了游戏的全部剧情点和流程，以及哲哲的游戏操作，请你输出哲哲的游戏进度。

输入格式：

输入第一行是两个正整数 N 和 M (1 ≤ N , M ≤ 105 )，表示总共有 N
个剧情点，哲哲有 M 个游戏操作。

接下来的 N 行，每行对应一个剧情点的发展设定。第 i 行的第一个数字是
Ki，表示剧情点 i 通过一些操作或选择能去往下面 Ki 个剧情点；接下来有 Ki
个数字，第 k 个数字表示做第 k 个操作或选择可以去往的剧情点编号。

最后有 M 行，每行第一个数字是 0、1 或 2，分别表示：

1. 表示哲哲做出了某个操作或选择，后面紧接着一个数字
   j，表示哲哲在当前剧情点做出了第 j
   个选择。我们保证哲哲的选择永远是合法的。

2. 表示哲哲进行了一次存档，后面紧接着是一个数字 j，表示存档放在了第 j
   个档位上。

3. 表示哲哲进行了一次读取存档的操作，后面紧接着是一个数字 j，表示读取了放在第
   j 个位置的存档。

   约定：所有操作或选择以及剧情点编号都从 1 号开始。存档的档位不超过 100
   个，编号也从 1 开始。游戏默认从 1 号剧情点开始。总的选项数（即

   ∑ Ki）不超过 106 。

输出格式：

对于每个
1（即存档）操作，在一行中输出存档的剧情点编号。最后一行输出哲哲最后到达的剧情点编号。

输入样例：

10 11

3 2 3 4

1 6

3 4 7 5

1 3

1 9

2 3 5

3 1 8 5

1 9

2 8 10

0

1 1

0 3

0 1

1 2

0 2

0 2

2 2

0 3

0 1

1 1

0 2

输出样例：

1

3

9

10

样例解释：

简单给出样例中经过的剧情点顺序：

1 -> 4 -> 3 -> 7 -> 8 -> 3 -> 5 -> 9 -> 10。

档位 1 开始存的是 1 号剧情点；档位 2 存的是 3 号剧情点；档位 1 后来又存了 9
号剧情点。

森森旅游 (30 分)

作者 DAI, Longao 单位 杭州百腾教育科技有限公司 代码长度限制 16 KB Java ( javac)
时间限制 3000 ms 内存限制 384 MB Python (python3) 时间限制 2000 ms 内存限制 128
MB 其他编译器 时间限制 1000 ms 内存限制 128 MB

好久没出去旅游啦！森森决定去 Z 省旅游一下。

Z 省有 n 座城市（从 1 到 n 编号）以及 m
条连接两座城市的有向旅行线路（例如自驾、长途汽车、火车、飞机、轮船等），每次经过一条旅行线路时都需要支付该线路的费用（但这个收费标准可能不止一种，例如车票跟机票一般不是一个价格）。

Z 省为了鼓励大家在省内多逛逛，推出了旅游金计划：在 i 号城市可以用 1
元现金兑换 ai
元旅游金（只要现金足够，可以无限次兑换）。城市间的交通即可以使用现金支付路费，也可以用旅游金支付。具体来说，当通过第
j 条旅行线路时，可以用 cj 元现金或 dj 元旅游金支付路费。注意：
每次只能选择一种支付方式，不可同时使用现金和旅游金混合支付。但对于不同的线路，旅客可以自由选择不同的支付方式。

森森决定从 1 号城市出发，到 n
号城市去。他打算在出发前准备一些现金，并在途中的某个城市将剩余现金 全部
换成旅游金后继续旅游，直到到达 n

号城市为止。当然，他也可以选择在 1 号城市就兑换旅游金，或全部使用现金完成旅程。

Z 省政府会根据每个城市参与活动的情况调整汇率（即调整在某个城市 1
元现金能换多少旅游金）。现在你需要帮助森森计算一下，在每次调整之后最少需要携带多少现金才能完成他的旅程。

输入格式:

输入在第一行给出三个整数 n，m 与 q（1 ≤ n ≤ 105 ，1 ≤ m ≤ 2 × 105 ，1
≤ q ≤ 105 ），依次表示城市的数量、旅行线路的数量以及汇率调整的次数。

接下来 m 行，每行给出四个整数 u，v，c 与 d（1 ≤ u, v ≤ n，1 ≤
c, d ≤ 109 ），表示一条从 u 号城市通向 v
号城市的有向旅行线路。每次通过该线路需要支付 c 元现金或 d
元旅游金。数字间以空格分隔。输入保证从 1 号城市出发，一定可以通过若干条线路到达
n
号城市，但两城市间的旅行线路可能不止一条，对应不同的收费标准；也允许在城市内部游玩（即
u 和 v 相同）。

接下来的一行输入 n 个整数 a1, a2, ⋯ , an （1 ≤ ai ≤ 109 ），其中 ai
表示一开始在 i 号城市能用 1 元现金兑换 ai 个旅游金。数字间以空格分隔。

接下来 q 行描述汇率的调整。第 i 行输入两个整数 xi 与 a′ （1 ≤ xi ≤
n，1 ≤ a′ ≤ 109 ），表示第 i 次汇率调整后，xi 号城市能用 1 元现金兑换

i i

a′
个旅游金，而其它城市旅游金汇率不变。**请注意：**每次汇率调整都是在上一次汇率调整的基础上进行的。

输出格式:

对每一次汇率调整，在对应的一行中输出调整后森森至少需要准备多少现金，才能按他的计划从
1 号城市旅行到 n 号城市。

再次提醒：如果森森决定在途中的某个城市兑换旅游金，那么他必须将剩余现金全部、一次性兑换，剩下的旅途将完全使用旅游金支付。

输入样例:

6 11 3

1 2 3 5

1 3 8 4

2 4 4 6

3 1 8 6

1 3 10 8

2 3 2 8

3 4 5 3

3 5 10 7

3 3 2 3

4 6 10 12

5 6 10 6

3 4 5 2 5 100

1 2

2 1

1 17

输出样例:

8

8

1

样例解释:

对于第一次汇率调整，森森可以沿着 1 → 2 → 4 → 6 的线路旅行，并在 2
号城市兑换旅游金；

对于第二次汇率调整，森森可以沿着 1 → 2 → 3 → 4 → 6 的线路旅行，并在 3
号城市兑换旅游金；

对于第三次汇率调整，森森可以沿着 1 → 3 → 5 → 6 的线路旅行，并在 1
号城市兑换旅游金。

还原文件 (30 分)

作者 陈越 单位 浙江大学 代码长度限制 16 KB Java ( javac) 时间限制 1500 ms
内存限制 128 MB Python (python3) 时间限制 400 ms 内存限制 64 MB 其他编译器
时间限制 200 ms 内存限制 64 MB

一份重要文件被撕成两半，其中一半还被送进了碎纸机。我们将碎纸机里找到的纸条进行编号，如图
1 所示。然后根据断口的折线形状跟没有切碎的半

张纸进行匹配，最后还原成图 2 的样子。要求你输出还原后纸条的正确拼接顺序。

图1 纸条编号

图2 还原结果

输入格式：

输入首先在第一行中给出一个正整数 N （1 < N ≤ 105
），为没有切碎的半张纸上断口折线角点的个数；随后一行给出从左到右 N
个折线角点的高度值（均为不超过 100 的非负整数）。

随后一行给出一个正整数 M （≤ 100），为碎纸机里的纸条数量。接下去有 M
行，其中第 i 行给出编号为 i（1 ≤ i ≤ M ）的纸条的断口信息，格式为：

K h[1] h[2] h[K]

其中 K 是断口折线角点的个数（不超过 104 + 1），后面是从左到右 K
个折线角点的高度值。为简单起见，这个“高度”跟没有切碎的半张纸上断口折线角点的高度是一致的。

输出格式：

在一行中输出还原后纸条的正确拼接顺序。纸条编号间以一个空格分隔，行首尾不得有多余空格。题目数据保证存在唯一解。

输入样例：

17

95 70 80 97 97 68 58 58 80 72 88 81 81 68 68 60 80

6

4 68 58 58 80

3 81 68 68

3 95 70 80

3 68 60 80

5 80 72 88 81 81

4 80 97 97 68

输出样例：

3 6 1 5 2 4

可怜的简单题 (30 分)

作者 吉如一 单位 北京大学 代码长度限制 16 KB 时间限制 10000 ms 内存限制 512 MB

九条可怜去年出了一道题，导致一众参赛高手惨遭团灭。今年她出了一道简单题 ——
打算按照如下的方式生成一个随机的整数数列 A:

1. 最开始，数列 A 为空。

2. 可怜会从区间 [1, n] 中等概率随机一个整数 i 加入到数列 A 中。

   1. 如果不存在一个大于 1 的正整数 w，满足 A 中所有元素都是 w
      的倍数，数组 A 将会作为随机生成的结果返回。否则，可怜将会返回第二步，
      继续增加 A 的长度。

      现在，可怜告诉了你数列 n 的值，她希望你计算返回的数列 A 的期望长度。

输入格式：

输入一行两个整数 n, p (1 ≤ n ≤ 1011 , n < p ≤ 1012 )，p
是一个质数。

输出格式：

在一行中输出一个整数，表示答案对 p
取模的值。具体来说，假设答案的最简分数表示为 x ，你需要输出最小的非负整数 z
满足 y × z ≡ x mod p

。

**输入样例 **1：

2 998244353

**输出样例 **1：

2

**输入样例 **2：

100000000 998244353

**输出样例 **2：

3056898

7-166 求整数的位数及各位数字之和 (15 分)

作者 C课程组 单位 浙江大学 代码长度限制 16 KB 时间限制 400 ms 内存限制 64 MB

对于给定的正整数N，求它的位数及其各位数字之和。

输入格式：

输入在一行中给出一个不超过109 的正整数N。

输出格式：

在一行中输出N的位数及其各位数字之和，中间用一个空格隔开。

输入样例：

321

输出样例：

3 6