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

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

1、小红的赛车队

假设有\(n\)个赛车队参加一场比赛，每个赛车队的车辆数为\(a_i\)辆，要将这\(n\)个赛车队分成小组，每个小组里的车辆总数不超过\(4\)辆，并且不能把赛车队拆开。问最少需要多少个小组。

输入

一行一个整数\(t\)，表示数据组数。

每组数据第一行一个整数\(n\)，表示赛车队数。

接下来一行\(n\)个整数\(a_i\)，表示每个赛车队的车辆数。

\(1 \le t \le 100\)
\(1\le n \le 10^3\)
\(1 \le a_i\le 4\)

输出

输出\(t\)行，每行一个整数，表示最少需要的小组数。

样例

输入：
1
4
1 2 3 4

输出：
3

提示：
前两个车队一组，第三个车队一组，第四个车队一组即可。

解答

本题可以使用贪心的思想进行解决。

可见，\(4\)辆一队的队伍无法和其它队伍成组，必须自己成组。\(3\)辆一队的队伍参加组合，要么自己成组，要么带上一个\(1\)辆一队的车队。

如此，处理完\(4\)辆一队和\(3\)辆一队的车队，剩下\(2\)辆一队和\(1\)辆一队的车队。为了尽量减少成组数量，让\(2\)辆一队的车队两个两个组合。如果\(2\)辆一队的车队还剩下一个，那么可以至多带上\(2\)个\(1\)辆一队的车队。剩下的\(1\)辆一队的车队直接尽可能地进行组合，如果这时仍然有\(c\)个\(1\)辆一队的车队，那么至少还需要组成\(\lceil c/4\rceil\)个组。

代码

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

int c[7];
int solve(){
    memset(c,0,sizeof(c));
    int n,x;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&x);++c[x];
    }
    int ans=c[4]+c[3];
    c[1]=max(0,c[1]-c[3]);
    ans+=c[2]>>1;
    if(c[2]&1){
        ++ans;
        c[1]=max(0,c[1]-2);
    }
    ans+=(c[1]+3)/4;
    return ans;
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        printf("%d\n",solve());
    }
}

2、小红走迷宫

小红和朋友被困在了迷宫里，迷宫有\(n\)个传送阵，每个传送阵都有一个编号\(i\)(编号从\(1\)到\(n\))，编号为\(i\)的传送阵会将小红传送到编号为\(a_i\)的传送阵。小红最初在编号为\(s\)的传送阵，朋友最初在编号为\(t\)的传送阵，小红和朋友都可以通过传送阵传送，每次传送都会花费一分钟（两人可以同时传送）。现在小红想知道，小红和朋友最少需要多少分钟才能在同一个传送阵里见面，如果不能见面，输出\(-1\)。

输入

第一行输入三个整数\(n,s,t\)，表示传送阵的数量，小红最初所在的传送阵编号，朋友最初所在的传送阵编号。

第二行输入\(n\)个整数\(a_i\)，表示编号为\(i\)的传送阵会将小红传送到编号为\(a_i\)的传送阵。

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

保证\(a_i\)数组中的元素互不相同。

输出

输出一个整数，表示小红和朋友最少需要多少分钟才能在同一个传送阵里见面，如果不能见面，输出\(-1\)。

样例

输入：
5 1 2
5 1 2 3 4

输出：
1

提示：
朋友可以通过一次传送到达小红所在位置。

解答

首先对小红自己的坐标进行多次迭代，求出首次到达时间，令\(c_i\)表示小红首次到达\(i\)的时间，\(c_i=-1\)意味着小红无法从\(s\)到达\(i\)。可见，小红必定会在有限次内多次到达同一个节点，这时停止迭代。

接下来让朋友的坐标进行多次迭代。同样的，只要到达已经传送过的节点就停止。假设朋友在时间\(i\)到达节点\(u\)，并且\(c_u\neq -1\)，那么说明小红可以以\(c_u\)的时间到达节点\(u\)，这时\(\min\{i,c_u\}\)是一个候选答案。

代码

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

const int N=100004;
int c[N],vis[N],a[N];
int main(){
    int n,s,t;
    scanf("%d %d %d",&n,&s,&t);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    memset(c,-1,sizeof(c));
    for(int i=0;i<=n+1;i++){
        if(c[s]!=-1) break;
        c[s]=i;
        s=a[s];
    }
    int ans=n+1;
    for(int i=0;i<=n+1;i++){
        if(!vis[t]){
            vis[t]=1;
            if(c[t]!=-1)
                ans=min(ans,max(i,c[t]));
            t=a[t];
        }
        else break;
    }
    if(ans>n) ans=-1;
    printf("%d\n",ans);
}

3、小红的前缀和之和

给定两个正整数\(n,x\)，小红希望你构造一个长度为\(n\)的数组，满足\(\displaystyle{\sum_{i=1}^n\text{sum}(i)= x}\)。

\(\text{sum}(i)\)即数组的前\(i\)项之和。换言之，小红希望你构造一个长度为\(n\)的数组满足，\(n\)个前缀和之和等于\(x\)。

要求数组的元素仅由\(1\)和\(2\)组成。

输入

两个正整数\(n,x\)

\(1\le n \le 10^5\)
\(1 \le x \le 10^{18}\)

输出

如果无解，请输出\(-1\)。

否则输出\(n\)个正整数，每个正整数为\(1\)或者\(2\)。有多解时输出任意即可。

样例

输入：
3 8

输出：
1 2 1

提示：
三个前缀和分别是1,3,4,1+3+4=8，符合条件。

解答

令需要打印的数组为\(a\)。那么根据\(\text{sum}(i)\)中每个元素的贡献，可以发现其前缀和的和为\(\displaystyle{s=\sum_{i=1}^n(n-i+1) a_i}\)。可以发现这是一个关于\(a\)的线性表达式，并且其系数都是正数。

由于\(a_i\in\{1,2\}\)，因此\(s\)的值至少为\(\dfrac{n(n+1)}{2}\)，至多为\(n(n+1)\)。这意味着如果存在答案，那么\(x\)的值应该在这两个界限之间。

之后开始考虑填入\(a\)的每个数。为了正确处理上下界的过程，我们假设这时填入某个新数组\(a'\)的元素\(a'_i\)的是\(0\)和\(1\)，并且数组之和为\(x'=x-\dfrac{n(n+1)}{2}\)，这意味着我们对每个元素都加上\(1\)就可以得到原问题的答案。一开始假设\(a'\)中所有元素为\(0\)。令\(s\)的系数\(c_i=n-i+1\)。我们按照\(i\)小到大的顺序（也就是\(c_i\)从大到小的顺序）枚举\(i\)，判断将\(a_i'\)改成\(1\)是否会导致前缀和之和\(\displaystyle{s'=\sum_{i=1}^nc_i a'_i}\)是否会超过\(x'\)，如果不超过，那么将\(a_i'\)变成\(1\)。可见只要\(x'\)不超过\(\dfrac{n(n+1)}{2}\)，这样子枚举一定是有解的。

代码

def solve():
    n, x = map(int, input().split())
    x -= n * (n + 1) // 2
    if x < 0:
        return [-1]
    a = []
    for i in range(n):
        if n - i <= x:
            a.append(2)
            x -= n - i
        else:
            a.append(1)
    return [-1] if x > 0 else a


print(*solve())

4、不相交区间

现有一个长度为\(n\)的数组\(a\)和\(m\)个区间。

你可以选择任意个区间，选择的区间不能相交。如果选择一个区间\([l,r]\)。那么可以获得\(\displaystyle{\sum_{i=l}^ra_i}\)的分数。

请你计算出你可以获得的最大分数。

请注意，如果区间右端点在数组的范围之外，则该区间不可选取。

假设两个区间分别是\([l_1,r_1]\)和\([l_2,r_2]\)，如果它们满足\(l_1 \le l_2\le r_1\)或\(l_2\le r_1\le r_2\)，则认为这两个区间相交。

输入

第一行两个整数\(n,m\)，表示数组的长度和区间的个数。

第二行\(n\)个整数\(a_i\)，表示数组的元素。

接下来\(m\)行每行两个整数\(l_i,r_i\)，表示每一个区间。

\(1\le n,m,a_i\le 10^5\)
\(1\le l\le r\le 10^5\)

输出

输出一个整数，表示可以获得的最大分数。

样例

解答

这是一道比较明显的动态规划问题。

令数组\(a\)的前缀和为\(\displaystyle{s_i=\sum_{j=1}^ia_j},s_0=0\)。令\(f(r)(0\le r\le n)\)表示前\(r\)个元素中，一个最优秀的选法所得到的最大分数和（如果有一些区间的右端点超过了\(r\)，那么很明显这些区间是无法被选择的）。那么可以写出其状态转移方程如下：

\(f(r)= \left \{\begin{aligned} &0 & & \text{if}\quad r=0 \\ &\max\left\{f(r-1),\max_{1\le j\le m,r_j=r} \{f(l_i-1)+s_r-s_{l_i-1}\}\right\}& & \text{if}\quad r>0 \\ \end{aligned}\right.\)

其中，如果不选择以\(r\)为端点的区间，那么就从\(f(r-1)\)转移过来，并不产生任何分数。否则，如果选择某个区间\([l_i,r]\)，那么为了保证区间不产生相交，其它的区间端点必须小于\(l_i\)，即从\(f(l_i-1)\)转移而来，并且选上了\([l_i,r]\)这个区间，得到了\(s_r-s_{l_i-1}\)的分数。

因此最终答案为\(f(n)\)。

代码

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

const int N=100005;
ll f[N],s[N];
int a[N];
vector<int>g[N];
int main(){
    int n,m,l,r;
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%lld",&s[i]);
        s[i]+=s[i-1];
    }
    for(int i=1;i<=m;i++){
        scanf("%d %d",&l,&r);
        if(r<=n) g[r].push_back(l);
    }
    for(int r=1;r<=n;r++){
        f[r]=f[r-1];
        for(int l:g[r]){
            f[r]=max(f[r],f[l-1]+s[r]-s[l-1]);
        }
    }
    printf("%lld\n",f[n]);
}