腾讯秋招 2023.09.10 编程题目与题解（算法岗）

发表于 2023-09-11 分类于笔试阅读次数：本文字数： 5.6k 阅读时长 ≈ 5 分钟

1、超市里的货物架

在一个超市里有一个货物架，上面有\(n\)个格子，编号\(1,2,\dots,n\)。

超市里共出售\(26\)种商品，分别用小写字母\(a,b,\dots,z\)表示。

当一个顾客前来购买商品的时候，他会从第一个格子查找到第\(n\)个格子，如果他在中间某一个格子处找到了自己想要的商品就会将他拿下来并购买它，然后立刻离开超市；如果他在中间某一个格子处发现这个格子里没有商品，他就会立刻停下来并离开超市；如果他走到最后也没有发现自己想要的商品也会离开超市。

货物架初始第个格子里的商品为\(s_i\)。现在有\(m\)个人将按照顺序进入超市，第\(i\)个人想要的商品为\(c_i\)。作为超市的管理员，你想要尽可能多的出售商品。你可以在这些人到来前任意调整商品位置，但是一旦第一个人进入超市你就不能再调整了。那么你最多可以卖出多少商品呢？

输入

第一行两个空格分隔的正整数\(n,m\)。

第二行一个长度为\(n\)只包含小写字母的字符串\(s\)。

第三行一个长度为\(m\)只包含小写字母的字符串\(c\)。

含义均如题面所述。

\(1 \le n,m \le 1000\)

输出

一行一个正整数代表答案。

样例

输入：
3 3
abc
abc

输出：
3

提示：
假如不进行调整，那么在第一个人购买第一个a后其他人都会因为第一个格子为空而离开，只能卖出一件商品。
如果将货物架调整到cba，就可以达到卖出三件商品的效果。

输入：
4 2
abbc
bb

输出：
1

提示：
无论如何调整，只有第一个人可以买到商品。

解答

由于顾客遇到空格就会离开，因此可以知道，每种商品最多只能被卖出一次。按照这条规则，越早来的顾客，其需要购买的商品需要放置的位置越后。

因此，只需要将输入的两个商品集合去重后再取交集即可。

代码

1 2	input() print(len(set(input()) & set(input())))

2、幂法谱半径

矩阵的谱半径在代数，概率，复分析，统计等领域有极为广泛的应用。具体地，假设一个\(n \times n\)的矩阵\(\mathbf{A}\)的特征值\(\lambda_1,\lambda_2,\dots,\lambda_n\)满足

\(|\lambda_1|\ge |\lambda_2|\ge |\lambda_3|\ge \dots\ge |\lambda_n|\)

那么称\(|\lambda_1|\)为矩阵\(\mathbf{A}\)的谱半径，也成为\(\mathbf{A}\)的主特征值。在数值计算领域，一直在致力于如何快速求解矩阵的谱半径，特别是大型的稀疏矩阵。常用的方法有幂法，原点平移法，Rayleigh商法等等，阅读下列关于幂法的信息，尝试编写程序，求解矩阵的谱半径，结果保留两位小数。

假设\(A\)的\(n\)个特征向量\(\{\mathbf{x}_i\}\)线性无关，那么给定一个初始向量\(\mathbf{v}^{(0)}\)，而\(\mathbf{v}^{(0)}\)可以张成：

\(\mathbf{v}^{(0)}=\alpha_1\mathbf{x}_1+\alpha_2\mathbf{x}_2+\dots+\alpha_n\mathbf{x}_n\)

的形式，令\(\mathbf{v}^{(k+1)}=\mathbf{Av}^{(k)}=\mathbf{A}^{k+1}\mathbf{v}^{(0)}\)，那么由特征向量和特征值的性质有

\(\begin{aligned} \mathbf{v}^{(k)}&=\mathbf{A}^k\mathbf{v}^{(0)}=\alpha_1\mathbf{A}^k\mathbf{x}_1+\alpha_2\mathbf{A}^k\mathbf{x}_2+\dots+\alpha_n\mathbf{A}^k\mathbf{x}_n\\ &=\alpha_1\lambda_1^k \mathbf{x}_1+\alpha_2\lambda_2^k\mathbf{x}_2+\dots+\alpha_n\lambda_n^k\mathbf{x}_n\\ &=\lambda_1^k\left[\alpha_1\mathbf{x}_1+\sum_{i=2}^n\alpha_i\left(\dfrac{\lambda_i}{\lambda_1}\right)^k\mathbf{x}_i\right] \end{aligned}\)

于是当\(k\)足够大的时候，有\(\mathbf{v}^{(k)}\approx \alpha_1\lambda_1^k\mathbf{x}_1\)，记\(\displaystyle{\varepsilon_k=\sum_{i=2}^n\alpha_i\left(\dfrac{\lambda_i}{\lambda_1}\right)^k\mathbf{x}_i}\)

那么上式可以化为\(\mathbf{v}^{(k)}=\lambda_1^k[\alpha_1\mathbf{x}_1+\varepsilon_k]\)。

此时，用\(\mathbf{v}^{(k)}_i\)来表示\(\mathbf{v}^{(k)}\)的第\(i\)个分量，那么有

\(\dfrac{\mathbf{v}^{(k+1)}_i}{\mathbf{v}^{(k)}_i}=\lambda_1\dfrac{\alpha_1\mathbf{x}_{1,i}+\varepsilon_{k+1,i}}{\alpha_1\mathbf{x}_{1,i}+\varepsilon_{k,i}}\)

两边取极限就有\(\dfrac{\mathbf{v}^{(k+1)}_i}{\mathbf{v}^{(k)}_i}\rightarrow \lambda_1\)，由此即可得到矩阵的谱半径。

按照题目所给算法计算即可，不过需要注意的是在更新\(v\)的过程中需要及时归一化，否则在矩阵幂次的过程中容易数值溢出（容易分析归一化对最终结果没有影响）

输入

第一行为矩阵阶数\(n\)，所考虑的矩阵的维度为\(n\times n,1<n<10\)；

接下来的\(i\)行\((1\le i\le n)\)行为矩阵的第\(i\)行元素，其中每一行有\(n\)个元素；

第\(n+1\)行为\(\mathbf{v}^{(0)}\)的初始化，有\(n\)个元素，依次构成向量\(\mathbf{v}^{(0)}\)；

输出

输出矩阵的谱半径，并保留两位小数。

样例

输入：
3
1.0 1.0 0.5
1.0 1.0 0.25
0.5 0.25 2.0
1.0 1.0 1.0


输出：
2.54

解答

直接使用式子\(\mathbf{v}^{(k+1)}=\mathbf{Av}^{(k)}\)迭代地求解高次幂的\(\mathbf{v}^{(k)}\)，并在求解过程中及时对\(\mathbf{v}^{(k)}\)进行归一化。

为了保证结果收敛，这里选择\(k=10^4\)，由此最终求出\(|\lambda_1|=\left|\dfrac{\mathbf{v}^{(k+1)}_1}{\mathbf{v}^{(k)}_1}\right|\)。

代码

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

vector<vector<double>>MatMul(vector<vector<double>>&a,vector<vector<double>>&b){
    int n=a.size(),m=a[0].size(),o=b[0].size();
    vector<vector<double>>c(n,vector<double>(o));
    for(int i=0;i<n;i++)
        for(int j=0;j<o;j++)
            for(int k=0;k<m;k++)
                c[i][j]+=a[i][k]*b[k][j];
    return c;
}
int main(){
    int n;
    scanf("%d",&n);
    vector<vector<double>>A(n,vector<double>(n));
    vector<vector<double>>v(n,vector<double>(1));
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            scanf("%lf",&A[i][j]);
    for(int i=0;i<n;i++)
        scanf("%lf",&v[i][0]);

    for(int i=0;i<10000;i++){
        v=MatMul(A,v);
        double s=0;
        for(int i=0;i<n;i++)
            s+=v[i][0];
        for(int i=0;i<n;i++)
            v[i][0]/=s;
    }
    vector<vector<double>>w=MatMul(A,v);
    printf("%.2f\n",abs(w[0][0]/v[0][0]));
}

3、考古大发现

2333年的一天，小明跟随驻地的考古队在灯塔洲（旧称北美洲）的地方挖出一系列的古代石碑文。根据测算，这些石碑文来自300多年的古人。如下图所示，这些石碑中有很多完全看不懂的文字。小明将这个情况告诉给领导大明。大明是密码破译专家兼自然语言处理专家，他认为可以先通过简单的处理对这些文字做简单的信息处理。

大明提出可以使用早在300多年前就被提出的TF-TDF技术来提取关键信息。TF-IDF(term frequency-inverse document frequency，词频-逆向文件频率) 是一种用于信息检索 (information retrieval) 与文本挖掘 (text mining)的常用加权技术。他的主要思想是

如果某个单词在一篇文章中出现的频率TF高，并且在其他文章中很少出现，则认为此词或者短语对于该文章非常重要。

举个例子，任意取一篇英文文章，"the"这个单词的出现频率很高，但是在其他文章中也很高，那么这个单词"the"对于我们取定的文章来说可能并不是太重要的单词；又如我们在着一篇美食点评的文章，"food"这个单词在该文章中出现频率很高，且在其他文章中出现很少(其他文章可能是关于时尚/教育/娱乐等内容的)，那么这个单词"food"对于该取定的美食点评文章就很重要。

为了计算的方便，我们定义第\(i\)个单词的TF为\(tf_i=\dfrac{n_i}{w}\)。其中\(n_i\)表示第\(i\)个单词在所有文章中出现的次数，\(w\)表示所有文章中总的词数。IDF的具体定义为\(idf_i=\ln \dfrac{D}{|\{j:t_i\in d_j\}|+1}\)，其中\(D\)表示的是文章的总数，\(|\{j:t_i\in d_j\}|\)表示包含第\(i\)个词\(t_i\)的文章数量。TF-IDF值则为\(tf_i\times idf_i\)。试判断所有出现过的词中最大的TF-IDF值是否大于一个给定阈值，如果大于则输出\(1\)，否则输出\(0\)。

输入

第\(1\)行为测试数据组数\(T\)

第\(2\)行为\(D,W,t,D\ge 1\)为文章的总数，\(W\ge1\)表示每篇文章的单词数，\(t\le 100\)为给定的闻值。

第\(3\)行到第\(D+2\)行为\(D\)篇文章的具体内容，每行有\(W\)个词。

输出

这些词中最大的TF-IDF值是都大于一个给定阈值，如果大于则输出\(1\)，否则输出\(0\)。

样例

输入：
2
3 3 0.3
df df rtfds
fsaf fg df
oo df df
3 3 0.6
fsdfa fasdfsfsdfsf tetaszgag
sssssssssssssss fdsfsaf gsagfsafasdfgasge
hahahahah ewrsafadfad sssssssssssssss

输出：
0
0

解答

第一次遍历，使用每个两个哈希表，用于统计每个单词\(t_i\)的总共出现次数\(n_i\)，以及记录单词出现的文章序号集合\(\{j:t_i\in d_j\}\)，从而计算出\(|\{j:t_i\in d_j\}|\)的值。

第二次遍历直接计算每个单词的TF-IDF最大值。枚举每个单词\(t_i\)，我们可以计算出\(tf_i=\dfrac{n_i}{D\cdot W},idf_i=\ln \dfrac{D}{|\{j:t_i\in d_j\}|+1}\)，最终判断\(\displaystyle{\max_{t_i}\{tf_i\cdot idf_i\}>t}\)是否满足即可。

代码

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

int solve(){
    int D,W;
    double t;
    cin>>D>>W>>t;
    unordered_map<string,unordered_set<int>>mp;
    unordered_map<string,int>cnt;
    for(int i=1;i<=D;i++){
        string s;
        for(int j=1;j<=W;j++){
            cin>>s;
            ++cnt[s];
            mp[s].insert(i);
        }
    }
    double mx=-1e9;
    for(auto &[s,n]:cnt){
        double tf=1.0*n/D/W;
        double idf = log(1.0*D/(mp[s].size()+1));
        mx=max(mx,tf*idf);
    }
    return mx>t;
}
int main(){
    int T;
    cin>>T;
    while(T--){
        printf("%d\n",solve());
    }
}

4、桥梁高度

牛妹打算用\(n\)根桥柱（所有桥柱高度都必须是正整数）搭建一座桥梁，为了保证桥梁的稳固性，任意两根相邻的桥柱的高度差不能超过\(1\)。由于牛牛太过于冲动，直接就把第\(1\)根和第\(n\)根桥摆好了（即桥梁两端的桥），现在牛妹不能拆除这两根桥柱。但是她想让桥梁最高处的高度尽可能的高，请帮助牛妹计算桥梁最高处的高度（即所用最高的桥柱的高度）。

输入

第一行输入一个正整数\(T\)，代表有\(T\)组输入。

接下来\(T\)行，每行三个正整数\(n,a,b\)，分别代表桥柱的个数，第一根和最后一根桥柱的高度。

\((1 \le T,a,b < 2\times 10^5, 2\le n\le 10^5)\)

输出

输出\(T\)行，第\(i\)行输出在\(i\)组输入的条件下所能搭建桥梁最高处的高度。

如果不存在建桥方案，则输出\(-1\)。

样例

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


输出：
1
2
4
-1
4

提示：
第一组输入的唯一方案为：[1,1]，答案为1。
第二组输入的唯一方案为：[1,2,1]，答案为2。
第三组输入的一种方案为：[3,4,3,2,2]，因此答案为4。
第四组输入没有建桥方案，输出-1。
第五组输入的唯一方案为：[1,2,3,4]，答案为4。

解答

不失一般性，假设\(a\le b\)。如果\(b-a>n-1\)，那么说明中间的\(n-2\)个桥柱不足以保证相邻之间的差的绝对值至多为\(1\)。

否则，为了保证绝对值不超过\(1\)这个条件，我们需要将柱子\(a\)的高度提升到桥柱\(b\)的高度，并且消耗掉\(b-a\)桥柱。自此，考虑新问题\(n'=n-(b-a),a'=b'=b\)。可以发现，剩下的柱子仍然能将最大高度抬升\(\left\lfloor\dfrac{n'-1}{2}\right\rfloor\)。因此最终答案为\(b+\left\lfloor\dfrac{n'-1}{2}\right\rfloor\)。

代码

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

int solve(){
    int n,a,b;
    scanf("%d %d %d",&n,&a,&b);
    if(a>b) swap(a,b);
    if(b-a>n-1) return -1;
    n-=b-a;
    return b+(n-1)/2;
}
int main(){
    int T;
    cin>>T;
    while(T--){
        printf("%d\n",solve());
    }
}

5、共生串

我们定义两个字符串\(S_1,S_2\)是共生的，当且仅当这两个字符串的最长公共子串的长度不小于\(k\)。

例如当\(k=2\)时，"aba"和"bba"是共生的（存在公共子串"ba"），而"aba"和"aaa"是非共生的。

我们将一个共生团定义为一些字符串的集合，其中任意两个字符串都可以通过一些共生关系链接，并且没有被其他任意一个共生团包含。例如当\(k=2\)时，对于字符串集合"aba"、"cba"、"cbc"，{"aba","cba","cbc" }是一共生团，而{"aba","cba"}不是，因为其被共生团{"aba","cba","cbc"}包含。特别的，一个单独的字符串构成的集合也可能是一个共生团（如果没有被其他共生团包含）。

现在给出\(n\)个字符串，每次删去一个字符串，你要回答剩下的串中，有多少共生团。

输入

第一行两个正整数\(n,k(1\le n,k\le 500)\)。

接下来\(n\)行，每行给出一个字符串，分别表示\(S_1,S_2,\dots, S_n(|S_i|\le 500)\)。

最后一行给出\(n\)个互不相同的在\([1,n]\)之间的正整数\(\{a_i\}\)，表示删除顺序。

输出

你要输出\(n+1\)行整数。

第\(0\)行代表不删除任何字符串，共生团的个数。

第\(i(i\in[1,n])\)行表示按照删除顺序，删掉了第a;个字符串后，剩余的共生团数量。

样例

输入：
3 2
aba
cba
cbc
2 1 3

输出：
1 
2
1
0

提示：
不删除任何字符串，只有{"aba","cba","cbc"}一个共生团；
删除"cba"后，有{"aba"}, {"cbc"}两个共生团；
删除"aba"后，有{"cbc"}一个共生团；
删除"cbc"后，没有共生团。

解答

这道题是一道拼接题，考察了字符串哈希和并查集。

我们计算出每个字符串\(s_i\)的所有长度为\(k\)的子串的哈希值。随后以哈希值\(h\)为键，将存在相同哈希值的所有字符的下标放在同一集合中。

接下来枚举存在相同长度为\(k\)的子串的一对字符串\((i,j)\)，并将它们连上一条边。从此我们得到一张图。

因此，题目中所说的共生块其实就是构造出的这个图的连通块数量。

然而，这题是对每一个节点删除后再考虑连通块数量，这里我们使用并查集进行解决，具体办法是逆序添加每个节点，然后再求出连通块数量即可。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N=504;

char s[N];
ull hs[N],pw[N];
int b=131;
ull geths(int l,int r){
    return hs[r]-hs[l-1]*pw[r-l+1];
}

int vis[N],n,k;
unordered_map<ull,vector<int>>mp;

vector<int>g[N];
int fa[N];
int find(int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
void merge(int x,int y){fa[find(x)]=find(y);}

int add[N];

int main(){
    scanf("%d %d",&n,&k);
    pw[0]=1;
    for(int i=1;i<N;i++)
        pw[i]=pw[i-1]*b;
    for(int i=1;i<=n;i++){
        scanf("%s",s+1);
        int l=strlen(s+1);
        for(int j=1;j<=l;j++){
            hs[j]=hs[j-1]*b+s[j];
        }
        for(int j=k;j<=l;j++){
            mp[geths(j-k+1,j)].push_back(i);
        }
    }
    for(int i=1;i<=n;i++)
        fa[i]=i;
    for(auto &[kk,vv]:mp){
        vector<int>&v=vv;
        sort(v.begin(),v.end());
        v.resize(unique(v.begin(),v.end())-v.begin());
        for(int i=0;i<v.size();i++){
            for(int j=i+1;j<v.size();j++){
                g[v[i]].push_back(v[j]);
                g[v[j]].push_back(v[i]);
            }
        }
    }
    vector<int>ans(n+1);
    for(int i=1;i<=n;i++){
        scanf("%d",&add[i]);
    }
    for(int i=n,cnt=0;i>=1;i--){
        ++cnt;
        int u=add[i];
        for(int v:g[u]){
            if(vis[v]&&find(u)!=find(v)){
                --cnt;
                merge(u,v);
            }
        }
        ans[i-1]=cnt;
        vis[u]=1;
    }
    for(int i=0;i<=n;i++)
        printf("%d\n",ans[i]);
}