腾讯笔试AK

顺序可能有误，记录一下

第一题：

用C++来做,Java莫名超时

#define FRER() freopen("i.txt","r",stdin);
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+10,inf=0x3f3f3f3f;

int main() {
    //FRER();
    vector<int> vec;
    int n,k;
    scanf("%d%d",&n,&k);
    while(n--) {int x; scanf("%d",&x); vec.push_back(x);}
    vec.erase(vec.begin()+k-1);
    for(int i=0; i<vec.size(); ++i) {
        if(i)printf(" ");
        printf("%d",vec[i]);
    }
    puts("");

    return 0;
}

第二题

后缀自动机

#define FRER() freopen("i.txt","r",stdin);
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
typedef long long ll;
const int N=1e4+10,M=26;
char s[N],s2[N];
int n,f,k;
struct SAM {
    int go[N][M],pre[N],mxl[N],c[N],ss[N],tot,last,siz[N],sum[N],vis[N],mx;
    void init() {last=tot=0; newnode(0); pre[0]=-1;}
    int newnode(int l) {
        int u=tot++;
        memset(go[u],0,sizeof go[u]);
        mxl[u]=l,siz[u]=0;
        return u;
    }
    void add(int ch) {
        int p=last,np=last=newnode(mxl[p]+1);
        siz[np]=1;
        for(; ~p&&!go[p][ch]; p=pre[p])go[p][ch]=np;
        if(!~p)pre[np]=0;
        else {
            int q=go[p][ch];
            if(mxl[q]==mxl[p]+1)pre[np]=q;
            else {
                int nq=newnode(mxl[p]+1);
                memcpy(go[nq],go[q],sizeof go[nq]);
                pre[nq]=pre[q],pre[q]=pre[np]=nq;
                for(; ~p&&go[p][ch]==q; p=pre[p])go[p][ch]=nq;
            }
        }
    }
    void build(char* s,int n) {init(); for(int i=0; i<n; ++i)add(s[i]-'a');}
    void toposort() {
        for(int i=0; i<tot; ++i)c[i]=0;
        for(int i=0; i<tot; ++i)++c[mxl[i]];
        for(int i=1; i<tot; ++i)c[i]+=c[i-1];
        for(int i=0; i<tot; ++i)ss[--c[mxl[i]]]=i;
    }
    void getsiz() {
        for(int i=tot-1; i>0; --i)siz[pre[ss[i]]]+=siz[ss[i]];
        siz[0]=0;
    }
    void getsum() {
        for(int i=0; i<tot; ++i)sum[i]=siz[i];
        for(int i=tot-1; i>=0; --i)
            for(int j=0; j<M; ++j)if(go[ss[i]][j])sum[ss[i]]+=sum[go[ss[i]][j]];
    }
    void qry(int u,int k) {
        int dep;
        for(dep=0; k>siz[u]; ++dep) {
            k-=siz[u];
            for(int i=0; i<M; ++i) {
                int v=go[u][i];
                if(!v)continue;
                if(k<=sum[v]) {s2[dep]=i+'a',u=v; break;}
                k-=sum[v];
            }
        }
        s2[dep]=0,puts(s2);
    }
    void run() {
        build(s,n);
        toposort();
        if(f)getsiz();
        else {for(int i=1; i<tot; ++i)siz[i]=1; siz[0]=0;}
        getsum();
        if(sum[0]<k)puts("-1");
        else qry(0,k);
    }
} sam;
int main() {
    //FRER();
    scanf("%s%d",s,&k),n=strlen(s);
    f=0;
    sam.run();
    return 0;
}

第三题回文

#define FRER() freopen("i.txt","r",stdin);
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=400+10,inf=0x3f3f3f3f;
int dp[N][N],ok[N][N],n;
char s[N];
int dfs(int l,int r) {
    int& ret=dp[l][r];
    if(~ret)return ret;
    ret=inf;
    if(ok[l][r])return ret=1;
    for(int i=l; i<r; ++i)ret=min(ret,dfs(l,i)+dfs(i+1,r));
    return ret;
}
int check(int l,int r) {
    for(int i=0; i<=r-l; ++i)if(s[l+i]!=s[r-i])return 0;
    return 1;
}
int main() {
    //FRER();
    scanf("%s",s+1),n=strlen(s+1);
    for(int l=1; l<=n; ++l)
        for(int r=l; r<=n; ++r)
            ok[l][r]=check(l,r);
    memset(dp,-1,sizeof dp);
    int k;
    for(scanf("%d",&k); k--;) {
        int l,r;
        scanf("%d%d",&l,&r);
        printf("%d\n",dfs(l,r));
    }
    return 0;
}

第四题木板

#define FRER() freopen("i.txt","r",stdin);
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=5000+10,inf=0x3f3f3f3f;
ll n,h[N],mi;
ll solve(ll l,ll r,ll hf) {
    ll mi=inf,cost=0;
    for(ll i=l; i<=r; ++i)mi=min(mi,h[i]);
    for(ll i=l,j; i<=r; ++i) {
        if(h[i]==mi)continue;
        for(j=i+1; j<=r&&h[j]>mi; ++j);
        cost+=solve(i,j-1,mi);
        i=j;
    }
    return min(cost+(mi-hf),r-l+1);
}
int main() {
    //FRER();
    scanf("%lld",&n);
    for(ll i=1; i<=n; ++i)scanf("%lld",&h[i]);
    printf("%lld\n",solve(1,n,0));
    return 0;
}

第五题

#define FRER() freopen("i.txt","r",stdin);
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e5+10,inf=0x3f3f3f3f;
ll f(ll x) {ll ret=0; for(; x; x/=10)ret+=x%10; return ret;}
int main() {
    //FRER();
    ll _;
    for(scanf("%lld",&_); _--;) {
        ll x;
        scanf("%lld",&x);
        ll y=0;
        for(; y*10+9<=x; y=y*10+9);
        printf("%lld\n",f(y)+f(x-y));
    }
    return 0;
}

#腾讯##笔试题目#