版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！
title: Namomo Spring Camp 2022 Div1 每日一题记录 (Week 10) categories:
Namomo Spring Camp 2022 Div1 每日一题记录 (2022.04.30-2022.05.06)
<!-- more -->5 s, 1024 MB
Alice 和 Bob 在玩一个井字游戏, 一共有 9 堆石子, 形成一个 $3\times 3$ 的网格, 玩家轮流移除石子, 每一轮游戏玩家选择一堆石子并从中移除正整数的石子, Alice 先手, 第一个操作完成得到空行或者空列的玩家获胜, 三堆不需要完全由同一个人移除, 对角线不算做胜利
特别的每个玩家在第一次移除石子时, 必须将所选石堆的石子完全移除
如果两个玩家都足够聪明, 现在 Alice 想知道第一步可以选哪些石堆保证她会赢得游戏, 输出必胜的数量
第一行一个数字 $T$
接下来 $T \times 3$ 行, 每行三个整数
$T$ 行, 每行一个整数
2
1 1 1
1 1 1
1 1 1
1 2 3
4 5 6
7 8 9
9
7
所有数据保证 $1\le T\le 5e5,1 \le 每一堆石子数量\le 1e9$
1 s, 1024 MB
给定一个 $1-N$ 的排列 $P$
对于一对数字 ${L, R}$ ($1 \le L < R \le n$), 让 $X_{L,R}$ 为 $PL, P{L+1}, \dots, P_{R}$ 的第二大值
请你求出下面式子的值
$$ \sum{L=1}^{N-1} \sum{R=L+1}^{N} X_{L,R} $$
第一行一个数字 $N$
接下来一行 $N$ 个整数 $P_1, P_2, \dots, P_N$
一行一个整数表示 $\sum{L=1}^{N-1} \sum{R=L+1}^{N} X_{L,R}$ 的值
5
1 2 3 4 5
30
所有数据保证 $2 \leq N \leq 100000, 1 \leq P_i \leq N, P_i \neq P_j(i \neq j)$
如果你用 $n \log n$ 的复杂度通过了本题, 你可以思考一下如何更快的通过本题
1 s, 1024 MB
五一期间, 小 t 去 $T$ 个国家游玩, 他发现每个国家都有自己的货币系统, 即货币面值构成的集合. 如中国的货币系统为 ${ 1, 5, 10, 20, 50, 100 } $
假设小 t 的钱包里每种面值的货币都有无限个. 小 t 旅游时需要购买一些东西, 不妨设其中的一个价值为 $x$, 因为小 t 的数学比较拉, 所以他每次会从钱包里找出不超过还需要支付的金额的最大货币, 用于支付, 一直到支付完毕
例如当货币系统为 ${1, 3, 6}$, 物品价值 $x = 10$ 时, 小 t 会依次使用面值为 $6, 3, 1$ 的金币进行支付
如果在当前国家, 对于任意价值的物品, 都不存在另一种支付方案, 使得用来支付的货币总数严格小于小 t 的方法. 那么我们说在该国家小 t 是聪明的. (保证每个国家都有面值为 $1$ 的货币, 即任意价值的物品都可以被支付)
给定这 $T$ 个国家的货币系统, 判断小 t 在这些国家是不是聪明的
第一行一个正整数 $T$, 表示国家的个数
对于每个国家, 第一行输入一个正整数 $N$, 表示该国家货币系统的大小
接下来一行输入 $N$ 个正整数 $a_1, a_2, ... , a_n$, 分别表示这 $N$ 种面值
对于每个国家, 输出一行一个字符串 : 如果在这个国家小 t 是聪明的, 输出 Yes, 否则 输出 No
你可以输出任意大小写形式 如 YES, yEs, NO 等
对于所有数据 满足 $1 \leq T \leq 100$, $1 \leq N \leq 1000$, $\sum{N} \leq 1000$, 并且 $1 = a_1 < a_2 < ... < a_n <= 10000$
3
3
1 2 5
4
1 3 8 13
4
1 3 4 10
Yes
Yes
No
对于第三个国家, 当我们购买价值为 $6$ 的物品时, 小 t 的方法会使用 ${4, 1, 1 }$. 但是存在 ${3, 3}$ 的支付方法, 使用的货币数量更少
1 s, 64 MB
Alice 和 Bob 正在玩一个关于石头的游戏
共有 $n$ ($n$ 为偶数) 堆石子, 其中第 $i$ 堆最初含有 $a_i$ 个石子
他们轮流选择 $\frac{n}{2}$ 堆非空石子, 每堆移除掉正数个 (可以不同) 的石子, 从 Alice 开始
不能执行操作的人将输掉游戏
假设 Alice 和 Bob 都足够聪明, 你知道谁会赢得游戏吗?
第一行包含一个整数 $n$ ($2\leq n \leq 10^6$), $n$ 为偶数
第二行包含 $n$ 个正整数 $a_1,\dots,a_n$ ($1\leq a_1,\dots,a_n \leq 10^9$)
Alice 或 Bob, 表示最终赢家
4
1 1 1 1
Bob
1 s, 256 MB
给出 $N$ 种硬币面值 $A_1$ 至 $A_N$, 其中 $1=A_1 \leq A2 \leq ... \leq A{N-1} \leq A_N$ 且对于 $2 \leq i \leq N$, $Ai$ 为 $A{i-1}$ 的倍数. 求最小的花费的硬币数量+找零的硬币的硬币数量使得花费硬币币值和 $\geq X$ 且花费硬币币值和 $-$ 找零硬币币值和 $=X$
第 $1$ 行 $2$ 个整数 $N,X$
第 $2$ 行 $N$ 个整数 $A_1$ 至 $A_N$. 保证 $A_1=1$, $Ai>A{i-1}$
$1$ 行 $1$ 个整数, 表示最小硬币总数
3 87
1 10 100
5
$1 \leq N \leq 60$
$1 = A_1 < ... < A_N \leq 1 \times 10^{9} $
$1 \leq X \leq 1 \times 10^{9}$
对于 $2 \leq i \leq N$, $Ai$ 是 $A{i-1}$ 的倍数
1 s, 1024 MB
对于序列 $a_1 , a_2 , \dots , a_n$ , 若它的子段 $al , a{l + 1} , \dots , a_r$ , 如果存在 $mid \in [l + 1, r - 1]$ , 使得 $al , a{l + 1} , \dots , a{mid}$ 是不减的, $a{mid} , a_{mid + 1} , \dots , a_r$ 是不增的, 且 $r - l + 1 \geq 3$ , 就称这个子段是山型的
若对于整数 $k$ $(3 \leq k \leq n)$ , 若子段 $[1 , k]$ , $[k + 1 , 2k]$ ,$\dots$, $[(m - 1)k + 1,mk]$ , $[mk + 1 , n]$ 都是山型的, 且 $mk \leq n , n - mk < k$ , 我们就称序列 $a$ 是一个山脉
现在给定一个正整数序列 $a$ , 其中值为 $-1$ 的数可以表示任何数, 请你找出所有使得该序列为山脉的整数 $k$
第一行输入一个整数 $n$, 表示序列的长度 $( 1 \leq n \leq 10^5 ) $
第二行输入 $n$ 个整数 $a_1 , a_2 , a_3 , \dots , a_n$ 表示给定的序列 .$( 1 \leq a_i \leq 10^9 \ 或 \ a_i = -1 )$
第一行一个整数 $m$ , 表示满足要求的 $k$ 的数量
接下来 $m$ 行, 每行一个整数, 从小到大输出所有满足要求的 $k$
11
7 -1 11 10 -1 -1 26 14 9 12 -1
1
4
1 s, 512 MB
平衡二叉树(AVL 树) , 是指左右子树高度差至多为 1 的二叉树, 并且该树的左右两个子树也均为 AVL 树. 现在问题来了, 给定 AVL 树的节点个数 $n$, 求有多少种形态的 AVL 树恰好有 $n$ 个节点
一行一个整数 $T(T\leq 2000)$ 表示数据组数
T 行, 每行一个整数 $n(n\leq 2000)$
每行一个数字表示结果, 由于结果巨大, 输出它对 $10^9 + 7$ 取余数的结果
1
10
60