美团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;
		}
	}
}

#美团笔试##笔试题目##美团#