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

文章目录

  • A 宇宙的终结
    • 题目大意
    • 主要思路
    • 代码
  • B 爱恨的纠葛
    • 题目大意
    • 主要思路
    • 代码
  • C 心绪的解剖
    • 题目大意
    • 主要思路
    • 代码
  • D 友谊的套路
    • 题目大意
    • 主要思路
    • 代码
  • E 未来的预言
    • 题目大意
    • 主要思路
    • 代码
  • G 人生的起落
    • 题目大意
    • 主要思路
    • 代码
  • I 时空的交织
    • 题目大意
    • 主要思路
    • 代码
  • J 绝妙的平衡
    • 题目大意
    • 主要思路
    • 代码

A 宇宙的终结

题目大意

在给定的某个区间内找到一个数，它是3个不同素数的积。

主要思路

这里范围比较小，而且是乘积的形式，如果其中最小的俩个数字分别是2和3，那么第三个数的最大取值也不会超过100/6，所以枚举前面的几个质数，然后暴力查找就可以了。

代码

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int l,r;
    int a[]={2,3,5,7,11,13,17,19,21};
    cin>>l>>r;
    for(int i=0;i<8;++i)
        for(int j=i+1;j<8;++j)
            for(int k=j+1;k<8;++k)
            {
                if(l<=a[i]*a[j]*a[k]&&a[i]*a[j]*a[k]<=r)
                {
                    cout<<a[i]*a[j]*a[k];
                    return 0;
                }
            }
    cout<<-1;
    return 0;
}

B 爱恨的纠葛

题目大意

给定俩数组，定义了一个叫做亲密度的东西就是ab俩数组一一对应相减取绝对值的最小值，现在对数组a进行排序，求亲密度最小时的a数组

主要思路

我们只需要找到其中一对就可以了，剩下的随便排都可以，可以把数组a预处理排序，然后对于每一个b数组中的数，在a数组钟进行二分查找最接近的那一个做差，然后记录哪一个是最接近的，最后在a数组中直接调换然后输出即可

代码

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5+10;
int a[N],b[N];

int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;++i)
        cin>>a[i];
    for(int i=0;i<n;++i)
        cin>>b[i];
    if(n==1)
    {
        cout<<a[0];
        return 0;
    }
    sort(a,a+n);
//     for(int i=0;i<n;++i)
//     {
//         cout<<a[i]<<" ";
//     }
    int minzhi=1e9+10;
    int minweizhi=0,mubiaoweizhi=0;
    for(int i=0;i<n;++i)
    {
        int left=0,right=n-1;
        while(left<right)
        {
            int mid=(left+right)>>1;
            if(a[mid]<b[i])left=mid+1;
            else right=mid;
        }
        int idx=left;
        int cha=INT_MAX;
        if(idx==0)
        {
            if((int)abs(a[0]-b[i])<(int)abs(a[1]-b[i]))
            {
                cha=(int)abs(a[0]-b[i]);
                idx=0;
            }
            else
            {
                cha=(int)abs(a[1]-b[i]);
                idx=1;
            }
        }
        else if(idx==n-1)
        {
            if((int)abs(a[n-1]-b[i])<(int)abs(a[n-2]-b[i]))
            {
                cha=(int)abs(a[n-1]-b[i]);
                idx=n-1;
            }
            else 
            {
                cha=(int)abs(a[n-2]-b[i]);
                idx=n-2;
            }
        }
        else 
        {
            int idx2;
            if((int)abs(b[i]-a[idx-1])<(int)abs(a[idx]-b[i]))
            {
                cha=(int)abs(b[i]-a[idx-1]);
                idx2=idx-1;
            }
            else 
            {
                cha=(int)abs(a[idx]-b[i]);
                idx2=idx;
            }
            if(cha>(int)abs(a[idx+1]-b[i]))
            {
                cha=(int)abs(a[idx+1]-b[i]);
                idx2=idx+1;
            }
            idx=idx2;
        }
        if(cha<minzhi)
        {
            minzhi=cha;
            minweizhi=i;
            mubiaoweizhi=idx;
        }
    }
    swap(a[minweizhi],a[mubiaoweizhi]);
    for(int i=0;i<n;++i)
    {
        cout<<a[i]<<" ";
    }
    return 0;
}

C 心绪的解剖

题目大意

把一个正整数分解成三个斐波那契数的和

主要思路

简单打表看了一下，最多也就是48个数字，直接暴力枚举注意点技巧就行

代码

#include<bits/stdc++.h>
#define debug(x) cout<<#x<<" = "<<x<<"\n"
using namespace std;

long long nums[50]{0,1};
int n=49;

void init()
{
    for(int i=2;i<49;++i)
    {
        nums[i]=nums[i-1]+nums[i-2];
    }
}

void solve()
{
    int target;
    cin>>target;
    // 枚举 a
    for (int i = 0; i < n; ++i) 
    {
        int k = n - 1;
        for (int j = i ; j < n; ++j) 
        {
            while (j <= k && nums[i] + nums[j] + nums[k] > target) 
            {
                --k;
            }
            if (nums[i] + nums[j] + nums[k] == target) 
            {
                cout<<nums[i]<<" "<<nums[j]<<" "<<nums[k]<<"\n";
                return ;
            }
        }
    }
    cout<<"-1\n";
}

int main()
{
    init();
    int t;
    cin>>t;
    while(t--)
    {
        solve();
    }
    return 0;
}

D 友谊的套路

题目大意

已知红队每一局获胜的概率为p，请问最终这场对战出现让二追三的概率是多少

主要思路

出现让二追三的局面的时候也就意味着前面四局第一第二输了，第三第四是赢的，后面那一局不用管就好

代码

#include<bits/stdc++.h>
using namespace std;

int main()
{
    double p;
    cin>>p;
    printf("%.8lf",pow(p,2)*pow(1-p,2));
    return 0;
}

E 未来的预言

题目大意

根据比赛信息，判断比赛得出胜负的时候，一共进行了多少局。输出比赛的情况

主要思路

一个简单的模拟，遍历字符串累加计数

代码

#include<bits/stdc++.h>
using namespace std;

int main()
{
    char x;
    int n;
    cin>>x;
    cin>>x;
    cin>>n;
    string s;
    cin>>s;
    int len=s.size();
    int r=0,p=0;
    for(int i=0;i<len;++i)
    {
        if(s[i]=='R')r++;
        else p++;
        if(r==(n+1)/2)
        {
            cout<<"kou!\n"<<i+1;
            return 0;
        }
        else if(p==(n+1)/2)
        {
            cout<<"yukari!\n"<<i+1;
            return 0;
        }
    }
    cout<<"to be continued.\n"<<len;
    return 0;
}

G 人生的起落

题目大意

形如 ( a , b , a ) , a > b (a,b,a),a>b (a,b,a),a>b的三元组称为“v-三元组”。 构造一个长度为n，和为S，且恰好有k个“v-三元组”的正整数数组。

主要思路

21212121这样够了后面全部放1，然后在考虑剩下数字，如果不够是-1，相同直接输出，如果还有剩余又看看还有没有空位，如果有就把剩下全给最前面（实际上是开头插入，如果给末尾可能刚刚好凑多一个212），没有空位就看看能不能对2集体加1，如果不能就-1，不然就一直+1直到不能操作，然后剩下数字丢给1(思路来自黄大师)

代码

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ll long long
#define pb push_back
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
    int t;
    cin>>t;
    while(t--)
    {
        int n,s,k;
        cin>>n>>s>>k;
        if(n==1&&k==0)
        {
            cout<<s<<endl;
            continue;
        }
       else if( (n==1&&k!=0)||(n==2&&k!=0) )
       {
           cout<<-1<<endl;
           continue;
       }
       else if(n==2&&k==0)
           {
               cout<<1<<" "<<s-1<<endl;
               continue;
           }
        else if(k==0)
        {
            for(int i=1;i<n;i++) cout << "1" << ' ';
            cout << s-n+1 << endl;
            continue;
        }
       else if(n<2*k+1) {cout<<-1<<endl;continue;}
       else if(k&&s<n+k+1) {cout<<-1<<endl;continue;}
        else 
        {
            ll t=(s-(n-(k+1)))/(k+1);
    vector<ll> ans;
    for(int i=1;i<=k;i++){
        ans.pb(t);
        ans.pb(1);
        s-=t+1;
    }ans.pb(t); s-=t;
    if(ans.size()==n){
        t=s/(n/2);
        for(int i=0;i<=n/2-1;i++){
            ans[i*2+1]+=t;
            s-=t;
        }
        t=0;
        while(s){
            ans[t*2+1]++;
            s--;
            t++;
        }
       if(n>1&&ans[1]==ans[0]) {cout << "-1\n";continue;}
    }
            else{
        t=ans.size();
        while(ans.size()<n){
            ans.pb(1);
            s--;
        }
        ans[t]+=s;
    }
    for(int i=0;i<=n-1;i++) cout << ans[i] << " \n"[i==n-1];
        }
       
    }
	
	return 0;
}

I 时空的交织

题目大意

选择一个子矩形，使得该子矩形所有元素的和尽可能大。

主要思路

假设选定的矩阵区间为 (r_i, r_j) : (c_i, c_j)，则子矩阵的和为：
在这里插入图片描述
问题转化为求数组 a 和 b 的一个非空连续子数组和乘积的最大值。

此外，a 数组和 b 数组的元素可以为负数，因此同时求出区间和的最大值和最小值，两两相乘取最大即可。

代码

#include<bits/stdc++.h>
#define debug(x) cout<<#x<<" = "<<x<<"\n"
using namespace std;

const int N = 1e5+10;
long long a[N],b[N];

int main()
{
    int n,m;
    long long maxzhi1=INT_MIN,maxzhi2=INT_MIN;
    cin>>n>>m;
    long long minzhi1=INT_MAX,minzhi2=INT_MAX;
    for(int i=0;i<n;++i)
    {
        cin>>a[i];
    }
    for(int i=0;i<m;++i)
    {
        cin>>b[i];
    }
    long long sum=0;
    long long sum2=0;
    for(int i=0;i<n;++i)
    {
        if(sum+a[i]>0)
        {
            sum+=a[i];
            maxzhi1=max(maxzhi1,sum);
        }
        else 
        {
            sum=0;
            maxzhi1=max(maxzhi1,a[i]);
        }
        //
        if(sum2+a[i]<0)
        {
            sum2+=a[i];
            minzhi1=min(minzhi1,sum2);
        }
        else 
        {
            sum2=0;
            minzhi1=min(minzhi1,a[i]);
        }
    }
///
    sum=0;
    sum2=0;
    for(int i=0;i<m;++i)
    {
        if(sum+b[i]>0)
        {
            sum+=b[i];
            maxzhi2=max(maxzhi2,sum);
        }
        else 
        {
            sum=0;
            maxzhi2=max(maxzhi2,b[i]);
        }
        /
        if(sum2+b[i]<0)
        {
            sum2+=b[i];
            minzhi2=min(minzhi2,sum2);
        }
        else 
        {
            sum2=0;
            minzhi2=min(minzhi2,b[i]);
        }
    }
    long long ans=INT_MIN;
    ans=max(ans,minzhi1*minzhi2);
    ans=max(ans,maxzhi1*maxzhi2);
    ans=max(ans,minzhi1*maxzhi2);
    ans=max(ans,maxzhi1*minzhi2);
    cout<<ans;
    return 0;
}

J 绝妙的平衡

题目大意

给定一棵有根树，若干个节点为红色。 为每个节点赋值1或2，使得每个以红色节点为根的子树，其节点值之和为3的倍数。

主要思路

对于每个红色节点，如果它没有白色子节点，则它的子树除它以外的和已经是的倍数，它为或都不可能再使它的子树和为的倍数。

如果它至少有1个白色子节点，则它和白色子节点可以配合使得它的子树和为的倍数。

因此，按DFS逆序遍历，白色节点先赋值为。若红色节点除其本身外，和不是的倍数，则用它补上；否则将任一白色子节点改为，它赋为。

代码

#include <bits/stdc++.h>
using namespace std;
const int N=100010;
vector<int> fa[N];
bool flag=1;
int sum[N];//每个根节点的子树权值之和
int tri[N]; //每个节点的值
char color[N];
int n;
void dfs(int u)
{
    bool st=0;
    if(color[u]=='R') st=1; //如果是红树先假设子树全为红树
    for(auto k:fa[u])  //遍历他的所有子树
    {
        dfs(k);  //搜索他的子树 
        if(color[k]=='W')  // 如果是白色假设条件不成立并且将这棵树的权值加到他的根节点  
        {
            st=0;
            sum[u]+=sum[k];  
        }
    }
    if(st) flag=0; //如果该节点为红色并且该结点的子树全为红色则不满足条件
}
void dfs1(int u)
{
    if(color[u]=='R')
    {
        if(sum[u]%3==1)
        {
            tri[u]=2;
            for(auto k:fa[u])
            {
                if(color[k]!='R')
                {tri[k]=2;break;}
            }
        }
        else if(sum[u]%3==2)
        {
            tri[u]=2;
        }
    }
    for(auto k:fa[u]) dfs1(k);
}
int main()
{
    cin>>n;
    cin>>color+1;
    for(int i=1;i<=n;i++)
    {
        tri[i]=1;
        sum[i]=1;
    }
    int p;
    for(int i=1;i<=n-1;i++)
    {
        cin>>p;
        fa[p].push_back(i+1);
    }
    dfs(1);  //判断是有解并且将每个根节点的权值计算出来
    if(!flag)
    {
        cout<<"-1"<<endl;
        return 0;
    }
    dfs1(1);
    for(int i=1;i<=n;i++)
        cout<<tri[i];
}

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

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

Kotlin 进阶版 协程

Kotlin 进阶版 协程

kotlin是协程的一种实现 Dispatchers.IO&#xff1a;适用于执行磁盘或网络 I/O 操作的调度器&#xff0c;例如文件读写、网络请求等。在 Android 中&#xff0c;Dispatchers.IO 会使用一个专门的线程池来处理这些操作&#xff0c;以防止阻塞主线程。 Dispatchers.Main&#xf…
阅读更多...
幻兽帕鲁服务器多少钱？有买过的吗？

幻兽帕鲁服务器多少钱？有买过的吗？

幻兽帕鲁服务器多少钱&#xff1f;太卷了&#xff0c;降价到24元1个月&#xff0c;阿里云4核16G10M游戏服务器26元1个月、149元半年&#xff0c;腾讯云4核16G游戏服务器32元、312元一年&#xff0c;华为云26元&#xff0c;京东云主机也是26元起。云服务器吧yunfuwuqiba.com给大…
阅读更多...
[RCTF2015]EasySQL1 题目分析与详解

[RCTF2015]EasySQL1 题目分析与详解

一、题目介绍&#xff1a; 1、题目来源&#xff1a; BUUCTF网址 2、题目介绍&#xff1a; 拿到flag。 二、解题思路&#xff1a; 我们发现题目首页有登录和注册账号两个选项&#xff0c;我们首先尝试注册账号&#xff0c;尝试注册username为admin的账号&#xff0c;输入密码…
阅读更多...
这10款设计工具，助你轻松搞定主视觉设计！

这10款设计工具，助你轻松搞定主视觉设计！

我们浏览网站、App或其他数字产品时&#xff0c;页面或屏幕上最显著最重要的部分&#xff0c;比如设计风格、颜色、排版、图片和元素等信息&#xff0c;就是数字产品的主视觉&#xff0c;也是用户首次接触产品时最能直观感受的部分。 由此可见&#xff0c;主视觉设计有多重要&…
阅读更多...
【大数据】Flink 内存管理（四）：TaskManager 内存分配（实战篇）

【大数据】Flink 内存管理（四）：TaskManager 内存分配（实战篇）

《Flink 内存管理》系列&#xff08;已完结&#xff09;&#xff0c;共包含以下 4 篇文章&#xff1a; Flink 内存管理&#xff08;一&#xff09;&#xff1a;设置 Flink 进程内存Flink 内存管理&#xff08;二&#xff09;&#xff1a;JobManager 内存分配&#xff08;含实际…
阅读更多...
PyTorch中Tensor（张量）数据结构内部观察

PyTorch中Tensor（张量）数据结构内部观察

上图中是一个张量embeds&#xff0c;打开其内部存储空间&#xff0c;我们可以看到内部的构成。在PyTorch中&#xff0c;Tensor 具有许多属性和方法。以下是其中一些关键的属性和方法&#xff1a; 属性&#xff1a; H&#xff1a; 在标准的PyTorch API中并没有直接表示为 .H 的…
阅读更多...
IO进程线程：共享内存

IO进程线程：共享内存

shmsnd.c #include<myhead.h> #define PAGE_SIZE 4096 //一页的大小 int main(int argc, const char *argv[]) {//1.创建key值key_t key-1;if((keyftok("/",k))-1){perror("ftok error");return -1;}printf("key%d\n",key);//2.通过key…
阅读更多...
【计算机网络】传输层——TCP和UDP详解

【计算机网络】传输层——TCP和UDP详解

文章目录 一. TCP和UDP简介二. UDP 协议详解1. UDP报文格式2. UDP的使用场景 三. TCP 协议详解1. TCP报文格式2. TCP协议的重要机制确认应答&#xff08;保证可靠传输的最核心机制&#xff09;超时重传连接管理&#xff08;三次握手、四次挥手&#xff09;&#xff01;&#xf…
阅读更多...
C语言 int和unsigned int逻辑比较

C语言 int和unsigned int逻辑比较

文章目录 测试1、测试 CMP (int,int)2、测试 CMP (int ,unsigned int)3、测试 CMP (unsigned int ,unsigned int) 总结 测试 在IAR(8.40.2)平台下测试单片机为STM32F103ZET6 1、测试 CMP (int,int) //a -2,b 3 int test_fun(int a, int b) {if(a>b){return 1;}else{re…
阅读更多...
[力扣 Hot100]Day35 LRU 缓存

[力扣 Hot100]Day35 LRU 缓存

题目描述 请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。 实现 LRUCache 类&#xff1a; LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存 int get(int key) 如果关键字 key 存在于缓存中&#xff0c;则返回关键字的值&#xff0c;否…
阅读更多...
Linux7.9环境源码编译安装ffmpeg6.x

Linux7.9环境源码编译安装ffmpeg6.x

1.官网ffmpeg下载源码 https://ffmpeg.org/download.html#build-windows 2.未安装x264库则先安装配置 可以先查询x264库: whereis libx264 安装编译工具和依赖库&#xff1a; sudo yum install gcc make cmake mercurial git yasm pkgconfig autoconf automake libtool sudo…
阅读更多...
【每日一题】938. 二叉搜索树的范围和-2024.2.26

【每日一题】938. 二叉搜索树的范围和-2024.2.26

题目&#xff1a; 938. 二叉搜索树的范围和 给定二叉搜索树的根结点 root&#xff0c;返回值位于范围 [low, high] 之间的所有结点的值的和。 示例 1&#xff1a; 输入&#xff1a;root [10,5,15,3,7,null,18], low 7, high 15 输出&#xff1a;32示例 2&#xff1a; 输入…
阅读更多...
Python实用技巧：输出列表（list）的倒序/逆序的几种方法

Python实用技巧：输出列表（list）的倒序/逆序的几种方法

Python实用技巧&#xff1a;输出列表&#xff08;list&#xff09;的倒序/逆序的几种方法 &#x1f4c5;2024年02月25日 &#x1f308; 个人主页&#xff1a;高斯小哥 &#x1f525; 高质量专栏&#xff1a;Matplotlib之旅&#xff1a;零基础精通数据可视化、Python基础【高质…
阅读更多...
力扣随笔之寻找重复数（中等287）

力扣随笔之寻找重复数（中等287）

思路1&#xff1a;暴力解法&#xff0c;根据要求不修改数组且只用常量级O(1)的额外空间&#xff0c;我们写两层嵌套循环&#xff0c;寻找重复的数;可以解决部分问题&#xff0c;但会超出时间限制无论Java还是C; Java实现&#xff1a; class Solution {public int findDuplicat…
阅读更多...
第四节：Vben Admin登录对接后端getUserInfo接口

第四节：Vben Admin登录对接后端getUserInfo接口

系列文章目录 第一节&#xff1a;Vben Admin介绍和初次运行 第二节&#xff1a;Vben Admin 登录逻辑梳理和对接后端准备 第三节&#xff1a;Vben Admin登录对接后端login接口 第四节&#xff1a;Vben Admin登录对接后端getUserInfo接口 文章目录 系列文章目录前言一、回顾Vben…
阅读更多...
Elastic Search的RestFul API入门：使用SQL查询ES

Elastic Search的RestFul API入门：使用SQL查询ES

确实，Elasticsearch 中也支持 SQL 语法，但我们通常使用 DSL 进行 API 操作，很少有人用 SQL 进行 Elasticsearch 的操作。然而，如果你刚开始学习 Elasticsearch，这一节的内容可以帮助你更快地理解 Elasticsearch（前提是你已经熟悉 SQL）。通过 SQL 查询，你可以进行一些简…
阅读更多...
HTTPS对HTTP的加密过程

HTTPS对HTTP的加密过程

1、HTTPS是在HTTP的基础上&#xff0c;引入了一个加密层&#xff08;SSL&#xff09;&#xff0c;对数据进行保护&#xff0c;HTTP 是明文传输的&#xff08;不安全&#xff0c;很可能会被运营商通过referer劫持&#xff0c;或者黑客通过修改链接来窃数据&#xff09; 2、加密…
阅读更多...
数字人的未来：数字人对话系统 Linly-Talker + 克隆语音 GPT-SoVITS

数字人的未来：数字人对话系统 Linly-Talker + 克隆语音 GPT-SoVITS

&#x1f680;数字人的未来&#xff1a;数字人对话系统 Linly-Talker 克隆语音 GPT-SoVITS https://github.com/Kedreamix/Linly-Talker 2023.12 更新 &#x1f4c6; 用户可以上传任意图片进行对话 2024.01 更新 &#x1f4c6; 令人兴奋的消息&#xff01;我现在已经将强…
阅读更多...
【数据结构】图——最短路径

【数据结构】图——最短路径

最短路径问题&#xff1a;从在带权有向图G中的某一顶点出发&#xff0c;找出一条通往另一顶点的最短路径&#xff0c;最短也就是沿路径各边的权值总和达到最小。 最短路径分为图中单源路径和多源路径。 本文会介绍Dijkstra和Bellman-Ford解决单源路径的问题 Floyd-Warshall解…
阅读更多...
实操 - openstack的自动化部署

实操 - openstack的自动化部署

一 、使用openstack自带的工具packstack部署allinone模式 此模式将所有的服务装在一个虚机中&#xff0c;用来测试 1.克隆一台虚拟机&#xff08;配置好七项&#xff09;virt-clone 2.下载openstack-packstack之前删除mariadb所有相关内容(可选项) #rpm -qa | grep mariad…
阅读更多...
最新文章

Copyright @ 2022~2023