微众银行 秋招 2023.09.03 编程题目与题解

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

1、切糖果

小美想要买糖果店的一根长长的糖果。糖果店顾客可以从中选取一个位置然后老板会在那切断，糖果前端到那个切断位置的糖果就会出售给这位顾客。这个糖果其实不同段有着不同的口味，小美希望她选出来的糖果中各个段有着不同的口味，在这基础上希望能选出尽可能长的糖果。小美想知道她能买到最长多长的糖果，请你帮帮她。

输入

第一行\(1\)个整数\(n\)，表示糖果的长度。

第二行\(n\)个整数\(a_1,a_2,\dots,a_n\)，其中\(a_i\)表示从糖果前端开始第\(i\)段的口味，每段均\(1\)为单位长度。

对于100%的数据，\(1\le n\le 50000，1\le a_i\le 50000\)

输出

输出一行一个整数表示能买到的糖果的最长长度，且其中不包含相同口味。

样例

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

输出：
3

提示：
如果我们买长度为4的糖果，包含的口味为[1,2,3,3]，存在了重复。
而长度为3时，包含的口味为[1,2,3]，不存在重复。因此长度3为最长的不存在重复口味糖果长度。

解答

只需要按顺序查看一下有没有数已经被标记即可，被标记了就停下来，之后的都不要了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100004;
int vis[N];
int main(){
    int r,n,x;
    scanf("%d",&n);
    for(r=0;r<n;r++){
        scanf("%d",&x);
        if(vis[x]) break;
        vis[x]=1;
    }
    printf("%d\n",r);
}

2、酷

酷酷的小明准备和小伙伴们展示他捏出来的超酷的橡皮泥士兵。在展示之前，小明发现有些橡皮泥士兵大小十分相似甚至相同，这让小明感觉不是很酷，因为小明想要他的橡皮泥作品都有自己的风格，即使是大小也要有区别。小明的\(n\)个橡皮泥士兵的大小分别为\(a_1,a_2,\dots,a_n\)，小明可以通过给某个士兵加一单位橡皮泥来使得其大小增加一单位。小明想知道如果他想要让所有的橡皮泥士兵大小都不相同，至少需要一共加多少单位橡皮泥。

输入

第一行\(1\)个整数\(n\)，表示小明的橡皮泥士兵数量。

第二行\(n\)个整数\(a_1,a_2,\dots,a_n\)，分别表示小明的橡皮泥士兵的大小。

对于100%的数据，\(1\le n\le 50000，1\le a_i\le 100000\)

输出

输出一行一个整数表示总共至少加多少单位的橡皮泥。

样例

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

输出：
5

提示：
我们给一个大小为1的橡皮泥士兵增加4单位橡皮泥，大小变为5；
再给一个大小为3的橡皮泥士兵增加1单位橡皮泥，大小变为4。
此时橡皮泥士兵们的大小分别为1、2、3、4、5，没有两个橡皮泥士兵拥有相同大小了。
可以证明没有更优方案。

解答

首先对数组中的所有元素进行排序，假设现在已经满足\(a_1\le a_2\le\dots\le a_n\)。

为了保证所有橡皮泥士兵的用料最小，我们将从小到大给每个士兵设定一个大小下限\(m_i\)，如果\(m_i>a_i\)，那么士兵的重量就需要补到\(m_i\)。接下来是计算这个下界，一开始\(m_1=-\infty\)。对于\(1\le i<n\)，如果\(a_i\ge m_i\)，那么说明当前橡皮泥士兵大小已经足够，下一个至少为\(a_i+1\)，即\(m_{i+1}=a_{i}+1\)；否则，需要为士兵补充\(m_i-a_i\)的大小，并且下一个大小至少为\(m_{i+1}=m_i+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
# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100004;
int a[N],n;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    sort(a+1,a+n+1);
    ll ans=0;
    int need=0;
    for(int i=1;i<=n;i++){
        if(a[i]<need){
            ans+=need-a[i];
            ++need;
        }
        else{
            need=a[i]+1;
        }
    }
    printf("%lld\n",ans);
}


3、平均值

小明有一个数组。他挑选了一个有理数\(u/v\)，现在他想知道这个数组有多少个子区间的平均值恰好等于\(u/v\)。数组的子区间即是数组中连续的一段区间，如数组\([4,2,6]\)有\(6\)个子区间\([4],[2],[6],[4,2],[2,6],[4,2,6]\)。

输入

第一行有三个整数\(n,u,v(1\le n,v\le 100000,1\le u\le n*v)\)，代表数组的长度，小明选择的有理数的分子和分母。输入保证\(u\)和\(v\)的最大公因数是\(1\)，即\(u/v\)是最简分数。

第二行有\(n\)个绝对值不超过\(1000000\)的整数，代表数组中的元素。

数字间两两有空格隔开。

输出

输出一个非负整数，代表所求的答案。

样例

1
2
3
4
5
6
输入：
6 5 2
2 4 1 3 2 3

输出：
6

解答

这题的思路和美团2023.08.26那场笔试的第五题类似。只要令\(b_i=a_i-u/v\)，那么问题就转化成求有多少个子数组的数组和为\(0\)。更具体地说，令\(b\)的前缀和为\(\displaystyle{s_i=\sum_{j=1}^ib_j}\)，其中\(s_0=0\)，那么相当于寻找有多少对\((i,j)\)满足\(0\le i<j\le n\land s_i=s_j\)即可。

然而，这次的\(s\)是一个有理数（而不是一个分数）。怎么简单处理呢？只需要将\(b_i\)中的所有数都扩大\(v\)倍即可。一个数组的元素和为\(0\)，那么它的所有元素之和的任意倍数也为\(0\)。

更具体的说，令\(c_i=v\cdot a_i-u\)，并且令\(c\)的前缀和为\(\displaystyle{s'_i=\sum_{j=1}^ic_j}\)，其中\(s'_0=0\)，那么只需要寻找有多少对\((i,j)\)满足\(s_i'=s_j'\)即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100004;
ll a[N],s[N];
int main(){
    int n,u,v;
    scanf("%d %d %d",&n,&u,&v);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        a[i]=a[i]*v-u;
        s[i]=s[i-1]+a[i];
    }
    map<ll,int>mp;
    mp[0]=1;
    ll ans=0;
    for(int i=1;i<=n;i++){
        ans+=mp[s[i]];
        ++mp[s[i]];
    }
    printf("%lld\n",ans);
}