版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！
title: Namomo Spring Camp 2022 Div1 每日一题记录 (Week 11) categories:
Namomo Spring Camp 2022 Div1 每日一题记录 (2022.05.07-2022.05.13)
<!-- more -->1 s, 1024 MB
给定 $n$ 和 $k$. 计算有多少长度为 $k$ 的数组 $a_1,a_2\dots, a_k$, 满足:
-$\sum_{i=1}^k a_i=n, a_i\geq 0$
输出答案对 $10^9+7$ 取模的结果
第一行两个整数 $k, n$
一个整数, 表示答案
4 2
2
1919 810
501617298
共 10 个测试点
测试点 $1, 2$ 满足 $n, k\leq 10$
测试点 $3, 4$ 满足 $n, k\leq 100$
测试点 $5, 6$ 满足 $n, k\leq 1000$
对于所有数据, 满足 $1\leq n, k\leq 10^4$
1 s, 128 MB
小 $C$ 养了 $n$ 只猫, 编号从 $1 - n$. 小 $C$ 不喜欢一次只给一头猫喂猫粮, 因此他选择一下喂很多只编号连续的猫, 并且每次喂的猫粮都是 不同种类 的. 现在有 $m$ 次操作, 每次操作给定 $op, \; l, \; r$
第一行两个个数字 $n, \; m$
接下来有 $m$ 行, 每行 $3$ 个整数 $op, \; l , \; r$
对于每次询问, 请输出 $1$ 行一个整数表示答案
5 4
1 1 1
1 2 2
2 1 1
2 1 2
1
2
所有数据保证 $0\leq n, \, m\leq 100000, 1 \le l \le r \le n$
1 s, 1024 MB
给定一个 $n\times m$ 的矩阵, 要求在每列中恰好选择一个数, 并且这些数里面存在两个数在同一行, 要求使这 $m$ 个数的最小值最大, 输出该值
第一行输入两个正整数 $n,m$
接下来 $n$ 行, 每行 $m$ 个正整数
一个正整数
2 2
1 2
3 4
3
$m=2$, 要求选择不超过 $2-1=1$ 行, 即只能选择一行, 选择第一行即 $1,2$, 最小值为 $1$, 选择第二行即 $3,4$, 最小值为 $3$, 所以答案为 $3$
$2 < n , m \leq 2500$
数据保证所有出现的数不超过 $10^9$
1 s, 1024 MB
有 $N$ 个字符串, 每一次操作可以任意选择一个字符串 T.(可以为空串并且不一定是题目所给的字符串) 然后考虑所有还没有被删除的字符串 S, 如果 T 是 S 的一个前缀(空串是任意串的前缀), 那么把它加入候选删除集合
但是每一次操作最多删除 $K$ 个字符串, 也就是说如果候选集合中字符串的数量大于 $K$, 那么什么也不会发生. 否则, 删除其中所有的字符串
求出最少需要多少次操作才能删掉所有的字符串
第一行输入两个正整数 $N$ 和 $K$. 如题意所示
接下来 $N$ 行, 每一行输入一个仅包含小写英文字母的字符串
数据保证没有两个相同的字符串
对于所有数据 满足 $1 \leq N \leq 100$,$1 \leq K \leq 20$,$\sum{len} <= 3 * 10^5$. (所有字符串的长度之和)
一行输出一个正整数, 表示最少需要多少次操作才能删除所有字符串
4 2
a
abc
abd
b
2
我们可以第一次操作选择 ab. 删掉 abc 和 abd
第二次操作选择空串. 将剩下的所有字符串删掉
4 2
d
c
ab
a
2
5 3
please
remove
all
these
files
3
1 s, 1024 MB
本题是 https://oj.daimayuan.top/problem/882 的加强版, 差别仅在于 $n$ 与 $S_i$ 的取值. 已使用红色字体标注题面中的区别
关于序列 ${S}$ 定义 $f(S) = \gcd(S_1, S_2, \cdots, S_n)$
我们熟知 $\gcd$ 运算具有结合律, 即 $\gcd(a, b, c, \cdots) = \gcd(a, \gcd(b, c, \cdots))$, 可以轻松算出 $f(S)$
然而 Patricky 认为, 那些 $f(S) = 1$ 的序列太过朴素. 现在给定 ${S}$, 他希望您能用下面的操作修改 ${S}$ 使得 $f(S) \ge 2$:
试回答使得 $f(S) \ge 2$ 的 最小 操作次数, 或回答不可能
输入包含两行, 第一行有一个整数 $n$, 表示 ${S}$ 的大小
接下来一行包含 $n$ 个用空格分隔的整数, 依次表示 $S_1, S_2, \cdots, S_n$
输出使得 $f(S) \ge 2$ 的最小操作次数. 如果不可能, 则在一行中输出 $-1$
-$1 \le n \le 10 ^ {\color{red}{6}}$ -$Si \in \color{red}{[0, 10^6]}$ 但保证 $\displaystyle \sum{i = 1} ^n S_i \ge 1$, 即元素不同时为 $0$
3
4 8 5
9
$[4, 8, 5] \rightarrow^4 [0, 12, 5] \rightarrow^5 [0, 17, 0]$
4
0 5 15 10
0
6
1 2 3 4 5 6
2
$[1, 2, 3, 4, 5, 6] \rightarrow [0, 3, 3, 4, 5, 6] \rightarrow [0, 3, 3, 3, 6, 6]$
1 s, 1024 MB
P 国的历法比较特殊, 每一年都有 $m$ 个月 , 每个月有 $d$ 天. 每个星期有 $w$ 天
每年的第一天也是一个星期的第一天
求出有多少对 $(x,y)$,$x < y$ 满足第 $y$ 个月的第 $x$ 天和第 $x$ 个月的第 $y$ 天在一个星期内是同一天
第一行一个整数 $t$, 表示数据组数.$(1 \leq t \leq 10^3)$
接下来 $t$ 行, 每行输入三个整数 $m,d,w$, 表示序列的长度 $( 1 \leq m,d,w \leq 10^9 )$
输出 $t$ 行, 每行一个整数, 表示满足要求二元对的数量
5
6 7 4
10 7 12
12 30 7
1 1 1
3247834 10298779 625324
6
9
5
0
116461800
水题, 略
1 s, 512 MB
给定一个长度为 $n$ 的数列 ${A}$
每次可以选择一个区间 $[l,r]$, 使这个区间内的数都加 $1$ 或者都减 $1$
请问至少需要多少次操作才能使数列中的所有数都一样, 并求出在保证最少次数的前提下, 最终得到的数列有多少种
一行一个整数 $n(n\leq 10^6)$ 表示数组长度
一行 $n$ 个整数, 第 i 个数表示 $A_i(|A_i|在int范围内)$
第一行输出最少操作次数 第二行输出最终能得到多少种结果
4
1 1 2 2
1
2