牛客小白87题解A-G

news/发布时间2024/4/20 21:00:56

A小苯的石子游戏

本题贪心模拟即可

B 小苯的排序疑惑

考虑到最简单的操作把n-1个数排好,最后一个看能否有序。即:a[1]<=min(a[2],a[3],a[4]..,a[n])|| a[n]>=max(a[1],a[2],a[3]....,a[n-1])满足条件,反之易得不可能

C&D 小苯的IDE括号问题

本题考察题意理解,简单版本我们可以只关注逻辑删除,hard需要我们物理删除,所以简单版本可以用双指针扫描,最后拼接,而hard版本因为指针是线性移动无法判断是否删除,所以hard版本用vector模拟队列即可 要注意的是可能需要翻转

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
const int mod=1e9+7;
void solved()
{int n,k;cin>>n>>k;string s;cin>>s;vector<char> l;vector<char> r;int flag=0;for(int i=0;s[i];i++){if(s[i]=='I'){flag=1;continue;}if(flag) r.push_back(s[i]);else l.push_back(s[i]);}reverse(r.begin(),r.end());string ans;while(k--){string d;cin>>d;if(d[0]=='b'){if(l.empty()) continue;if(!r.empty()&&r.back()==')'&&l.back()=='('){l.pop_back();r.pop_back();}else l.pop_back();}else if(d[0]=='d'){if(r.empty()) continue;r.pop_back();}else if(d[0]=='<'){if(l.empty()) continue;r.push_back(l.back());l.pop_back();}else{if(r.empty()) continue;l.push_back(r.back());r.pop_back();}}for(auto d:l) ans+=d;ans+='I';reverse(r.begin(),r.end());for(auto d:r) ans+=d;cout<<ans<<endl;}
signed main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t = 1;while (t--){solved();}}

E 小苯的数组构造

首先考察 如果a[i]< a[i-1] 那么我们可以把a[i]变成a[i-1]可以发现,前缀a[i]的值都会变成前缀最大值,所以b[i]=前缀最大-a[i], 考虑最大的b[i],如果极差小于b[i],可以证明无法满足单调,故,max bi为最大值.

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
const int mod=1e9+7;
void solved()
{int n;cin>>n;vector<int> a(n+1);vector<int> b(n+1);for(int i=1;i<=n;i++) cin>>a[i];for(int i=2;i<=n;i++){if(a[i]<a[i-1]){b[i]=a[i-1]-a[i];a[i]=a[i-1];}}for(int i=1;i<=n;i++) cout<<b[i]<<" ";
}
signed main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t = 1;while (t--){solved();}
}

F 小苯的数组切分

本题考察位运算性质,首先一点 and 操作 只减不增,能维持a[n] 都算不错,所以把r固定在n,一定没有问题,考虑枚举l即可。

 #include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
const int mod=1e9+7;
void solved()
{int n;cin>>n;vector<int> f(n+1),g(n+1),a(n+1);for(int i=1;i<=n;i++) cin>>a[i];for(int i=n-1;i>=2;i--) f[i]=f[i+1]|a[i];for(int i=1;i<=n;i++) g[i]=g[i-1]^a[i];int ans=0;for(int i=1;i<=n-1;i++){ans=max(ans,f[i+1]+g[i]+a[n]);}cout<<ans<<endl;
}
signed main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t = 1;while (t--){solved();}
}

G 小苯的逆序对

此题比较缝合考察了逆序对以及数论容斥的一些知识。考虑gcd(i,j)=x的逆序对,那么怎么求呢?
设g[x] 表示 x|gcd(i,j)的逆序对个数 那么 f[x]=g[x]-f[2x]-f[3x]-f[4x].....。 所以我们对每个x单独求,答案就是f[1].
求逆序对,我们要怎么样保证 x|gcd(i,j) 呢? 很简单,把x的倍数全部单独划分一个数组求逆序对即可,我是用值域树状数组求的,要考虑树状数组的清空,那么每次我们映射的时候就映射x的多少倍即可,这样方便清空降低时间复杂度。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
const int mod=1e9+7;
const int N=2e5+10;
int tree[N];
void updata(int idx,int k,int n){while(idx<=n){tree[idx]+=k;idx+=(idx)&(-idx);}
}
int query(int idx){int res=0;while(idx){res+=tree[idx];idx-=(idx)&(-idx);}return res;
}
void solved()
{int n;cin>>n;vector<int>  b(n+1);vector<int>  a[n+1];vector<int>  d[n+1];for(int i=1;i<=n;i++){cin>>b[i];}for(int i=1;i<=n;i++){for(int j=i;j<=n;j+=i) a[j].push_back(i);}for(int i=1;i<=n;i++){for(auto &k:a[b[i]]){d[k].push_back(b[i]/k);}}auto cal=[&](int k){int res=0;//cout<<k<<":";for(int i=0;i<d[k].size();i++){//cout<<d[k][i]<<" ";res+=(i-query(d[k][i]));updata(d[k][i],1,d[k].size()+1);}// cout<<res<<endl;for(int i=0;i<=d[k].size()+1;i++) tree[i]=0; return res;};vector<int> f(n+1);for(int i=n;i>=1;i--){f[i]=cal(i);for(int j=i+i;j<=n;j+=i) f[i]-=f[j];}cout<<f[1]<<endl;}
signed main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t = 1;while (t--){solved();}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.jwkm.cn/p/24768736.html

如若内容造成侵权/违法违规/事实不符,请联系宁远站长网进行投诉反馈email:xxxxxxxx@qq.com,一经查实,立即删除!

相关文章

Large Batch Experience Replay

发表时间:2021(ICML 2022) 文章要点:这篇文章把experience replay看做一个通过importance sampling来估计梯度的问题,从理论上推导经验回放的最优采样分布,然后提出LaBER (Large Batch Experience Replay)算法来近似这个采样分布。 非均匀采样mini batch可以看成一个基于re…

【译】为什么AI写作会显得枯燥无味

原作:本乌兰西 引子:绘画中减色混合的原理照片由 Unsplash 上的 Lucas K 拍摄当我还是个孩子的时候,我坐在一个有各种颜色的调色板前,努力尝试混合尽可能多的颜色。怀着兴奋的眼神,我看着鲜艳的颜色在画面上融合。随着越来越多的颜色相互融合,我困惑地盯着由此产生的聚合…

手把手教你如何下载小鹅通上已购买的视频课程

前言:很多同学都想知道小鹅通中视频课程怎么下载,但是小鹅通上面已购买的视频课程是不提供直接下载方式的,所以下面就教大家如何用学无止下载器下载小鹅通上面已购买的视频课程。 一、电脑网页打开小鹅通官网(https://study.xiaoe-tech.com),找到已购买的课程二、找到想要…

CRC算法原理和代码实现

前言 ​ 由于现在的工作涉及到协议的对接,而协议使用CRC进行校验。并且在MATLAB传C的过程中有可能需要使用到CRC来校验数据。所以在这篇文章中对CRC校验的有关知识进行梳理,也是自己对这方面知识点的梳理和总结吧。 什么是CRC校验 ​ CRC(Cyclic Redundancy Checksum循环冗余…

QT打包

Qt打包程序提示“应用程序无法正常启动(0xc000007b)”/未找到Qt5Core.dll的正确解决方案 先打到配置环境变量的页面

RabbitMQ 消息模型

参考链接: https://blog.csdn.net/qq_40991313/article/details/126801025?spm=1001.2014.3001.55013.5.3.总结描述下Direct交换机与Fanout交换机的差异? Fanout交换机将消息路由给每一个与之绑定的队列 Direct交换机根据RoutingKey判断路由给哪个队列 如果多个队…