0810 第 16 场 小白入门赛/强者挑战赛

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

T1. 喜鹊罢工【算法赛】

问题描述

七夕节到了，牛郎织女一年一度的浪漫相会也即将到来。然而，天庭新近实施了一项不合理的政策——"加班不给加班费"，这导致喜鹊们纷纷抗议并罢工，拒绝参与搭建连接银河两岸的鹊桥。

面对这样的困境，织女决定采取行动，她打算用自己的巧手编织出美丽的彩虹丝巾来搭建一座天桥，以确保与牛郎的相会能够如期进行。

已知每条彩虹丝巾的长度都是精确的 $7$ 米，而银河的宽度则是 $365$ 米。在织女精湛的编织技艺下，每条丝巾与下一条丝巾的连接部分可以巧妙地融合，几乎不产生任何长度上的损失。现在，请你计算，织女至少需要编织多少条彩虹丝巾，才能成功跨越银河，与牛郎团聚。

输入格式

本问题不需要任何外部输入。

输出格式

请输出一个整数，代表织女为了搭建足够跨越银河的天桥，至少需要编织的彩虹丝巾的数量。

T2. 牛郎取名【算法赛】

问题描述

什么？牛郎和织女竟然有孩子了！是的没错，在经过了每年一度的鹊桥相会后，他们的爱情终于开花结果。

为了给孩子取一个好听的名字，牛郎翻遍了天上的典籍，最终决定从织女精心准备的字符锦囊中按照特定的顺序选取所有字符来命名。

这个锦囊呀，一共包含了 $n$ 个小写字符，可以表示为 $s = s_1 s_2 \dots s_n$。牛郎苦思冥想后，确定了选取的顺序，依次为 $p_1, p_2, \dots, p_n$，并计划从织女的字符锦囊中分别取出第 $p_1, p_2, \dots, p_n$ 个字符，按顺序组成新的名字。

例如，锦囊里的字符是 $abcd$，牛郎选择了第 $3, 1, 2, 4$ 个字符，那么孩子的名字就是 $cabd$。

现在，牛郎将选取规则 $p$ 告诉你，请你帮他算出最终会组成什么样的名字吧！

喜鹊们都在叽叽喳喳地期待着这个特别的名字呢！

输入格式

第一行输入一个正整数 $n$（$1\leq n \leq 10^5$），表示字符宝囊中字符的个数。

第二行输入一个长度为 $n$、仅包含小写字母的字符串 $s$ ，表示字符宝囊中的字符。

第三行输入 $n$ 个整数 $p_1, p_2, \dots, p_n$（$1\leq p_i \leq n$，$p_i$ 互不相同） ，表示选取字符的顺序。

输出格式

输出一行一个字符串，表示最终组成的名字。

样例输入

5
abcde
5 4 3 2 1

样例输出

edcba

T3. 织女的考验【算法赛】

问题描述

七夕节即将到来，七夕城热闹非凡，牛郎想邀约美丽的织女一同前往七夕城漫步。

织女并不想轻易地接受牛郎的邀约，于是向他提出了一个有趣的字符串问题：

• 给定两个长度相等的小写字符串 $S$ 和 $T$，牛郎需要判断是否可以从 $S$ 和 $T$ 中各删除一个字符，使得删除后的 $S$ 经过重新排列后等于 $T$。若可以则输出 YES，否则输出 NO。

织女表示，如果牛郎能够回答正确，她就会同意牛郎的邀约。

但是，牛郎不太擅长处理字符串问题，为了抱得美人归，他需要你的帮助来解决这个问题。

输入格式

第一行输入一个整数 $t(1 \le t \leq 10^3)$，表示询问的数量。

接下来 $t$ 行，每行输入两个小写字符串 $S,T(1 \leq |S|,|T| \leq 10^3)$ 表示一次询问。

数据保证 $\sum_{i=1}^{t} |S|$ 不超过 $10^6$。

输出格式

输出 $t$ 行，每行一个整数表示答案，

输入样例

3
aba aac
abc ade
c d

输出样例

YES
NO
YES

说明

对于第 $3$ 个查询，操作后 $S,T$ 为空也视为相等。

T4. 仙男仙女【算法赛】

问题描述

七夕佳节，银河之上，鹊桥横跨，牛郎织女相会。

今年的鹊桥格外热闹，因为不仅织女翘首以盼，更有 $n$ 位美丽的单身仙女也来到了这里，希望能邂逅属于自己的幸福。

为了方便区分，每位仙女都被分配了一个唯一的编号，分别为 $1, 2, \ldots, n$。由于仙女数量众多，鹊桥上显得拥挤不堪。我们可以把鹊桥看作是一条笔直的天河，仙女 $i$ 位于天河上的坐标 $p_i$ 处。有些心急的仙女可能会挤在同一个坐标上，期盼着早点遇到心仪的对象。

为了维持秩序，同时也为了给仙女们创造一个良好的相亲环境，鹊桥的管理者月老决定制定一个规则：每位仙女都需要保持一定的安全距离。具体来说，对于仙女 $i$，月老会根据她的魅力值设定一个安全距离 $a_i$ 。只有当仙女 $i$ 周围 $a_i$ 的距离（即 $[p_i - a_i, p_i + a_i]$）内没有其他仙女时，她才能安心地与前来搭讪的仙男交谈，完成脱单。

然而，月老最近忙着为人间牵线搭桥，实在无暇顾及仙界的单身情况。因此，他找到了你，一个擅长算法的凡间少年，希望你能帮他算一下，今年七夕佳节，最终会有多少位仙女能够成功脱单？

输入格式

第一行包含一个整数 $n$（$1\leq n \leq 10^5$），表示仙女的数量。

第二行包含 $n$ 个整数 $p_1, p_2, ..., p_n$（$1\leq p_i \leq 10^9$），表示每位仙女在鹊桥上的坐标。

第三行包含 $n$ 个整数 $a_1, a_2, ..., a_n$（$1\leq a_i \leq 10^9$），表示每位仙女的安全距离。

输出格式

输出一个整数，表示能够成功脱单的仙女数量。

样例输入

5
1 5 6 7 10
2 2 2 2 2

样例输出

2

样例说明

能够成功脱单的有编号为 $1$、编号为 $5$ 的仙女。

T5. 牛郎的微信群【算法赛】

问题描述

在现代社会，随着通讯技术的高速发展，牛郎和织女不再依赖每年七夕才能相见，他们可以通过微信每天保持联系。

玩转微信的牛郎还建立了一个微信群，群里成员都是帮助过他们的喜鹊。

现在已知这个微信群里有 $n$ 个成员，分别用 $1, 2, \ldots, n$ 来标记。成员之间共有$n-1$ 对朋友关系，这些关系形成了一棵树结构。

为了更好地组织交流，牛郎想请你帮他计算出每个成员的“朋友的朋友”数量。具体来说，对于每个成员 $i = 1, 2, \ldots, n$，请你计算与该成员的距离为 $2$ 的其他成员的数量（“距离”是指在树中两个成员之间直接相连的边的数量）。

输入格式

第一行包含一个整数 $n$（$2\leq n \leq 2\times 10^5$），表示微信群成员的数量。

接下来 $n - 1$ 行，每行包含两个整数 $u$ 和 $v$（$1\leq u,v \leq n$，$u\neq v$），表示成员 $u$ 和成员 $v$ 之间存在朋友关系。

输出格式

输出一行，包含 $n$ 个整数。第 $i$ 个整数表示成员 $i$ 的“朋友的朋友”的数量。

样例输入

5
1 2
1 3
1 4
2 5

样例输出

1 2 2 2 1

样例说明

图片描述

• 成员 $1$ 的“朋友的朋友”有：成员 $5$。
• 成员 $2$ 的“朋友的朋友”有：成员 $3$、成员 $4$。
• 成员 $3$ 的“朋友的朋友”有：成员 $2$、成员 $4$。
• 成员 $4$ 的“朋友的朋友”有：成员 $2$、成员 $3$。
• 成员 $5$ 的“朋友的朋友”有：成员 $1$。

T6. 久别重逢【算法赛】

问题描述

每年的七月初七，本是牛郎织女鹊桥相会的甜蜜时刻。但在今年，状况突发，这对分别已久的恋人重逢时竟产生了一丝陌生，致使双方的亲密度降为 $0$。

为了重新点燃昔日的爱火，牛郎织女决定通过一次次的约会来提升亲密度。不过天庭有严格的规定，他们的亲密度不可超过 $n$。一旦超过 $n$，爱情之火就会因燃烧得过旺而触怒天条（天庭的戒律森严，对于爱情的尺度把控极为谨慎）。

牛郎深知每一次约会的机会都来之不易，他希望每次约会过后，亲密度能够至少能提升 $k$，毕竟他们相聚的时光是那样的短促，小幅度的增长实在难以满足他对爱情的热切渴望。他望着织女那熟悉又陌生的脸庞，心中暗暗发誓，一定要让这份感情恢复如初，甚至更加深厚。而织女又何尝不想与牛郎重归于好，她那美丽的眼眸中闪烁着坚定的光芒，愿意与牛郎一同努力，跨越这道因生疏而产生的情感鸿沟。

现在，请你计算出“在每次约会亲密度至少提升 $k$ 且亲密度总和不超过 $n$ ”的前提下，牛郎和织女的亲密度可以有多少种不同的变化过程？由于答案可能很大，请将结果对 $10^9 + 7$ 取余。

输入格式

输入仅一行，包含两个整数 $n$（$1\leq n \leq 10^5$），$k$（$1\leq k \leq n$），分别表示亲密度上限和每次约会后亲密度至少提升的幅度。

输出格式

输出一个整数，表示在每次约会亲密度至少提升 $k$ 且亲密度总和不超过 $n$ 的前提下，牛郎和织女亲密度变化过程的不同种类数对 $10^9 + 7$ 取余的结果。

样例输入

5 2

样例输出

8

样例说明

仅约会 $0$ 次：

• 亲密度：$0$。

仅约会 $1$ 次：

• 亲密度：$0 \rightarrow 2$。
• 亲密度：$0 \rightarrow 3$。
• 亲密度：$0\rightarrow 4$。
• 亲密度：$0\rightarrow 5$。

约会 $2$ 次：

• 亲密度：$0 \rightarrow 2 \rightarrow 4$。
• 亲密度：$0\rightarrow 2\rightarrow 5$。
• 亲密度：$0\rightarrow 3 \rightarrow 5$。

T7. 婚礼【算法赛】

问题描述

在遥远的天庭之中，有一对命运相连的天仙：牛郎和织女。他们相爱多年，奈何受到种种阻碍，一直未能修成正果。直到有一天，众神垂青，决定为他们举办一场盛大的天庭婚礼，庆祝这对天仙鸳鸯的喜结良缘。

在婚礼筹备过程中，最让新郎新娘头疼的就是如何挑选合适的伴娘和伴郎。毕竟在天庭中有 $(n + m + 1)$ 位神仙都希望参与其中，每个人对加入伴娘团或伴郎团都有着不同程度的向往和喜爱。

作为主婚人，牛郎和织女当然希望能够选出一支最高兴的伴娘团和伴郎团。也就是说，他们需要找到一种方案，使得被选中的神仙们的总开心程度达到最大。但由于名额限制，必然会有一位神仙无法参与进来，这无疑是个令人头痛的难题。

那么，当第 $i(i\in [1, n])$ 位神仙不参与到婚礼的伴娘团和伴郎团时，整个婚礼团队的最大开心程度是多少呢?

输入格式

第一行输入两个整数 $n,m(1 \leq n,m \leq 10^5)$ 表示伴娘团和伴郎团所需要的人数。

第二行输入 $n+m+1$ 个整数 $a_1,a_2,\cdots,a_{n+m+1}(0 \leq a_i \leq 10^9)$，第 $i$ 个整数表示第 $i$ 个神仙参加伴娘团时的开心程度。

第三行输入 $n+m+1$ 个整数 $b_1,b_2,\cdots,b_{n+m+1}(0 \leq b_i \leq 10^9)$，第 $i$ 个整数表示第 $i$ 个神仙参加伴郎团时的开心程度。

输出格式

输出 $n+m+1$ 个整数，其中第 $i$ 个整数表示第 $i$ 位神仙不参加伴娘伴郎团时婚礼团队的最大开心程度。

输入样例

3 2
1 2 3 4 5 7
5 2 9 2 7 1

输出样例

29 30 25 28 27 25

说明

对于第 $1$ 个神仙，当其不参加婚礼时。$[2,4,6]$ 号神仙参加伴娘团，$[3,5]$ 号神仙参加伴娘团可以得到最大开心程度。答案为 $2+4+7+9+7=29$。

T8. 七夕城【算法赛】

问题描述

七夕来临，天庭之中洋溢着浪漫的氛围。在充满诗情画意的七夕城里，有一对儿年轻的天仙——牛郎和织女，他们打算利用这个佳节为自己赚些零花钱。

这对天仙恋人商量后，决定分别在七夕城的不同集市售卖鲜花。七夕城共有 $N$ 个集市，通过 $N-1$ 条道路相互连通，其中 $1$ 号集市被视为主集市，七夕城的大门也坐落于此。每个集市都有一个热闹程度 $A_i$ 的值。

牛郎和织女的目标是：找到两个不同的集市 $u$ 和 $v$，其中 $u$ 为牛郎的售卖点，$v$ 为织女的售卖点，使得 $A_u$ 与 $A_v$ 的按位异或值 $A_u \oplus A_v$ 最小。同时，牛郎希望能够在从自己的集市 $u$ 前往 $1$ 号主集市的路上，恰好经过织女所在的集市 $v$，这样两人就可以一起离开七夕城。

现在，牛郎想知道，当织女位于 $v(v \in[1,n])$ 号集市售卖时，$A_u \oplus A_v$ 可能的最小值为多少，若不存在符合条件的 $u$ 号集市则输出 $-1$。

输入格式

第一行输入一个整数 $N(2 \leq N \leq 10^5)$ 表示集市数量。

接下来 $N-1$ 行每行输入两个整数 $u,v( 1 \leq u,v \leq N, u\ e v)$ 表示集市 $u,v$ 之间存在一条道路。

最后一行输入 $N$ 个整数 $A_1,A_2,A_3,\cdots,A_N(1 \leq A_i \leq 10^8)$ 表示每个集市的热闹程度。

输出格式

输出一行 $n$ 个整数表示答案。

输入样例

5
3 4
2 4
1 2
4 5
7 10 18 92 1

输出样例

6 11 -1 78 -1

说明

样例的图如下，当 $v=4$ 时，令 $u=3$ 可以使得 $A_u \oplus A_v$ 最小。

图片描述

T9. 花魁之争【算法赛】

问题描述

每逢七夕，牛郎织女都会在鹊桥上相会。为了增添节日气氛，王母娘娘决定借鉴这一浪漫传统，在天庭举办一场别开生面的“花魁大赛”。

比赛共有 $n$ 位仙女参加比赛。每位仙女都准备了一串花环，花环可以看作是一个字符串，字符串上的每个字符都表示花环中的一朵花。由于仙女们心灵纯净，彼此之间毫无秘密，因此每位仙女都知道其他仙女的花环是什么样的。

比赛的规则如下：每位仙女需要确定她们心目中鹊桥的适宜长度（长度为正整数），并将这个长度告知织女。织女会从所有仙女所提供的长度中选取最短的作为鹊桥的最终长度（记为 $m$）来搭建鹊桥。在鹊桥搭建完成之后，每位仙女都必须对自己的花环进行 $m$ 次调整。每次调整，可以选择花环中两个不同位置的花朵，并交换它们的位置。待所有仙女都调整完后，拥有字典序最小的花环的仙女将赢得比赛，成为今年的“花魁”（如果有多个仙女都拥有字典序最小的花环，那么她们将共同分享“花魁”的称号）。

已知所有仙女都想要成为“花魁”，并且都会采用最优策略。那么请问，在这种情况下，会有多少仙女成为“花魁”？

每位仙女希望在自己成为花魁的前提下，共享花魁称号的仙女尽可能少。

输入格式

第一行包含一个整数 $n$（$2 \leq n \leq 10^5$），表示参加比赛的仙女数量。

接下来 $n$ 行，每行包含一个长度在 $2 \sim 10^5$ 之间、仅由小写字符构成的字符串 $S$，表示仙女们的花环。

数据保证输入的字符串总长度不超过 $10^6$。

输出格式

输出一个整数，分别表示“花魁”的数量。

样例输入

3
abc
acb
bac

样例输出

2

样例说明

在最优方案下，第二位仙女和第三位仙女选择的长度可以是 $1$。由于 $1$ 是最小的正整数，因此无论第一位仙女选择的长度为多少，$m$ 都必定为 $1$。

在必须进行 $1$ 次调整的情况下：

• 第一位仙女可以将 $abc$ 中的 $b$ 和 $c$ 交换，得到 $acb$。
• 第二位仙女可以将 $acb$ 中的 $b$ 和 $c$ 交换，得到 $abc$。
• 第三位仙女可以将 $bac$ 中的 $b$ 和 $a$ 交换，得到 $abc$。

第二位仙女、第三位仙女将成为“花魁”，“花魁”的总数为 $2$。