Namomo Spring Camp 2022 Div1 每日一题记录 (Week 10)
Namomo Spring Camp 2022 Div1 每日一题记录 (2022.04.30-2022.05.06)
New Stone Game
5 s, 1024 MB
题目描述
Alice 和 Bob 在玩一个井字游戏，一共有 9 堆石子，形成一个 \(3\times 3\) 的网格，玩家轮流移除石子，每一轮游戏玩家选择一堆石子并从中移除正整数的石子，Alice 先手，第一个操作完成得到空行或者空列的玩家获胜，三堆不需要完全由同一个人移除，对角线不算做胜利
特别的每个玩家在第一次移除石子时，必须将所选石堆的石子完全移除
如果两个玩家都足够聪明，现在 Alice 想知道第一步可以选哪些石堆保证她会赢得游戏，输出必胜的数量
输入格式
第一行一个数字 \(T\)
接下来 \(T \times 3\) 行，每行三个整数
输出格式
\(T\) 行，每行一个整数
样例输入
1 | 2 |
样例输出
1 | 9 |
数据规模
所有数据保证 \(1\le T\le 5e5,1 \le 每一堆石子数量 \le 1e9\)
解题思路
复杂度
代码参考
Show code
第二大数字和
1 s, 1024 MB
题目描述
给定一个 \(1-N\) 的排列 \(P\)
对于一对数字 \({L, R}\) (\(1 \le L < R \le n\)), 让 \(X_{L,R}\) 为 \(P_L, 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}\) 的值
样例输入
1 | 5 |
样例输出
1 | 30 |
数据规模
所有数据保证 \(2 \leq N \leq 100000, 1 \leq P_i \leq N, P_i \neq P_j(i \neq j)\)
题外话
如果你用 \(n \log n\) 的复杂度通过了本题，你可以思考一下如何更快的通过本题
解题思路
复杂度
代码参考
Show code
货币系统
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\)
样例输入
1 | 3 |
样例输出
1 | Yes |
样例解释
对于第三个国家，当我们购买价值为 \(6\) 的物品时，小 t 的方法会使用 \(\{4, 1, 1 \}\). 但是存在 \(\{3, 3\}\) 的支付方法，使用的货币数量更少
解题思路
复杂度
代码参考
Show code
石子游戏 III
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, 表示最终赢家
样例输入
1 | 4 |
样例输出
1 | Bob |
解题思路
复杂度
代码参考
Show code
硬币 (AtCoder abc231_e)
1 s, 256 MB
题目描述
给出 \(N\) 种硬币面值 \(A_1\) 至 \(A_N\), 其中 \(1=A_1 \leq A_2 \leq ... \leq A_{N-1} \leq A_N\) 且对于 \(2 \leq i \leq N\), \(A_i\) 为 \(A_{i-1}\) 的倍数。求最小的花费的硬币数量 + 找零的硬币的硬币数量使得花费硬币币值和 \(\geq X\) 且花费硬币币值和 \(-\) 找零硬币币值和 \(=X\)
输入格式
第 \(1\) 行 \(2\) 个整数 \(N,X\)
第 \(2\) 行 \(N\) 个整数 \(A_1\) 至 \(A_N\). 保证 \(A_1=1\), \(A_i>A_{i-1}\)
输出格式
\(1\) 行 \(1\) 个整数，表示最小硬币总数
样例输入
1 | 3 87 |
样例输出
1 | 5 |
数据规模
\(1 \leq N \leq 60\)
$1 = A_1 < ... < A_N ^{9} $
\(1 \leq X \leq 1 \times 10^{9}\)
对于 \(2 \leq i \leq N\), \(A_i\) 是 \(A_{i-1}\) 的倍数
解题思路
复杂度
代码参考
Show code
山脉 (CodeForces Gym 103185B)
1 s, 1024 MB
题目描述
对于序列 \(a_1 , a_2 , \dots , a_n\) , 若它的子段 \(a_l , a_{l + 1} , \dots , a_r\) , 如果存在 \(mid \in [l + 1, r - 1]\) , 使得 \(a_l , 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 n ^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\)
样例输入
1 | 11 |
样例输出
1 | 1 |
解题思路
复杂度
代码参考
Show code
平衡二叉树
1 s, 512 MB
题目描述
平衡二叉树 (AVL 树) , 是指左右子树高度差至多为 1 的二叉树，并且该树的左右两个子树也均为 AVL 树。现在问题来了，给定 AVL 树的节点个数 \(n\), 求有多少种形态的 AVL 树恰好有 \(n\) 个节点
输入描述
一行一个整数 \(T(T\leq 2000)\) 表示数据组数
T 行，每行一个整数 \(n(n\leq 2000)\)
输出描述
每行一个数字表示结果，由于结果巨大，输出它对 \(10^9 + 7\) 取余数的结果
输入样例
1 | 1 |
输出样例
1 | 60 |