2019年春季腾讯开发岗提前批笔试

2019-03-09

字数统计: 2.2k字 | 阅读时长: 10分

2019年下学期参加腾讯的提前批笔试，写了一篇题解。

前言

笔试过程中除了第三题拿了$80$分，其余$4$题都是$100$分，可以放心食用。

由于笔试中途没有保存题目描述，所以以下题面都是简要题意。
有的题目复杂度并不是最优的，但足够拿到满分。
欢迎交流思路。
题目来源：**$2019$ 春季腾讯移动客户端提前批笔试**
内容：编程题 $5$ 道

第一题，约瑟夫环问题（难度1星）

题意：
有 $n$ 个人围成一个圈，从第 $s$ 个人开始报数，从数字 $1$ 开始报，谁报到数字 $m$ ，谁退出。
已知 $n,s,m$ ，求退出的顺序序列。$ n,s,m \lt 10000 $ 。
思路：
由于 $n$ 很小，不妨直接暴力模拟。O(n)维护一个$vector$，每次都可以$O(1)$求出退出的人。总复杂度$O(n^2)$。
似乎有 $O(n)$的做法，但是我不会，笔试过程中不能翻模板，所以就没写了，有兴趣的可以去看看。

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

int main(){
    int n,s,m;
    scanf("%d%d%d",&n,&s,&m);
    vector<int> vec(n);
    for(int i=0;i<n;i++)vec[i]=i+1;
    s--;m--;
    while(n){
        int pos = (s+m)%n;
        s=pos;
        printf("%d\n",vec[pos]);
        vec.erase(vec.begin()+pos,vec.begin()+pos+1);
        n--;
    }
    return 0;
}

第二题，线段树问题（难度3星）

题意：
给一个数组h[n]，表示n个人的身高，他们一字排开。$n \lt 100000$ 。
对于所有人，求出他右边第一个比他高的人的坐标，如果不存在比他高的人，输出0。
也就是说$for(i,inrange( 1..n) )$ 找到 $j$ 使得 $i \lt j$ && $h[i] \lt h[j]$。
思路：
线段树裸题。
以下是我的代码的思路，当然还有更优秀的做法，但是思维难度更高。
- 对于每一个 $i$ ，二分一个区间$[l,r]$，如果$[l,mid]$这个区间内有人比$i$高，那么$r=mid$，否则$l=mid$ 。
- 对于二分的区间范围内，查询区间最大值的复杂度，最朴素的是$O(n)$的，用线段树可以优化到$O(nlogn)$。
- 所以整体复杂度$O(nlog^2n)$。
以下是$O(nlogn)$的简要思路：
我们可以直接不用二分，把二分的过程嵌套到线段树中实现，比上面的做法难，所以不再赘述。
评价：
还好线段树能够手写，不然“不准翻板子”这一条限定要被我喷成屎。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e5+10;
int n;
int h[maxn];
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define intmid int mid=l+r>>1
int maxv[maxn<<2];
void push_up(int rt){
    maxv[rt]=max(maxv[rt<<1],maxv[rt<<1|1]);
}
void build(int l,int r,int rt){
    if(l==r){
        maxv[rt]=h[l];return;
    }intmid;
    build(lson);build(rson);push_up(rt);
}
int query(int L,int R,int l,int r,int rt){
    if(L<=l&&R>=r){
        return maxv[rt];
    }intmid;
    int ret=0;
    if(L<=mid)ret=max(ret,query(L,R,lson));
    if(R>mid)ret=max(ret,query(L,R,rson));
    return ret;
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",h+i);
    }
    build(1,n,1);
    int l,r,mid;
    for(int i=1;i<=n;i++){
        l=i,r=n+1;
        while(r-l>1){
            mid=l+r>>1;
            if(query(i+1,mid,1,n,1)>h[i]){
                r=mid;
            } else l=mid;
        }
        if(r==n+1)printf("0\n");
        else printf("%d\n",r);
    }
    return 0;
}

第三题，关于合法序列的动态规划问题（难度5星）

题意：
给两个由括号组成的字符串，$s1$和$s2$，把$s1$和$s2$合并起来，得到一个串$S$，这个S保证要是一个合法的括号序列。$|s1|,|s2| \lt 2500$ 。
*合法的例子**：$()()$ ， $(())$
*在保证在原来的串内部，字符顺序不可以改变**的情况下。
问有多少种方案。方案数对 $1e9+7$ 取模。
举个例子：
$(($
$))$
答案为$2$。
思路：
想着用 $dp[i][j]$表示 $s1$ 用了前 $i$ 个，且 $s2$ 用了前 $j$ 个的状态数。但是不知道问题出在哪里了，样例没过。
所以写了一发最暴力的暴搜。每次找到一个答案，都使得答案$+1$，最后骗到了**$80$**分，也是没谁了。
暴搜思路很简单，所以就不再多说了，直接贴代码吧。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
string s1,s2;
ll ans;
bool ok(string s){
    int cnt=0;
    for(int i=0;i<s.size();i++){
        if(s[i]=='(')cnt++;
        else cnt--;
        if(cnt<0)return 0;
    }
    if(cnt)return 0;
    for(int i=s.size()-1;i>=0;i--){
        if(s[i]==')')cnt++;
        else cnt--;
        if(cnt<0)return 0;
    }
    return (cnt==0);
}
void dfs(int i,int j,string s=""){
    if(i<s1.size()&&j<s2.size()){
        s+=s1[i];
        dfs(i+1,j,s);
        s[s.size()-1]=s2[j];
        dfs(i,j+1,s);
    }
    else if(i<s1.size()){
        s+=s1[i];
        dfs(i+1,j,s);
    }
    else if(j<s2.size()){
        s+=s2[j];
        dfs(i,j+1,s);
    }
    else{
        if(ok(s))ans++;
    }
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>s1>>s2;
    dfs(0,0);
    cout<<ans;
    return 0;
}

第四题，杂题(sort + map + 二分查找)（难度2星）

题意
一个公司里有$n$个人，每个人的代码能力是$v[i]$，每个人的薪水$sal[i] = v[i] - rank(v[i] in 1..n)$，其中$rank$的意思是在公司里代码能力由低到高的排名，排名从$1$开始。
给m个询问，问薪水等于x的人有多少个。
$n,m\lt100000 , v[i]\lt50000000000$ 。
思路：
首先对代码能力数组排序，从而可以二分查找到每个人的排名，从而可以算出每个人的薪水。
然后由于薪水数字很大，可以使用红黑树($map$)进行映射。
整体复杂度$O((n+m)logn)$ 。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m;
const int maxn = 800005;
ll v[maxn];
ll vv[maxn];
ll val[maxn];
map<int,int> mp;
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        scanf("%lld",v+i);
        val[i]=vv[i]=v[i];
    }
    sort(vv+1,vv+1+n);
    int x;
    for(int i=1;i<=n;i++){
        x=lower_bound(vv+1,vv+1+n,v[i])-vv;
        val[i]-=x;
        mp[val[i]]++;
    }
    while(m--){
        scanf("%d",&x);
        printf("%d\n",mp[x]);
    }
    return 0;
}

第五题，杂题(前缀和+贪心+二分查找）（难度4星）

题意：
有一条长度无限的道路，运动员初始速度为$v$，有$n$组啦啦队给他加油，每一组的加油区间用$[x,y]$描述。
运动员在位置$pos$时，如果有人给他加油，他就会保持当前速度前行，否则他就会降低$1$个单位的速度。
*速度降低到 $0$ 的时候就不跑了**。运动员可以选择任意起跑位置，求他能跑的最长距离。
$v \lt 1e10 , x,y \lt 1e10 ,n \lt 2e5$。
思路：
首先对所有啦啦队进行排序，然后维护一个前缀和数组$pre[i]$，表示在第 $i$个啦啦队加油的时候，前面损失了多少速度。
然后对于每个啦啦队，计算出从这个啦啦队的位置开始跑，能跑多远。这个时候二分能跑到的最后一个啦啦队的位置便可。由于预处理出$pre[]$数组，所以在进行判断时，复杂度可以达到$O(1)$
所以整体复杂度是$O(nlogn)$。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5+10;
struct node{
    ll x,y;
    node(int x=0,int y=0):x(x),y(y){}
    friend bool operator < (node a,node b){
        if(a.x==b.x)return a.y>b.y;
        return a.x<b.x;
    }
}p[maxn<<1];
int n;
ll v;
ll pre[maxn<<1];
int main(){
    scanf("%d%lld",&n,&v);
    for(int i=1;i<=n;i++){
        scanf("%lld%lld",&p[i].x,&p[i].y);
    }sort(p+1,p+1+n);
    for(int i=2;i<=n;i++){
        pre[i]=pre[i-1];
        if(p[i].x>p[i-1].y){
            pre[i]+=p[i].x-p[i-1].y;
        }
        else {
            p[i].x=min(p[i].x,p[i-1].x);
            p[i].y=max(p[i].y,p[i-1].y);
        }
    }
    pre[n+1]=1e17;
    int l,r,mid;
    ll ans=0;
    for(int i=1;i<=n;i++){
        l=i,r=n+2;
        while(r-l>1){
            mid=l+r>>1;
            if(pre[mid]-pre[i]<v){
                l=mid;
            }
            else{
                r=mid;
            }
        }
        ans=max(ans,p[l].y+v - (pre[l]-pre[i]) - p[i].x);
    }
    cout<<ans<<endl;
    return 0;
}

总结

知识点：动态规划，线段树，约瑟夫环（链表），二分查找，STL容器，前缀和等等。
感觉自己的动态规划能力真的很差，继续加油叭……
惊奇队长 真好看咔咔咔。