3218 问题 D: 蓝桥杯2024年第十五届省赛真题-零食采购

 时间限制: 1s 内存限制: 256MB
题目描述
小蓝准备去星际旅行,出发前想在本星系采购一些零食,星系内有 n 颗星球,由 n − 1 条航路连接为连通图,第 i 颗星球卖第 ci 种零食特产。小蓝想出了 q 个采购方案,第 i 个方案的起点为星球 si ,终点为星球 ti ,对于每种采购方案,小蓝将从起点走最短的航路到终点,并且可以购买所有经过的星球上的零食(包括起点终点),请计算每种采购方案最多能买多少种不同的零食。
输入

输入的第一行包含两个正整数 n, q ,用一个空格分隔。

第二行包含 n 个整数 c1, c2, · · · , cn ,相邻整数之间使用一个空格分隔。

接下来 n − 1 行,第 i 行包含两个整数 ui, vi ,用一个空格分隔,表示一条航路将星球 ui 与 vi 相连。接下来 q 行,第 i 行包含两个整数 si, ti ,用一个空格分隔,表示一个采购方案。

输出
输出 q 行,每行包含一个整数,依次表示每个采购方案的答案。

样例输入

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

样例输出

3
2
提示

【样例说明】

第一个方案路线为 {4, 2, 1, 3} ,可以买到第 1, 2, 3 种零食;第二个方案路线为 {1, 2, 4} ,可以买到第 1, 2 种零食。

【评测用例规模与约定】

对于 20% 的评测用例,1 ≤ n, q ≤ 5000 ;对于所有评测用例,1 ≤ n, q ≤ 105,1 ≤ ci ≤ 20,1 ≤ ui, vi ≤ n,1 ≤ si, ti ≤ n。

比赛公告

2024年第十五届蓝桥杯软件赛决赛C/C++大学A组真题

试题A: 艺术与篮球(本题总分:5 分)

【问题描述】

    小蓝出生在一个艺术与运动并重的家庭中。

妈妈是位书法家,她希望小蓝能通过练习书法,继承她的艺术天赋,并练就一手好字。爸爸是一名篮球教练,他希望小蓝能通过篮球锻炼身体,培养运

动的激情和团队合作的精神。

    为了既满足妈妈的期望,又不辜负爸爸的心意,小蓝决定根据日期的笔画数来安排自己的练习。首先,他会将当天的日期按照“YYYYMMDD”的格式转换成一个8 位数,然后将这8 位数对应到汉字上,计算这些汉字的总笔画数。如果总笔画数超过50,他就去练习篮球;如果总笔画数不超过50,他就去练习书法。

    例如,在2024 年1 月1 日这天,日期可表示为一个8 位数字20240101,其转换为汉字是“二零二四零一零一”。日期的总笔画数为2+13+2+5+13+1 + 13 + 1 =50,因此在这天,小蓝会去练习书法。

    以下是汉字的笔画数对照表:

现在,请你帮助小蓝统计一下,在2000 年1 月1 日到2024 年4 月13 日这段时间内,小蓝有多少天是在练习篮球?

【答案提交】

这是一道结果填空题,你只需要算出结果后提交即可。本题的结果为一个整数,在提交答案时只填写这个整数,填写多余的内容将无法得分。


试题B: 五子棋对弈(本题总分:5 分)

【试题背景】

“在五子棋的对弈中,友谊的小船说翻就翻?” 不!对小蓝和小桥来说,五子棋不仅是棋盘上的较量,更是心与心之间的沟通。这两位挚友秉承着“友谊第一,比赛第二” 的宗旨,决定在一块5 x 5 的棋盘上,用黑白两色的棋子来决出胜负。但他们又都不忍心让对方失落,于是决定用一场和棋(平局)作为彼

此友谊的见证。

比赛遵循以下规则:

1. 棋盘规模:比赛在一个5  5 的方格棋盘上进行,共有25 个格子供下棋使用。

2. 棋子类型:两种棋子,黑棋与白棋,代表双方。小蓝持白棋,小桥持黑棋。

3. 先手规则:白棋(小蓝)具有先手优势,即在棋盘空白时率先落子(下棋)。

4. 轮流落子:玩家们交替在棋盘上放置各自的棋子,每次仅放置一枚。

5. 胜利条件:率先在横线、竖线或斜线上形成连续的五个同色棋子的一方获胜。

6. 平局条件:当所有25 个棋盘格都被下满棋子,而未决出胜负时,游戏以平局告终。

在这一设定下,小蓝和小桥想知道,有多少种不同的棋局情况(终局不同看成不同情况,终局相同而落子顺序不同看成同一种情况),既确保棋盘下满又保证比赛结果为平局。

【答案提交】

这是一道结果填空题,你只需要算出结果后提交即可。本题的结果为一个整数,在提交答案时只填写这个整数,填写多余的内容将无法得分。