美团8.29大数据开发工程师笔试 1,1,1,0,1
第四题读错题了 发现有问题已经懒得写了 感觉自己真的拉跨
希望能过吧
T1 一个字符串 串首串尾各有一个加密串 串首加密串包含MT子串并以T结尾 串尾加密串包含MT子串并以M开头 求最长的原本的字符串
很水 我觉得不用说了
T2 水水水 比第一题还水
T3 一棵树 两个人在两个节点 一个人跑一个人追 问最晚多长时间能追到
很简单 两遍BFS 跑的人在扩展结点时注意如果当前节点的时间戳已经大于等于追的人对应的时间戳 就不要扩展了 之后返回跑的人能遍历到的节点中追的人的时间戳的最大值
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#define maxn 50001
using namespace std;
vector<int>G[maxn];
void addedge(int from,int to) {
G[from].push_back(to);
G[to].push_back(from);
}
int dist[maxn], d2[maxn];
int main() {
int n, s, t;
cin >> n >> s >> t;
queue<int>que;
que.push(s);
for (int i = 0; i < n - 1; i ++) {
int from,to;
cin >> from >> to;
addedge(from, to);
}
while (!que.empty()) {
int k = que.front();
que.pop();
for (int i = 0; i < G[k].size(); i ++) {
int u = G[k][i];
if (!dist[u]) {
dist[u] = dist[k] + 1;
que.push(u);
}
}
}
int ans = 0;
que.push(t);
while (!que.empty()) {
int k = que.front();
que.pop();
ans = max(ans, dist[k]);
if(dist[k] <= d2[k])
continue;
for (int i = 0; i < G[k].size(); i ++) {
int u = G[k][i];
if (!d2[u]) {
d2[u] = d2[k] + 1;
que.push(u);
}
}
}
cout << ans;
} T4 我太菜了不会 T5 有A,B两个数组 长度相同都<=2000(妈的 这数据怎么这么弱) 有q(<=2000 妈的怎么还是这么弱)次询问 一开始B全为-1 询问有两种形式 一个是将A中以a开头长度为k的数据复制到B的b位置 另一个是查询B的x位置对应的值 看起来好像暴力能过（复杂度最坏n方 怎么第五题出了这么个fw题 奇怪） 但我用的线段树+LAZYTAG思想（变成NlgN了 感觉对这种弱的厉害的数据其实优化作用不大） 但不同的是 因为这个复制是没有累加的 所以不需要进行pushdown 而只需要对每个结点记录一个操作时间 查询时拿出所查询节点在线段树中对应的节点 一路往上爬 找到时间戳最新的tag 之后通过tag查找A数组 这应该很快非常快
#include <iostream>
#include <cstdio>
#include <cstring>
#define maxn 2001
using namespace std;
int segStarta[maxn * 4], segStartb[maxn * 4], segTime[maxn * 4];
int data[maxn];
int ori[maxn];
int n;
void build (int l, int r, int o) {
//cout << "build" << l << " " << r << " " << o << endl;
if (l == r) {
ori[l] = o;
return;
}
int mid = (l+r)/2;
build(l, mid, o<<1);
build(mid + 1, r, o<<1|1);
}
void addLabel(int l, int r,int ll, int rr, int o, int labelx, int labely, int segTimee) {
if (l >= ll && r <= rr) {
segStarta[o] = labelx;
segStartb[o] = labely;
segTime[o] = segTimee;
//cout << "add" << l << " " << r << " " << labelx << " " << labely << endl;
return;
}
int mid = (l+r)/2;
if (ll <= mid) {
addLabel(l,mid,ll,rr,o<<1,labelx,labely,segTimee);
}
if (rr > mid) {
addLabel(mid+1,r,ll,rr,o<<1|1,labelx,labely,segTimee);
}
}
void paste(int a, int b, int len, int segTimee) {
addLabel(0, n-1, b, b+len-1, 1, a, b, segTimee);
}
int query(int x) {
int o = ori[x];
int labA = -1, labB = -1, segTimee = -1;
while (o) {
if(segStarta[o] != -1 && segTime[o] > segTimee) {
labA = segStarta[o];
labB = segStartb[o];
segTimee = segTime[o];
}
o >>= 1;
}
if (labA == -1)
return -1;
return data[x - labB + labA];
}
int main() {
memset(segStarta, -1, sizeof(segStarta));
memset(segStartb, -1, sizeof(segStarta));
cin >> n;
for (int i = 0; i < n; i ++) {
cin >> data[i];
}
build(0,n-1,1);
int q;
cin >> q;
for (int i = 0; i < q; i++) {
int k;
cin >> k;
if (k == 1) {
int off, a, b;
cin >> off >> a >> b;
paste(a - 1, b - 1, off, i);
} else {
int x;
cin >> x;
cout << query(x - 1) << endl;
}
}
} 
哔哩哔哩公司福利 314人发布
投递淘天集团等公司10个岗位