2024-3-30 网易雷火笔试题题解(A~C)

一小时写了A~C 剩下两小时没调出D的最后D还是0分

A

题目描述

网易在从两年前开始对司龄1，3，6，10年的员工发纪念积木，今年决定补发以前没有补发的积木，问还各个类型的积木需要多少个

输入描述：

第一行输入一个N （1<=N<=10000）,表示雷火的员工数量。

接下来一行是N个整数(1<=司龄<=20)，表示每个员工今年达到的司龄。

思路:

暴力特判前两年有没有发过那几个奖品

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;

#define _for(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
int cnt[4];
int main(void)
{
    int n;
    scanf("%d",&n);
    _for(i,1,n)
    {
        int x;
        scanf("%d",&x);
        if(x>=1) cnt[0]++;
        if(x>=3) cnt[1]++;
        if(x>=6) cnt[2]++;
        if(x>=10) cnt[3]++;
        if(x-1==1) cnt[0]--;
        if(x-1==3) cnt[1]--;
        if(x-1==6) cnt[2]--;
        if(x-1==10) cnt[3]--;
        if(x-2==1) cnt[0]--;
        if(x-2==3) cnt[1]--;
        if(x-2==6) cnt[2]--;
        if(x-2==10) cnt[3]--;
    }
    _for(i,0,3) printf("%d ",cnt[i]);
}

B:(O(NlogN)解法)

题目描述：

初始有一个长度为1的文本，我们可以采用Ctrl A全选文本，Ctrl S选中单个文本，Ctrl C复制文本,Ctrl V粘贴文本，问给n个k，对于每个k得到一个长度为k的文本至少需要多少次。

思路：

当我们得到一个长度为x的串后，我们可以通过该串全选一次，复制一次，然后粘贴若干次后，去更新其他值（该部分时间复杂度与欧拉常数有关，总体复杂度为O(nlogn)），也可以通过该数字，选中单个文本一次，复制一次，粘贴若干次，去更新其他值(由于更新条件是dp[r]-dp[l]>r-l+2，因此可以构造val[x]=dp[x]-x，因此，我们可以维护val[x]的最小值mn，当val[i]>mn+2时，我们可以将dp[i]更新为mn+2+i，由于对于数组每个元素，可以O(1)求解，该部分的时间复杂度为O(n))。综上，总体复杂度为O(n)，（复杂度中与n表示数据范围）

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;

#define _for(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
const int lim=16384;
int dp[lim];
int val[lim];
inline void funct()
{
    memset(dp,1,sizeof(dp));
    dp[1]=0;
    int mn=1000000000;
    for(int i=1;i<lim;i++)
    {
        dp[i]=min(dp[i],mn+2+i);
        val[i]=dp[i]-i;
        mn=min(val[i],mn);
        for(int j=i+i,cnt=3;j<lim;j+=i,++cnt)
        {
            dp[j]=min(dp[i]+cnt,dp[j]);
        }
    }
}
int main(void)
{
    int T;
    scanf("%d",&T);
    funct();
    // _for(i,1,16) printf("%d: %d\n",i,dp[i]);
    while(T--)
    {
        int x;
        scanf("%d",&x);
        printf("%d\n",dp[x]);
    }
}

C

题目简述：

有一个战斗力为p的玩家，以及一个n个怪物（怪物按战斗力正序输入），m个BOSS，可以耗费1cost，击败一个战斗力小于自己的非BOSS怪物，然后获得该怪物的战斗力，也可以耗费1cost,使得自己的战斗加上p/10，问，对于每个BOSS，如果需要击败该BOSS，需要消耗几cost

思路：

将能打过的所有怪物存入优先队列中，每次战斗力更新后，是否有新增可打败怪物，倘若有则更新可以战胜怪物列表。给BOSS存入优先队列（小根堆）中，当队列顶的BOSS不能打败时，考虑如何提升战斗力，为了使提升的战斗力最大化，我们可以看可战胜怪物中战斗力最高的怪物与p/10谁大，去决定打怪物还是让自己战斗加上p/10。直到所有BOSS的结果都计算出为止

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
using namespace std;

#define _for(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)

#define MAXN 100050
int monster[MAXN];
int ans[MAXN];
class node
{
public:
    int request,id,ans;
    node(int _request,int _id)
    {
        request=_request;
        id=_id;
        ans=0;
    }
    bool operator <(const node& b)const&
    {
        return b.request<request;
    }
};
priority_queue<node> BOSS_queue;
priority_queue<int> monster_queue;
int p,n,m;
inline void update_monster_queue(int &place,int x)
{
    for(place;place<=n&&monster[place]<x;place++)
    {
        monster_queue.push(monster[place]);
    }
}
int main(void)
{
    scanf("%d%d%d",&p,&n,&m);
    
    _for(i,1,n)
    {
        scanf("%d",&monster[i]);
    }
    _for(i,1,m)
    {
        int x;
        scanf("%d",&x);
        BOSS_queue.push(node(x+1,i));
    }
    int place=1;
    int cnt=0;
    update_monster_queue(place,p);
    while(!BOSS_queue.empty())
    {
        node now_BOSS=BOSS_queue.top();
        printf("%d %d\n",now_BOSS.id,now_BOSS.request);
        while(p<now_BOSS.request)
        {
            ++cnt;
            if(!monster_queue.empty()&&monster_queue.top()>p/10)
            {
                p+=monster_queue.top();
                monster_queue.pop();
            }
            else
            {
                p+=p/10;
            }
            update_monster_queue(place,p);
        }
        ans[now_BOSS.id]=cnt;
        BOSS_queue.pop();
    }
    _for(i,1,m)
    {
        printf("%d\n",ans[i]);
    }
}