2024年9月GESP 7级编程题

小杨寻宝

题目描述

小杨有一棵包含 nn 个节点的树，树上的一些节点放置有宝物。

小杨可以选择任意一个节点作为起始点并在树上移动。
但每当小杨经过一条边后就会被该条边删除。
在访问任何包含宝物的节点时都会获得相应的宝物。

小杨想请你帮他判断自己能否成功取得所有宝物。

输入格式

第一行包含一个正整数 tt ，代表测试用例组数。

接下来是 tt 组测试用例。对于每组测试用例，一共 n+1n+1 行。

第一行包含一个正整数 nn ，代表树的节点数。

第二行表示nn个非负整数a₁,a₂,…,aₙ。其中具体而言，在这些整数值中：如果ai等于1，则节点ii拥有宝物；反之，则该节点ii没有宝物。

随后的n-1行中每一行都包含两个正整数x_{i}, y_{i}（i=1,2,\dots,n-1），表示存在一条连接节点x_{i}和y_{i}的边。

输出格式

对于每组测试数据，如果小杨能成功取得所有宝物，输出 Yes ，否则输出 No 。

样例 #1

样例输入 #1

    2
    5
    0 1 0 1 0
    1 2
    1 3
    3 4
    3 5
    5
    1 1 1 1 1
    1 2
    1 3
    3 4
    3 5
    
    
    AI生成项目
![](https://ad.itadn.com/c/weblog/blog-img/images/2025-07-13/QDSbTdcMkuYpH8zJAF6rq54vi2Vw.png)

样例输出 #1

    Yes
    No
    
    
    AI生成项目

提示

样例解释

对于第一组测试案例而言，在节点 22 开始行动，并按照编号为 2、1、3、4 的顺序依次访问各节点即可成功获取所有目标物品。

数据范围

针对所有数据集，在满足 t 的取值范围为 [ ]以及 n 的取值范围为 [ ]的情况下，并且确保树结构中至少存在一个节点被放置了宝物。

矩阵移动

题目描述

小杨在一个n \times m的矩阵中（仅包含0、1和问号）进行操作。矩阵行从上至下依次标记为1至n号行（Row i, i=1,2,\ldots,n），列从左至右依次标记为1至m号列（Column j, j=1,2,\ldots,m）。起始点位于矩阵左上角(1, 1)处，在每次移动时可以选择向下或向右方向前进；目标位置设于右下角(n, m)处，并在此处停止移动。在路径上的每一个单元格内若遇到标记值为"一"的位置则会增加当前得分（起始点与终点也会被计入），其余情况则不会有任何得分变化。初始得分为零分

为了实现目标, 小杨能够将矩阵中最多xx个符号?转换为符号1. 修改后的矩阵中, 小杨会选择最优路径从左上角走到右下角. 为了计算他的最高得分, 小杨希望了解自己能够获得的最大分数.

输入格式

第一行包含一个正整数 tt ，代表测试用例组数。

接下来是 tt 组测试用例。对于每组测试用例，一共 n+1n+1 行。

第一行包含三个正整数 n,m,xn,m,x ，含义如题面所示。

之后 nn 行，每行包含一个长度为 mm 且仅包含 0 1 ? 三种字符的字符串。

输出格式

在每组测试用例中，请输出一个整数表示在最优策略下小杨能获得的最大分数。

样例 #1

样例输入 #1

    2
    3 3 1
    000
    111
    01?
    3 3 1
    000
    ?0?
    01?
    
    
    AI生成项目

样例输出 #1

    4
    2
    
    
    AI生成项目

提示

样例解释

对于第二组测试用例，将 (1,1)(1,1) 或者 (3,3)(3,3) 变成 1 均是最优策略。

数据范围

针对所有数据集，在 t 的取值范围内（t ∈ [1, 10]）以及 n 和 m 都满足（n, m ∈ [1, 500]）的情况下，请确保这些测试用例的总计算量不超过每秒 2.5×1e5 次运算。