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

#笔经##美团#