首页 > 腾讯8.23笔试题 客户端
头像
Refrian
编辑于 2020-08-24 10:20
+ 关注

腾讯8.23笔试题 客户端

简述

  • 岗位:客户端
  • 写题语言:C++
  • 吹爆腾讯的笔试题……感觉是最近做的最有区分度的一套,做起来非常爽

题目一

  • 合并木棍,每次任取两根,合并代价是两根木棍的长度,输出最小代价
  • 唯一没有AC的题……从堆里取出来的时候顺手取到了int里,安详去世
  • AC:50%
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<ll,ll> P;
const int inf=0x7fffffff;

int main(){
    int T;scanf("%d",&T);
    while(T--){
        int n;scanf("%d",&n);
        ll t;
        priority_queue<ll,vector<ll>,greater<ll>>a;
        for(int i=0;i<n;i++){
            scanf("%lld",&t);
            a.push(t);
        }
        ll res=0;
        while(a.size()>1){
            int x=a.top();a.pop();
            int y=a.top();a.pop();
            a.push(x+y);
            res+=x+y;
        }
        printf("%lld\n",res);
    }
    return 0;
}

题目二

  • 按字典序第k小字串
  • 后缀自动机(划去),范围5000刚好可以带优化的暴力
  • 优化点主要来源于k<=5,非常非常关键
  • AC:100%
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<ll,ll> P;
const int inf=0x7fffffff;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    string a;cin>>a;
    int k;cin>>k;
    set<string>res;
    for(int i=1;i<=6;i++){
        for(int j=0;j+i<=a.size();j++){
            string t(a.begin()+j,a.begin()+j+i);
            res.insert(t);
            if(res.size()>k)res.erase(--res.end());
        }
    }
    auto i=res.begin();
    while(--k)++i;
    cout<<*i<<endl;
    return 0;
}

题目三

  • 给定地图,打怪升级,每次只能前进一层
  • BFS解了,都没优化直接过
  • AC:100%
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<int,int> P;
const int inf=0x7fffffff;

int n,m,res;
char a[605][605];
int vis[605][605];
int dx[]={0,0,-1,1},dy[]={1,-1,0,0};

int bfs(int cur){
    int bx,by,ex,ey,l=0;
    for(int i=0;i<n;i++)
        for(int j=0;j<m;j++){
            if(a[i][j]==cur+'0')bx=i,by=j;
            else if(a[i][j]==cur+'0'+1)ex=i,ey=j;
        }
    queue<P>q;
    q.push(P(bx,by));
    while(!q.empty()){
        P t=q.front();q.pop();
        for(int i=0;i<4;i++){
            int nx=t.first+dx[i],ny=t.second+dy[i];
            if(nx>=0&&nx<n&&ny>=0&&ny<m&& a[nx][ny]!='#'&&(a[nx][ny]=='.'||a[nx][ny]<='0'+cur+1)&&vis[nx][ny]==0){
                vis[nx][ny]=vis[t.first][t.second]+1;
                q.push(P(nx,ny));
            }
        }
    }
    return vis[ex][ey];
}

bool check(){
    res=0;
    for(int i=0;i<9;i++){
        memset(vis,0,sizeof(vis));
        int x=bfs(i);
        if(x==0)return 0;
        res+=x;
    }
    return 1;
}

int main(){
    scanf("%d%d ",&n,&m);
    for(int i=0;i<n;i++)scanf("%s",a[i]);
    if(check()==0)cout<<"-1"<<endl;
    else cout<<res<<endl;
    return 0;
}

题目四

  • LIS裸题
  • 偷了个懒,递减反过来跑了一次
  • AC:100%
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<ll,ll> P;
const int inf=0x7fffffff;

int LIS(vector<int>&dp,vector<int>&a,int n){
    fill(dp.begin(),dp.begin()+n,inf);
    for(int i=0;i<n;i++){
        *lower_bound(dp.begin(),dp.begin()+n,a[i])=a[i];
    }
    return (lower_bound(dp.begin(),dp.begin()+n,inf)-dp.begin());
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int T;cin>>T;
    while(T--){
        int n;cin>>n;
        vector<int>a(n),dp(n);
        for(int i=0;i<n;i++)cin>>a[i];
        int x=LIS(dp,a,n);
        reverse(a.begin(),a.end());
        int y=LIS(dp,a,n);
        cout<<max(x,y)<<endl;
    }
    return 0;
}

题目五

  • 是否包含长度为m的回文子串
  • 稍微改了下输出结果的马拉车
  • AC:100%
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<ll,ll> P;
const int inf=0x7fffffff;

bool manacheck(string&a,int m){
    string b="$#";
    for(auto i:a)b+=i,b+="#";
    int n=b.size(),x=0,y=0;
    vector<int>p(n,0);
    for(int i=1;i<n;i++){
        if(x>i)p[i]=min(p[2*y-i],x-i);
        else p[i]=1;
        while(b[i+p[i]]==b[i-p[i]])++p[i];
        if(x<i+p[i])x=i+p[i],y=i;
    }
    for(auto i:p)if(i-1>=m)return 1;
    return 0;
}

int main(){
    int T;cin>>T;
    while(T--){
        int n,m;cin>>n>>m;
        string a;cin>>a;
        if(manacheck(a,m))cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}


全部评论

(11) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐