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

发表于 分类于 阅读次数： 本文字数： 3k 阅读时长 ≈ 3 分钟

1、小红的01串

小红拿到了一个01串，她准备将若干个字符'1'染成红色，将若干个字符'0'染成蓝色，但有个限制：如果一个'0'和一个'1'相邻，那么它们不能同时染色。

小红想知道，最多可以染多少个字符？

输入

输入仅有一行，为小红拿到的01串。

字符串长度不超过\(200000\)。

输出

一个正整数，代表能染色的最多字符。

样例

1
2
3
4
5
6
7
8
输入：
110011

输出：
4

提示：
染红第一个、第三个、第五个、第六个字符即可。

解答

对于一个01相间，长度为\(n\)的比特串，对它染色的最多个数为\(\lceil n/2\rceil\)，因为相邻两个不能同时染色。

因此，我们对原来的字符串分拆成多个极大01相间子串（即前一个子串的最后一个字符要和后一个子串的第一个字符相同），分别统计它们的最多染色数并相加即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <bits/stdc++.h>
using namespace std;

const int N=200004;
char s[N];
int main(){
    scanf("%s",s+1);
    int n=strlen(s+1);
    int ans=0;
    for(int i=1,j;i<=n;i=j){
        for(j=i+1;j<=n&&s[j]!=s[j-1];++j);
        ans+=(j-i+1)/2;
    }
    printf("%d\n",ans);
}

2、小红刷抖音

小红很喜欢刷抖音，抖音后台有一个推荐系统，小红向上滑动屏幕时，该推荐系统会计算应显示给小红的短视频。

用数值量化而言，每个短视频有一个内存占用\(a_i\)（画质越好的视频内存占用越大），以及该视频可以带给小红愉悦度为\(b_i\)。

值得注意的是，当小红每次重复刷到同一个视频时，观看该视频获得的愉悦度会除以\(2\)（向下取整）。

例如，若一个视频初始给小红获得的愉悦度为\(5\)，那么第二次小红获得的愉悦度会变成2，第三次为\(1\)，第四次以后再刷到这个视频获得的愉悦度就为0了。

小红一共进行了\(q\)次刷视频操作。

为了使得手机不卡顿，推荐系统每次会选择一个内存占用不高于\(x_i\)的视频。

如果有多个这样的视频，推荐系统会推荐满足条件的播放画质最好的那个视频（即内存占用最高的视频）。

如果有多个视频的画质都是最好，那么推荐系统会推荐当前愉悦度最高的视频。

当小红观看完这个视频后，即可获得该视频的愉悦度，请你计算小红刷完所有视频时获得的总愉悦度。

输入

第一行输入两个正整数\(n,q\)，代表视频的总数量、小红刷视频的次数。

第二行输入\(n\)个正整数\(a_i\)，代表每个视频的内存占用。

第三行输入\(n\)个正整数\(b_i\)，代表每个视频第一次观看时给小红带来的愉悦值。

第四行输入\(q\)个正整数\(x_i\)，代表每次小红刷视频时，系统推荐的视频占用内存的上限。

  • \(1\le n,q \le 10^5\)
  • \(1 \le a_i,b_i,z_i\le 10^9\)
  • 保证\(x_i\)一定不小于\(a_i\)的最小值。

输出

一个整数，代表小红获得的愉悦度总和。

样例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
输入：
3 4
3 5 1
3 4 2
3 3 6 1

输出：
10

提示：
第一次刷视频，推荐系统推荐给小红第一个视频。小红获得愉悦度3。
第二次刷视频，推荐系统推荐给小红第一个视频。由于是第二次观看，小红获得愉悦度1。
第三次刷视频，推荐系统推荐给小红第二个视频。小红获得愉悦度4。
第四次刷视频，推荐系统推荐给小红第三个视频。小红获得愉悦度2。

解答

这题由于是优先查找内存不超过\(x_i\)且取最大，再查找愉悦值最大，因此我们可以使用一个有序的数据结构进行解决。

具体做法是将每个不同的内存占用作为键，其对应的愉悦值可以用一个最大堆进行存储。由此，C++的map是最满足当前需要的容器。对于一次查询\(x_i\)，只需要通过二分在map中找到最大的那个内存值，然后再将对应的最大堆元素取出，计入答案，并将其整除\(2\)的值重新插入最大堆即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=100004;
map<int,priority_queue<int>>mp;
int a[N],b[N],n,m;
int main(){
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++) scanf("%d",&b[i]);
    for(int i=1;i<=n;i++) mp[a[i]].push(b[i]);
    ll ans=0;
    int x;
    for(int i=1;i<=m;i++){
        scanf("%d",&x);
        auto it=mp.upper_bound(x);
        --it;
        priority_queue<int>&q=it->second;
        int k=q.top();q.pop();
        ans+=k;
        q.push(k>>1);
    }
    printf("%lld\n",ans);
}

3、小红玩大富翁游戏

小红在玩一个大富翁游戏，游戏的地图为一排房子，从左到右编号依次从\(1\)到\(n\)。

每个房子有一个购买价格\(a_i\)和一个经过它的房租价格\(b_i\)，当小红经过一个自己没有购买的房子时，她就需要交房租（已购买的房子则不需要交房租）。

在游戏开始前，小红可以购买任意数量的房子，然后开始游戏。

游戏中，小红会按照一个给定的排列\(p\)的顺序依次经过所有的房子（排列\(p\)为房子的编号顺序，\(p\)的大小为\(n\)，即每个房子都会作为一次目标）。

小红每经过一套房子都需要交租金，除非已购买。初始小红在第一个房子的左边，当她按照顺序经过了所有房子后，她会再次移动到第\(n\)个房子的右边。

请你计算小红最少的总花费。

输入

第一行输入一个整数\(n(1\le n\le 10^5)\)，代表房子的总数。

第二行输入一个排列\(p_i(1\le p_i\le n)\)，代表小红经过的房子编号顺序。

第三行输入\(n\)个整数\(a_i(1\le a_i\le 10^9)\)，代表编号\(i\)的房子的购买价格。

第四行输入\(n\)个整数\(b_i(1\le b_i \le 10^9)\)，代表编号\(i\)房子的经过房租价格。

保证\([1,n]\)中每个数在\(p\)数组中都出现且仅出现一次。

输出

一行一个整数，表示最少的花费。

样例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
输入：
4
1 3 2 4
5 4 2 4
1 3 1 1

输出：
8

提示：
游戏开始前买下第二个房子，花费4。
开始游戏时，小红先向右走一步到达1号房子，房租价格为1。
然后向右走2步到达3号房子，当小红经过2号房子时，由于2号房子已经购买，则不用交房租。然后到达3号房子时交房租价格为1。
然后向左走1步到达2号房子，不需要交房租。
然后向右走2步到达4号房子，经过的3号房子和4号房子分别交价格为1的房租。
最后向右离开这个大富翁地图。

解答

我们需要统计每个房子被经过的次数\(c_i\)，那么最终答案为\(\displaystyle{\sum_{i=1}^n\min\{a_i,b_i\cdot c_i\}}\)，也就是说，如果\(a_i\le b_i\cdot c_i\)，那么就租下第\(i\)栋房子，否则不租。

为了求出数组\(c_i\)，我们可以考虑使用差分数组进行解决。假设\(t\)是差分数组，并且目前处在位置\(x\)，并且走向\(y\)（为了避免端点重复计算，这一个过程只会计算终点\(y\)的价值）。如果\(x<y\)，那么就对\(t_{x+1}\)加上\(1\)，对\(t_{y+1}\)减去\(1\)。如果\(x>y\)，那么就对\(t_x\)减去\(1\)，\(t_y\)加上\(1\)。

对于题目输入的排列。我们只需要令\(p_0=0,p_{n+1}=n+1\)，那么整个过程就恰好不重不漏地完成计算，最终有\(c_i=c_{i-1}+t_i,c_0=0\)。此后直接计算答案即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=200004;
int s[N];
int p[N],a[N],b[N],n;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&p[i]);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++) scanf("%d",&b[i]);
    ++s[1];
    --s[p[1]+1];
    ++s[p[n]+1];
    for(int i=1;i<n;i++){
        int x=p[i],y=p[i+1];
        if(x<y){
            ++s[x+1];--s[y+1];
        }
        else{
            ++s[y];--s[x];
        }
    }
    ll ans=0;
    for(int i=1;i<=n;i++){
        s[i]+=s[i-1];
        ans+=min(1ll*a[i],1ll*b[i]*s[i]);
    }
    printf("%lld\n",ans);
}

4、小红的机器人

小红有一个机器人，她可以对机器人进行以下\(4\)种指令：

  • L：向左一步。
  • R：向右一步。
  • U: 向上一步。
  • D: 向下一步。 小红现在给定了一个指令集（有上下左右最多四种操作）。

小红希望选出一个非空子序列（在指令集中可以不连续），使得机器人执行这段子序列指令后回到原地。小红想知道最终有多少选择方式？由于答案可能过大，请对\(10^9+7\)取模。

我们定义，两个子序列中存在某位置字母的选择情况不同（例如在第一个子序列中选择了第\(x\)个字符，而在第二个子序列中没选），则称为两个不同的子序列。

输入

一行仅包含'L', 'R', 'U', 'D'四种字符的字符串，长度不超过\(500000\)。

输出

一个整数，代表子序列的选择方案。

样例

1
2
3
4
5
6
7
8
9
输入：
LLRUU

输出：
2

提示：
第一种方案：选择第一个字符和第三个字符组成子序列"LR"，向左走一步，向右走一步，回到原点。
第二种方案：选择第二个字符和第三个字符组成子序列"LR"，向左走一步，向右走一步，回到原点。

解答

可以发现，这些指令是没有顺序性的。即前面的指令执行结果并不会影响后面的执行执行结果。因此，最终机器人的位置只和不同指令的个数有关，而和顺序没有关系。

如果一条非空指令能够使机器人回到原点，那么L, R的数量必须相等，U, D的数量必须相等。并且可以发现，两个维度的坐标都是独立互不干扰的，可以使用乘法原理计算完成。

因此，假设\(c_L,c_R,c_U,c_D\)分别是输入的字符串的L, R, U, D的指令数，那么我们可以得到最终答案为：

\[\left(\sum_{i=0}^{\min\{c_L,c_R\}}\dbinom{c_L}{i}\cdot\dbinom{c_R}{i}\right)\cdot \left(\sum_{i=0}^{\min\{c_U,c_D\}}\dbinom{c_U}{i}\cdot\dbinom{c_D}{i}\right)-1\]

其中最后的\(-1\)是指指令为空的情况。

本题的实现基于线性逆元，当然也可以不写，直接求出阶乘再计算逆元也是可以的。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
# include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=500004;
ll mod=1e9+7;
ll fac[N],finv[N],inv[N];
void init(int n){
    fac[0]=fac[1]=inv[1]=finv[0]=finv[1]=1;
    for(int i=2;i<=n;i++){
        fac[i]=fac[i-1]*i%mod;
        inv[i]=(mod-mod/i)*inv[mod%i]%mod;
        finv[i]=finv[i-1]*inv[i]%mod;
    }
}
ll C(int n,int m){
    return fac[n]*finv[n-m]%mod*finv[m]%mod;
}
char s[N];
int cnt[128];
ll cal(int x,int y){
    ll ans=0;
    int w=min(x,y);
    for(int i=0;i<=w;i++)
        ans=(ans+C(x,i)*C(y,i))%mod;
    return ans;
}
int main(){
    scanf("%s",s+1);
    int n=strlen(s+1);
    init(n);
    for(int i=1;i<=n;i++)
        ++cnt[s[i]];
    ll m1=cal(cnt['L'],cnt['R']);
    ll m2=cal(cnt['U'],cnt['D']);
    ll ans=m1*m2%mod;
    printf("%lld\n",ans);
}

如果觉得我的文章对您有用，请随意打赏。您的支持将鼓励我继续创作！
Ujimatsu Chiya 微信 微信
Ujimatsu Chiya 支付宝 支付宝