笔试题 7

字节跳动

[难度: 1 星] 卖火柴的小女孩（节选）

问题描述

小女孩又擦亮一根火柴，火光把四周照得通亮，奶奶在火光中出现了。奶奶朝着她微笑着，那么温柔，那么慈祥。

“奶奶——”小女孩激动得热泪盈眶，扑进了奶奶的怀抱，“奶奶，请把我带走吧，我知道，火柴一熄灭，您就会不见了！”

“我亲爱的孙女儿，奶奶不会离开你的。奶奶学会了一种魔法，只要你能用三根火柴拼出一个三角形，这三根火柴就永远不会熄灭！”

“真的吗？太好了！奶奶，我现在就可以拼出来。看！还是个三边相等、有三条对称轴的正三角形呢！”小女孩激动得手舞足蹈。

“傻孩子，魔法怎么会这么简单就能完成的呢，火柴的长度需要满足一定的条件，它们的长度都为整数，也必须在 $[l, r]$ 的区间内，且任意两根火柴的长度不能相等。”

这可难倒小女孩了，你能帮她达成心愿吗？

输入格式

输入包含两个正整数 $l$ 和 $r$，含义如题。

输出格式

如果小女孩的心愿能够达成，则在第一行输出 YES，并在第二行输出三个整数，表示答案，否则输出 NO。若有多种可能的答案，输出任意一种即可。

输入样例 1

10 15

输出样例 1

YES
10 15 13

输入样例 2

500 500

输出样例 2

NO

数据范围

1 <= l <= r <= 100000

解题思路

首先检查 $[l, r]$ 的区间长度至少要为 3，其次找到 $r$, $r-1$, $r-2$，只要满足 $(r-2)+(r-1)>r$（或者特判 1, 2, 3 的非法情况），就是答案，属于偏思维题，本题没有唯一解，spj 需要检查的情况比较多。

[难度: 1 星] 小 Byte 的情书

问题描述

小 Byte 想在七夕当天写情书给小 Dance 表白。但是小 Byte 很害羞，不希望别人看见这封情书，于是就利用一些规则对这封情书进行了加密，并将加密后的情书和加密法则送给了小 Dance。由于情书篇幅比较大，小 Byte 的加密法则解密起来过于烦琐，小 Dance 不能看懂，这样的话小 Byte 表白就失败了。小 Byte 拜托你去帮小 Dance 解密情书，使他表白成功！

已知小 Byte 的情书内容原文为一串不加标点的英文，如 "Welcome to bytedance"。小 Byte 的加密法则为：

1. 对每个单词进行加密；
2. 不改变单词的大小写；
3. 针对每个单词，从第 1 个字母开始标序号，到最后一个字母，取出所有序号为奇数的字母，连起来作为加密后单词的前半部分。再倒着取出所有序号为偶数的字母，作为单词的后半部分。例如："abcdefg" 他加密后的前半部分为 "aceg"，加密后的后半部分为 "fdb"，整个字符串加密后为 "acegfdb"。

输入格式

第一行为一个整数 $n$，表示情书中总共有 $n$ 个单词，第二行为一串不带标点的字符串，单词仅包含大写字母与小写字母，每个单词之间用一个空格分隔，为加密后的情书。

输出格式

利用规则解密后的情书内容。

输入样例

3
Wloemce to btdnecaey

输出样例

Welcome to bytedance

数据范围

整篇情书的字母数量之和不大于 5000。

解题思路

用两个下标在单词两端扫描，一个从左往右扫，另一个从右往左扫，来填充原单词，当处于原单词奇数位的时候，取左边的下标对应的字母，当处于原单词偶数位的时候，取右边的下标对应的字母，两个下标不断往中间靠拢，直到填满整个单词。

[难度: 2 星] 小 Byte 的 RP

问题描述

字节跳动的笔试马上就要开始了，小 Byte 从一周前就开始紧张，他祈祷自己能够拿到满意的分数——这时候上帝出现了，告诉他其实每个人都有一个 RP 值，并且以周为单位，在一周的开始，上帝给每个人每天都设了一个 RP 值，RP 值越高，他在这天就越幸运。

上帝给了小 Byte 一个机会，允许他调整自己的 RP 值，若他将自己一周中某一天的 RP 值增加 1，在另一天他的 RP 值必须要减少 1，他有无数次调整的机会，但是一旦确定下来，就不能改变，他接下来这一周就必须按照这个 RP 值生活。在调整的过程中 RP 值必须始终保持在区间 $[0, 9]$ 以内，不能超出这个范围，且每天的 RP 值都必须为整数。若小 Byte 每天严格遵守这样的 RP 值生活，到笔试当天，他的分数就等于过去 7 天每一天 RP 值的乘积，否则他将受到惩罚得到 0 分。

输入格式

第一行为一个整数 $T$，表示有 $T$ 组数据，接下去 $T$ 行，每行 7 个整数 $a_i$，第 $i$ 个整数表示第 $i$ 天小 Byte 的 RP 值。

输出格式

输出小 Byte 能得到的最大的笔试分值。

输入样例

2
1 1 1 1 1 1 1
0 1 1 1 1 1 2

输出样例

1
1

数据范围

1 <= T <= 100, 0 <= a_i <= 9

解题思路

由于对其中 1 个数字加 1 就要对另 1 个数字减 1，因此 7 个数字的总和始终不变。

1. 由基本不等式拓展可以得到，要使得乘积最大必须要尽量平均分这 7 个数字。令 $sum=a_1+a_2+\cdots+a_7,~mod=sum\%7$，可知 7 个数中有 $mod$ 个数被分配为 $\lfloor\frac{sum}{7}\rfloor+1$，有 $7-mod$ 个数字被分配为 $\lfloor\frac{sum}{7}\rfloor$，因此答案为：
   

   $$ans=\left(\lfloor\frac{sum}{7}\rfloor+1\right)^{mod}\times\lfloor\frac{sum}{7}\rfloor^{7-mod}$$

2. 定义 $dp_{i,j}$ 表示前 $i$ 个数字的和为 $j$ 时能得到的最大乘积。第 $i$ 个数字可以取的合法范围为 $\left[0,\min(9, j)\right]$，枚举第 $i$ 个数字可能的取值 $k$，可以得到递推式：
   

   $$dp_{i,j}=\max(dp_{i-1,j-k}\times k)\quad k\in[0,\min(j,9)],~j-k\leq9(i-1)$$
   初始条件为 $dp_{1,j}=j,~j\in[0,9]$，最后的答案就是 $dp_{7,sum}$，也就是前 7 个数字的和为 $sum$ 时乘积的最大值。

[难度: 2 星] Greatest Common Divisor

问题描述

给定一个 $n$ 个节点的多叉树，树的根节点编号为 1，第 i 个节点权值为 $w_i$，总共有 $q$ 次询问，每次询问树上任意两个节点 $u,v$，对于所有包含这两个节点的子树，找到节点数最少的，并求出该子树中，所有其他节点权值的最大公约数。

输入格式

第一行为两个整数 $n$ 和 $q$，表示有 $n$ 个节点和 $q$ 次询问。

第二行为 $n$ 个整数，$w_1,w_2,\cdots,w_n$，分别表示每个节点的权值。

接下来的 $n-1$ 行，每行两个整数 $u,v$，表示节点 $u$ 与节点 $v$ 之间有一条连边。

接下来的 $q$ 行，每行为两个整数，即询问的两个节点编号。

输出格式

对于每次询问，输出题目所求答案，每次询问的输出占一行。若除去被询问的节点后不存在其他节点，则输出 0。

输入样例

6 4
20 30 15 10 1 100
2 1
3 4
5 6
5 3
1 3
4 5
5 2
5 3
5 6

输出样例

15
5
10
0

数据范围

对于 $50\%$ 的数据，$2\leq n,q\leq1000$

对于 $100\%$ 的数据，$2\leq n,q\leq1000000,~1\leq w_i\leq10^9,~1\leq u,v\leq n,~u\neq v$

数据保证结构为一棵树

解题思路

题目所求子树即被询问的两个节点的最近公共祖先所对应的子树，求最近公共祖先可以用树链剖分或 LCA 在 $O(\log n)$ 内求得，对整棵树 dfs，按照 dfs 的顺序对每个节点从 1 到 $n$ 编号，即可将整棵树展开成一个一维数组，每一个子树对应数组内一段连续的区间，将被询问的两个节点从数组中去掉，即求三段连续区间的 gcd，gcd 满足可加性，且整棵树不带修改，可以用 ST 表预处理，以 rmq 的方式计算连续区间内的 gcd，最后求三段连续区间的 gcd，将答案的初始值设为 0 即可（0 和其他任意整数 $4$ 的 gcd 为 $x$）。总时间复杂度为 $O(n+2n\log n+n\log n\log n+q(\log n+3\log n))$。

[难度: 3 星] 香槟酒

问题描述

为了庆祝字节跳动七周年，活动台前幕后的工作人员们开了一场香槟酒会。

所有酒杯被摞成一个金字塔，接着由主持人从最顶层的酒杯往下倒酒，如果顶层的酒杯被倒满了酒，多出来的酒就会溢出到第二层（向左右两边溢出的速率相等，如下图）。现在我们按照从上到下、从左到右的顺序对酒杯从 1 开始编号，第 $i$ 层第 $j$ 个酒杯的编号为 $(i,j)$，例如顶层的酒杯编号为：$(1,1)$。

每一个酒杯的容积都相同，我们设为一个单位体积，问如果想要把酒杯 $(i,j)$ 装满，最少需要多少单位体积的香槟酒？

输入格式

输入为两个正整数 $a,b$，表示被询问的酒杯编号。

输出格式

输出一个实数，表示至少需要向最顶端的酒杯倒多少单位体积的香槟，才能倒满酒杯 $(a,b)$。

如果你的输出与标准输出的绝对值不超过 $10^{-6}$，则认为你的程序是正确的。

输入样例 1

1 1

输出样例 1

1

输入样例 2

2 2

输出样例 2

3

数据范围

1 <= b <= a <= 30

解题思路

可以发现，如果已知要倒多少香槟酒到顶端的酒杯，就可以 $O(n^2)$ 地计算出酒杯 $(i,j)$ 最终含有的香槟酒的体积（用一个二维数组保存对应位置酒杯的酒的体积，模拟一遍倒酒的过程，注意没有被倒满的酒杯无法溢出）。

并且：往顶端的酒杯倒越多的香槟酒，酒杯 $(i,j)$ 内香槟酒的体积可能就越大，如果把香槟酒的总体积作为变量，酒杯 $(i,j)$ 内的香槟酒体积作为函数值，就是一个单调非递减的函数，满足二分性质，因此可以用二分来求满足函数值等于 1 的变量的最小值。

由找规律可以得到，要倒满 $(30,30)$ 位置的酒杯需要最大的体积，最大值为 $2^{30}-1$，因此二分的初始区间为 $[1,2^{30}-1]$。

数据注意

一定要包含一组 30 30 的数据。