2024牛客寒假算法基础集训营6

2024-02-25 20:44

本文主要是介绍2024牛客寒假算法基础集训营6,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • A-宇宙的终结
  • B-爱恨的纠葛
  • C-心绪的解剖
  • D-友谊的套路
  • E-未来的预言
  • F-命运的抉择
  • I-时空的交织
  • J-绝妙的平衡

A-宇宙的终结

用试除法分解质因数,判断是否刚好分解为三个不同的质数

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
int l,r;
void solve() {cin>>l>>r;for(int i=l;i<=r;i++){int x=i;int cnt=0;set<int>s;for(int j=2;j<=x/j;j++){if(x%j==0){while(x%j==0){x/=j;s.insert(j);cnt++;}}}if(x>1) cnt++,s.insert(x);if(cnt==3&&(int)s.size()==3){cout<<i<<endl;return;}}cout<<-1<<endl;
}
signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t=1;
//    cin>>t;while(t--) {solve();}return 0;
}

B-爱恨的纠葛

一开始题目读错了,亲密度看成是和了,后面发觉是最小值

只要找到两个数差值最小是多少,然后那两个数对应,其它随意排

利用二分,先将b升序,枚举a中的每一个数,在b中二分出离a最近的数,然后找到差值最小的

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
typedef pair<int, int>PII;
const int N = 1e5 + 10;
int n;
int a[N];
void solve() {cin >> n;for (int i = 1; i <= n; i++) cin >> a[i];vector<PII>ans;for (int i = 1; i <= n; i++) {int x;cin >> x;ans.push_back({x, i});}sort(ans.begin(), ans.end());int res = 2e9;int aa;int aaa, bbb;for (int i = 1; i <= n; i++) {int l=0,r=ans.size()-1;while(l<r){int mid=(l+r)/2;if(ans[mid].first>=a[i]) r=mid;else l=mid+1;}if(l<(int)ans.size()){aa=abs(ans[l].first-a[i]);if(res>aa) res=aa,aaa=i,bbb=l;}if(l>0){aa=abs(ans[l-1].first-a[i]);if(res>aa) res=aa,aaa=i,bbb=l-1;}}//a[aaa]和b[ans[bbb].second]对应swap(a[aaa],a[ans[bbb].second]);for(int i=1;i<=n;i++) cout<<a[i]<<' ';cout<<endl;
}
signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t = 1;
//    cin>>t;while (t--) {solve();}return 0;
}

C-心绪的解剖

斐波那契数非常的少,第45个就已经超出1e9了,先全部存起来

然后优先选大的(利用二分),然后选小的,选三个数,并减去,如果最后剩下的数大于0,那么无解

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N=1e5+10;
int f[N];
void solve() {f[0]=0;f[1]=1;for(int i=2;i<=45;i++) f[i]=f[i-1]+f[i-2];int q;cin>>q;while(q--){int n;cin>>n;vector<int>ans;int l=0,r=45;while(l<r){int mid=(l+r+1)/2;if(f[mid]<=n) l=mid;else r=mid-1;}ans.push_back(f[l]);n-=f[l];l=0,r=45;while(l<r){int mid=(l+r+1)/2;if(f[mid]<=n) l=mid;else r=mid-1;}ans.push_back(f[l]);n-=f[l];l=0,r=45;while(l<r){int mid=(l+r+1)/2;if(f[mid]<=n) l=mid;else r=mid-1;}ans.push_back(f[l]);n-=f[l];if(n) cout<<-1<<endl;else{for(auto v:ans) cout<<v<<' ';cout<<endl;}}
}
signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t=1;
//    cin>>t;while(t--) {solve();}return 0;
}

D-友谊的套路

当时就想着小红让2追3,忘记考虑小紫让2追3了

小红让2追3的概率为 ( 1 − p ) 2 (1-p)^2 (1p)2* p 3 p^3 p3

小紫让2追3的概率为 p 2 p^2 p2* ( 1 − p ) 3 (1-p)^3 (1p)3

两者概率加起来

#include<bits/stdc++.h>
#include<cstdio>
#define endl '\n'
#define int long long
using namespace std;
double p;
void solve() {cin>>p;double ans1=pow(p,3)*pow(1-p,2);double ans2=pow(p,2)*pow(1-p,3);double ans=ans1+ans2;printf("%.10f\n",ans);
}
signed main() {
//	ios::sync_with_stdio(false);
//	cin.tie(0);
//	cout.tie(0);int t=1;
//    cin>>t;while(t--) {solve();}return 0;
}

E-未来的预言

模拟即可

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
string s;
string t;
void solve() {cin>>s>>t;int x=0;for(int i=2;i<(int)s.size();i++){x=x*10+s[i]-'0';}int cnt=(x+1)/2;map<int,int>mp;for(int i=0;i<(int)t.size();i++){if(t[i]=='R') mp[0]++;else mp[1]++;if(mp[0]==cnt){cout<<"kou!"<<endl;cout<<i+1<<endl;return;}if(mp[1]==cnt){cout<<"yukari!"<<endl;cout<<i+1<<endl;return;}}cout<<"to be continued."<<endl;cout<<t.size()<<endl;
}
signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t=1;
//    cin>>t;while(t--) {solve();}return 0;
}

F-命运的抉择

gcd(a,b)可以将a质因数分解,将b质因数分解,然后将公共的质因数乘起来
有公共质因子的两个数应该在同一个集合中
枚举质因子,把它的倍数都放进同一个集合中
如果最后全合成一个集合了,那么无解

集合的合并与查找–>并查集

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N=1e6+10;
int p[N];
int find(int x){if(p[x]!=x) p[x]=find(p[x]);return p[x];
}
bool st[N];
int prime[N];
int cnt;
//欧拉筛
void get_prime(int n){for(int i=2;i<=n;i++){if(!st[i]) prime[cnt++]=i;for(int j=0;prime[j]<=n/i;j++){st[prime[j]*i]=true;if(i%prime[j]==0) break;}}
}
int n;
int a[N];
unordered_map<int,vector<int>>ans;
void solve() {ans.clear();cin>>n;for(int i=1;i<=n;i++) p[i]=i;for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=n;i++){int x=a[i];for(int j=2;j<=x/j;j++){if(x%j==0){while(x%j==0){x/=j;ans[j].push_back(i);//含有质因子j的数的下标}}}if(x>1){ans[x].push_back(i);}}for(auto v:ans){auto tmp=v.second;for(int i=1;i<(int)tmp.size();i++){int a=find(tmp[i]),b=find(tmp[i-1]);if(a!=b) p[a]=b;}}
//	for(int i=1;i<=n;i++) cout<<p[i]<<' ';
//	cout<<endl;vector<int>res1,res2;int first;for(int i=1;i<=n;i++){if(find(i)==i){first=i;break;}}for(int i=1;i<=n;i++){if(find(i)==first) res1.push_back(a[i]);else res2.push_back(a[i]);}if(res2.size()==0){cout<<-1<<' '<<-1<<endl;return;}cout<<res1.size()<<' '<<res2.size()<<endl;for(auto v:res1) cout<<v<<' ';cout<<endl;for(auto v:res2) cout<<v<<' ';cout<<endl;
//	for(int i=0;i<cnt;i++) cout<<prime[i]<<' ';
//	cout<<cnt<<endl;
}
signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t=1;cin>>t;while(t--) {solve();}return 0;
}

I-时空的交织

求出数组a连续子段为正的最大,为负的最小,同理,对b

然后正正得正,负负得负,取max

如果相乘不能为正,那么特判有没有0,如果有0,答案为0

如果没有0,那么找一个最小的单元格

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N=1e5+10;
int a[N],b[N];
int dp1[N],dp2[N],dp3[N],dp4[N];
int n,m;
void solve() {cin>>n>>m;for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=m;i++) cin>>b[i];bool ok=false;for(int i=1;i<=n;i++){if(a[i]==0) ok=true;}for(int i=1;i<=m;i++){if(b[i]==0) ok=true;}dp1[0]=0;for(int i=1;i<=n;i++){dp1[i]=max(a[i],dp1[i-1]+a[i]);dp2[i]=min(a[i],dp2[i-1]+a[i]);}for(int i=1;i<=m;i++){dp3[i]=max(b[i],dp3[i-1]+b[i]);dp4[i]=min(b[i],dp4[i-1]+b[i]);}int ans1=0,ans2=0,ans3=0,ans4=0;for(int i=1;i<=n;i++){ans1=max(ans1,dp1[i]);ans2=min(ans2,dp2[i]);}for(int i=1;i<=m;i++){ans3=max(ans3,dp3[i]);ans4=min(ans4,dp4[i]);}int ans=-2e9;if(ans1>0&&ans3>0) ans=max(ans,ans1*ans3);if(ans2<0&&ans4<0) ans=max(ans,ans2*ans4);if(ans>0){cout<<ans<<endl;return;}if(ok){cout<<0<<endl;return;}vector<int>r1,r2,r3,r4;for(int i=1;i<=n;i++){if(a[i]>0) r1.push_back(a[i]);else r2.push_back(a[i]);}for(int i=1;i<=m;i++){if(b[i]>0) r3.push_back(b[i]);else r4.push_back(b[i]);}if(r1.size()) sort(r1.begin(),r1.end());if(r2.size()){sort(r2.begin(),r2.end());reverse(r2.begin(),r2.end());}if(r3.size()) sort(r3.begin(),r3.end());if(r4.size()){sort(r4.begin(),r4.end());reverse(r4.begin(),r4.end());}
//	cout<<r1.size()<<' '<<r2.size()<<' '<<r3.size()<<' '<<r4.size()<<endl;ans=-2e9;if(r1.size()&&r4.size()) ans=max(ans,r1[0]*r4[0]);if(r2.size()&&r3.size()) ans=max(ans,r2[0]*r3[0]);cout<<ans<<endl;
}
signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t=1;
//    cin>>t;while(t--) {solve();}return 0;
}

J-绝妙的平衡

参考2024牛客寒假算法基础集训营6(C,F,G,I,J) - 知乎 (zhihu.com)

如果一个红点的儿子全是红点,那它必须也是3的倍数,不可能,这样是无解的,因为只能赋值1和2

当一个红色节点没有子节点或者所有的子节点均为红色时无解。其他情况下可以进行贪心,将所有的节点赋值为1,然后根据红色节点的子节点权值和来修改该红色节点和它的任意一个白色节点

#include<bits/stdc++.h>
#define endl '\n'
#define int long long
using namespace std;
const int N=1e5+10;
int sum[N],ans[N];
int n;
string s;
vector<vector<int>>e(N);
map<int,int>mp;
void dfs(int x){int res=1;for(auto v:e[x]){dfs(v);if(!mp[v]) res+=sum[v];//加上白色节点上的数字,红色节点不用管,因为已经是3的倍数了}if(mp[x]){if(res%3==2) ans[x]++;//权值和加1变为3的倍数else if(res%3==1){//权值和加2为3的倍数//将节点x加1,以及它的一个子节点加1,一开始赋值为1,每个节点最多加1ans[x]++;ans[e[x][0]]++;//自底向上,如果有解的话,红色节点的儿子节点中一定有白色节点,对于红色节点,如果res%3==1,就算儿子节点的红色节点+1,它也会通过递归往下调整}}sum[x]=res;//x节点的子节点的权值之和
}
void solve() {cin>>n>>s;for(int i=1;i<=n;i++) e[i].clear();mp.clear();for(int i=0;i<n;i++){if(s[i]=='R') mp[i+1]=1;}for(int i=2;i<=n;i++){int x;cin>>x;e[x].push_back(i);//i的父节点为x}bool ok;for(int i=1;i<=n;i++){sum[i]=1,ans[i]=1;//每个节点先赋值为1ok=false;for(auto v:e[i]){//儿子节点中存在白色节点if(!mp[v]){ok=true;break;}}if(mp[i]&&!ok){//当前节点为红色且儿子节点中不存在白色节点,无解cout<<-1<<endl;return;}}dfs(1);for(int i=1;i<=n;i++) cout<<ans[i];cout<<endl;}
signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int t=1;
//    cin>>t;while(t--) {solve();}return 0;
}

这篇关于2024牛客寒假算法基础集训营6的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/746655

相关文章

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

C#基础之委托详解(Delegate)

《C#基础之委托详解(Delegate)》:本文主要介绍C#基础之委托(Delegate),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1. 委托定义2. 委托实例化3. 多播委托(Multicast Delegates)4. 委托的用途事件处理回调函数LINQ

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.

golang字符串匹配算法解读

《golang字符串匹配算法解读》文章介绍了字符串匹配算法的原理,特别是Knuth-Morris-Pratt(KMP)算法,该算法通过构建模式串的前缀表来减少匹配时的不必要的字符比较,从而提高效率,在... 目录简介KMP实现代码总结简介字符串匹配算法主要用于在一个较长的文本串中查找一个较短的字符串(称为

通俗易懂的Java常见限流算法具体实现

《通俗易懂的Java常见限流算法具体实现》:本文主要介绍Java常见限流算法具体实现的相关资料,包括漏桶算法、令牌桶算法、Nginx限流和Redis+Lua限流的实现原理和具体步骤,并比较了它们的... 目录一、漏桶算法1.漏桶算法的思想和原理2.具体实现二、令牌桶算法1.令牌桶算法流程:2.具体实现2.1

0基础租个硬件玩deepseek,蓝耘元生代智算云|本地部署DeepSeek R1模型的操作流程

《0基础租个硬件玩deepseek,蓝耘元生代智算云|本地部署DeepSeekR1模型的操作流程》DeepSeekR1模型凭借其强大的自然语言处理能力,在未来具有广阔的应用前景,有望在多个领域发... 目录0基础租个硬件玩deepseek,蓝耘元生代智算云|本地部署DeepSeek R1模型,3步搞定一个应

Python中的随机森林算法与实战

《Python中的随机森林算法与实战》本文详细介绍了随机森林算法,包括其原理、实现步骤、分类和回归案例,并讨论了其优点和缺点,通过面向对象编程实现了一个简单的随机森林模型,并应用于鸢尾花分类和波士顿房... 目录1、随机森林算法概述2、随机森林的原理3、实现步骤4、分类案例:使用随机森林预测鸢尾花品种4.1

MySQL中my.ini文件的基础配置和优化配置方式

《MySQL中my.ini文件的基础配置和优化配置方式》文章讨论了数据库异步同步的优化思路,包括三个主要方面:幂等性、时序和延迟,作者还分享了MySQL配置文件的优化经验,并鼓励读者提供支持... 目录mysql my.ini文件的配置和优化配置优化思路MySQL配置文件优化总结MySQL my.ini文件

Python基于火山引擎豆包大模型搭建QQ机器人详细教程(2024年最新)

《Python基于火山引擎豆包大模型搭建QQ机器人详细教程(2024年最新)》:本文主要介绍Python基于火山引擎豆包大模型搭建QQ机器人详细的相关资料,包括开通模型、配置APIKEY鉴权和SD... 目录豆包大模型概述开通模型付费安装 SDK 环境配置 API KEY 鉴权Ark 模型接口Prompt