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兩種數字。
小美現在想要知道，有多少個連續(xù)的子序列，序列中的數字乘積為正。

#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題（狀壓）

題意

小美現在在廚房做飯。小美發(fā)現食材現在只夠每種菜做一份?，F在同一時刻（即不分先后順序）來了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個房間。小美初始擁有一個指針，指在一號房間。
游戲共持續(xù)m秒，每秒會有一個房間產生炸彈，小美的指針不能在這個房間中。
每秒結束的瞬間，小美可以使用一次魔法，把指針切換到另一個房間中，該過程會消耗一個能量。
你的任務是計算小美無傷通過音游所需要消耗的最小能量。
保證第一秒的炸彈不發(fā)生在一號房間中/

思路

因為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）

題意

現在給你一顆樹，每個樹上的節(jié)點會被涂成黑色或白色。
現在定義好節(jié)點：
對于白色的節(jié)點：若該節(jié)點沒有子節(jié)點，或該節(jié)點子節(jié)點中至少有一個為黑色節(jié)點，則該節(jié)點是好節(jié)點
對于黑色的節(jié)點：若該節(jié)點沒有子節(jié)點，或該節(jié)點的所有子節(jié)點均為白色節(jié)點，則該節(jié)點是好節(jié)點
你的任務是找出這棵樹上黑色的好節(jié)點和白色的好節(jié)點各有幾個。

思路

暴力dfs，記錄節(jié)點下面的黑白節(jié)點個數即可。

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

#筆經##美團#