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]);
}
}
太烦了