字节跳动秋招 2023.10.08 编程题目与题解

发表于 2023-10-09 分类于笔试阅读次数：本文字数： 3.8k 阅读时长 ≈ 3 分钟

1、小红操作数组

小红拿到了一个数组，她准备进行任意次以下操作：

选择一个正整数\(x\)，使得数组的每个\(a_i\)都变成\(x\%a_i\)。

小红希望最终数组的每个元素都相等目大于\(0\)。她想要你告诉她能否达成目的。

输入

有多组测试用例，第一行输入一个整数\(t\)，表示用例组数。

接下来每\(2\times t\)行，表示一组用例。对于每组用例：

第一行输入一个正整数\(n\)，代表数组的大小。

第二行输入\(n\)个正整数\(a_i\)，代表小红拿到的数组。

\(1\le t, n, a_i \le 10^5\)

保证\(n\)的总和不超过\(10^5\)。

输出

如果可以使得所有数相等且大于\(0\)，输出"Yes"。否则输出"No"。

样例

输入：
3
2
3 6
3
1 2 3
2
3 3

输出：
Yes
No
Yes

解答

如果\(a\)中的这些数都相同，那么不需要任何操作就是符合题意的。

否则，就需要进行至少\(1\)次操作。如果存在某个\(a_i=1\)，那么无论选什么\(x\)，\(a_i\)都变成\(0\)，这是不符合题意的；否则我们选\(x=1\)进行一次操作，那么下一步\(a\)中所有数都变成\(1\)，这是符合题意的。

代码

def solve():
    input()
    st = set(map(int, input().split()))
    return 1 not in st or len(st) == 1


T = int(input())
for _ in range(T):
    print("Yes" if solve() else "No")

2、小红的有根树

小红拿到了一棵有根树，其中根是\(1\)号节点。小红准备给每个节点染成红色或者绿色或者蓝色。但是有以下两个要求：

每个节点和它的父亲颜色不同。（如果它存在父亲）
每个节点和它的父亲的父亲颜色不同。（如果它存在父亲的父亲）

请你输出任意一种染色方案。

输入

第一行输入一个正整数\(n\)，代表节点的数量。

接下来的\(n-1\)行，每行输入两个正整数\(u\)和\(v\)，代表节点\(u\)和节点\(v\)有一条边连接。

\(1 \le n \le 10^5\)
\(1\le u,v\le n\)

输出

一个长度为\(n\)的、仅由'R','G','B'三种字母组成的字符串。第\(i\)个字符为'R'代表\(i\)号节点被染成红色，为'G'代表染成绿色，'B'代麦染成蓝色。

如果有多解，输出任意即可。

样例

输入：
4
1 2
3 4
1 3

输出：
BGRG

样例1的染色如下图：

graph TD
  1((1));2((2));3((3));4((4))
  classDef red-node fill:red, color:white;
  classDef blue-node fill:blue, color:white;
  classDef green-node fill:green, color:white;
  class 1 blue-node;
  class 2 green-node;
  class 3 red-node;
  class 4 green-node;
  1---2;3---4;1---3

解答

从另一个角度考虑这个问题：对于一个节点\(u\)，其所有直系后代和直系后代的直系后代都不能和\(u\)有相同的颜色。因此，我们只需要让\(u\)的所有直系后代染上同一种颜色，以及让直系后代的直系后代也染上同一种颜色即可。

也就是说，每一层染上的颜色都是相同的，只需要相邻三层的节点染上的颜色都不相同即可，这个过程通过DFS即可完成。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=100004;

vector<int>g[N];
char s[N],t[]="RGB";
void dfs(int u,int fa,int d){
    s[u]=t[d%3];
    for(int v:g[u]){
        if(v==fa) continue;
        dfs(v,u,d+1);
    }
}
int main(){
    int n,x,y;
    scanf("%d",&n);
    for(int i=1;i<n;i++){
        scanf("%d %d",&x,&y);
        g[x].push_back(y);
        g[y].push_back(x);
    }
    dfs(1,0,0);
    puts(s+1);
}

3、小红做糖葫芦

小红想用山楂制作糖葫芦，一串糖葫芦用一串字符串表示，糖葫芦的甜度为串上所有字符的甜度之和。字符的甜度为这个字符与字符'a'的差值。

即'a'的甜度为\(0\)，'b'的甜度为\(1\)……，'z'的甜度为\(25\)。小红有\(n\)个山植按顺序从\(1\)到\(n\)依次摆放，山植被表示为一个字符，山植的甜度即为字符的甜度。

小红制作糖葫芦时，需要取出一段连续的山楂制作成糖葫芦。

小红想知道，在所有可能被制成的糖葫芦中，甜度第\(k\)大的糖葫芦甜度为多少？

若有一根糖葫串本身或翻转后与另一串糖葫芦相同，则这两串糖葫芦被视为是相同的糖葫芦。

例如，糖葫芦"abc"与"cba"被认为是相同的。

糖动芦。

输入

第一行输入两个整数\(n,k(1\le n\le 200,1\le k\le n \times(n+1)/2)\)

第二行输入一个长度为\(n\)的字符串，表示山楂的摆放顺序。

输出

一行一个整数，表示甜度第\(k\)大的是多少。若可能产生的糖葫芦数小于\(k\)，则输出\(-1\)。

样例

输入：
3 4
abc

输出：
1

提示：
可能制作的糖葫芦串为a,b,c,ab,bc,abc。甜度分别为0,1,2,1,3,3，其中第4甜的糖葫芦串甜度为1。

输入：
3 4
aba

输出：
0

提示：
可以制作的糖葫芦只有4种："a"、"b"、"ab"、"aba"甜度分别是0,1,1,2，第4甜的糖葫芦甜度为0。请注意，"ba"和"ab"被视为同一种糖葫芦。

解答

这题可以使用暴力完成，因为它的长度只有\(n\le 200\)。

使用一个集合\(S\)存储一些字符串。枚举输入的字符串\(s\)中的每个子串，判断它是否已经存在了\(S\)中，如果不存在，那么就暴力求它的甜度值出来存放在另一个数组\(A\)中，并将\(s\)和\(s\)的逆序存入\(S\)中。

最终将\(A\)排序后，输出第\(k\)大的值即可，当然如果\(A\)的长度不足\(k\)，那么输出\(-1\)。

代码

n, k = map(int, input().split())
s = input()
st = set()
a = []
for i in range(n):
    for j in range(i, n):
        t = s[i:j + 1]
        if t in st:
            continue
        st.add(t)
        st.add(t[::-1])
        a.append(sum(ord(ch) - ord('a') for ch in t))

a.sort(reverse=True)
print(-1 if k > len(a) else a[k - 1])

4、小红合并数组

小红拿到了一个数组，她可以进行以下操作：选择两个相同的元素\(x\)，将它们删除，并将\(2x\)添加进数组。这种操作称为一次“合并”。

小红在进行合并之前可以先往数组里添加任意一个元素。之后小红希望最大化“合并”的次数。请你帮帮小红。

输入

第一行输入一个正整数\(n\)，代表数组的大小。

第二行输入\(n\)个正整数\(a_i\)，代表小红拿到的数组。

\(1\le n \le 10^5\)
\(1 \le a_i \le 10^9\)

输出

输出两个整数，第一个数为添加的元素，第二个数为合并的最大次数。

如果有多种添加的方案，输出任意一个即可。

样例

输入：
3
1 1 3

输出：
3 2

提示：
添加3后，数组变成[1,1,3,3]，可以合并两次。
添加2也是可以的，依然可以合并2次。

解答

可见，无论一开始对\(a\)怎么操作，到最后无法合并时，\(a\)中的所有数都只出现了一次。并且，按照二进制中“进位”的性质，无论执行操作的次序如何，到最后无法合并时，最终得到的数组总是同一个数组（与其说是数组，不如说是集合\(S\)，因为这些数都是无序的）。

对于一个新加入的\(x\)，如果\(x,2x,4x,8x,\dots,2^{k-1}x\)都在数组中，但是\(2^kx\)不在数组中，那么我们可以进行\(k\)次合并操作，并且最终得到新的数\(2^kx\)。

因此，考虑已经对\(a\)进行完了所有操作，得到数组\(a'\)，这时数组\(a'\)没有办法再进行下一步操作，我们将\(a'\)看成是一个集合\(S\)。枚举\(S\)中的每个数\(x\)，作为一开始要添加到数组\(a\)中的数，然后找到最大的\(k\)使得\(x,2x,4x,8x,\dots,2^{k-1}x\)都在数组中，但是\(2^kx\)不在数组中。这时我们就可以多进行\(k\)次操作。由于整个操作的过程中，数组的元素和保持不变，因此这个\(k\)值也会很小，直接枚举即可。

最终，找到最大的\(k\)值和对应的\(x\)，那么总操作次数为\(n-|S|+k\)。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=100004;

ll a[N];
int n;
int main(){
    scanf("%d",&n);
    unordered_set<ll>st;
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
    }
    for(int i=1;i<=n;i++){
        ll x=a[i];
        while(st.count(x)){
            st.erase(x);
            x<<=1;
        }
        st.insert(x);
    }
    ll k=0;int v=0;
    for(ll x:st){
        if(x%2==0&&st.count(x/2)) continue;
        int j;
        for(j=1;st.count(x<<j);++j);
        if(j>v){
            k=x;v=j;
        }
    }
    printf("%lld %d\n",k,n-st.size()+v);
}

5、小红统计子数组

小红拿到了一个大小为\(n\)的数组，她想知道，有多少个连续子数组满足，该子数组所有元素的乘积是\(k\)的倍数？

输入

第一行输入两个正整数\(n\)和\(k\)。

第二行输入\(n\)个正整数\(a_i\)。

\(1\le n \le 10^5\)
\(1\le a_i \le 10^6\)
\(1\le k \le 10^{12}\)

输出

满足条件的子数组数量。

样例

输入：
3 6
2 3 4

输出：
3

解答

这题我们可以很轻易地想到使用双指针来解决。令\(\displaystyle{s_i=\prod_{j=1}^ia_j,s_0=1}\)为数组\(a\)的前缀积，那么区间\(a[l:r]\)的子数组元素之积可以表示成\(\dfrac{s_r}{s_{l-1}}\)。枚举每个右指针\(r\)，找到一个最小的\(l(0\le l\le r)\)满足\(\dfrac{s_r}{s_l}\)不是\(k\)的倍数。那么\(\forall i=[0,l)\)，子数组\(a[i+1,r]\)都是\(k\)的倍数，将这\(l\)个数都统计进答案即可。时间复杂度为\(O(n)\)。

但是问题在于，前缀积\(s_i\)的值可能很大。如何进行优化？

考虑\(k\)这个数，如果一个数是\(k\)的倍数，那么对于它所有在\(k\)中的质因子的出现次数都至少是\(k\)对应的质因子的出现次数。更正式的说，令\(k\)的质因数分解为\(\displaystyle{k=\prod_{i=1}^mp_i^{e_i}}\)，那么如果一个数\(n\)满足它是\(k\)的倍数，那么\(\forall i\in[1,m],n\)至少有\(e_i\)个质因子\(p_i\)。

这启发我们可以换另外一种思路，将一个前缀积转化为多个前缀和的做法。首先构造\(m\)个数组\(b_i\)，其中\(b_{i,j}\)表示\(a_j\)包含的质因子\(p_i\)的个数，令\(\displaystyle{t_{i,j}=\sum_{k=1}^jb_{i,k},b_{i,0}=0}\)，也就是说，\(t_{i,j}\)其实是\(s_{i,j}\)中因子\(p_i\)的次数，这时我们上面类似的思路，同样采用如下双指针法，即可完成本题：枚举每个右指针\(r\)，找到一个最小的\(l(0\le l\le r)\)。使得存在\(i\in[1,m],t_{i,r}-t_{i,l}<e_i\)成立，类似的，将\(l\)统计进答案即可。时间复杂度为\(O(n\log k+\sqrt{k})\)，足以通过本题。

代码

import sympy

n, k = map(int, input().split())
a = list(map(int, input().split()))
fact = list(sympy.factorint(k).items())
ls = [[0] * len(fact)]
for x in a:
    b = ls[-1].copy()
    for i, (p, r) in enumerate(fact):
        while x % p == 0:
            x //= p
            b[i] += 1
    ls.append(b)


def check(l, r):
    for i in range(len(fact)):
        if ls[r][i] - ls[l][i] < fact[i][1]:
            return True
    return False


l = 0
ans = 0
for r in range(1, n + 1):
    while not check(l, r) and l < r:
        l = l + 1
    ans += l
print(ans)