编程
一、最大乘积
描述：
给定一个无序数组，包含正数、负数和 0 0 0，要求从中找出 3 3 3 个数的乘积，使得乘积最大，要求时间复杂度： O ( n ) O(n) O(n)，空间复杂度：$O(1) $
输入描述:
无序整数数组 A [ n ] A[n] A[n]
输出描述:
满足条件的最大乘积
输入样例:
3 4 1 2
输出样例:
24
题解：
这个题出的太不走心，输入描述有够烂的，数据范围也没有，完全是教科书式的出题习惯。
在线处理，因为不知道数据范围并且空间复杂度要求 O ( 1 ) O(1) O(1)，一边输入一边处理，处理出来数列中前三大和前三小的数，然后比较 m a x 1 ∗ m a x 2 ∗ m a x 3 max1 * max2 * max3 max1∗max2∗max3 和 m i n 1 ∗ m i n 2 ∗ m a x 1 min1 * min2 * max1 min1∗min2∗max1，输出大的即可，注意数据溢出。
尽管上面考虑的地方已经足够 A C AC AC，但是并不能说明代码是完全正确的，因为我们还要考虑很多奇怪的地方，例如 n < 3 n < 3 n<3 的情况，还有无法凑够上述两个式子的情况。
这里提供两个代码，均已 A C AC AC，第二个代码考虑到了各种奇怪的情况。
代码 A A A：
#include <bits/stdc++.h>
using namespace std;
int A, n;
int max1, max2, max3;
int min1, min2;
void check_max(int x)
{
if (x > max1)
{
swap(x, max1);
}
if (x > max2)
{
swap(x, max2);
}
if (x > max3)
{
swap(x, max3);
}
}
void check_min(int x)
{
if (x < min1)
{
swap(x, min1);
}
if (x < min2)
{
swap(x, min2);
}
}
int main()
{
max1 = max2 = max3 = 0;
min1 = min2 = 0;
cin >> n;
while (n--)
{
cin >> A;
check_max(A);
check_min(A);
}
long long ans1 = 1LL * max1 * max2 * max3;
long long ans2 = 1LL * min1 * min2 * max1;
if (ans1 > ans2)
{
cout << ans1 << '\n';
}
else
{
cout << ans2 << '\n';
}
return 0;
}
代码 B B B：
#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
int A, n;
int max1, max2, max3;
int min1, min2;
int max_neg1, max_neg2, max_neg3;
void check_max(int x)
{
if (x > max1)
{
swap(x, max1);
}
if (x > max2)
{
swap(x, max2);
}
if (x > max3)
{
swap(x, max3);
}
}
void check_min(int x)
{
if (x < min1)
{
swap(x, min1);
}
if (x < min2)
{
swap(x, min2);
}
}
void check_max_neg(int x)
{
if (x > max_neg1)
{
swap(x, max_neg1);
}
if (x > max_neg2)
{
swap(x, max_neg2);
}
if (x > max_neg3)
{
swap(x, max_neg3);
}
}
int main()
{
max1 = max2 = max3 = 0;
min1 = min2 = 0;
max_neg1 = max_neg2 = max_neg3 = -INF;
cin >> n;
if (n < 3)
{
cout << "我也不知道该输出啥" << '\n';
return 0;
}
int t = n;
int cnt_pos = 0, cnt_neg = 0;
while (t--)
{
cin >> A;
if (A < 0)
{
cnt_neg++;
check_min(A);
check_max_neg(A);
}
else if (A > 0)
{
cnt_pos++;
check_max(A);
}
}
if (cnt_pos == 0)
{
if (cnt_neg < n)
{
cout << 0 << '\n';
}
else
{
cout << max_neg1 * max_neg2 * max_neg3 << '\n';
}
}
else if (cnt_pos == 1)
{
if (cnt_neg < 2)
{
cout << 0 << '\n';
}
else
{
cout << min1 * min2 * max1 << '\n';
}
}
else if (cnt_pos == 2)
{
if (cnt_neg < 2)
{
if (cnt_neg + cnt_pos < n)
{
cout << 0 << '\n';
}
else
{
cout << min1 * max1 * max2 << '\n';
}
}
else
{
cout << min1 * min2 * max1 << '\n';
}
}
else
{
long long ans1 = 1LL * max1 * max2 * max3;
long long ans2 = 1LL * min1 * min2 * max1;
if (ans1 > ans2)
{
cout << ans1 << '\n';
}
else
{
cout << ans2 << '\n';
}
}
return 0;
}
二、大整数相乘
描述：
有两个用字符串表示的非常大的大整数,算出他们的乘积，也是用字符串表示。不能用系统自带的大整数类型。
输入描述：
空格分隔的两个字符串，代表输入的两个大整数
输出描述：
输入的乘积，用字符串表示
输入样例：
72106547548473106236 72106547548473106236 72106547548473106236 982161082972751393 982161082972751393 982161082972751393
输出样例：
70820244829634538040848656466105986748 70820244829634538040848656466105986748 70820244829634538040848656466105986748
题解：
这个题是一个模版题，有十分简单的写法，就是模拟乘法运算，也有比较高级的解法，用到快速傅里叶变换，但是对于这种机试没必要用快速傅立叶，因为这个真的很容易写错，代码不是特别容易记，如果说这种机试和比赛一样，可以带模版，那么两种随便哪个都好。
代码：
#include <stdio.h>
#include <string.h>
#define _MAX 1001
// 递归进位函数
void Carrying(int tag,int i,int j,int *p)
{
p[i+j]+=tag;
if (p[i+j]>9)
{
tag=p[i+j]/10;
p[i+j] %=10;
Carrying(tag, i+1, j, p); // 写成Carrying(tag, i, j+1, p);也成立，为了让i+j递增而已
}
return ;
}
int main(int argc, const char * argv[])
{
int product[2 * _MAX],i=0,j=0,numOneLen,numTwoLen,tag;
char numOne[_MAX],numTwo[_MAX];
memset(product, 0, sizeof(int) * 2 * _MAX); // 初始化product数据为0
scanf("%s%s",numOne,numTwo); // 存数据
numOneLen=(int)strlen(numOne);
numTwoLen=(int)strlen(numTwo);
// 数据逆序
for (i=0; i<numOneLen/2; i++)
{
tag=numOne[i];
numOne[i]=numOne[numOneLen-1-i];
numOne[numOneLen-1-i]=tag;
}
for (i=0; i<numTwoLen/2; i++)
{
tag=numTwo[i];
numTwo[i]=numTwo[numTwoLen-1-i];
numTwo[numTwoLen-1-i]=tag;
}
// 逐位相乘
for (i=0; i<numOneLen; i++)
{
for (j=0; j<numTwoLen; j++)
{
tag=((int)numOne[i]-48)*((int)numTwo[j]-48);
Carrying(tag, i, j, product); // 递归
}
}
// 倒序输出结果
for (i=_MAX * 2 - 1; i>0; i--)
{
if (product[i]!=0)
{
break; // 查找到第一个不等于0的跳出
}
}
for (j=i; j>=0; j--)
{
printf("%d",product[j]);
}
printf("\n");
return 0;
}
三、六一儿童节
描述：
六一儿童节，老师带了很多好吃的巧克力到幼儿园。每块巧克力 j j j 的重量为 w [ j ] w[j] w[j]，对于每个小朋友 i i i，当他分到的巧克力大小达到 h [ i ] h[i] h[i] (即 w [ j ] > = h [ i ] w[j]>=h[i] w[j]>=h[i])，他才会上去表演节目。老师的目标是将巧克力分发给孩子们，使得最多的小孩上台表演。可以保证每个 w [ i ] > 0 w[i]> 0 w[i]>0 且不能将多块巧克力分给一个孩子或将一块分给多个孩子。
输入描述：
第一行： n n n，表示 h h h 数组元素个数
第二行： n n n 个 h h h 数组元素
第三行： m m m，表示 w w w 数组元素个数
第四行： m m m 个 w w w 数组元素
输出描述：
上台表演学生人数
输入样例：
3 3 3
2 2 3 2\ 2\ 3 2 2 3
2 2 2
3 1 3\ 1 3 1
输出样例：
1 1 1
题解：
贪心问题，首先对数据进行排序，然后遍历 w [ ] w[] w[] 给 h [ ] h[] h[] 分配，一直到巧克力遍历完或者人手一个巧克力为止。
####代码：
#include <bits/stdc++.h>
using namespace std;
int n, m;
vector<int> h, w;
int main()
{
int x;
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> x;
h.push_back(x);
}
cin >> m;
for (int i = 0; i < m; i++)
{
cin >> x;
w.push_back(x);
}
sort(h.begin(), h.end());
sort(w.begin(), w.end());
int cnt = 0;
int i = 0, j = 0;
while (i < n && j < m)
{
if (h[i] <= w[j])
{
cnt++;
i++;
j++;
}
else
{
j++;
}
}
cout << cnt << endl;
return 0;
}
四、迷宫寻路
描述：
假设一个探险家被困在了地底的迷宫之中，要从当前位置开始找到一条通往迷宫出口的路径。迷宫可以用一个二维矩阵组成，有的部分是墙，有的部分是路。迷宫之中有的路上还有门，每扇门都在迷宫的某个地方有与之匹配的钥匙，只有先拿到钥匙才能打开门。请设计一个算法，帮助探险家找到脱困的最短路径。如前所述，迷宫是通过一个二维矩阵表示的，每个元素的值的含义如下 0 − 0- 0− 墙， 1 − 1- 1− 路， 2 − 2- 2− 探险家的起始位置， 3 − 3- 3− 迷宫的出口，大写字母 − - −门，小写字母 − - − 对应大写字母所代表的门的钥匙
输入描述：
迷宫的地图，用二维矩阵表示。第一行是表示矩阵的行数和列数 M M M 和 N N N
后面的 M M M 行是矩阵的数据，每一行对应与矩阵的一行（中间没有空格）。 M M M 和 N N N 都不超过 100 100 100, 门不超过 10 10 10 扇。
输出描述：
路径的长度，是一个整数
输入样例：
5 5 5\ 5 5 5
02111 02111 02111
01 a 0 A 01a0A 01a0A
01003 01003 01003
01001 01001 01001
01111 01111 01111
输出样例：
7
####题解：
查找二维矩阵迷宫最短路径一般可以使用 b f s bfs bfs 来解，但是这里存在一个问题就是找钥匙，如果没有钥匙时，最短路径一定是不含有重复经过的格点，但是这里因为要找钥匙，所以可能存在重复经过的格点，这样我们不能单纯记录某一个点是否到达过，而应该记录下来在当前钥匙持有情况下到达的点的情况。
此时，我们应该考虑，如何表示钥匙持有状态呢？
题目中告诉我们钥匙最多有十把，那么我们钥匙的状态数不会超过 2 10 2^{10} 210，所以我们可以采用二进制位来表示钥匙的状态。 0000000000 0000000000 0000000000，表示一把钥匙都没有，也是初始状态， 111111111 111111111 111111111 ，表示持有十把钥匙，也就是说，当最低位二进制位为 0 0 0 时，说明我们没有 A A A 的钥匙 a a a，如果为 1 1 1，则说明我们有。
所以我们定义 b o o k [ i ] [ j ] [ k ] book[i][j][k] book[i][j][k] 表示在钥匙持有状态为 k k k 的时候是否到达过第 i i i 行 j j j 列的格子。
所以这个题我们直接从起点开始 b f s bfs bfs 即可，用 b o o k [ i ] [ j ] [ k ] book[i][j][k] book[i][j][k] 来表示抵达状态，找到出口为止，准确的来说，这个题应该算是有重复路径的最短路径查找，这种题一般都是增加一个维度来表示状态，而这个增加的维度多数都是使用二进制来表示状态的。
代码：
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 111;
const int MAXM = 1111;
const int DIR[4][2] = {0, 1, 0, -1, 1, 0, -1, 0};
int N, M;
char G[MAXN][MAXN];
bool book[MAXN][MAXN][MAXM];
struct node
{
int x, y, k, step;
node(int x, int y, int k, int step) : x(x), y(y), k(k), step(step) {}
};
int bfs(int sX, int sY)
{
queue<node> Q;
Q.push(node(sX, sY, 0, 0));
while (!Q.empty())
{
node head = Q.front();
Q.pop();
if (G[head.x][head.y] == '3')
{
return head.step;
}
for (int i = 0; i < 4; i++)
{
int nx = head.x + DIR[i][0];
int ny = head.y + DIR[i][1];
if (nx >= N || nx < 0 || ny >= M || ny < 0 || G[nx][ny] == '0')
{
continue;
}
int key = head.k;
if ('a'<= G[nx][ny] && G[nx][ny] <= 'z')
{
key = key | (1 << (G[nx][ny] - 'a'));
}
if ('A' <= G[nx][ny] && G[nx][ny] <= 'Z' && (key & (1 << (G[nx][ny] - 'A'))) == 0)
{
continue;
}
if (!book[nx][ny][key])
{
book[nx][ny][key] = 1;
Q.push(node(nx, ny, key, head.step + 1));
}
}
}
return -1;
}
int main()
{
scanf("%d%d", &N, &M);
for (int i = 0; i < N; i++)
{
scanf("%s", G[i]);
}
memset(book, 0, sizeof(book));
int flag = 0;
for (int i = 0; i < N; i++)
{
if (flag == 1)
{
break;
}
for (int j = 0; j < M; j++)
{
if (G[i][j] == '2')
{
flag = 1;
book[i][j][0] = 1;
printf("%d\n", bfs(i, j));
break;
}
}
}
return 0;
}
京公网安备 11010502036488号