ps：没有答案，考场上的代码，不一定对，大佬们轻喷，可以提供点更好的思路~
试题C：训练士兵
解题思路
对于每次训练，需要考虑采用士兵单独训练还是组团训练的方式，故每次训练将所需训练次数大于0的士兵花费进行求和，与组团训练进行比较，以此判断是否要采用组团训练的方式
代码
#include<bits/stdc++.h>
#include<unordered_map>
#include<unordered_set>
#define ll long long
using namespace std;
int N, S;
int main() {
cin >> N >> S;
int n = N;
vector<int> p; //成本
vector<int> c; //次数
while (n--) {
int pi, ci;
cin >> pi >> ci;
p.push_back(pi);
c.push_back(ci);
}
int sum = 0;
while (1) {
int flag = 1;
int consume = 0;
for (int i = 0; i < c.size(); i++) {
if (c[i] > 0)
{
consume += p[i];
c[i]--;
flag = 0;
}
}
sum += min(consume, S);
if (flag) break;
}
cout << sum;
return 0;
}试题D：团建
解题思路
对于该题，考虑层序遍历，先将树的孩子用vector容器进行存储，因题目说明每棵树不会有节点的值重复，故进行层序遍历，判断树的每层是否有相同结点值，以此判断最长公共前缀
代码
#include<bits/stdc++.h>
#include<unordered_map>
#include<unordered_set>
#define ll long long
using namespace std;
const int T = 200000;
vector<vector<int>> tree1(T);
vector<vector<int>> tree2(T);
vector<int> nums1(T);
vector<int> nums2(T);
int N, M;
int get() {
int sum = 0;
int t1 = 1, t2 = 1;
if (nums1[1] == nums2[1]) sum++;
else return 0;
while (1) {
int i, j;
int flag = 1;
if (tree1[t1].size() == 0 || tree2[t2].size() == 0) break;
for (i = 0; i < tree1[t1].size(); i++) {
for (j = 0; j < tree2[t2].size(); j++) {
if (nums1[tree1[t1][i]] == nums2[tree2[t2][j]]) //寻找公共前缀
{
flag = 0;
t1 = tree1[t1][i];
t2 = tree2[t2][j]; //选取下一层的父节点
sum++;
break;
}
}
}
if (flag) break;
}
return sum;
}
int main() {
cin >> N >> M;
int n = N, m = M;
int temp;
while (n--) {
cin >> temp;
nums1[N - n] = temp;
}
while (m--) {
cin >> temp;
nums2[M - m] = temp;
}
n = N - 1; m = M - 1;
int t1, t2;
while (n--) {
cin >> t1 >> t2;
tree1[min(t1, t2)].push_back(max(t1, t2));
}
while (m--) {
cin >> t1 >> t2;
tree2[min(t1, t2)].push_back(max(t1, t2)); //存储每个节点的孩子
}
cout << get();
return 0;
}试题E: 成绩统计
解题思路
对于该题，考虑动态规划解法，先取前k个人的成绩计算其方差，并将成绩记录在数组中，记录当前均值，设小蓝已检查前i-1个人的成绩，若方差依然大于T，找出离均值最远的一个成绩，若第i个人的成绩距离当前均值更近，则剔除离均值较远的成绩，使得方差变小，若遍历完整个数组均找不到更小的方差，返回-1
代码
#include<bits/stdc++.h>
#include<unordered_map>
#include<unordered_set>
#define ll long long
using namespace std;
vector<double> t;
vector<double> nums;
int N, k, T;
bool calculate0() { //判断方差是否小于指定值
double e;
double sum = 0;
for (auto num : t) {
sum += num;
}
e = sum / k;
double val = 0;
for (auto num : t) {
val += (num - e) * (num - e);
}
val /= k;
if (val < T) return true;
else return false;
}
int main() {
cin >> N >> k >> T;
int n = N;
while (n--) {
double temp;
cin >> temp;
nums.push_back(temp);
}
if (N < k) { cout << -1; return 0; }
double mean = 0;
for (int i = 0; i < k; i++) {
t.push_back(nums[i]);
mean += nums[i];
}
mean /= k;
if (calculate0()) { cout << k; return 0; }
for (int length = k; length < nums.size(); length++) {
double sub = 0;
int x = -1;
for (int i = 0; i < t.size(); i++) {
if (abs(t[i] - mean) > sub) {
sub = abs(t[i] - mean);
x = i;
}
}
if (x != -1 && sub > abs(nums[length] - mean)) //判断是否更接近均值
t[x] = nums[length];
if (calculate0()) { cout << length + 1; return 0; }
}
cout << -1;
return 0;
}试题F：因数计数
解题思路
循环遍历数组，判断因数找出所有的有序二元组对，并用集合进行存储，遍历集合，以i,j,k,l互不相等为条件，生成有序四元组，计算四元组个数
代码
#include<bits/stdc++.h>
#include<unordered_map>
#include<unordered_set>
#define ll long long
using namespace std;
set<pair<int, int>> s;
int main() {
int N;
cin >> N;
vector<int> nums;
while (N--) {
int temp;
cin >> temp;
nums.push_back(temp);
}
for (int i = 0; i < nums.size(); i++) {
for (int j = i + 1; j < nums.size(); j++) {
if (nums[i] % nums[j] == 0)
s.insert({ j + 1,i + 1 });
if(nums[j] % nums[i] == 0)
s.insert({ i + 1,j + 1 }); //判断ai和aj是否为对方的因数
}
}
int sum = 0;
for (auto t1 : s) {
for (auto t2 : s) {
if (t1.first != t2.first && t1.first != t2.second && t1.second != t2.first && t1.second != t2.second)
sum++;
}
}
cout << sum;
return 0;
}试题G：零食采购
解题思路
该题是一道图论问题，目的是寻找最短路径下能采购到的零食总数，故先利用矩阵生成无向连通图，再采用深度优先遍历，存储两点之间的所有路径，再判断哪条最短路径，在最短路径下模拟零食采购，用集合存储零食种类，集合大小即为所求零食种类数
代码
#include<bits/stdc++.h>
#include<unordered_map>
#include<unordered_set>
#define ll long long
using namespace std;
int N, q;
vector<int> type;
vector<int> temp;
void dfs(int b, int e,vector<vector<int>>& line,vector<vector<int>> matrix,int length) {
if (b == e) { line.push_back(temp); return; }
if (length > N) return;
for (int i = 0; i < matrix[b].size();i++) {
if (matrix[b][i] == 1) {
temp.push_back(i); //将当前节点加入路径中
dfs(i, e, line, matrix,length+1);
temp.pop_back();
}
}
return;
}
int main() {
cin >> N >> q;
vector<int> t(N, 0);
vector<vector<int>> matrix(N, t);
int n = N;
while (n--) {
int temp;
cin >> temp;
type.push_back(temp);
}
n = N - 1;
while (n--) {
int i, j;
cin >> i >> j;
matrix[i - 1][j - 1] = 1;
matrix[j - 1][i - 1] = 1; //生成无向连通图
}
while (q--) {
int begin0, end0;
cin >> begin0 >> end0;
vector<vector<int>> line;
dfs(begin0 - 1, end0 - 1, line,matrix,0);
int minlength = line[0].size();
int f = 0;
for (int i = 0; i < line.size(); i++)
{
if (line[i].size() < minlength) {
f = i;
minlength = line[i].size(); //寻找最短路径
}
}
set<int> s;
s.insert(type[begin0 - 1]);
for (auto x : line[f]) {
s.insert(type[x]); //模拟零食采购
}
cout << s.size();
}
return 0;
}
