美团2024届秋招笔试第一场编程【代码】

发现之前上课口胡的好多bug😅😅   现在贴上的代码都是AC的

一、小美的排列构造

题意：小美定义一个数组a的权值计算如下：

首先将a的每一对相邻两项求和，得到一个b数组。那么b数组的最大值减最小值即为a数组的权值。

例如，若a=[2,1,3]，那么b=[3,4]，b数组的极差是1。因此a数组的权值为1。

现在小美希望你能构造一个长度为n的排列，满足权值尽可能小。你能帮帮她吗？

排列是指一个长度为n的数组，其中 1 到n每个元素恰好出现一次。

#include
#include
using namespace std;
const int N = 2e5 + 10;
vector<int>ans;
int n;
int main()
{
	cin >> n;
	int h = 1, t = n;
	for (int i = 1; i <= n / 2; i++) {
		ans.push_back(h);
		ans.push_back(t);
		h++;
		t--;
	}
	if (n & 1)ans.push_back(n / 2 + 1);
	for (int x : ans) {
		cout << x << " ";
	}
	return 0;
}

二、小美的好矩阵

题意：

小美定义一个矩阵是好矩阵，当且仅当该矩阵满足：
1. 矩阵仅由'A'、'B'、'C'三种字符组成。且三种字符都出现过。
2. 矩阵相邻的字符都不相等。

现在给定一个n∗m的矩阵，小美想知道有多少个3*3的子矩阵是好矩阵，你能帮帮她吗？

之前口胡的解法真是没眼看😛😛😛

#include
#include
#include
using namespace std;
const int N = 1e3 + 10;
char s[N][N];
int dx[] = { -1,-1,-1,0,0,1,1,1 };
int dy[] = { -1,0,1,-1,1,-1,0,1 };
int n, m;
map<int, int>mp;
bool fun(int x, int y, int a, int b)
{
	char k1 = s[x][y] - 'A' + 1;
	mp[k1]++;
	char k2 = s[a][b] - 'A' + 1;
	mp[k2]++;
	if (s[x][y] == s[a][b])return 1;
	if (s[a][b] != 'A' && s[a][b] != 'B' && s[a][b] != 'C')return 1;
	if (s[x][y] != 'A' && s[x][y] != 'B' && s[x][y] != 'C')return 1;
	return 0;
}
int main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> s[i][j];
		}
	}
	int ans = 0;
	for (int i = 1; i + 2 <= n; i++) {
		for (int j = 1; j + 2 <= m; j++) {
			mp.clear();
			if (fun(i, j, i, j + 1))continue;
			if (fun(i, j, i + 1, j))continue;
			if (fun(i, j + 1, i, j + 2))continue;
			if (fun(i, j + 2, i + 1, j + 2))continue;
			if (fun(i + 1, j, i + 2, j))continue;
			if (fun(i + 2, j, i + 2, j + 1))continue;
			if (fun(i + 2, j + 1, i + 2, j + 2))continue;
			if (fun(i + 2, j + 2, i + 1, j + 2))continue;
			if (fun(i + 1, j + 1, i + 1, j))continue;
			if (fun(i + 1, j + 1, i + 1, j + 2))continue;
			if (fun(i + 1, j + 1, i + 2, j + 1))continue;
			if (fun(i + 1, j + 1, i, j + 1))continue;
			if (mp[1] >= 1 && mp[2] >= 1 && mp[3] >= 1)ans++;
		}
	}
	cout << ans << endl;
	return 0;
}

三、小美的蛋糕切割

题意：

小美有一个矩形的蛋糕，共分成了 n 行 m 列，共 n×m 个区域，每个区域是一个小正方形，已知蛋糕每个区域都有一个美味度。她想切一刀把蛋糕切成两部分，自己吃一部分，小团吃另一部分。

小美希望两个人吃的部分的美味度之和尽可能接近，请你输出∣s1​−s2​∣的最小值。（其中s1​代表小美吃的美味度，s2​代表小团吃的美味度）。

请务必保证，切下来的区域都是完整的，即不能把某个小正方形切成两个小区域。

因为只切一刀 ，切的位置只有（n+m-2)种可能。二维前缀和模拟即可

#include
using namespace std;
typedef long long LL;
const int N = 1e3 + 10;
int a[N][N];
LL s[N][N];
int n, m;
int main()
{
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			cin >> a[i][j];
			s[i][j] = s[i][j - 1] + s[i - 1][j] - s[i - 1][j - 1] + a[i][j];
		}
	}
    //特判只有一个蛋糕
	if (n == 1 && m == 1) { 
		cout << a[1][1] << endl;
		return 0;
	}
	LL ans = 1e9;
	//枚举横
	for (int i = 2; i <= n; i++) {
		LL ans1 = s[i - 1][m];
		LL ans2 = s[n][m] - ans1;
		ans = min(ans, abs(ans1 - ans2));
	}
	//枚举列
	for (int i = 2; i <= m; i++) {
		LL ans1 = s[n][i - 1];
		LL ans2 = s[n][m] - ans1;
		ans = min(ans, abs(ans1 - ans2));
	}
	cout << ans << endl;
	return 0;
}

5555下次不敢口胡了😭😭😭😭