3.12 美团笔试题

A题(暴力)

题意

小美现在相信一些数字能给他带来好运。
这些数字至少满足以下两个特征中的一种:
  • 数字是11的整数倍。
  • 数字中至少包含两个1。
小美现在给你若干数字,希望你回答这个数字是不是幸运数。
例如:132是11的12倍,满足条件1,101有两个1,满足条件2。

#include "bits/stdc++.h"
using namespace std;

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	int _; cin >> _;
	while(_--) {
		int n; cin >> n;
		if(n % 11 == 0) {
			cout << "yes" << endl;
			continue ;
		}
		int cnt = 0;
		while(n) cnt += (n % 10 == 1), n /= 10;
		cout << (cnt >= 2 ? "yes" : "no") << endl;
	}		

	return 0;
}

B题(前缀积)

题意

小美现在有一个序列,序列中仅包含1和 - 1两种数字。
小美现在想要知道,有多少个连续的子序列,序列中的数字乘积为正。
#include "bits/stdc++.h"
using namespace std;

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	int n; cin >> n;
	int ans = 0;
	vector<int> a(n);
	for(int i = 0;i < n; i++) cin >> a[i];
	for(int i = 1;i < n; i++) a[i] *= a[i - 1];
	for(int i = 0;i < n; i++) {
		for(int j = i;j < n; j++) {
			ans += (a[j] * (i > 0 ? a[i - 1] : 1) == 1);
		}
	}
	cout << ans << endl;
	return 0;
}

C题(状压)

题意

小美现在在厨房做饭。小美发现食材现在只够每种菜做一份。现在同一时刻(即不分先后顺序)来了n个顾客。每个顾客都有想两份要点的菜。只有当顾客吃到全部自己想要的菜的时候,顾客才会满意。
现在你的任务是,合理地接取顾客的订单要求,尽可能让更多的顾客满意,并输出最多有多少顾客可以满意。

思路

首先看到数据n=20,所以可以使用状压dp。
(平时做题的时候先看数据范围,一般的题目都能从数据范围猜出使用的算法)
假设mask上的1为当前选取的顾客,则判断一份食物是否被这些顾客选取多次,因为食物只有一份,按照题意模拟就好。
#include "bits/stdc++.h"
using namespace std;

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	int n, m; cin >> n >> m;
	vector<int> a(n), b(n);
	for(int i = 0;i < n; i++) cin >> a[i] >> b[i];
	int ans = 0;
	for(int mask = 0;mask < (1 << n); mask++) {
		vector<bool> vis(m);
		int res = 0;
		bool flag = 1;
		for(int i = 0;i < n; i++) {
			if(mask >> i & 1) {
				res++;
				if(vis[a[i]] || vis[b[i]]) {
					flag = 0;
					break ;
				}
				vis[a[i]] = vis[b[i]] = 1;
			}
		}
		if(flag) ans = max(ans, res);
	}
	cout << ans << endl;
	return 0;
}

D题(DP)

题意

题目描述:
小美现在打音游。这个音游的玩法是这样的:
共有n个房间。小美初始拥有一个指针,指在一号房间。
游戏共持续m秒,每秒会有一个房间产生炸弹,小美的指针不能在这个房间中。
每秒结束的瞬间,小美可以使用一次魔法,把指针切换到另一个房间中,该过程会消耗一个能量。
你的任务是计算小美无伤通过音游所需要消耗的最小能量。
保证第一秒的炸弹不发生在一号房间中/

思路
因为n只有10,所以设dp[i][j]表示为到第i秒,指针指向j房间的最小能量。
所以转移方程为:

if(a[i] == j) dp[i][j] = 1e9 (因为第i秒指针不能指向j房间)

else dp[i][j] = min(dp[i][j], min(dp[i - 1][j], dp[i - 1][a[i]] + 1));(可以从上1秒转移过来,或者从房间a[i]转移过来,不过需要消耗能量)

#include "bits/stdc++.h"
using namespace std;

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	int n, m; cin >> n >> m;
	vector<int> a(m);
	for(int i = 0;i < m; i++) cin >> a[i];
	vector<vector<int>> dp(m + 1, vector<int>(n + 1, 1E9));
	dp[0][1] = 0;
	for(int i = 1;i <= m; i++) {
		for(int j = 1;j <= n; k++) {
			if(a[i - 1] == j) dp[i][j] = 1E9;
			else dp[i][j] = min(dp[i][j], min(dp[i - 1][j], dp[i - 1][a[i - 1]] + 1));
		}
	}
	cout << *min_element(dp.back().begin(), dp.back().end()) << endl;
	return 0;
}


E题(dfs)

题意

现在给你一颗树,每个树上的节点会被涂成黑色或白色。
现在定义好节点:
对于白色的节点:若该节点没有子节点,或该节点子节点中至少有一个为黑色节点,则该节点是好节点
对于黑色的节点:若该节点没有子节点,或该节点的所有子节点均为白色节点,则该节点是好节点
你的任务是找出这棵树上黑色的好节点和白色的好节点各有几个。

思路

暴力dfs,记录节点下面的黑白节点个数即可。
#include "bits/stdc++.h"
using namespace std;

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	int n; cin >> n;
	vector<int> color(n);
	for(int i = 0;i < n; i++) cin >> color[i];	
	int root;
	vector<vector<int>> g(n);
	for(int i = 0;i < n; i++) {
		int x; cin >> x;
		if(x == 0) root = i;
		else {
			x--;
			g[x].push_back(i);
		}
	}

	int ans1 = 0, ans0 = 0;
	function<void(int)> dfs = [&](int u) {
		int cnt1 = 0, cnt0 = 0;
		for(int v : g[u]) {
			if(color[v] == 1) cnt1++;
			else cnt0++;
			dfs(v);
		}
		if(color[u] == 1 && (cnt0 + cnt1 == 0 || cnt0 == g[u].size())) ans1++;
		if(color[u] == 0 && (cnt0 + cnt1 == 0 || cnt1 > 0)) ans0++;
	};
	dfs(root);
	cout << ans0 << " " << ans1 << endl;
	return 0;
}


#笔经##美团#
全部评论
老哥太强了
点赞 回复
分享
发布于 2022-03-12 19:32
我几乎全贪心做的
点赞 回复
分享
发布于 2022-03-12 19:55
饿了么
校招火热招聘中
官网直投
有没有状态压缩的讲解?
点赞 回复
分享
发布于 2022-03-12 20:14
第四题题目是啥呀?
点赞 回复
分享
发布于 2022-03-12 20:22
阿里巴巴企业智能事业部急缺java简历,部门竞争小,不内卷,可私信或+qq:2226533775;帮忙跟进面试流程;如果已在流程中想转BU面试,或者帮忙捞简历都可以联系!
点赞 回复
分享
发布于 2022-03-15 18:52
求问接到了后续面试通知吗 我也是3.12考试的😥 但还没有消息
点赞 回复
分享
发布于 2022-03-18 15:59
吸吸算法智慧
点赞 回复
分享
发布于 2022-03-22 00:47
刷到校友,强
点赞 回复
分享
发布于 2022-03-23 02:53

相关推荐

26 140 评论
分享
牛客网
牛客企业服务