3.12 美团笔试题解

• 输入n个数字，判断每个数字满足以下两个条件之一：
  • 是11的倍数
  • 数位里面1的个数大于等于2
• 如果满足输入yes，否则输出no
• 思路很简单，直接模拟判断即可。

#include<bits/stdc++.h>
using namespace std;
bool judge(int x) {
	if(x%11==0) {
		return true;
	}
	int sum=0;
	while(x) {
		if(x%10==1) sum++;
		x/=10;
	}
	return sum>=2;
}
int main() {
	int n;
	cin>>n;
	while(n--) {
		int x;
		cin>>x;
		if(judge(x)) {
			puts("yes");
		} else {
			puts("no");
		}
	}
	return 0;
}

• 输出n(0<n<1000)个数字，每个数字可能是1或者是-1，问连续的序列的乘积是正数的数有多少个？
• 之前刚好刷leetcode遇到个类似的。我们利用前缀和来求，但是我们需要转换一下，我们发现为了使序列的乘积为正数，那么-1的个数一定要是偶数个，所以我们将输入的-1转换为1，输入的1转换为0.然后就可以利用前缀和先预处理然后O(1)地求出每段的-1的个数啦。

#include<bits/stdc++.h>
using namespace std;
int pre[1010];
int main() {
	int n;
	cin>>n;
	for (int i=1;i<=n;i++) {
		int x;
		cin>>x;
		if(x==-1) x=1; 
        else x=0;
		pre[i]=pre[i-1]+x;
	}
	int ans=0;
	for (int i=1;i<=n;i++) {
		for (int j=0;j<i;j++) {
			int tmp=pre[i]-pre[j];
			if(tmp%2==0)  ans++;
		}
	}
	cout<<ans<<endl;
	return 0;
}        

• n个顾客点餐，每个顾客可以点两份餐，数据保证点的餐的种类在1-m，但是饭店现在只可以提供一份1-m种类的餐各一份。
• 问最多可以满足多少位顾客的点餐需求。（0<n<20)
• 看数据，一看就知道是状态压缩，我们可以用一个二进制表示出所有的状态，那么我们最优的答案可以肯定是在所有状态里面的一种了，我们枚举所有的状态，判断是否合法，如果合法，那么就维护一个最优的就行啦。对于每种状态，如果这个位对应的二进制下是1，就表示需要满足这位顾客的需要，否则就是对于这位顾客的两份点餐都不满足。如果在需要满足某位顾客的时候已经没有某一个种类的餐了，那么就说明这种状态是不合法的，我们跳过。
  

#include<bits/stdc++.h>
using namespace std;
int a[22][2];
unordered_map<int,bool> vis;
int main() {
	int n,m;
	cin>>n>>m;
	for (int i=0;i<n;i++) {
		cin>>a[i][0]>>a[i][1];
	}
	int ans=0;
	for (int i=0;i<(1<<n);i++) {
		int sum=0;
		bool flag=true;
		vis.clear();
		for (int j=0;j<n;j++) {
			if((i>>j)&1) {
				++sum;
				// 存在某一份餐已经被消费了
				if(vis[a[j][0]]||vis[a[j][1]]) {
					flag=false;
					break;
				} else {
					vis[a[j][0]]=true;
					vis[a[j][1]]=true;
				}
			}
		}
		if(flag) {
			ans=max(ans,sum);
		}
	}
	cout<<ans<<endl;
	return 0;
}

• n个房间（0<n<=10)，初始的时候A在第一个房间，现在有一个游戏，游戏时长为m（0<m<=10000)秒，给出m 秒每秒的炸弹所在的房间，A需要在每秒避开这些炸弹，也就是A不能在有炸弹的房间。A可以在每秒后选择移动到n个房间中的一个，但是需要消耗1个能量，当然也可以不移动，问A最少需要消耗多少能量。
• 一个动态规划的题目，其实看数据范围也可以猜到。dp[i][j]表示是在第i秒的时候在第j个房间的最小的消耗。然后定义初态和转移方程就行了，第i秒的状态肯定是从第i-1秒的状态转移过来的，我们维护每个状态的最小花费就行了。

#include<bits/stdc++.h>
using namespace std;
int dp[10010][13];
int a[10010];
int main() {
	int n,m;
	cin>>n>>m;
	for (int i=1;i<=m;i++) {
		cin>>a[i];
	}
	memset(dp,0x3f,sizeof(dp));
	dp[1][1]=0;
	for (int i=2;i<=n;i++) {
		dp[1][i]=1;
	}
	for (int i=2;i<=m;i++) {
		for (int j=1;j<=n;j++) {
			// 第i秒肯定不能选a[i]这个房间
			if(a[i]!=j) {
				for (int k=1;k<=n;k++) {
					if(j!=k) {
						dp[i][j]=min(dp[i][j],dp[i-1][k]+1);
					} else {
						dp[i][j]=min(dp[i][j],dp[i-1][k]);
					}
				}
			}
		}
	}
	int ans=1e9;
	for (int i=1;i<=n;i++) {
		ans=min(ans,dp[m][i]);
	}
	cout<<ans<<endl;
	return 0;
}

• 首先输入一个数n(0<n<100000)，表示树的结点的个数，然后输入n个数表示每个结点的颜色，0表示白色，1表示黑色。 接下来输入n个数，表示第i个结点的父节点，如果是0就表示这个结点时根节点。
• 然后，对于白色结点，如果他的子节点中存在一个黑色结点或者它是叶子结点，那么他就是好结点；对于黑色结点，如果它的所有子节点都是白色或者它是叶子结点，那么它就是好结点。
• 问，树里面白色好结点和黑色好结点的个数。
• 这里我们采用建图然后dfs爆搜的方法即可成功切掉本题。

#include<bits/stdc++.h>
using namespace std;
int a[10010];
int fa[10010];
vector<int> v[10010];
int b=0,w=0;
void dfs(int root) {
	if(a[root]==0) {
		if(v[root].size()==0) {
			w++;
			return;
		}
		for (auto x:v[root]) {
			if(a[x]==1) {
				w++;
				break;
			}
		}
		for (auto x:v[root]) {
			dfs(x);
		}
	} else {
		if(v[root].size()==0) {
			b++;
			return;
		}
		bool flag=true;
		for (auto x:v[root]) {
			if(a[x]==1) {
				flag=false;
				break;
			}
		}
		if(flag) b++;
		for (auto x:v[root]) {
			dfs(x);
		}
	}
}
int main() {
	int n;
	cin>>n;
	for (int i=1;i<=n;i++) {
		cin>>a[i];
	}
	int root;
	for (int i=1;i<=n;i++) {
		cin>>fa[i];
		if(fa[i]==0) root=i; 
        else {
			v[fa[i]].push_back(i);
		}
	}
	dfs(root);
	cout<<b<<" "<<w<<endl;
	return 0;
}