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

目录

A.宇宙的终结

B.爱恨的纠葛

C.心绪的解剖

D.友谊的套路

E.未来的预言

F.命运的抉择

G.人生的起落

I.时空的交织

J.绝妙的平衡

K.错综的统一

A.宇宙的终结

直接暴力

我们可以发现数据范围特别小题目特别简单，如果能够马上想到一个容易写的做法就可以马上写上去

bool check(int x){if(x==1) return false;for(int i=2;i<=x/i;i++)if(x%i==0) return false;return true;
}
void solve(){int l,r; cin>>l>>r;vector<int> v;for(int i=2;i<=r;i++){if(check(i)){v.push_back(i);}}for(int i=0;i<v.size();i++)for(int j=i+1;j<v.size();j++)for(int k=j+1;k<v.size();k++){int x=v[i]*v[j]*v[k];if(x>=l && x<=r){cout<<x<<endl;return ;}}cout<<-1<<endl;return ;
}

B.爱恨的纠葛

左右二分

明显的要求我们安排数的位置我们可以发现对于一个数在他的左右是具有二分性质的所有考虑两边同时使用二分即可

int a[N],b[N],op[N],ans[N];
bool st[N];void solve(){cin>>n;for(int i=1;i<=n;i++) cin>>a[i];for(int i=1;i<=n;i++) cin>>b[i];for(int i=1;i<=n;i++) ans[i]=2e9+10;sort(a+1,a+1+n);for(int i=1;i<=n;i++){int l=1,r=n;while(l<r){int mid=l+r>>1;if(a[mid]>=b[i]) r=mid;else l=mid+1;}if(a[l]>=b[i]){ans[i]=a[l]-b[i];op[i]=l;}l=1,r=n;while(l<r){int mid=l+r+1>>1;if(a[mid]<=b[i]) l=mid;else r=mid-1;}if(a[l]<=b[i]){if(b[i]-a[l]<ans[i]){ans[i]=b[i]-a[l];op[i]=l;}}}int res=2e9+10;for(int i=1;i<=n;i++){if(ans[i]<res) res=ans[i];}vector<int> now(n+5);for(int i=1;i<=n;i++){if(ans[i]==res){now[i]=op[i];st[op[i]]=true;break;}}int l=1;for(int i=1;i<=n;i++){if(!now[i]){while(st[l]) l++;now[i]=l;st[l]=true;}cout<<a[now[i]]<<' ';}cout<<endl;return ;
}

C.心绪的解剖

斐波那契的性质

我们可以知道斐波那契只要到了70多位之后面的数就会特别大，所以只需要考虑对70的数据范围做n^3即可

int dp[N];
map<int,TUP> mp;
void intn(){dp[0]=0,dp[1]=dp[2]=1;for(int i=2;i<=70;i++){dp[i]=dp[i-1]+dp[i-2];}for(int i=0;i<=70;i++)for(int j=0;j<=70;j++)for(int k=0;k<=70;k++)mp[dp[i]+dp[j]+dp[k]]={dp[i],dp[j],dp[k]};
}
void solve(){int x; cin>>x;if(mp.count(x)){auto [a,b,c]=mp[x];cout<<a<<' '<<b<<' '<<c<<endl;}else cout<<-1<<endl;return ;
}

D.友谊的套路

签到题

直接按照题目模拟即可

void solve(){double p,res=0;cin>>p;res=p*p*(1-p)*(1-p)*(1-p)+(1-p)*(1-p)*p*p*p;cout<<LF(7)<<res<<endl;return ;
}

E.未来的预言

我们可以发现这也是简单的模拟不过有一个小问题就是字符串读入数字的转化算一个小坑

void solve(){string s; cin>>s;string res; cin>>res;n=res.size(); res=' '+res;int x=0;for(int i=2;i<s.size();i++){x=x*10+(s[i]-'0');}x=x/2+1;int R=0,P=0;for(int i=1;i<=n;i++){if(res[i]=='R') R++;else P++;if(R==x){cout<<"kou!"<<endl;cout<<i<<endl;return ;}if(P==x){cout<<"yukari!"<<endl;cout<<i<<endl;return ;}}cout<<"to be continued."<<endl;cout<<n<<endl;return ;
}

F.命运的抉择

我们来找一下性质，也就是说如果b,c中任意取一个数出来都是gcd等于1说明如果两个数有其他公约数的话一定都是在一个数组里面比如 2，4一定是在一起的，也就是手说他们之间是有一条边的所以我们可以考虑把所有数的约数筛选出来，然后对他们的倍数进行连边，最后利用最小生成树的思路来合并，如果说都合并在一起那就是不可，否则可行

int a[N],p[N];
int find(int x){if(x!=p[x]) p[x]=find(p[x]);return p[x];
}    void solve(){ cin>>n;unordered_map<int,int> yes;for(int i=1;i<=n;i++){cin>>a[i];int x=a[i];if(!yes.count(x))p[x]=x,yes[x]++;for(int j=2;j<=x/j;j++){if(x%j==0){while(x%j==0) x/=j;if(!yes.count(j))p[j]=j,yes[j]++;int fx=find(a[i]),fj=find(j);if(fx!=fj) p[fx]=fj;}}if(x>1){if(!yes.count(x))p[x]=x,yes[x]++;int fx=find(x),fa=find(a[i]);if(fx!=fa) p[fx]=fa;}}unordered_map<int,int> use;for(int i=1;i<=n;i++){int x=a[i];if(find(x)==x) use[x]++;for(int j=2;j<=x/j;j++){if(x%j==0){while(x%j==0) x/=j;if(find(j)==j) use[j]++;}}  if(x>1 && find(x)==x) use[x]++;}int ans=use.size();if(ans==1){cout<<-1<<' '<<-1<<endl;return ;}int x=a[1];vector<int> b,c;for(int i=1;i<=n;i++){int fx=find(x),fa=find(a[i]);if(fx==fa)b.push_back(a[i]);else c.push_back(a[i]);}cout<<b.size()<<' '<<c.size()<<endl;for(auto&v:b) cout<<v<<' ';cout<<endl;for(auto&v:c) cout<<v<<' ';cout<<endl;return ;
}

G.人生的起落

细节构造

对于构造题我们需要一点一点的额来处理这个问题

1.首先构造一个v三元组至少需要三个

2.其次需要构造k个v三元组需要使用至少2k+1个位置

3.我们可以构造的最少消耗的v三元组是2 1 2

4.注意三元组的要求是两边都要相等

我们不妨开始判断

1.如果位置少不行

2.如果说s小于最少使用也不行

3.如果构造之后不是3元组不行

由此可以进行进一步的推理和演算

void solve(){cin>>n>>s>>k;int need = k ? (2*k+1) : 0;if(need>n) return cout<<-1<<endl,void();if(need==n && s>3*k+2){int res = 3*k+2;s-=res;if(s<k+1) return cout<<-1<<endl,void();vector<int> ans(n+5);for(int i=1;i<=n;i++){if(i&1) ans[i]=2;else ans[i]=1;}int t=s/(k+1),more=s%(k+1);for(int i=1;i<=n;i++){if(ans[i]==2) ans[i]+=t;else{ans[i]+=(more ? 1 : 0);if(more>0) more--;}}for(int i=1;i<=n;i++) cout<<ans[i]<<' ';cout<<endl;return ;}if(k){int res = 3*k+2 + (n-need);if(res>s) return cout<<-1<<endl,void();for(int i=1;i<=k;i++) cout<<2<<' '<<1<<' ';cout<<2<<' ';s-=3*k+2;n-=need;if(!n) return cout<<endl,void();}int x=s/n,more=s%n;vector<int> res;for(int i=1;i<=n;i++){cout<<(x + (more ? 1 : 0))<<' ';if(more>0) more--;}cout<<endl;return ;
}

I.时空的交织

对于这种题目我们都是去找性质可以发现其实两个数相乘就是两个区间中取出来一段做乘法，要求最后的结果最大，也就是{最大*最大，最大*最小，最小*最小，最小*最小}题目转化为区间中找一段连续的最大值或者连续的最小值，简单处理即可

int a[N],b[N];
int get1(int a[],int n){int suma=0,ansa=-1e9-10;for(int i=1;i<=n;i++){suma+=a[i];ansa=max(ansa,suma);if(suma<0) suma=0;}return ansa;
}
int get2(int a[],int n){int suma=0,ansa=1e9+10;for(int i=1;i<=n;i++){suma+=a[i];ansa=min(ansa,suma);if(suma>0) suma=0;}return ansa;
}
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];LL res=max({get1(a,n)*get1(b,m),get1(a,n)*get2(b,m),get2(a,n)*get1(b,m),get2(a,n)*get2(b,m)});cout<<res<<endl;return ;

J.绝妙的平衡

树的性质

可以发现如果每一个红色的都至少有一个黑色直系的子节点就一定有解，但是最后的方案如何呢，可以发现只需要微调一下，不妨令所有的节点都是2，如果黑色节点之和不是3的倍数改变红节点为补数即可，否则把红节点改为1，找一个子儿子也改为1即可

vector<int> g[N];
int cnt[N],ans[N];
string s; 
vector<int> res;
void dfs(int u,int fa){for(auto&v:g[u]){if(v==fa) continue;dfs(v,u);if(s[v]=='W'){cnt[u]+=cnt[v];}}if(s[u]=='R'){if(cnt[u]==0){cout<<-1<<endl;exit(0);}int x=cnt[u]*2;if(x%3){ans[u]=3-(x%3);}else{ans[u]=1;for(auto&v:g[u]){if(v==fa) continue;if(s[v]=='W'){ans[v]=1; break;}}}cnt[u]=0;}else{cnt[u]++;}}void solve(){cin>>n;cin>>s; s=' '+s;for(int i=2;i<=n;i++){int x; cin>>x;g[x].push_back(i);g[i].push_back(x);}for(int i=1;i<=n;i++) ans[i]=2;dfs(1,-1);for(int i=1;i<=n;i++) cout<<ans[i];cout<<endl;return ;
}

K.错综的统一

题目意思明显的就是不能有大于等于2的回文串，所以就是考虑只有三个字母也就是red,的排列，同时考虑竖着的也就是12种情况，我们可以先构造出来然后按照二维前缀和的方式来维护求和即可

构造可以先构造第一行然后第二行对应变化，对于2*2的格子需要特判

char s[M][M];
char g[M][M][13];
int ans[M][M][13];
string op[]={" ","red","red","rde","rde","edr","edr","erd","erd","der","der","dre","dre"};
string A[]={" ","re","er","rd","dr","ed","de"};void solve(){cin>>n>>m>>q;for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)cin>>s[i][j];for(int c=1;c<=12;c++){for(int j=1,k=0;j<=n;j++,k++){k%=3;g[1][j][c]=g[1][j][c+1]=op[c][k];}g[2][1][c]=(c&1 ? g[1][2][c] : g[1][3][c]);g[2][2][c]=(c&1 ? g[1][3][c] : g[1][1][c]);for(int i=2;i<=n;i++)for(int j=1;j<=m;j++)if(!g[i][j][c]){for(auto&t:{'r','e','d'}){if(t!=g[i-1][j][c] && t!=g[i-2][j][c] && t!=g[i][j-1][c] && t!=g[i][j-2][c]){g[i][j][c]=t; break;}}}}for(int u=1;u<=12;u++){for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){ans[i][j][u] = s[i][j]!=g[i][j][u];ans[i][j][u]+=ans[i-1][j][u];ans[i][j][u]+=ans[i][j-1][u];ans[i][j][u]-=ans[i-1][j-1][u];}}}while(q--){int x1,y1,x2,y2; cin>>x1>>y1>>x2>>y2;int res=n*m;if(x2-x1==1 && y2-y1==1){for(int i=1;i<=6;i++){res=min(res,(s[x1][y1]!=A[i][0]) + (s[x1][y1+1]!=A[i][1]) + (s[x1+1][y1]!=A[i][1]) + (s[x1+1][y1+1]!=A[i][0]) );}}for(int i=1;i<=12;i++){res=min(res,ans[x2][y2][i]-ans[x2][y1-1][i]-ans[x1-1][y2][i]+ans[x1-1][y1-1][i]);}cout<<res<<endl;}return ;
}

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

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

若依框架的使用

若依框架的使用

文章目录 1,前端2,后端3,数据库4,测试 1,前端 2,后端 3,数据库 4,测试
阅读更多...
MinGW-w64的下载与安装

MinGW-w64的下载与安装

文章目录 1 下载2 安装3 配置环境变量4 验证 1 下载 官网地址&#xff1a;https://www.mingw-w64.org/github地址&#xff1a;https://github.com/niXman/mingw-builds-binaries/releases windows下载 跳转github下载 版本号选择&#xff1a;13.2.0是GCC的版本号&#xff1b…
阅读更多...
鸿蒙开发(四)-低代码开发

鸿蒙开发(四)-低代码开发

鸿蒙开发(四)-低代码开发 本文主要介绍下鸿蒙下的低代码开发。 鸿蒙低代码是指在鸿蒙操作系统进行应用开发时&#xff0c;采用简化开发流程和减少编码量的方式来提高开发效率。 1&#xff1a;开启低代码开发 首先我们打开DevEco Studio .然后创建工程。 如图所示&#xff…
阅读更多...
如何在Linux部署FastDFS文件服务并实现无公网IP远程访问内网文件——“cpolar内网穿透”

如何在Linux部署FastDFS文件服务并实现无公网IP远程访问内网文件——“cpolar内网穿透”

文章目录 前言1. 本地搭建FastDFS文件系统1.1 环境安装1.2 安装libfastcommon1.3 安装FastDFS1.4 配置Tracker1.5 配置Storage1.6 测试上传下载1.7 与Nginx整合1.8 安装Nginx1.9 配置Nginx 2. 局域网测试访问FastDFS3. 安装cpolar内网穿透4. 配置公网访问地址5. 固定公网地址5.…
阅读更多...
【C++】string类（介绍、常用接口)

【C++】string类（介绍、常用接口)

&#x1f308;个人主页&#xff1a;秦jh__https://blog.csdn.net/qinjh_?spm1010.2135.3001.5343&#x1f525; 系列专栏&#xff1a;http://t.csdnimg.cn/eCa5z 目录 string类的常用接口说明 string类对象的常见构造 ​编辑 string字符串的遍历&#xff08;迭代器&#xf…
阅读更多...
LoadRunner学习：RuntimeSetting、参数化、关联、（unfinished

LoadRunner学习：RuntimeSetting、参数化、关联、（unfinished

LoadRunner RuntimeSetting 运行时设置 在Vuser中设置Run-time Settings RunLogic&#xff1a;运行逻辑&#xff0c;决定了脚本真正执行逻辑&#xff0c; Init和End部分代码只能执行一次。决定脚本真正执行逻辑的意思是&#xff0c;在Run中的代码和Number of Iteration决定了…
阅读更多...
[HackMyVM]Quick 2

[HackMyVM]Quick 2

kali:192.168.56.104 主机发现 arp-scan -l # arp-scan -l Interface: eth0, type: EN10MB, MAC: 00:0c:29:d2:e0:49, IPv4: 192.168.56.104 Starting arp-scan 1.10.0 with 256 hosts (https://github.com/royhills/arp-scan) 192.168.56.1 0a:00:27:00:00:05 (Un…
阅读更多...
如何把黑白照片变成彩色？分享3款神奇的技术！

如何把黑白照片变成彩色？分享3款神奇的技术！

在数字化时代&#xff0c;我们手中的老照片不仅仅是回忆的载体&#xff0c;更是时光的见证。那些年代久远的黑白照片&#xff0c;虽然承载着珍贵的记忆&#xff0c;但却少了些许生动的色彩。那么&#xff0c;你是否想过让这些黑白旧影焕发新生&#xff0c;重现昔日的斑斓色彩呢…
阅读更多...
ChatGPT无法发送消息问题解决

ChatGPT无法发送消息问题解决

如果您的 Chatgpt 网页版这几日一直无法发送消息&#xff0c;或者发送了消息&#xff0c;也没有相应的回复&#xff0c;如下图所示&#xff1a; 现在 OpenAI 已经修复了这个 BUG。 用户可以尝试清理 OpenAI 网站的缓存&#xff0c;之后再重新登录&#xff0c;即可正常发送消息。…
阅读更多...
全网最全压力测试攻略大全，建议收藏备用！

全网最全压力测试攻略大全，建议收藏备用！

压力测试 压力测试是一种软件测试&#xff0c;用于验证软件应用程序的稳定性和可靠性。压力测试的目标是在极其沉重的负载条件下测量软件的健壮性和错误处理能力&#xff0c;并确保软件在危急情况下不会崩溃。它甚至可以测试超出正常工作点的测试&#xff0c;并评估软件在极端…
阅读更多...
Linux 学习(持续更新。。。)

Linux 学习(持续更新。。。)

wc命令 命令直接执行&#xff0c;输出包含四项&#xff0c;分别代表&#xff1a;行数、字数、字节数、文件。 例子:编译下列代码: #include <stdio.h> #include <stdlib.h> #include <unistd.h> #include <string.h> #include <fcntl.h> #inclu…
阅读更多...
Facebook、亚马逊养号选择什么代理IP？

Facebook、亚马逊养号选择什么代理IP？

之前我们讨论过很多关于代理器的问题。它们的工作原理是什么?在不同的软件中要使用那些代理服务器?这些代理服务器之间的区别是什么?什么是反检测浏览器等等。 除了这些问题&#xff0c;相信很多人也会关心在使用不同平台的时代理器的选择问题。比如&#xff0c;为什么最好…
阅读更多...
MATLAB 四点确定唯一球面参数（44）

MATLAB 四点确定唯一球面参数（44）

MATLAB 四点确定唯一球面参数（44） 一、算法简介二、算法实现1.代码2.结果一、算法简介 根据给定的四个点，快速拟合获取球的中心和半径，具体代码如下： 二、算法实现 1.代码 代码如下（示例）： point1 = [0.0, 0.0, 0.0]
阅读更多...
一个系列很多样式的wordpress外贸建站模板

一个系列很多样式的wordpress外贸建站模板

菌菇干货wordpress跨境电商模板 食用菌、羊肚菌、牛肝菌、香菇、干黄花菜、梅干菜、松茸wordpress跨境电商模板。 https://www.jianzhanpress.com/?p3946 餐饮调味wordpress跨境电商模板 豆制品、蛋黄糖、烘焙、咖啡、调料、调味酱、餐饮调味wordpress跨境电商模板。 http…
阅读更多...
git 如何将多个提交点合并为一个提交点 commit

git 如何将多个提交点合并为一个提交点 commit

文章目录 核心命令详细使用模式总结示例 核心命令 git merge branch2 是将分支branch2的提交点合并到本地当前分支。 而在执行这条命令的时候&#xff0c;加一个选项--squash就表示在合并的时候将多个提交点合并为一个提交点。 git merge --squash branch2 先看squash单词的意…
阅读更多...
基于单片机的视觉导航小车设计

基于单片机的视觉导航小车设计

目 录 摘 要 I Abstract II 引 言 1 1 总体方案设计 3 1.1 方案论证 3 1.2 项目总体设计 3 2 项目硬件设计 4 2.1 主控模块设计 4 2.1.1单片机选型 4 2.1.2 STM32F103RCT6芯片 4 2.2单片机最小系统电路 5 2.3电机驱动模块设计 7 2.4红外模块设计 8 2.5红外遥控模块设计 9 2.6超…
阅读更多...
css相邻元素边框重合问题，解决方案

css相邻元素边框重合问题，解决方案

1、如下图所示&#xff0c;在给元素设置边框后&#xff0c;相邻元素会出现重合的问题 2、解决方案 给每个元素设置margin-top以及margin-left为负的边框 <div style"width: 300px;display: flex;flex-wrap: wrap;margin-top: 50px;"><div style"border…
阅读更多...
MySQL-QA-异常问题及解决方案(持续更新)

MySQL-QA-异常问题及解决方案(持续更新)

MySQL-Q&A(持续更新) 1.1 PID文件找不到 问题描述 错误详情&#xff1a; ERROR&#xff01;The server quit without updating PID file (/usr/local/mysql/data/localhost.localdomain.pid) 解决方案 首先排查配置文件&#xff0c;一般路径为&#xff1a;/etc/my.cnf 检查…
阅读更多...
蓝桥杯2023真题（4）

蓝桥杯2023真题（4）

1.景区导游&#xff08;树上前缀和、最近公共祖先&#xff09; 思路 路线&#xff1a;2 -> 6 -> 5 -> 1 1.一个点都不去去掉的花费记作sum 2.去掉第一个点&#xff0c;sum - cost[2 -> 6] 3.去掉第二个点&#xff0c;sum - cost[2 -> 6] - cost[6 -> 5] co…
阅读更多...
01、python_爬虫的相关概念

01、python_爬虫的相关概念

一、什么是爬虫&#xff1f; 爬虫是网络爬虫的简称&#xff0c;指的是一种自动化程序&#xff0c;用于在互联网上抓取信息。爬虫的核心工作包括爬取网页、解析数据和存储数据。 通俗来说就是&#xff1a;通过一个程序&#xff0c;根据url(http://taobao.com)进行爬取网页&…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023