0406 第 9 场 小白入门赛/强者挑战赛

• 小白入门赛：https://www.lanqiao.cn/oj-contest/newbie-9/
• 强者挑战赛：https://www.lanqiao.cn/oj-contest/senior-9/
• 题解回放：https://www.bilibili.com/video/BV1Kq421A7ci/

T1. 省赛总动员【算法赛】

问题描述

即将迎来第 $15$ 届蓝桥杯省赛的盛大开幕，愿每一位参赛者都能在比赛中取得令人满意的成绩！

对此，您可以打印 No.1 为省赛中的自己加油打气。

什么？你没有参加本届蓝桥杯 ？（ 可惜.jpg

无妨，您同样可以打印 No.1 为本场周赛拿下一个 AC。

输入格式

本题为填空题，无需输入即可作答。

输出格式

输出一个字符串，表示答案。

T2. 盖印章【算法赛】

问题描述

小 Z 喜欢盖印章。

有一天，小 Z 得到了一个 $n\times m$ 的网格图，与此同时，他的手上有两种印章（分别称为 A，B），如下图所示。

他想将这两种印章盖在这个网格图上。

由于小 Z 是一个有原则的人，他将按照以下规则进行操作。

1. 每个印章所形成的图案的边必须和网格图边重合。
2. 对于网格图上的每一个格子，最多只能被一个印章图案覆盖。
3. 对于每个印章，可以将印章顺时针旋转 $90^{\circ},180^{\circ},270^{\circ}$。
4. 印章的图案在网格图上必须是完整的。

给定小 Z 所盖完印章的网格图以及两种印章的使用次数 $K$，请你分别求出两种印章的使用次数。可以证明，在这种情况下二者的使用次数是唯一的。

数据保证存在一种方案达到要求。

具体例子可以参考样例。

输入格式

第一行包含三个正整数 $n ,m, K(2 \le n \times m \le 10^{6}, 0 \le K \le n \times m)$，具体意义如题面所示。

接下来有 $n$ 行长度为 $m$ 的 01 串，其中 1 表示这个位置被印章图案覆盖。否则表示这个位置没有被覆盖。

输出格式

输出两个整数，第一个整数为 A 出现的次数，第二个整数为 B 出现的次数。

样例输入 1

3 3 2
110
110
110

样例输出 1

2 0

样例输入 2

3 3 3
110
110
110

样例输出 2

0 3

说明

上述样例如图所示

T3. 学《树论》的贝贝 2.0【算法赛】

问题描述

对于一棵 $n$ 个结点的有根树，结点按 $1\sim n$ 编号。

• 约定一条链长度为 $k$，当且仅当其恰好含有 $k$ 条边。
• 约定两条长度为 $k$ 的链有交集，当且仅当他们包含相同编号的节点。
• 若任意两条长度为 $k$ 的链均有交集，则称这棵树为“好树”。

给定整数 $n,k$，贝贝想知道，好树的叶子结点（儿子数量为 $0$ ）数量最少为多少？

输入格式

第一行，包含一个整数 $T( 1\le T \le 10^5 )$，表示评测用例组数。

接下来的 $T$ 行，每行包含两个整数 $n,k(1\le n,k\le 10^{18})$。

输出格式

共 $T$ 行，对于每组评测用例输出一行答案，包含一个整数，表示好树的叶子结点数量的最少值。

样例输入

2
4 1
2 5

样例输出

2
1

说明

第一个测试用例，约定 $1$ 为根节点，答案所对应的好树，如下图所示：

第二个测试用例，约定 $1$ 为根节点，答案所对应的好树，如下图所示：

T4. 字符迁移【算法赛】

问题描述

小蓝最近获得了一个长度为 $N$ 的字符串 $S$，他对它爱不释手。

小桥为了考验小蓝对字符串的处理能力，决定给他提出一个挑战，她会进行 $Q$ 次操作：

• 每次操作给定三个整数 $l,r,k$，将 $S$ 的第 $l$ 个字符到第 $r$ 个字符都循环右移 $k$ 次。

小桥想让小蓝回答她在操作完成后 $S$ 是多少？小蓝陷入了困境，于是请你帮帮他！

字符右移表示为按字母表进行移动，例如 a 右移 $1$ 次变为 b，b 右移 $2$ 次变为 d。特别地，z 右移 $1$ 次变回为 a。

输入格式

第一行输入两个整数 $N,Q(1 \le N,Q \le 2 \times 10^5)$ 表示字符串 $S$ 的长度和小桥操作次数。

第二行输入一个字符串 $S$，保证 $S$ 只包含小写字符。

接下来 $Q$ 行每行输入三个整数 $l,r,k(1 \leq l \leq r \leq N,1 \leq k \leq 10^9)$ 表示一次操作。

输出格式

输出一个字符串表示答案。

输入样例

5 3
abcde
1 5 3
1 2 4
2 5 3

输出样例

hlijk

T5. 字典树考试【算法赛】

问题描述

蓝桥学院最近教学了字典树这一数据结构，小蓝是全班的第一名，他不仅掌握了普通字典树，还自学了 $01$ 字典树的使用。

为了展示自己的能力，他向全班同学出了以下问题：

• 给定一个长度为 $N$ 的数组 $A$ ，你能否求出表达式 $\sum_{i=1}^N\sum_{j=i+1}^N f(A_i \And A_j)$ 的值 ? 其中，$f(x)$ 表示 $x$ 二进制表示中 $1$ 的个数，$\And$ 表示按位与运算。

然而，这个问题很快就被小桥同学迅速解决了，尽管她明明没有学过 $01$ 字典树。

现在小蓝想让你也尝试解决这个问题。

输入格式

第一行输入一个整数 $N(1 \le N\le 2 \times 10^5)$ 表示数组 $A$ 的长度。

第二行输入 $N$ 个整数 $A_1,A_2,A_3,\cdots,A_N$ 表示数组 $A(0 \leq A_i\leq10^9)$。

输出格式

输出一个整数表示答案。

输入样例

3
1 3 2

输出样例

2

T6. 无理数位数查询【算法赛】

问题描述

设 $f(m)$ 为所有 $m$ 进制正整数连接起来构造的一个 $m$ 进制无理数。

$f(10)$ 如下所示：

$$0.123456789101112131415161718192021 \ldots$$

可以看出小数点后第 $12$ 位数字是 $1$。

给定若干次询问，每次询问给出两个整数 $n,m$，求 $f(m)$ 的第 $n$ 位的数字。

输入格式

第一行包含一个正整数 $T(1 \le T \le 10^{4})$，表示测试用例的数量。

每个测试用例只有一行，包含两个正整数 $n,m(1 \le n \le 10^{18}, 2 \le m \le 10)$。具体意义如题面所示。

输出格式

对于每个测试用例，输出一行一个整数，表示答案。

样例输入

4
1000 10
200 3
300 4
10 5

样例输出

3
2
1
2

T7. 贝贝的集合【算法赛】

问题描述

贝贝有一个大小为 $n$ 的可重集合 $\{2^{a_1},2^{a_2},\cdots,2^{a_n}\}$，

• 可重集合，即集合中的数允许出现多次。

约定一次操作的过程如下：

• 第一步，从集合中取出两个数并从集合中删除，约定较小的为 $x$，较大的为 $y$，即 $x\le y$；
• 第二步，将 $2x$ 插入集合中；
• 第三步，若 $y\ e x$，则将 $y-x$ 插入集合中。

贝贝想知道，经过若干次操作后，集合的大小最小可以为多少？

输入格式

第一行，包含一个整数 $n(1\le n\le 10^5)$。

第二行，包含 $n$ 个整数 $a_1,a_2,\cdots,a_n(1\le a_i\le 10^9)$。

输出格式

仅一行，包含一个整数，表示经过若干次操作后，集合的大小的最小值。

样例输入

5
1 1 1 3 1

样例输出

1

说明

一种贝贝可能的操作顺序如下：

第一次操作，取出 $2^1,2^1$，操作完毕后集合变成 $\{2^1,2^1,2^2,2^3\}$。

第二次操作，取出 $2^1,2^1$，操作完毕后集合变成 $\{2^2,2^2,2^3\}$。

第三次操作，取出 $2^2,2^2$，操作完毕后集合变成 $\{2^3,2^3\}$。

第四次操作，取出 $2^3,2^3$，操作完毕后集合变成 $\{2^4\}$。

故最终集合大小的最小值为 $1$。

T8. 学《博弈论》的贝贝 2.0【算法赛】

问题描述

BeiBei 和 NingNing 在玩硬币游戏。初始时，有 $n$ 枚硬币排列成一排，均正面朝上。

二人轮流执行以下操作：

• 选择连续 $k$ 枚硬币，并且最左边的那枚硬币需要正面朝上；
• 然后将它们全部翻转。

BeiBei 先手，当玩家首次无法完成上述操作时，该玩家判负。BeiBei 和 NingNing 都足够聪明。

若游戏无法结束，请你输出 “Equal” 。

否则请你输出该游戏最终的获胜者，并且你还需要输出获胜者的第一步的必胜方案数。

输入格式

第一行包含一个正整数 $T(1 \le T \le 10^5)$，表示测试用例的数量。

每个测试用例仅一行，包含两个正整数 $n,k(1\le k\le n\le 10^{18})$ 。

输出格式

对于每个测试用例，输出格式如下：

第一行，包含一个字符串，若游戏无法结束请你输出 “Equal”。否则输出 “BeiBei” 或 “NingNing”，表示最终的获胜者。

当游戏可以结束时，请输出第二行，最终获胜者为 “BeiBei” 时，则只输出一个整数，表示其第一步的必胜方案数量。最终获胜者为 “NingNing” 时，则输出两个整数，表示考虑 BeiBei 的第一步走法的所有情况，NingNing 第一步的必胜方案数量的最小值、最大值。

样例输入

2
1 1
4 3

样例输出

BeiBei
1
BeiBei
2

T9. 组合数【算法赛】

问题描述

给定 $a,b,n$，求

$$\sum_{ i = 0}^{\left \lfloor \frac{n - b}{a} \right \rfloor} {\binom{n}{a \times i + b}}$$

的值，由于结果可能很大，请输出结果对 $10^{9} +7$ 取模的值作为答案。

注：

• 其中 $\lfloor x \rfloor$ 表示最大的不超过 $x$ 的整数，如 $\lfloor 1.2 \rfloor = 1,\lfloor 4 \rfloor =4$ 。
• 其中 $\dbinom{n}{m}$ 表示组合数，即 $\dbinom{n}{m} = C_n^m = \dfrac{n!}{(n-m)!m!}$ 。

输入格式

第一行包含一个正整数 $T(1 \le T \le 3)$，表示测试用例的数量。

每个测试用例只有一行，包含三个正整数 $a, b, n(0 \le b < a \le 50, a \le n \le 10^{9})$。具体意义如题面所示。

输出格式

对于每个测试用例，输出一行一个整数，表示答案。

样例输入

3
1 0 10
20 2 1000
20 10 100000

样例输出

1024
208666789
572605725