HRBU 2021暑期训练解题报告Day1
目录
A - Stack
B - Queue
C - Shaolin
D - Equal Sums
E - Potions (Hard Version)
F - Buy and Resell
G - 度度熊学队列
A - Stack
题意：
逆波兰表示法是一种将运算符写在操作数后面的描述程序（ 算式）的方法。
举个例子，我们平常用中缀表示法描述的算式（ 1 + 2 ) * ( 5 + 4 )，
改为逆波兰表示法之后则是丨2 + 5 4 + *。
相较于中缀表示法， 逆波兰表示法的优势在于不需要括号。
请输出以逆波兰表示法输入的算式的计算结果。
思路：
利用栈将输入数据进行存储，当遇到运算符号时将栈顶2个元素取出，运算之后放回。
考察点：栈(Stack)，数据结构，模拟 坑点：输入为整行输入，需要使用一定手段。代码：
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int maxn=2e5+100;
int main()
{
stack<int> s;
string ss;
getline(cin,ss);
for(int i=0;i<ss.size();i++){
if(ss[i]==' ') continue;
else if(ss[i]>='0'&&ss[i]<='9'){
int n=0;
while(ss[i]>='0'&&ss[i]<='9'){
n=n*10+ss[i]-'0';
i++;
}
s.push(n);
}
else
{
int a=s.top();
s.pop();
int b=s.top();
s.pop();
switch(ss[i]){
case '+':{
s.push(a+b);break;
}
case '-':{
s.push(b-a);break;
}
case '*':{
s.push(a*b);break;
}
default:break;
}
}
}
cout<<s.top()<<endl;
}
B - Queue
题意：
现有名称为 namei 且处理时间为 timei 的n个任务按顺序排成一列，
CPU通过循环调度法逐一处理这些任务，每个任务最多处理q毫秒。
如果q毫秒后任务尚未处理完毕，那么该任务将被移动至队伍最末尾，CPU随即开始处理下一个任务。
请编写一个程序，模拟循环调度法，按完成时间递增顺序输出每个任务的完成时间。
思路：
使用队列模拟循环调度算法。
考察点：队列(Queue)，数据结构，模拟，结构体（struct）代码：
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int maxn=2e5+100;
int main()
{
queue<pair<string,int> > q;
int n,k,t;
string name;
cin>>n>>k;
for(int i=0;i<n;i++){
cin>>name>>t;
q.push(make_pair(name,t));
}
int ti=0;
while(!q.empty()){
pair<string,int> p;
p=q.front();
q.pop();
if(p.second>k){
p.second-=k;
q.push(p);
ti+=k;
}
else{
ti+=p.second;
cout<<p.first<<" "<<ti<<endl;
}
}
}
C - Shaolin
题意：
少林寺以其功夫和尚而闻名。
每年都有很多年轻人去少林寺，想在那里出家。
少林大师对一个年轻人的评价主要是看他的才能或对佛经的理解，但武功也要考虑在内。
当一个年轻人通过了所有的测试，并被宣布为少林新和尚时，将会有一场打斗，作为欢迎派对的一部分。
每个和尚都有一个唯一的id和唯一的战斗等级，都是整数。新来的和尚必须和一个战斗等级最接近他的老和尚战斗。
如果有两个老和尚满足这个条件，新和尚就会选择格斗等级比他低的那个
这位师傅是少林第一个和尚，他的id是1，武功等级是10亿。
他刚刚丢掉了比赛记录。但他仍然记得谁更早加入少林，谁更晚加入。
请帮他找回打架记录。
思路：
使用map容器存储数据：
map[战力值]=编号值
利用map容器的特点：默认按key值降序排序，将当前和尚B战力插入后使用map::find寻找和尚B在当前排行榜中的位置，从而找到战力高于他的和尚A与战力低于他的和尚C，再根据题目找到B的对手即可完成此题。
考察点：映射对(Map)，数据结构，模拟代码：
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int maxn=2e5+100;
int main()
{
int n;
while(cin>>n&&n){
map<int,int> p;
p[10000000]=1;
int id,fight;
for(int i=0;i<n;i++){
int enemy;
cin>>id>>fight;
p[fight]=id;
map<int,int>::iterator it=p.find(fight),it2;
if(it==p.begin()){
enemy=(++it)->second;
}
else{
it2=it;
it2++;
it--;
if(it2->first-fight< fight-it->first)
enemy=it2->second;
else
enemy=it->second;
}
cout<<id<<" "<<enemy<<endl;
}
}
}
D - Equal Sums
题意：
给定k的数字序列，第i个序列有ni个元素。
是否能找到两个序列，使得两个序列各减去自身序列中的任意一个数之后序列和相等。
可以则输出一个合理的答案即可，不可以则输出“NO”。
输出格式：
YES
id1 pos1
id2 pos2
序列id1在删除pos1位置上的数字之后的序列和为s1
序列id2在删除pos2位置上的数字之后的序列和为s2
s1==s2
思路：
建立map容器存储数据：
map[序列和]=pair<第i个序列，第pos位的值> //当第i个序列去掉第pos位的值时的序列和
暴力对每个序列进行模拟，查找map中是否含有相同序列和的pair组合。
代码：
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int maxn=200100;
map<ll,pair<int,int> > q;
vector<ll> arr[maxn];
int main()
{
int k;
int flag=0;
cin>>k;
for(int i=0;i<k;i++){
int n;
cin>>n;
ll sum=0,x;
for(int j=0;j<n;j++){
cin>>x;
arr[i].push_back(x);
sum+=x;
}
for(int j=0;j<n;j++){
if(flag==1) break;
ll ans=sum-arr[i][j];
map<ll,pair<int,int> >::iterator it=q.find(ans);
if(it!=q.end()){
int que=(*it).second.first;
if(que==i+1) continue;
else{
cout<<"YES"<<endl;
cout<<i+1<<" "<<j+1<<endl;
cout<<(*it).second.first<<" "<<(*it).second.second<<endl;
flag=1;
}
}
else
q[ans]=make_pair(i+1,j+1);
}
}
if(!flag) cout<<"NO"<<endl;
}
E - Potions (Hard Version)
题意：
冒险家踏上了一条不归路，接下来的路上一共有n个关卡，你需要按顺序冒险，但是可以选择跳过某些关卡。
冒险家一开始没有金币。
通关每个关卡会获得ai个金币，但ai可以是负的。
冒险家希望自己可以通关更多的关卡，但又不希望自己的金币变成负数。
根据已知信息求出冒险家最多可以通关多少关卡。
思路：
使用优先队列存储在考虑范围之内的关卡的收益值，优先级为从小到大。
每当解锁新关卡B时，首先判断当前金币是否允许我们直接进入新关卡B（收益不能为负）。
代码：
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
const int maxn=200100;
ll a[maxn];
int main()
{
ll n;
cin>>n;
for(ll i=0;i<n;i++)
cin>>a[i];
priority_queue<ll,vector<ll>,greater<ll> > p;
ll sum=0;
ll l=0;
while(l<n){
sum+=a[l];
if(sum<0){
if(!p.empty()){
ll tmp=p.top();
p.pop();
if(a[l]<tmp){
p.push(tmp);
sum-=a[l];
}
else{
p.push(a[l]);
sum-=tmp;
}
}
else
sum-=a[l];
}
else p.push(a[l]);
l++;
}
cout<<p.size()<<endl;
}
F - Buy and Resell
题意：
你是一个商人，非常的有钱，你正在旅游，但是这仍然无法阻止你做生意。
旅途中一共有n个城市，这n座城市流通一种共同的货物，你打听到了每座城市关于这个货物的进价与售价相同（？）。
你打算小赚一波。
一开始你有无数的钱，经过每个城市的时候，你可以选择：
请输出旅游之后你能获得的最大利润值，并输出最小的交易次数。
样例解释：
4
1 2 10 9
第一个城市买进，贸易次数+1，利润：-1
第二个城市买进，贸易次数+1，利润：-3
第三个城市卖出，贸易次数+1，利润：7
第四个城市卖出，贸易次数+1，利润：16
答案为
16 4
思路：
我们使用优先队列存储我们会考虑进行贸易的城市的价格，优先级为由小到大。
当我们在某个城市选择以a价格买入b价格卖出时，我们向队列里加入两个b，并且把b-a算入利润中。
那么如果在之后的操作中，我们想以a买入以c卖出，我们的实际操作是：
买入队列中的b以c卖出，这时我们的收益是c-b+b-a=c-a，而且还有一个b在队列中。
对于整个模拟过程中，当我们买入的物品为不是之前加入队列的物品则贸易次数+2，否则不交易。
考察点：优先队列(Priority queue)，数据结构，贪心，思维 坑点：出现1 2 11 9的情况（中间商寻找最贪的解法）代码：
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
priority_queue<ll,vector<ll>,greater<ll> > q;
ll a[100010];
int main()
{
int t,n;
cin>>t;
while(t--){
cin>>n;
for(int i=0;i<n;i++) cin>>a[i];
while(!q.empty()) q.pop();
map<int,int> mp;
ll value=0;
ll cnt=0;
for(int i=0;i<n;i++){
if(!q.empty()&&q.top()<a[i]){
int x=q.top();
q.pop();
value+=(a[i]-x);
cnt+=2;
if(mp[x]) mp[x]--,cnt-=2;
q.push(a[i]);
mp[a[i]]++;
}
q.push(a[i]);
}
cout<<value<<" "<<cnt<<endl;
}
}
G - 度度熊学队列
题意：
中文题还需要我给题意？
思路：
1000%的模拟题，选好容器然后开始苦逼的肝代码就行了。
考察点：数据结构，模拟，耐心，列表(list)，双端队列(deque)，映射对(Map) 坑点：纯写双端队列(deque)会炸空间，但列表(list)不会代码：
#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
typedef long long ll;
map<int,deque<int> > q;
int main()
{
int n,Q;
while(~scanf("%d%d",&n,&Q)){
q.clear();
int flag,u,v,w;
for(int i=0;i<Q;i++){
scanf("%d",&flag);
if(flag==1){
scanf("%d%d%d",&u,&w,&v);
if(w==1) q[u].push_back(v);
else q[u].push_front(v);
}
else if(flag==2){
scanf("%d%d",&u,&w);
if(q[u].empty()) cout<<"-1"<<endl;
else{
int ans;
if(w==1){
ans=q[u].back();
q[u].pop_back();
}
else{
ans=q[u].front();
q[u].pop_front();
}
cout<<ans<<endl;
}
}
else{
scanf("%d%d%d",&u,&v,&w);
if(w==0){
q[u].insert(q[u].end(),q[v].begin(),q[v].end());
q[v].clear();
}
else{
q[u].insert(q[u].end(),q[v].rbegin(),q[v].rend());
q[v].clear();
}
}
}
}
}
相关知识
暑期动物医院社会实践报告
亚宠展薅羊毛Day1
2021快手宠物生态报告
2021广州黄埔区九龙第三小学暑期校内托管报名指南（含入口）
暑期租车火了，机票价格降了！
中国游客暑期开启全球“逛吃”模式
暑期社会实践：参观导盲犬训练基地
2021宠物市场数据分析报告
自制宠物营养餐Day1
《2021中国宠物行业发展趋势报告》正式发布
网址: HRBU 2021暑期训练解题报告Day1 https://m.mcbbbk.com/newsview494873.html
| 上一篇: 亢雅军简介 |
下一篇: 宠物“老师”成为新职业 |
