U370635 10.12模拟赛改题

10.12模拟赛改题 通过一个 Subtask 即可 AC。 Subtask.0 为 T1； Subtask.1 为 T2； Subtask.2 为 T3； Subtask.3 为 T4；

# 10.12 模拟赛 | 题目名 | 夕景昨日 | 透明答案 | 界外科学 | T 匹配 | | - | :-: | :-: | :-: | :-: | | 文件名 | switch | game | buy | match | | 题目类型 | 传统 | 传统 | 传统 | 传统 | | 时空限制 | $\text{1s 512M}$ | $\text{1s 512M}$ | $\text{1s 512M}$ | $\text{1s 512M}$ | --- # 夕景昨日 switch **题目描述** Shintaro 制作了 $n$ 个开关，每个开关的状态可被设置为 $+$ 或 $−$。 现在你有一个数列 $A=(a_1,\dots,a_n)$，和一个初始值为 $0$ 的变量 $v$。你可以自由地操纵开关，当第 $i$ 个开关被设置为 $+$ 状态时， $v$ 会加上 $a_i$，被设置为 $−$ 状态时，$v$ 会减去 $a_i$。 请你判断是否有两种及以上不同的方式操纵开关，使得最后得到的 $v$ 值相等。 **输入格式** 第一行一个数 $n$，表示开关的个数。 第二行 $n$ 个数，第 $i$ 个数表示 $a_i$ **输出格式** 如果有请输出 `Yes`，否则输出 `No`。 **样例输入1** ``` 3 1 2 3 ``` **样例输出1** ``` Yes ``` **样例输入2** ``` 4 3 4 5 10 ``` **样例输出2** ``` No ``` **数据范围** 对于 $20\%$ 的数据，$n \le 10$。 对于 $100\%$ 的数据，$1 \le n \le 10 ^ 5, 0 \le a_i \le 5 \times 10^5$。 --- # 透明答案 game **题目描述** Ayano 和 Bob 在玩简单的取石子游戏。最初有 $n$ 堆石子，每堆有 $2$ 块。 Ayano 和 Bob 轮流取石子（从 Ayano 开始）。每一次取石子时当前玩家可以任选一堆，如果还剩下 $k$ 块石子，则可以从这堆中取出 $1$ 到 $k$ 之间的任意数量的石子。 此外，每 $3$ 回合他们会添加一堆石子（含 $2$ 块石子）。换句话说，在第 $t$ 次操作（两个人操作的总次数）之后，如果 $t$ 可以被 $3$ 整除，则添加一堆 $2$ 块石子的石子堆。 （即使在第 $t$ 次操作中取完了所有石子，如果 $t$ 可被 $3$ 整除，也会添加新石子堆并继续游戏。） 双方都采取最优策略，无法操作的玩家输掉游戏。请你判断哪个玩家获胜。 **输入格式** 一行一个数 $n$，表示最初石子的堆数。 **输出格式** 如果 Ayano 获胜则输出 `Ayano`，否则输出 `Bob`。 **样例输入1** ``` 1 ``` **样例输出1** ``` Ayano ``` **样例输入2** ``` 998 ``` **样例输出2** ``` Bob ``` **数据范围** 对于 $30\%$ 的数据，$n \le 10$。 对于 $100\%$ 的数据，$n \le 1000$。 --- # 界外科学 buy **题目描述** ENE 是一位电脑少女，这天她在帮 Shintaro 网上购物。网店一共有 $n$ 件物品，第 $i$ 件物品有 $a_i$ 的价格，并且购买这件物品会给 Shintaro 带来 $b_i$ 的满足度，不同的物品获得的满足度会累加。 Shintaro 最多只能支付 $m$ 元。由于他资金有限，ENE 黑入了网店的支付系统。在她操作之后，总价格的计算方式是将所有物品的价格给 $\operatorname{xor}$ （异或运算）起来。 如 Shintaro 现在买了价格为 $1, 2, 4, 7$ 的四件物品，总价格为 $1⊕2⊕4⊕7=0$。 Shintaro 现在想知道在足够支付所买的物品的前提下，他最多能获得多少满足度。 **输入格式** 第一行两个数 $n,m$，表示物品的个数和 Shintaro 最多能支付多少钱。 第二行 $n$ 个数，第 $i$ 个数 $a_i$ 表示第 $i$ 件物品的价格。 第三行 $n$ 个数，第 $i$ 个数 $b_i$ 表示第 $i$ 件物品能带给 Shintaro 的满足度。 **输出格式** 一行一个数表示答案。 **样例输入1** ``` 4 3 1 3 4 5 2 5 -3 100 ``` **样例输出1** ``` 104 ``` **样例输入2** ``` 1 1000000000 1 -1000000000 ``` **样例输出2** ``` 0 ``` **样例输入3** ``` 4 8 1 2 4 8 13 6 32 50 ``` **样例输出3** ``` 51 ``` **数据范围** 对于 $30\%$ 的数据，$n \le 5$。 对于 $50\%$ 的数据，$n \le 20$。 对于另外 $20\%$ 的数据，$1 \le m,a_i \le 100$。 对于 $100\%$ 的数据，$1 \le n \le 36,1 \le m,a_i,|b_i| \le 10^9$。 --- # T 匹配 match **题目描述** 婷姐造了一棵 $n$ 个点的树（$n$ 为偶数），她希望将树上的点两两匹配。也就是说对于任意一个结点 $u$，有且仅有一个结点 $v$ 与之配对。 不过婷姐对于匹配有一些限制。对于两个匹配 $(u,v)$ 和 $(x,y)$，婷姐要求这两个匹配要么相离，要么一个包含另一个。 相离：$u$ 到 $v$ 的路径与 $x$ 到 $y$ 的路径不相交。 包含：$u$ 到 $v$ 的路径包含 $x$ 到 $y$ 的路径或者 $x$ 到 $y$ 的路径包含 $u$ 到 $v$ 的路径。 婷姐需要你告诉他，这样的匹配一共有多少种方案。答案对 $998244353$ 取模。 两个方案不同当且仅当存在某个结点，使得在这两个方案中与它配对的那个结点不同。 **输入格式** 第一行一个整数 $n$。 接下来 $n−1$ 行每行 $2$ 个整数 $x,y$，表示树上的一条边。 **输出格式** 一行一个整数表示方案数，对 $998244353$ 取模。 **样例输入** ``` 8 1 2 3 4 5 6 7 8 1 4 3 6 5 8 ``` **样例输出** ``` 14 ``` **数据范围** 对于 $20\%$ 的数据，$n \le 8$。 对于 $50\%$ 的数据，$n \le 100$。 对于 $100\%$ 的数据，$2 \le n \le 2000$。保证 $n$ 是偶数。

见问题描述

见问题描述

见问题描述