版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！
title: Namomo Spring Camp 2022 Div1 每日一题记录 (Week 8) categories:
Namomo Spring Camp 2022 Div1 每日一题记录 (2022.04.16-2022.04.22)
<!-- more -->3 s, 1024 MB
定义
$$ rad(n)=\prod_{\begin{matrix} p|n\ p\in Prime \end{matrix}}p $$
给定整数 $n$, 若存在两个正整数 $a$,$b$,满足 $a+b=n$,同时 rad($a\times b \times n$)< $n$,输出 YES, 否则输出 NO
第一行一个数字 $T$
接下来 $T$ 行每行输入 $1$ 个整数 $n$
每行输出 YES 或 NO
3
4
18
30
YES
YES
NO
所有数据保证 $1\le T \le 10,1\le n \le 1e18$
1 s, 1024 MB
有 $n$ 个盘子, 分别是 $1,2,...,n$, 第 $i$ 个盘子里面装了 $a_i(1 \le a_i \le 3)$ 个蛋糕, 小 $N$ 会每次按照下面的方式吃蛋糕, 直到蛋糕吃完
每次等概率的从 $n$ 个盘子中挑选一个, 假设选中了第 $i$ 个盘子, 如果第 $i$ 个盘子里面有蛋糕, 那么小 $N$ 会吃掉一个, 如果第 $i$ 个盘子里面没有蛋糕, 小 $N$ 什么也不做
请你求出吃掉所有的蛋糕的期望次数
第一行一个数字 $n$
接下来一行 $n$ 个整数 $a_1, a_2, \dots, a_n$
输出吃掉所有的蛋糕的期望次数, 误差小于等于 $10^{-9}$ 被视为正确
2
1 2
4.5
所有数据保证 $1\leq n\leq 300, 1 \leq a_i \leq 3$
1 s, 1024 MB
有 $N$ 个骑士, 他们的初始攻击力分别为 $a_1, a_2, ... , a_n$. 并且每个骑士都有一个增益能力 $b_i$
对于每个骑士, 他都会选择一名其他骑士(不包含自己), 使被选择骑士的攻击力增加 $b_i$
判断是否有一种骑士的排列, 不管骑士如何选择增益的对象, 都满足骑士的攻击力从左到右是不增的
第一行一个正整数 $T$, 表示数据组数
对于每组数据 第一行一个正整数 $N$, 表示骑士的个数
接下来 $N$ 行, 每行两个整数. 第 $i$ 行表示 $a_i$ 和 $b_i$. 即骑士 $i$ 的初始攻击力和增益能力
对于每组数据, 如果能存在一种排列骑士的方案满足要求, 就输出 Yes
否则 输出 No
对于所有数据, 满足 $1 \leq T \leq 1000$, $2 \leq N \leq 100$, $0 \leq a_i, b_i \leq 10^6$
3
2
15 25
10 5
3
7 0
7 3
10 0
3
10 10
20 20
30 30
Yes
Yes
No
对于第一组数据, 由于 $N = 2$, 所以骑士的攻击力最后一定有 $35, 20$. 显然存在方案
对于第二组数据, 我们可以构造骑士排列为 $10, 7, 7$ 其中增益能力为 $3$ 的骑士放在最后一个. 这样一来无论增益能力为 $3$ 的骑士如何选择, 都满足要求
对于第三组数据, 我们可以证明没有满足要求的方案, 于是输出 No
1 s, 64 MB
Alice 和 Bob 正在玩一个关于石子的游戏
共有 $n$ 堆石子, 其中第 $i$ 堆最初含有 $a_i$ 个石子
他们轮流执行下列操作之一, 从 Alice 开始
不能执行任何操作的人将输掉游戏
假设 Alice 和 Bob 都足够聪明, 你知道谁会赢得游戏吗?
第一行包含一个整数 $n$ ($1\leq n \leq 10^6$)
第二行包含 $n$ 个正整数 $a_1,\dots,a_n$ ($1\leq a_1,\dots,a_n \leq 10^9$)
Alice 或 Bob, 表示最终赢家
2
2 2
Alice
1 s, 128 MB
农场正在举办一场派对!
有编号从 $1$ 开始的 $n$ 种小吃, 每种小吃只有一份. 有 $m$ 个客人会来, 每个客人有两种最喜欢的口味
农场主可以以某种方式让客人排队依次前来
每个客人来到农场时, 会把他喜欢的口味的小吃全部吃掉, 如果没有他喜欢的口味, 那么他就会伤心地离开
请问令客人如何排队, 能使伤心的客人最少? 输出最少的伤心的客人的数量
第一行输入两个整数 $n, m$ $(2 \leq n \leq 10^5, 1 \leq m \leq 10^5)$ , 分别为小吃的数量和客人的数量
接下来 $m$ 行, 每行输入两个整数 $x_i, y_i$ $(1 \leq x_i, y_i \leq n, x_i \neq y_i)$ , 为编号为 $i$ 的客人喜欢的两种小吃的编号
输出一个整数, 为最少的伤心的客人的数量
5 4
1 2
4 3
1 4
3 4
1
6 5
2 3
2 1
3 4
6 5
4 5
0
在第 $1$ 组样例中, 可以让客人按照 $3, 1, 2, 4$ 的顺序排队, 3 号客人会吃掉小吃 1 和小吃 4, 然后 1 号客人会吃掉小吃 2, 2 号客人吃掉小吃 3, 4 号客人吃不到喜欢的小吃伤心的离开了, 所以答案为 1
在第 $2$ 组样例中, 可以按照 $2, 1, 3, 5, 4$ 的顺序排队, 没有客人会伤心
1 s, 1024 MB
给定一个长度为 $n$ 的括号串 $S$ , 有 $m$ 次询问 , 每次询问区间 $[l,r]$ 中的最长子序列长度, 满足是合法括号串
括号串为只由 $($ 和 $)$ 组成的字符串
合法括号串的定义如下:
第一行两个整数 $n,m$ , 含义如题面所示. $(1 \leq n , m \leq 10^5)$
第二行一个字符串 $S$ , 保证 $S$ 中只包含 $($ 和 $)$
接下来 $m$ 行 , 每行两个整数 $l,r$ , 含义如题面所示. $(1 \leq l \leq r \leq n)$
输出共 $m$ 行 , 第 $i$ 行表示第 $i$ 次询问的答案
10 5
))()()()))
6 10
7 8
7 7
7 8
4 9
2
2
0
2
4
2 s, 1024 MB
有一个 $n \times m$ 的整数矩阵 A, 其中每个数字范围都在 $[0, k)$
对于一次操作, 你可以执行下列两种操作中的一种
给定 $n, m, k, A$
是否能通过若干次上面的操作, 将 A 变为全 0 矩阵, 如果可以, 输出最小操作数, 否则, 输出-1
一行三个整数 $1\leq n\leq 2000, 1\leq m \leq 2000, 1\leq k\leq 10^9$
接下来 $n$ 行每行 $m$ 个数, 表示矩阵 A 的初始状态
一行, 如果可以输出操作数, 否则输出-1
3 3 10
0 0 9
0 0 9
9 9 8
2
3 3 10
1 0 9
0 0 9
9 9 8
-1