阿里淘天 秋招 2023.09.20 编程题目与题解

1、小红的子数组权值

小红拿到了一个数组。她定义一个连续子数组的权值为：子数组内不同元素的个数。小红想知道，权值分别为\(1,2,3,\dots,n\)的子数组数量有多少个？

输入

第一行输入一个正整数\(n\)，代表数组的元素数量。

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

\(1\le n,a_i \le 2000\)

输出

\(n\)个整数，分别代表权值为\(1,2,3,\dots,n\)的子数组数量。

样例

输入：
4
1 2 2 3

输出：
5 4 1 0

解答

这题比较简单，只需要枚举每个数组元素作为起点，然后从右开始一个个插入一个单重集合中，再统计这个集合的大小即可。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2004;
int c[N],a[N],n;
int main(){
    unordered_set<int>st;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=n;i++){
        st.clear();
        for(int j=i;j<=n;j++){
            st.insert(a[j]);
            ++c[st.size()];
        }
    }
    for(int i=1;i<=n;i++)
        printf("%d%c",c[i], " \n"[i==n]);
}

2、平均数大于\(k\)的最长子序列

给定\(n\)个正整数组成的数组，求平均数大于\(k\)的最长子序列的长度。

输入

第一行输入两个正整数\(n\)和\(k\)，用空格隔开。

第二行输入\(n\)个正整数\(a_i\)，用来表示数组。

• \(1\le n\le 200000\)
• \(1\le k,a_i \le 10^9\)

输出

如果不存在子序列的平均数大于\(k\)，则输出\(-1\)。

否则输出最长子序列的长度。

样例

输入：
5 2
3 1 1 2 3

输出：
4

提示：
取3, 1, 2, 3，平均数为2.25.

解答

我们构造\(b_i=a_i-k\)，那么原题目的含义就变成了在\(b\)中求取一个最长的子序列，其平均值大于\(0\)，也就是说其和大于\(0\)。

那么问题很简单，从大到小将\(b\)中的元素加入到子序列之中，直到子序列的元素之和不超过\(0\)即停止。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=100004;
int a[N],n,k;
int main(){
    scanf("%d %d",&n,&k);
    for(int i=0;i<n;i++)
        scanf("%d",&a[i]);
    sort(a,a+n,greater<int>());
    ll s=0;int p=0;
    for(p=0;p<n;p++){
        s+=a[p]-k;
        if(s<=0) break;
    }
    printf("%d\n",p);
}

3、小红的01问号串

小红定义一个字符串的权值为：相邻的不同字符对数。例如"10011"的权值为\(2\)，其中有\(2\)对相邻字符不同。

小红拿到了一个\(01\)串，其中有一些字符是'?'。设'?'字符的数量有\(k\)个，已知共有\(2^k\)种不同的01串(每个问号可以是\(0\)或者\(1\))。小红想知道，这\(2^k\)种不同的01串的权值之和是多少？ 答案对\(10^9+7\)取模。

输入

一个仅包含'0', '1'和'?'的字符串，长度不超过\(10^5\)。

本题有部分用例，字符串长度不超过\(20\)。

输出

最终的权值之和对\(10^9+7\)取模的值。

样例

输入：
01?

输出：
3

提示：
"011"的权值为1，"010"的权值为2。权值和为3。

解答

我们只考虑相邻一对字符串所做出的贡献值。

• 假设这一对相邻的字符串是01或者是10，那么由于这个字符串有\(2^k\)个，这一相邻对做出了\(2^k\)的贡献。

• 假设这一对相邻的字符串是0?, ?0, 1?, ?1中的一个，那么这一对为了做出贡献，问号必须填上不同的数字。对于另外的\(k-1\)个问号，它们可以随意填充。因此这一对相邻的字符串做出了\(2^{k-1}\)的贡献。

• 假设这一对相邻的字符串是??，那么这一对为了做出贡献，两个问号要么是01，要么是10，有两种填法。对于其它\(k-2\)个问号，可以随意填充，因此这一对相邻的字符串做出了\(2\cdot 2^{k-2}=2^{k-1}\)的贡献。

• 对于其余情况（即00和11），它们肯定不会做出贡献，因此忽略。

因此，将这些贡献值累加即可得到答案。

代码

s = input()
mod = 10 ** 9 + 7
ans = 0
k = s.count('?')
for i in range(len(s) - 1):
    t = s[i:i + 2]
    if t.count('?'):
        ans += pow(2, k - 1, mod)
    elif t[0] != t[1]:
        ans += pow(2, k, mod)
ans %= mod
print(ans)