简述
- 岗位：客户端
- 写题语言：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) 回帖