小红书8月30日算法岗笔试编程题
1、小红书订餐（AC）
给定每种餐的份数，每人最多只能订一份餐，并且可以预定与取消；问输入列表中每人预定或者取消的操作是否成功。
#include<iostream>
#include<algorithm>
#include<string>
#include<map>
#include<vector>
using namespace std;
int main() {
int n, m; cin >> n >> m;
map<string, int> food;
string x;
int y;
for (int i = 0; i < n; i++) {
cin >> x >> y;
food[x] = y;
}
map<string, string> record;
string a, b, c;
while (cin >> a >> b >> c) {
if (b == "release") {
if (record[a] == c) {
record[a] = "";
food[c]++;
cout << "yes" << endl;
} else {
cout << "no" << endl;
}
} else {
if (record[a] == "" && food[c] > 0) {
record[a] = c;
food[c]--;
cout << "yes" << endl;
} else {
cout << "no" << endl;
}
}
}
return 0;
} 2、奖励金币（AC）
从 n 个宝箱中随机选 k 个，问已选 k 个宝箱中金币之和是质数的方案有多少种。
#include<iostream>
#include<algorithm>
#include<string>
#include<map>
#include<vector>
using namespace std;
int result = 0;
bool isZhiShu(long long x) {
if (x < 2) {
return false;
}
long long R = sqrt(x);
for (int d = 2; d <= R; d++) {
if (x % d == 0) {
return false;
}
}
return true;
}
void backtrack(vector<int> &A, int i, int cont, long long sum, int k) {
if (cont == k) {
if (isZhiShu(sum)) {
result++;
}
return;
}
if (i == A.size()) {
return;
}
backtrack(A, i + 1, cont + 1, sum + A[i], k);
backtrack(A, i + 1, cont, sum, k);
}
int main() {
int n, k; cin >> n >> k;
vector<int> A(n);
for (int i = 0; i < n; i++) {
cin >> A[i];
}
backtrack(A, 0, 0, 0, k);
cout << result << endl;
return 0;
} 3、宝箱金币（通过55%，TLE）
有一个 n 行 m 列的二维宝箱矩阵，每个宝箱中有一些金币；从中任选 r 行 c 列，组成新的矩阵，求该矩阵中相邻（上下左右四个方向相邻）宝箱中金币差的和的最小值。#include<iostream>
#include<algorithm>
#include<string>
#include<map>
#include<vector>
using namespace std;
int result = 0x7FFFFFFF;
int cal_dis_sum(vector<vector<int>> &select, int r, int c) {
int dis_sum = 0;
for (int i = 0; i < r; i++) {
for (int j = 0; j < c - 1; j++) {
dis_sum += abs(select[i][j] - select[i][j + 1]);
}
}
for (int j = 0; j < c; j++) {
for (int i = 0; i < r - 1; i++) {
dis_sum += abs(select[i][j] - select[i + 1][j]);
}
}
return dis_sum;
}
vector<vector<int>> rows, cols;
void select_rows(int cur, int cont, int r, int n, vector<int> temp) {
if (cont == r) {
rows.push_back(temp);
return;
}
if (cur == n) {
return;
}
temp.push_back(cur);
select_rows(cur + 1, cont + 1, r, n, temp);
temp.pop_back();
select_rows(cur + 1, cont, r, n, temp);
}
void select_cols(int cur, int cont, int c, int m, vector<int> temp) {
if (cont == c) {
cols.push_back(temp);
return;
}
if (cur == m) {
return;
}
temp.push_back(cur);
select_cols(cur + 1, cont + 1, c, m, temp);
temp.pop_back();
select_cols(cur + 1, cont, c, m, temp);
}
int main() {
int n, m, r, c; cin >> n >> m >> r >> c;
vector<vector<int>> record(n, vector<int>(m));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cin >> record[i][j];
}
}
vector<int> temp_rows, temp_cols;
select_rows(0, 0, r, n, temp_rows);
select_cols(0, 0, c, m, temp_cols);
for (int i = 0; i < rows.size(); i++) {
for (int j = 0; j < cols.size(); j++) {
vector<vector<int>> select_res(r, vector<int>(c));
int start_i = 0;
for (int i_each = 0; i_each < r; i_each++) {
int start_j = 0;
for (int j_each = 0; j_each < c; j_each++) {
select_res[start_i][start_j] = record[rows[i][i_each]][cols[j][j_each]];
start_j++;
}
start_i++;
}
int dis_sum_temp = cal_dis_sum(select_res, r, c);
result = min(result, dis_sum_temp);
}
}
cout << result << endl;
return 0;
} 
