美团 2023年春招 JAVA后端开发方向

分糖

时间限制:3000MS
内存限制: 589824KB
题目描述:
小美因乐于助人的突出表现获得了者师的嘉奖。
老师允许小美从一堆n个编号分别为1,2,..,n的糖果中选择任意多个糖果作为奖励(每种编号的果各一个)，
但为了防止小美一次吃太多糖果有害身体健康，老师设定了个眼制: 
如果选择了编号为i的果，那么就不能选择编号为 i-1,i-2,i+1,i+2的四个糖果了。
在小美看来,每个糖果都有一个对应的美味值，小美想让她选出的糖果的美味值之和最大!
作为小美的好朋友，请你帮帮她!

输入描述

第一行一个整数n，表示糖果数量。
第二行n个整数a1,a2,...,an，其中ai表示编号为i的糖果的美味值。
1<=n<=50000，1<=ai<=10000

输出描述

输出一行一个数，表示小美能获得的糖果美味值之和最大值。

样例输入

7
3 1 2 7 10 2 4

样例输出

14

思路：设定dfs(idx,sum)，i表示当前考虑第i个糖果，sum表示当前美味值的和。

第一种情况：每个位置都可以不选，那么对应的下一个状态就是dfs(i+1,sum)。

第二种情况：当满足满足used[i-2] = used[i-1] =false时，那么就可以选当前糖果，即令used[i]=true，下一个状态为dfs(i+1,sum+a[i])，状态退出时置used[i]=false。

#include<iostream>
using namespace std;

const int maxn = 5e4 + 7;
int n, a[maxn], global_max;
bool used[maxn];

void DFS(int idx, int sum){
	if(idx == n){
		global_max = max(global_max, sum);
		return;
	}
	bool can_use = true;
	for(int i = max(idx - 2, 0); i < idx; ++ i){
		can_use &= (! used[i]);
	}
	if(can_use){
		used[idx] = true;
		DFS(idx + 1, sum + a[idx]);
		used[idx] = false;
	}
	DFS(idx + 1, sum);
}

int main(){
	cin >> n;
	int idx;
	for(idx = 0; idx < n; ++ idx){
		cin >> a[idx];
	}	
	DFS(0, 0);
	cout << global_max;
	return 0;
} 

有一个剪枝优化的方法即，当我们考虑i号糖果时，如果剩下的所有糖果都考虑了(显然这不可能，因为并不满足当选择j时不选择j-1，j-2，j+1，j+2)，但是如果剩下的都选了还不能大于当前得到的最大值，那很显然这种情况可以直接不考虑了，因为及时考虑了也不可能是答案。

#include<iostream>
using namespace std;

const int maxn = 5e4 + 7;
int n, a[maxn], rest[maxn], global_max; //rest[i] 除去0-i-1部分即i-n-1部分的和 
bool used[maxn];

void DFS(int idx, int sum){
	if(sum + rest[idx] <= global_max){
		return;
	}
	if(idx == n){
		global_max = max(global_max, sum);
		return;
	}
	bool can_use = true;
	for(int i = max(idx - 2, 0); i < idx; ++ i){
		can_use &= (! used[i]);
	}
	if(can_use){
		used[idx] = true;
		DFS(idx + 1, sum + a[idx]);
		used[idx] = false;
	}
	DFS(idx + 1, sum);
}

int main(){
	cin >> n;
	int idx, prefix_sum = 0, sum = 0;
	for(idx = 0; idx < n; ++ idx){
		cin >> a[idx];
		sum += a[idx];
	}	
	for(idx = 0; idx < n; ++ idx){
		rest[idx] = sum - prefix_sum;
		prefix_sum += a[idx];
	}
	DFS(0, 0);
	cout << global_max;
	return 0;
} 

春游

时间限制:3000MS
内存限制: 589824KB
题目描述:
小美因乐于助人的突出表现获得了者师的嘉奖。
老师允许小美从一堆n个编号分别为1,2,..,n的糖果中选择任意多个糖果作为奖励(每种编号的果各一个)，
但为了防止小美一次吃太多糖果有害身体健康，老师设定了个眼制: 
如果选择了编号为i的果，那么就不能选择编号为 i-1,i-2,i+1,i+2的四个糖果了。
在小美看来,每个糖果都有一个对应的美味值，小美想让她选出的糖果的美味值之和最大!
作为小美的好朋友，请你帮帮她!

输入描述

第一行两个整数n和m，表示小美的巧克力数量和小美的询问数量
第二行n个整数a1,a2,...,an，表示n块正方形巧克力板的边长。注意你不能将巧克力板进行拆分。
第三行m个整数q1,q2,...,qm，第i个整数qi表示询问: 如果小美选择多少块巧克力板?
(不考虑体积影响，我们认为只要质量满足要求，巧克力板总能塞进包里)
1<=n,m<=50000,1<=ai<=10^4,1<=qi<=10^18

输出描述

输出一行m个整数，分别表示每次询问的答案

样例输入

5 5
1 2 2 4 5
1 3 7 9 15

样例输出

1 2 3 4 5

思路：我们先单看某一个查询qi，要想装最多的块数，不考虑体积只考虑体重，那么肯定尽量装重量小的巧克力才能装最多的块数。现在我们看多个查询，我们可以从小到大进行查询，因为一定会满足 大包能装的数量不会小于小包的，因此我们只需要在小包装的基础上，试着装更多块即可，即对查询做一次离线排序后，计算答案，再按照输入顺序排序回去输出答案。

#include<iostream>
#include<algorithm>
using namespace std;

const int max_num = 5e4 + 7;
int a[max_num];

struct Query{
	long long q_value;
	int ori_idx, answer;
};
Query queries[max_num];

int main(){
	int n, m, idx, query_idx, a_idx;
	long long q_value;
	cin >> n >> m;
	for(a_idx = 1; a_idx <= n; ++ a_idx){
		cin >> a[a_idx];	
	} 
	for(query_idx = 1; query_idx <= m; ++ query_idx){
		cin >> q_value;
		queries[query_idx] = Query{q_value, query_idx, 0};
	} 
	
	sort(queries, queries + m, [](Query A, Query B){
		return A.q_value < B.q_value;	
	});
	
	q_value = 0;
	a_idx = 1;
	for(query_idx = 1; query_idx <= m; ++ query_idx){
		while(a_idx <= n - 1 && q_value + a[a_idx + 1] < queries[query_idx].q_value){
			q_value += a[a_idx ++];
 		}
  queries[query_idx].answer = a_idx;
	}
	
	sort(queries, queries + m, [](Query A, Query B){
		return A.ori_idx < B.ori_idx;	
	});
	for(query_idx = 1; query_idx <= m; ++ query_idx){
		cout << queries[query_idx].answer << " ";
	}
	return 0;
}

当然，如果读者注意到本题数据描述上的条件，n<=50000,1<=ai<=10^4,1<=qi<=10^18，a的最大和为5*10^8，因此当查询大于这个界限值的时候，很显然所有的巧克力都能装下。

解释器

时间限制:3000MS
内存限制: 589824KB
题目描述:
小美因为自己差劲的表达能力而苦恼，小美想制作一个解释器，这样她可以在无法表达的情况下让解释器
帮她解释程序。好巧不巧小美翻开了编译原理的书，找到了解释器的制作方式，她决定先制作一个书上练
习题中描述的小解释器试试。小美需要诞入一行字符串，其格式为"key1=val1;key2=val2;...;
keyn-1=valn-1;keyn =valn;"(不包含引号)。这样的n对key,value对，其中keyi和vali为第i对
key,value对，且均为仅包含大小写英文字母、数字与斜杠的非空字符串。例如对于字符串
"SHELL=/bin/bash;HOME=/home/xiaomei;LOGNAME=xiaomei;"，那么其中包含三对keyvalue对，
以(keyvalue)形式展示分别为(SHELL,/bin/bash)、(HOME,/home/xiaomei)、(LOGNAME,xiaomei)。
接下来，小美的解释器需要接受q次询问，每次询问给出一个仅包含大小写英文字母、数字与斜杠的非空
字符串，如果存在某对key,value对的key值与之相同，那么输出对应的value; 如果存在多对key,value
对的key值与之相同，那么输出其中编号最大的，也即最后那一对的value值;如果一对也不存在，那么输出
EMPTY。

输入猫述

第一行一个字符串S，满足题中所述格式。
接下来一个整数q，表示有q个询问。
接下来q行，每行一个仅包含大小写英文字母、数字与斜杆的非空字符串，分别为S1,S2,...,Sq
依次表示q次询问。
令|S|表示字符串S的长度。
1<=|S|<=50000，0<sum{|si|, i=[1,q]}<=|S|，1<=q<=300，S中至少包含一对key,value对

输出描述

输出q行，每行一个字符串表示答案

输入样例

LOGNAME=default;SHELL=/bin/bash;HOME=/home/xiaomei;LOGNAME=xiaomei;
4
SHELL
HOME
LOGNAME
logname

输出样例

/bin/bash
/home/xiaomei
xiaomei
EMPTY

思路：本题最直观的想法就是对字符串进行分割，首先以';'分割出每一个key-value对，然后对每一个key-value对再以=分割得到key和value，再以哈希表存储。对于 如果存在多对key,value
对的key值与之相同，那么输出其中编号最大的，也即最后那一对的value值，其实不需要特殊考虑，因为在哈希表内，对同一个key的赋值，编号大的value一定会覆盖编号小的。

#include<iostream>
#include<string>
#include<unordered_map>
using namespace std;

unordered_map<string, string> key_value;

void add(string str){
	int i, n = str.length();
	for(i = 0; i < n; ++ i){
		if(str[i] == '='){
			string key = str.substr(0, i);
			string value = str.substr(i + 1, n - i);
			cout << key << ":" << value << endl;
			key_value[key] = value;
			break;
		}
	}
}

void analysis_str(string& str){
	int i, start = 0 , n = str.length();
	for(i = 0; i < n; ++ i){
		if(str[i] == ';'){
			add(str.substr(start, i - start));
			start = i + 1;
		}
	}
	if(start < n) add(str.substr(start, n - start));//处理一下如果输入末尾没有;的问题 
}

int main(){
	string str, query;
	int q,  i;
	cin >> str >> q;
	analysis_str(str);
	while(q --){
		cin >> query;
		cout << (key_value.find(query) == key_value.end() ? "EMPTY" : key_value[query]) << endl;
	}
	return 0;
}

当然还有一个快一点的方法，先按照;再按照=划分总共会导致整个串遍历两次，考虑到输入的格式规范：key,value均为仅包含大小写英文字母、数字与斜杠的非空字符串，所以我们可以利用简单的状态机，初始状态为0，当状态为0时，遍历到的字符都是key的部分，而当遇到=时，状态切换到1，当状态为1时 ，遍历到的字符都是value的部分，而当遇到;时，表示已经遍历完了一个key-value对，此时状态切换为0。

#include<iostream>
#include<string>
#include<unordered_map>
using namespace std;

unordered_map<string, string> key_value;

int main(){
	string str, query, key;
	int q, i, start = 0, n;
	bool zero_state = false;
	cin >> str >> q;
	n = str.length();
	for(i = 0; i < n; ++ i){
		if(str[i] == '='){
			key = str.substr(start, i - start);
			start = i + 1;
			zero_state = false;
		}else if(str[i] == ';'){
			key_value[key] = str.substr(start, i - start);
			start = i + 1;
			zero_state = true;
		}
	} 
	if(start < n) key_value[key] = str.substr(start, i - start);//处理一下如果输入末尾没有;的问题 
	while(q --){
		cin >> query;
		cout << (key_value.find(query) == key_value.end() ? "EMPTY" : key_value[query]) << endl;
	}
	return 0;
}