美团后端笔试题解 2023.3.11 附源码
T1 100/100
总之就是找连续段长度，答案就是连续段长度/2之和
// 100 points
#include <bits/stdc++.h>
#define int long long
#define sc(a) scanf("%lld",&a)
#define pr(a) printf("%lld",a)
using namespace std;
int n;
char s[100005];
vector<int> tmp;
int ans=0;
signed main() {
scanf("%s",s);
n=strlen(s);
char c=s[0];
int cnt=0;
for(int i=0;i<n;++i) {
if(s[i]==c) ++cnt;
else {
tmp.push_back(cnt);
c=s[i];
cnt=1;
}
}
tmp.push_back(cnt);
for(auto i:tmp) ans+=i/2;
pr(ans);
return 0;
}
T2 100/100
经典dp，状态从左和上转移过来，注意颜色不同时k的判断
我不仅要吐槽，这道题题面说起点位置的金币一定为0，但实际数据可不是这样的，如果你让dp[0][0]=val[0][0]的话就会像我最开始那样45%
// 100 points
#include <bits/stdc++.h>
#define int long long
#define sc(a) scanf("%lld",&a)
#define pr(a) printf("%lld",a)
using namespace std;
int n,m,k;
int v[505][505];
char mp[505][505];
char s[505];
int dp[505][505];
signed main() {
sc(n),sc(m),sc(k);
for(int i=0;i<n;++i) {
scanf("%s",s);
for(int j=0;j<m;++j)
mp[i][j]=s[j];
}
for(int i=0;i<n;++i)
for(int j=0;j<m;++j)
sc(v[i][j]);
for(int i=0;i<n;++i)
for(int j=0;j<m;++j)
dp[i][j]=-10000000000;
dp[0][0]=0;
int ans=0;
for(int i=0;i<n;++i)
for(int j=0;j<m;++j) {
if(i-1>=0
&&mp[i][j]==mp[i-1][j])
dp[i][j]=max(dp[i][j],dp[i-1][j]+v[i][j]);
if(i-1>=0
&&mp[i][j]!=mp[i-1][j]
&&dp[i-1][j]>=k)
dp[i][j]=max(dp[i][j],dp[i-1][j]-k+v[i][j]);
if(j-1>=0
&&mp[i][j]==mp[i][j-1])
dp[i][j]=max(dp[i][j],dp[i][j-1]+v[i][j]);
if(j-1>=0
&&mp[i][j]!=mp[i][j-1]
&&dp[i][j-1]>=k)
dp[i][j]=max(dp[i][j],dp[i][j-1]-k+v[i][j]);
ans=max(ans,dp[i][j]);
}
pr(ans);
return 0;
}
/*
1 3 5
BBR
0 6 10
*/
T3 100/100
一个比较经典的区间覆盖问题，首先要考虑使用差分和前缀和，其次由于数据范围过大，只能使用map来统计答案
// 100 points
#include <bits/stdc++.h>
#define int long long
#define sc(a) scanf("%lld",&a)
#define pr(a) printf("%lld",a)
using namespace std;
int n;
int a[100005];
int b[100005];
map<int,int> mp;
vector<pair<int,int>> v;
signed main() {
sc(n);
for(int i=0;i<n;++i) sc(a[i]);
for(int i=0;i<n;++i) sc(b[i]);
for(int i=0;i<n;++i) {
mp[a[i]]++;
mp[b[i]+1]--;
}
int sum=0;
for(auto i:mp) {
sum+=i.second;
mp[i.first]=sum;
}
//for(auto i:mp) cout<<i.first<<' '<<i.second<<endl;
int mx=-1;
for(auto i:mp) mx=max(mx,i.second);
pr(mx);printf(" ");
int ans=0;
for(auto i:mp) v.push_back(i);
for(int i=0;i<v.size();++i) {
if(v[i].second!=mx) continue;
if(i==v.size()-1) ++ans;
else ans+=v[i+1].first-v[i].first;
}
pr(ans);
return 0;
}
/*
3
2 1 5
6 3 7
*/
T4 81/100
可能是最折磨人的大模拟，写了一百多行，写到最后也没调出来，遂直接放弃
// 81 points
#include <bits/stdc++.h>
#define int long long
#define sc(a) scanf("%lld",&a)
#define pr(a) printf("%lld",a)
using namespace std;
char a[300],b[300];
int dpos[2]={0,0};
int wpos[2]={15,15};
int mp[16][16];
int ddir=2;
int wdir=4;
bool dfire() {
if(ddir==1) {
for(int i=dpos[0];i>=0;--i)
if(i==wpos[0]&&dpos[1]==wpos[1])
return true;
} else if(ddir==2) {
for(int j=dpos[1];j<16;++j)
if(dpos[0]==wpos[0]&&j==wpos[1])
return true;
} else if(ddir==3) {
for(int i=dpos[0];i<16;++i)
if(i==wpos[0]&&dpos[1]==wpos[1])
return true;
} else if(ddir==4) {
for(int j=dpos[1];j>=0;--j)
if(dpos[0]==wpos[0]&&j==wpos[1])
return true;
}
return false;
}
bool wfire() {
if(wdir==1) {
for(int i=wpos[0];i>=0;--i)
if(i==dpos[0]&&wpos[1]==dpos[1])
return true;
} else if(wdir==2) {
for(int j=wpos[1];j<16;++j)
if(wpos[0]==dpos[0]&&j==dpos[1])
return true;
} else if(wdir==3) {
for(int i=wpos[0];i<16;++i)
if(i==dpos[0]&&wpos[1]==dpos[1])
return true;
} else if(wdir==4) {
for(int j=wpos[1];j>=0;--j)
if(wpos[0]==dpos[0]&&j==dpos[1])
return true;
}
return false;
}
signed main() {
scanf("%s",a);
scanf("%s",b);
mp[0][0]=1; // d
mp[15][15]=2; // w
int n=strlen(a);
for(int i=0;i<n;++i) {
if(a[i]=='F'&&b[i]=='F') {
if(dfire()&&wfire()) {
pr(i+1);
puts("");
printf("P");
return 0;
} else if(dfire()&&!wfire()) {
pr(i+1);
puts("");
printf("D");
return 0;
} else if(!dfire()&&wfire()) {
pr(i+1);
puts("");
printf("W");
return 0;
}
} else if(a[i]=='F'&&b[i]!='F') {
if(dfire()) {
pr(i+1);
puts("");
printf("D");
return 0;
}
} else if(a[i]!='F'&&b[i]=='F') {
if(wfire()) {
pr(i+1);
puts("");
printf("W");
return 0;
}
}
// d move
if(a[i]=='U') {
ddir=1;
if(dpos[0]-1>=0&&mp[dpos[0]-1][dpos[1]]!=2)
dpos[0]--;
} else if(a[i]=='D') {
ddir=3;
if(dpos[0]+1<16&&mp[dpos[0]+1][dpos[1]]!=2)
dpos[0]++;
} else if(a[i]=='L') {
ddir=4;
if(dpos[1]-1>=0&&mp[dpos[0]][dpos[1]-1]!=2)
dpos[1]--;
} else if(a[i]=='R') {
ddir=2;
if(dpos[1]+1<16&&mp[dpos[0]][dpos[1]+1]!=2)
dpos[1]++;
}
// wmove
if(b[i]=='U') {
wdir=1;
if(wpos[0]-1>=0&&mp[wpos[0]-1][wpos[1]]!=1)
wpos[0]--;
} else if(b[i]=='D') {
wdir=3;
if(wpos[0]+1<16&&mp[wpos[0]+1][wpos[1]]!=1)
wpos[0]++;
} else if(b[i]=='L') {
wdir=4;
if(wpos[1]-1>=0&&mp[wpos[0]][wpos[1]-1]!=1)
wpos[1]--;
} else if(b[i]=='R') {
wdir=2;
if(wpos[1]+1<16&&mp[wpos[0]][wpos[1]+1]!=1)
wpos[1]++;
}
// crush
//if(dpos[0]==wpos[0]&&dpos[1]==wpos[1]) {
// pr(i);
// puts("");
// printf("P");
// return 0;
//}
mp[dpos[0]][dpos[1]]=1;
mp[wpos[0]][wpos[1]]=2;
}
// count
int wc=0,dc=0;
for(int i=0;i<16;++i)
for(int j=0;j<16;++j)
if(mp[i][j]=='1') ++dc;
else if(mp[i][j]=='2') ++wc;
puts("256");
if(wc>dc) printf("W");
else if(wc==dc) printf("P");
else printf("D");
return 0;
}
/*
RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR
UUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUUU
*/
T5 100/100
简单统计一下子树即可，非常简单
// 100 points
#include <bits/stdc++.h>
#define int long long
#define sc(a) scanf("%lld",&a)
#define pr(a) printf("%lld",a)
using namespace std;
int n,ans=0;
char v[10005];
vector<int> eg[10005];
pair<int,int> dfs(int x) {
pair<int,int> p={0,0};
for(auto i:eg[x]) {
auto t=dfs(i);
p.first+=t.first;
p.second+=t.second;
}
if(p.first==p.second) ++ans;
if(v[x-1]=='R') ++p.first;
else ++p.second;
return p;
}
signed main() {
sc(n);
scanf("%s",v);
for(int i=2;i<=n;++i) {
int f;
sc(f);
eg[f].push_back(i);
}
dfs(1);
pr(ans);
return 0;
}
#笔试##笔试复盘##美团笔试#
投递华为等公司10个岗位 >