科大讯飞秋招 2023.08.13 笔试题目与题解（Java&安卓方向）

发表于 2023-08-13 更新于 2023-08-19 分类于笔试阅读次数：本文字数： 2k 阅读时长 ≈ 2 分钟

1、最大优美排列

小红认为一个排列是优美的，当且仅当对于任意\(i\in[1,n],a_{a_i}=n-a_i+1\)成立，其中\(n\)代表排列的长度，\(a_i\)表示排列的第\(i\)个元素。

她想知道\(1-n\)的所有优美排列中，字典序最大的是哪一个？

注意，排列的定义为，若长度为\(n\)的序列中，\(1\)到\(n\)都出现过且仅出现一次，则称该序列为一个排列。

输入

一个正整数\(n(1\le n\le 10^5)\)，代表排列的长度。

输出

一行\(n\)个正整数，用空格隔开。代表字典序最大的优美排列。

样例

输入：
2

输出：
2 1

解答

打表后可以发现，这个逆序的数组（即\(a_i=n-i+1\)）恰好是题目中所求的数组，可见它具有最大字典序。如下等式可以简单证明这个过程：

\(\begin{aligned} a_{a_i}&=a_{n-i+1}\\ &=i\\ &=n-(n-i+1)+1\\ &=n-a_i+1 \end{aligned}\)

代码

1 2	n = int(input()) print(" ".join(str(x) for x in range(n, 0, -1)))

2、小红走字符串

小红有一个长度为\(n\)字符串\(s\)，他需要从第\(1\)个字符走到第\(n\)个字符，他每次只能走到相邻的字符。当他从\(s_i\)走到\(s_{i+1}\)时，他会消耗\(s_{i+1}-s_i\)点体力值。\(s_{i+1}-s_i\)若是负数，意味着他将恢复\(|s_{i+1}-s_i|\)点体力值，若体力值消耗到小于\(0\)，则小红将无法继续走。字符相减时字符'a'代表1，字符b'代表2......以此类推。已知小红现在有\(k\)点体力值，他能否从\(s_1\)走到\(s_n\)。若能走到，请输出他的剩余体力值，否则输出\(-1\)。

输入

第一行两个整数\(n,k(1\le n,k\le 10^5)\)。

第二行一个长度为\(n\)字符串\(s\)。

输出

一行一个整数，表示他的剩余体力值。若无法走到，则输出\(-1\)。

样例

输入：
5 2
abcca

输出：
2

提示：
初始处理第一个字符时，体力值为2。
处理第二个字符时，体力值为1。
处理第三个字符时，体力值为0
处理第四个字符时，体力值为0。
处理第五个字符时，体力值为2。
最终输出2

解答

按顺序枚举两个相邻字母的ascii码之差（注意字母间的ascii码之差和字母间的序号之差必定是相同的），然后添加到体力值\(k\)中，如果小于\(0\)则即时退出。如此反复，直到最后输出最终体力值。

代码

n, k = map(int, input().split())
s = input()
for i in range(n - 1):
    d = ord(s[i + 1]) - ord(s[i])
    k -= d
    if k < 0:
        k = -1
        break
print(k)

使用差分的性质，可以有另外一种写法：

n, k = map(int, input().split())
s = input()
mn = min(s)
if k + ord(mn) - ord(s[0]) < 0:
    print(-1)
else:
    print(k + ord(s[-1]) - ord(s[0]))

3、科大讯飞机器存储问题

智能语音、自然语言理解是科大讯飞较核心的技术、且保持在了世界前沿水平在自然语言理解中，自然语言处理 (nlp) 为一个常见的技术，本题的具体场景也和这个技术相关。

自然语言处理 (nlp)经常会需要解决一些字符串的子串问题。我们把它抽象为数组的连续子数组问题。当处理一个数组时，机器会存储数组的一些连续子数组不过为了节省存储空间，当机器遇到多个完全相同的连续子数组时只会存储一次。

现在有一个棘手的问题，给定了两个长度为\(n\)的数组，这两个数组均满足以下性质：\(1\)到\(n\)恰好出现了一次，请你判断机器存储完所有的连续子数组时，一共存储了多少次。

输入

第一行输入一个正整数\(n\),代表数组的长度。

第二行输入\(n\)个正整数\(a_i\)，代表第一个数组。

第三行输入\(n\)个正整数\(b_i\)，代表第二个数组。

\(1\le n\le 2\times 10^5\)

输出

机器存储的次数。

样例

输入：
3
1 2 3
2 3 1

输出：
8

提示：
[1], [2], [3], [1,2], [2,3], [3,1], [1,2,3], [2,3,1]一共存储了8次。

解答

我们只需要统计有多少个子数组在\(a,b\)中同时出现（假设同时出现次数为\(c\)），然后再去重即可，因此最终答案为\(n(n+1)-c\)。

接下来考虑计算\(c\)值。首先枚举这些公共子数组的左端点（假设在\(a\)中位置为\(l_a\)，在\(b\)中的位置为\(l_b\)），对于每对左端点\((l_a,l_b)\)，使用双指针法，同时一直向右枚举，直到两个位置不相等为止（假设这个最右端点分别为\(r_a,r_b\)），那么对于\(\forall p:0\le p\le r_a-l_a\)，都有\(a[l_a:l_a+p]=b[l_b:l_b+p]\)，这些子数组都是需要去重的，一共有\(r_a-l_a+1=r_b-l_b+1\)个需要去重。

但是，上面这种做法是\(O(n^2)\)的。不妨换一种新的考虑方式，假设现在对一对\((l_a,l_b)\)，按照上面的方式，我们求出了一对最右端点\((r_a,r_b)\)。那么对于\(\forall p:0\le p\le r_a-l_a\)，对\((l_a+p,l_b+p)\)按照上面的方式（可见\(a[l_a+p]=b[l_b+p]\)仍然成立），仍然可以求出最右端点仍然是\((r_a,r_b)\)。这启发我们可以求出一个个不相交的极大公共子数组，其内部的所有子数组仍然是公共子数组，只需要将它们一并统计即可，这些子数组一共有\(\dfrac{(r_a-l_a+1)(r_a-l_a+2)}{2}\)个。这种方式可以在\(O(n)\)时间内完成。

代码

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

const int N=200004;
int a[N],b[N],pos_b[N],n;
ll tri(int n){
    return 1ll*n*(n+1)/2;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=n;i++){
        scanf("%d",&b[i]);
        pos_b[b[i]]=i;
    }
    ll sum=0;
    for(int i=1,j,k;i<=n;){
        // 为了方便表示，这里的子数组a[i : j], b[pos[a[i]] : k]都是左闭右开的，因此计算方式和解答不一样。
        for(j=i,k=pos_b[a[i]];j<=n&&k<=n&&a[j]==b[k];j++,k++);
        sum+=tri(j-i);
        i=j;
    }
    ll ans=tri(n)*2-sum;
    printf("%lld\n",ans);
}