网易雷火 4.22 笔试题解 【仅限于前3题】
事先声明，因为题目3没能在笔试时间内解出。所以个人也只是2题选手而已。【感觉凉了
另外有没有大佬解出了第四题，能交流一下第四题的解法吗？
题目1 消灭敌人数量
数学运算。遍历所有敌人节点，计算当前节点到黑洞中心的距离是否小于等于黑洞半径即可。
最后，返回所有满足条件的节点的总数即可。
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
int main()
{
int N;
double R;
cin >> N >> R;
vector<vector<double>> bodys(N,vector<double>(3,0));
for(int i=0;i<N;i++) cin >> bodys[i][0] >> bodys[i][1] >> bodys[i][2];
double c_x,c_y,c_z;
cin >> c_x >> c_y >> c_z;
int result = 0;
for(int i=0;i<N;i++)
{
double now_len = pow(pow(bodys[i][0] - c_x,2) + pow(bodys[i][1] - c_y,2) + pow(bodys[i][2] - c_z,2),0.5);
if(now_len <= R) result++;
}
cout << result << endl;
return 0;
}
题目2 飞机问题
模拟思路。
其实可以近似看作是操作系统里的PV问题? 具体可以使用懒处理思路：当无人机群返回时，如果当前无人机群前置无人机群还未返回，反正此时返回无人机群所得到的无人机也是处于休眠状态，不如先将其标记，等到前置无人机群都已经返回时再一并处理。同时，还有一点需要注意，虽然题目中没有明确说明，但从对测试案例的测试过程中发现。但返回请求的返回无人机群的操作结束后【在处理派出无人机请求等待队列前】，如果此时条件满足需要进行基地升级，则必须进行基地升级操作。【否则可能导致部分测试用例无法通过】
解题步骤如下【其实可以直接边看代码边看注释，个人自我感觉这题的注释还是写的比较详细的】：
1.构建run_struct结构题存储每一次请求对应的无人机群的相关信息，构建plan_run类用于处理题目逻辑
2.构建 sleep_nums 【但其实个人后续代码未使用】,run_nums,can_nums,total 记录当前基地内关于无人机的各项信息
3.建立 return_wait 队列存储等待返回的无人机群的相关信息，建立 run_wait 队列存储等待请求派遣的无人机群的相关信息，建立id_set 集合存储当前已经请求返回但前置无人机群还未返回的无人机群id。【以便后续懒处理】
4.构建 up_total() 函数以实现基地的升级操作，构建 new_run() 函数及其具体逻辑以实现对派出无人机群请求的操作，建立 now_return() 函数及其具体逻辑以实现对请求无人机群返回指令的操作。
5.构建main()函数内容，以实现格式化输入输出。
#include <iostream>
#include <queue>
#include <vector>
#include <unordered_set>
using namespace std;
typedef struct
{
int nums;
int id;
}run_struct;
class plan_run
{
private:
int sleep_nums = 0; // 当前休眠的无人机数
int run_nums = 0; // 当前正在执行任务的无人机数
int can_nums; // 当前可以使用的无人机数
int total; // 当前等级下，基地的无人机总数
public:
queue<run_struct> run_wait; // 派出无人机请求等待队列
queue<run_struct> return_wait; // 当前派出待返回的无人机的队列
unordered_set<int> id_set; // 目前已经使用指令申请返回的无人机编号集合
// 构造函数
plan_run(int C):total(C){ can_nums = total; };
// 功能函数 返回值均为当前请求后新派出的无人机数目
// 升级
void up_total(int m)
{
total = m;
can_nums = total;
}
// 派出
int new_run(int id,int m)
{
run_struct run_temp;
run_temp.id = id;
run_temp.nums = m;
if(m > total && total == can_nums) this->up_total(m);
if(m <= can_nums)
{
// 执行派遣 将请求放入等待返回队列末尾
can_nums -= m;
run_nums += m;
return_wait.push(run_temp);
return m;
}
else
{
// 当前可用无人机数不足，将请求放入等待队列末尾
run_wait.push(run_temp);
return 0;
}
}
// 返回
int now_return(int id)
{
// 表示当前所要返回的无人机群为最早未返回的无人机群
if(id == return_wait.front().id)
{
run_struct now_temp = return_wait.front();
return_wait.pop();
can_nums += now_temp.nums;
run_nums -= now_temp.nums;
// 如果 已有的请求返回的后续无人机序列编号 不为空 则按时间顺序返回
if(!id_set.empty())
{
while(!id_set.empty() && !return_wait.empty() && id_set.find(return_wait.front().id) != id_set.end())
{
now_temp = return_wait.front();
return_wait.pop();
can_nums += now_temp.nums;
run_nums -= now_temp.nums;
id_set.erase(now_temp.id);
}
}
}
else
{
id_set.insert(id);
}
// 是否需要更新升级 再详细阅读题目后再考虑编写 确认需要升级
if(!run_wait.empty() && can_nums < run_wait.front().nums && can_nums == total) this->up_total(run_wait.front().nums);
// 处理派出请求等待队列
int now_run_nums = 0;
// 只要当前的无人机数超过派出请求等待队列队首的请求数量 则进行派遣
while(!run_wait.empty() && can_nums >= run_wait.front().nums)
{
run_struct now_run_temp;
now_run_temp = run_wait.front();
run_wait.pop();
can_nums -= now_run_temp.nums;
run_nums += now_run_temp.nums;
now_run_nums += now_run_temp.nums;
return_wait.push(now_run_temp);
}
// 返回当前新派出的无人机数量
return now_run_nums;
}
};
int main()
{
int C,N;
cin >> C >> N;
plan_run A(C);
for(int i=0;i<N;i++)
{
int now_id,now_m;
cin >> now_id >> now_m;
if(now_id == -1)
{
cout << A.now_return(now_m) << endl;
}
else
{
cout << A.new_run(now_id,now_m) << endl;
}
}
return 0;
}
题目3 炉石传说 【因为没想到会是输入格式问题导致段错误，导致个人没能在笔试时间内做出来······】
具体考虑回溯思路。
需要注意的是，如果当前敌方存在存活的嘲讽随从，则只针对嘲讽随从进行回溯遍历。而在当前可用随从攻击次数结束之后，在使用亵渎法术时，现存的圣盾可以当成一点额外的生命值处理。同时，如果使用亵渎法术的花费cost超过了8，则这时候直接使用法术B更为合理，具体判断公式即为：min(cost,8);
具体解题过程如下：
1.建立Game_Manager 类来处理游戏逻辑，建立man_struct结构题存储随从数据
2.建立init()函数来通过输入的数据初始化Game_Manager类 M对象
3.建立Attack()和Attack_Down()函数来实现随从攻击对当前游戏状态的变化，以及后续回溯时的状态复原。
4.建立super_A() 函数来实现法术A的递归使用【就是题目中的亵渎法术】
5.编写run_main()和run_Attack()函数来对回溯算法进行整体实现。
6.编写main()函数中内容，进行标准格式化输入输出【个人就是没想到当初段错误是这里的输入错误导致的】
#include <iostream>
#include <vector>
#include <unordered_set>
#include <string>
#include <algorithm>
#include <stdlib.h>
#include <stdio.h>
using namespace std;
// 创建随从结构体 用于保存随从的数据
typedef struct
{
int attack;
int life;
int attack_nums = 0;
int cf = 0;
int sd = 0;
bool sd_used = false;
}man_struct;
// 创建游戏管理员类 通过该类进行游戏交互
class GameManager
{
private:
vector<man_struct> A_man_list; // 玩家A的随从队列
vector<man_struct> B_man_list; // 玩家B的随从队列
public:
// 功能函数
// 随从攻击
void Attack(int id_A,int id_B)
{
if(A_man_list[id_A].sd == 0 || B_man_list[id_B].attack == 0) A_man_list[id_A].life -= B_man_list[id_B].attack;
else
{
A_man_list[id_A].sd = 0;
A_man_list[id_A].sd_used = true;
}
if(B_man_list[id_B].sd == 0 || A_man_list[id_A].attack == 0) B_man_list[id_B].life -= A_man_list[id_A].attack;
else
{
B_man_list[id_B].sd = 0;
B_man_list[id_B].sd_used = true;
}
A_man_list[id_A].attack_nums++;
B_man_list[id_B].attack_nums++;
}
void Attack_Down(int id_A,int id_B)
{
// 当当前随从的被打击数不为1时，证明不是这一次导致的圣盾消失，故只回溯生命状态
if(A_man_list[id_A].sd_used == true && A_man_list[id_A].attack_nums == 1)
{
A_man_list[id_A].sd = 1;
A_man_list[id_A].sd_used = false;
}
else A_man_list[id_A].life += B_man_list[id_B].attack;
if(B_man_list[id_B].sd_used == true && B_man_list[id_B].attack_nums == 1)
{
B_man_list[id_B].sd = 1;
B_man_list[id_B].sd_used = false;
}
else B_man_list[id_B].life += A_man_list[id_A].attack;
A_man_list[id_A].attack_nums--;
B_man_list[id_B].attack_nums--;
}
// 法术A
void super_A(vector<int>& now_lifes)
{
int now_dead = 0;
for(int i=0;i<now_lifes.size();i++)
{
if(now_lifes[i] > 0)
{
now_lifes[i]--;
if(now_lifes[i] <= 0) now_dead++;
}
}
if(now_dead > 0) super_A(now_lifes);
}
int sum_list(vector<int>& nums)
{
int sum = 0;
for(int i=0;i<nums.size();i++) sum += nums[i];
return sum;
}
//寻找当前最优解 回溯
int run_Attack(int do_max,int now_do,vector<int>& used)
{
int cost = 0;
vector<int> now_lifes;
// 计算当前使用法术的费用情况
// 同时，对于某些特殊的情况 不一定当前的随从全部攻击完后，其结果就最优，故在此对每一次回溯均进行一次法术消耗的测试
for(int i=0;i<A_man_list.size();i++)
{
if(A_man_list[i].life > 0) now_lifes.push_back(A_man_list[i].life + A_man_list[i].sd);
}
for(int i=0;i<B_man_list.size();i++)
{
if(B_man_list[i].life > 0) now_lifes.push_back(B_man_list[i].life + B_man_list[i].sd);
}
while(sum_list(now_lifes) != 0)
{
super_A(now_lifes);
cost += 2;
// 当cost超过8时 此时无需再进行后续处理 直接使用法术B【cost 8】即可 也可以在 while 中判断
if(cost >= 8) break;
}
// 当攻击次数超过限制 仅考虑使用法术的情况
if(now_do >= do_max)
{
return min(cost,8);
}
// 还可以攻击时
int result = min(cost,8);
for(int i=0;i<B_man_list.size();i++)
{
if(used[i] == 1) continue;
used[i] = 1;
vector<int> cf_list;
for(int j=0;j<A_man_list.size();j++)
{
if(A_man_list[j].life > 0 && A_man_list[j].cf == 1) cf_list.push_back(j);
}
if(!cf_list.empty())
{
for(int j = 0;j<cf_list.size();j++)
{
this->Attack(cf_list[j],i);
result = min(result,this->run_Attack(do_max,now_do + 1,used));
this->Attack_Down(cf_list[j],i);
}
}
else
{
for(int j=0;j<A_man_list.size();j++)
{
if(A_man_list[j].life <= 0) continue;
this->Attack(j,i);
result = min(result,this->run_Attack(do_max,now_do + 1,used));
this->Attack_Down(j,i);
}
}
used[i] = 0;
}
return result;
}
// 运行主函数
int run_main()
{
vector<int> used(B_man_list.size(),0);
int m = B_man_list.size();
return run_Attack(min(2,m),0,used);
}
// init
void init(int nums_A,string str_A,int nums_B,string str_B)
{
int now_A = 0,now_B = 0;
while(nums_A--)
{
man_struct temp;
while(str_A[now_A] != ' ')
{
if(str_A[now_A] == '(')
{
temp.sd = 1;
}
else if(str_A[now_A] <= '9' && str_A[now_A] >= '0')
{
int now_nums = 0;
if(str_A[now_A] == '1' && now_A+1 < str_A.length()-1 && str_A[now_A + 1] =='0')
{
now_nums = 10;
}
else now_nums = str_A[now_A] - '0';
if(now_A >0 && str_A[now_A - 1] == '/')
{
temp.life = now_nums;
}
else temp.attack = now_nums;
if(now_nums == 10) now_A++;
}
else if(str_A[now_A] == '!') temp.cf = 1;
now_A++;
}
now_A++;
//temp.total_life = temp.life;
A_man_list.push_back(temp);
}
while(nums_B--)
{
man_struct temp;
while(str_B[now_B] != ' ')
{
if(str_B[now_B] == '(')
{
temp.sd = 1;
}
else if(str_B[now_B] <= '9' && str_B[now_B] >= '0')
{
int now_nums = 0;
if(str_B[now_B] == '1' && now_B+1 < str_B.length()-1 && str_B[now_B + 1] =='0')
{
now_nums = 10;
}
else now_nums = str_B[now_B] - '0';
if(now_B >0 && str_B[now_B - 1] == '/')
{
temp.life = now_nums;
}
else temp.attack = now_nums;
if(now_nums == 10) now_B++;
}
else if(str_B[now_B] == '!') temp.cf = 1;
now_B++;
}
now_B++;
//temp.total_life = temp.life;
B_man_list.push_back(temp);
}
}
};
int main()
{
// 策略判断 因为是寻求cost花费最小 故优先使用随从攻击敌方随从 而后使用法术A 如果法术A使用四次以上 则直接使用法术B 单回合最大花销不会超过8
int N;
cin >> N;
while(N--)
{
int nums_A,nums_B;
string str_A = "",str_B = "";
cin >> nums_A;
for(int i=0;i<nums_A;i++)
{
string temp;
cin >> temp;
str_A += temp + ' ';
}
cin >> nums_B;
for(int i=0;i<nums_B;i++)
{
string temp;
cin >> temp;
str_B += temp + ' ';
}
// 格式化输入测试 如有需要自行取消注释
// cout << "str_A: " << str_A << endl;
// cout << "str_B: " << str_B << endl;
GameManager M;
M.init(nums_A,str_A,nums_B,str_B);
cout << M.run_main() << endl;
}
return 0;
}
#网易雷火后端笔试4.22##网易雷火##网易信息集散地##网易雷火游戏笔试#
