网易雷火 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;
}