当前位置: 首页 > news >正文

2024蓝桥杯——宝石问题

先展示题目

声明

以下代码仅是我的个人看法,在自己考试过程中的优化版,本人考试就踩了很多坑,我会—一列举出来。代码可能很多,但是总体时间复杂度不高只有0(N²)

函数里面的动态数组我没有写开辟判断和free,这里我忽略掉了。

正文

先直接抛出最后的代码:

 

我也觉得太长了,大家可以当做知识点的掌握来看吧。

从数据中取出n个数的问题-->可以拓展到取出所有子集问题

先讲子集问题

这个问题我们可以用三个for循环来做,但是时间复杂度太高了。所以我们有以下的方法。

一个数取不取就有两种情况。我们可以用0或1来表示。那么我们就可以用二进制来表示我们的取或不取,用每位二进制的位置来对于每个元素。

例如:有1 2 两个数字。我们就可以用两位二进制来表示:00 01 10 11分别表示 不取任何数 取2 取1 都取。一共有2^2次方中情况

那么我们推广到n,就有2^n种。

我们来尝试写一下代码。

直接用二进制

完全没问题。

用数组模拟二进制

这里有一个问题不知道大家看到没:2^n 容易溢出。因此我们可以用数组来模拟二进制的自增。

自增问题涉及到进一问题,所以我们需要运用到递归,递归的判断终止条件就是n+1位由0变成1。

所以我们需要开辟n+1长度的数组nums。

用类似递归来实现
用循环(最优解)

这里几个continue和return一定要有,不然逻辑就错了

这样的话我们就可以遍历任何长度的数组的子集了!

下面把代码给大家

#include<stdio.h>
#include<stdlib.h>

void nums_add(int* arr, int len) {
    if (len == 1) {
        *arr = 1;
        return;
    }
    else if (*arr == 1) {
        *arr = 0;//加一后变成零了
        nums_add(arr + 1, len - 1);//让后面一位加一,然后剩余长度减一
    }
    else if(*arr==0){
        *arr=1;//0加成1
    }
}

void nums_add_(int* arr, int len) {
    int k = len,i=0;
    while (1) {
        if (k == 1) {
            arr[i] = 1;//如果长度为1了就退出
            return;
        }
        if (arr[i] == 1) {
            arr[i] = 0;
            ++i;
            --k;
            continue;//如果要进一我们还要循环一次,所以用continue
        }
        else if (arr[i] == 0) {
            arr[i] = 1;
        }
        return;//到这里表示从0加到一,我们就不需要再循环了,直接结束循环
    }
}
int main() {
    int n = 0;
    scanf("%d", &n);
    int* arr = (int*)malloc(n * sizeof(int));
    if (!arr)return -1;
    for (int x = 0; x < n; ++x) {
        scanf("%d", arr + x);
    }

    int* nums = (int*)calloc(n+1, sizeof(int));
    int m[3];
    while (1) {
        nums_add_(nums, n + 1);
        if (nums[n] == 1)break;
        int k = 0;
        for (int x = 0; x < n; ++x) {
            if (nums[x] == 1)
            {
                if (k == 3)break;//已经有三个了还要存,直接跳过这个
                m[k++] = arr[x];
            }
        }
        if (k!=3)continue;//如果不等于三个,直接跳过到下一个循环
        printf("%d %d %d",m[0],m[1],m[2]);
        printf("\n");
    }
    return 0;
}

因为递归会开辟内存,所以后面的代码我们都用第二种非递归的

取出长度固定的所有子集

如果我们只要里面长度为3的子集怎么办呢?

自增变量来判断

我们可以在for循环里面先用一个长度为三的数组来存储我们的数据,再用一个变量来看是否满足。满足就打印。

在递归/非递归的时候就检测好

递归的时候我们完全就可以把1的数量统计好,所以可以做以下改变

但是这样也没怎么变化嘛,那么我们既然可以知道1了,我们再储存一下有1的数组的位置可以吧?

这里我们发现是反着来的,我们把打印的顺序反过来就行了。因为这里的m数组相当于栈

#include<stdio.h>
#include<stdlib.h>

void nums_add(int* begain_arr, int* arr, int* m, int* p, int len, int* number) {
    if (len == 1) {
        *arr = 1;
        return;
    }
    else if (*arr == 1) {
        *arr = 0;//加一后变成零了
        --(*number);
        if (*p>0) {
            --p;
        }
        nums_add(arr,arr + 1,m,p, len - 1,number);//让后面一位加一,然后剩余长度减一
    }
    else if(*arr==0){
        ++(*number);
        *arr=1;//0加成1
        if (*p < 3) {
            m[(*p)++] = (int)(arr - begain_arr);
        }
    }
}

void nums_add_(int* arr,int*m,int *p,int len, int*number) {
    int k = len,i=0;
    while (1) {
        if (k == 1) {
            arr[i] = 1;//如果长度为1了就退出
            return;
        }
        if (arr[i] == 1) {
            arr[i] = 0;
            --(*number);
            ++i;
            --k;
            if (*p>0) {
                --(*p);
            }
            continue;//如果要进一我们还要循环一次,所以用continue
        }
        else if (arr[i] == 0) {
            arr[i] = 1;
            ++(*number);
            if (*p < 3) {
                m[(*p)++] =i;
            }
        }
        return;//到这里表示从0加到一,我们就不需要再循环了,直接结束循环
    }
}
int A_(int m, int n) {//非递归型
    int k = 1, i = m, j = n;
    while (1) {
        if (i == 1)return k * j;
        else {
            k *= j;
            --i;
            --j;
        }
    }
}
int C_(int m, int n) {
    return m == 0 ? 1 : A_(m, n) / A_(m, m);
}
int main() {
    int n = 0;
    scanf("%d", &n);
    int* arr = (int*)malloc(n * sizeof(int));
    if (!arr)return -1;
    for (int x = 0; x < n; ++x) {
        scanf("%d", arr + x);
    }

    int* nums = (int*)calloc(n+1, sizeof(int));
    int m[3] , p = 0 , number1 = 0;//定义number1存储我们的1的数量
    while (1) {
        nums_add_(nums,m,&p, n + 1, &number1);
        if (nums[n] == 1)break;
        int k = 0;
        if (number1 != 3)continue;
        printf("%d %d %d",m[2],m[1],m[0]);
        printf("\n");
    }
    return 0;
}

那么我们第一部分终于也是完成了,我嘞个豆真是多!!!!!!!!!!!!!!!!!!!!!!!!!

a,b的最小公倍数和最大公约数

我们题目要求的是最小公倍数,那么求这个我们可以枚举,但是时间复杂度复很高,所以我们就有特殊的算法。

我们首先要了解一个知识点就是

a*b=最大公约数(a,b)*最小公倍数(a,b)

我们求最小公倍数可能没有优秀的算法,但是我们最大公约数有优秀的算法。那么就可以通过这个式子进行转化。

辗转相除法求最大公约数

举个例子:求16 和 24的最大公约数

                24%16 =8

                16%8 = 0

                所以答案是8 

如果开始两个数字交换呢?

                16%24=16

                24%16=8 

                16%8=0

我们发现就是多了一部,没有太大差别。

那么我们开始实现

这里return的是最大公约数。

如果求三者的最大公约数或者最小公倍数,把其中两个数的先求出来,再看成整体和另一个求。

S

那么图中的表达式我们就可以算了

这里同样的,先除法再乘法,防止溢出了。

创建二维数组来存储三个都是1的数据。

我们就要用一个二维数组来储存我们的数据。那么每一个数组的长度是多少呢?

根据组合数我们要C(3,n)长度。排列组合在编程里面也很常见,我们也要知道他是怎么算出来的,排列组合我在下面讲到

排列组合函数

先是讲A(m,n)

如果m=n,那么就是算的阶乘。

我们可以通过A(m,n)=A(m-1,n-1)*n   来计算

C(m,n)

它有两个公式可以算,一个是C(m,n)=A(m,n)/A(n,n)  另一个是C(m,n)=n!/m!/(n-m)!

那么那个好呢?当然是第一个,第一个数字间相乘的次数少,不容易溢出。

储存后方便我们后面再取。

我们再用一个变量来存储S的最大值

那么我们的宝石问题就完成了。

真的完成了吗?

no no no

存储根本不需要二维数组,我写到这才发现,我们只要用一个长度为3个数组来储存最大的数据就行了

那么我们的排列组合函数就不需要了。

另外补充

我们m数组的长度定义的太短了,会产生越界访问。所以可以将m数组的长度定义长一点。可以和arr的数组一样长.

提前排序来解决字典序要求

我们的代码已经可以计算了,但是还有最后一个坑。例如我们逆向输入

因为S(5,4,3)和S(1,2,3)的值是一样的,所以我们不会存后面字典序小的数据。我们最要先将数据进行排序。

这里我们光速搓一个快排出来

在计算之前排好序就行了。

最终的代码

相关文章:

2024蓝桥杯——宝石问题

先展示题目 声明 以下代码仅是我的个人看法&#xff0c;在自己考试过程中的优化版&#xff0c;本人考试就踩了很多坑&#xff0c;我会—一列举出来。代码可能很多&#xff0c;但是总体时间复杂度不高只有0(N) 函数里面的动态数组我没有写开辟判断和free&#xff0c;这里我忽略…...

three.js加载模型报错,Error: THREE.GLTFLoader: No DRACOLoader instance provided.

three.js加载模型报错&#xff0c;Error: THREE.GLTFLoader: No DRACOLoader instance provided. 原因&#xff1a;该模型是压缩过的&#xff0c;需要 DRACOLoader 我们先找到该文件夹 node_modules three examples jsm libs draco 将draco拷贝到public下 import { GLTFLoad…...

Spring VS Spring Boot

目录 定义 Spring Spring Boot 区别 优劣对比 Spring Spring的优势 Spring的劣势 Spring Boot Spring Boot的优势 Spring Boot的劣势 适用场景 Spring的适用场景 Spring Boot的适用场景 初学者如何选择学习 定义 Spring Spring是一个轻量级的、开源的Java开发…...

Linux入门(Linux介绍,安装,常用命令,防火墙的设置,注意事项)

目录 一、Linux介绍 1. Linux简介 1 什么是Linux 2 Linux的应用 3 为什么要学习Linux 2. Linux分类 1 按照市场需求分 2 按照原生程度分 3.小结 二、Linux安装 1. vmware介绍 2. 安装VMWare 3. 安装CentOS 4. 登录查看ip 5. 远程连接工具 1 使用FinalShell连接L…...

vue2创建项目的两种方式,配置路由vue-router,引入element-ui

提示&#xff1a;vue2依赖node版本8.0以上 文章目录 前言一、创建项目基于vue-cli二、创建项目基于vue/cli三、对吧两种创建方式四、安装Element ui并引入五、配置路由跳转四、效果五、参考文档总结 前言 使用vue/cli脚手架vue create创建 使用vue-cli脚手架vue init webpack创…...

MySql 表中的id突然变很大,如何给id重新排序

目录 一、场景 二、解决方法 一、场景 我们在开发过程中&#xff0c;难免遇到id突然增大的情况。 由于id突然增大很多&#xff0c;我们重新增加数据时候id会默认加1 那么如何让id 重新从1按顺序排序呢 二、解决方法 点击编辑表&#xff0c;然后新建一个字段id2&#xff0c;将…...

leetcode练习——哈希表

目录 3. 无重复字符的最长子串 题目描述 解题思路 代码实现 349. 两个数组的交集 题目描述 解题思路 代码实现 ​​​​454. 四数相加 II 题目描述 解题思路 代码实现 242. 有效的字母异位词 题目描述 解题思路 代码实现 438. 找到字符串中所有字母异位词 题目…...

配置交换机 SSH 管理和端口安全

实验1:配置交换机基本安全和 SSH管理 1、实验目的 通过本实验可以掌握&#xff1a; 交换机基本安全配置。SSH 的工作原理和 SSH服务端和客户端的配置。 2、实验拓扑 交换机基本安全和 SSH管理实验拓扑如图所示。 3、实验步骤 &#xff08;1&#xff09;配置交换机S1 Swit…...

基于SpringBoot+Vue的装饰工程管理系统(源码+文档+包运行)

一.系统概述 如今社会上各行各业&#xff0c;都喜欢用自己行业的专属软件工作&#xff0c;互联网发展到这个时候&#xff0c;人们已经发现离不开了互联网。新技术的产生&#xff0c;往往能解决一些老技术的弊端问题。因为传统装饰工程项目信息管理难度大&#xff0c;容错率低&a…...

vue3中axios添加请求和响应的拦截器

本章主要是以记录为主。 在src创建一个utils文件夹&#xff0c;并在utils中创建一个request.js文件。 // 引入axios import axios from "axios"; // import qs from "qs"; // 创建axios实例 const instance axios.create(); // 请求拦截器 instance.int…...

<router-link>出现Error: No match for {“name“:“home“,“params“:{}}

在将<a></a>标签换到<router-link></router-link>的时候出现No match for {"name":"home","params":{}}这样的错误&#xff0c;其中格式并无错误&#xff0c; <router-link class"navbar-brand active" …...

prompt 工程整理(未完、持续更新)

工作期间会将阅读的论文、一些个人的理解整理到个人的文档中&#xff0c;久而久之就积累了不少“个人”能够看懂的脉络和提纲&#xff0c;于是近几日准备将这部分略显杂乱的内容重新进行梳理。论文部分以我个人的理解对其做了一些分类&#xff0c;并附上一些简短的理解&#xf…...

兼容性测试用例

备注:本文为博主原创文章,未经博主允许禁止转载。如有问题,欢迎指正。 个人笔记(整理不易,有帮助,收藏+点赞+评论,爱你们!!!你的支持是我写作的动力) 笔记目录:学习笔记目录_pytest和unittest、airtest_weixin_42717928的博客-CSDN博客 个人随笔:工作总结随笔_8、…...

阿里云4核8G云服务器价格多少钱?700元1年

阿里云4核8G云服务器价格多少钱&#xff1f;700元1年。阿里云4核8G服务器租用优惠价格700元1年&#xff0c;配置为ECS通用算力型u1实例&#xff08;ecs.u1-c1m2.xlarge&#xff09;4核8G配置、1M到3M带宽可选、ESSD Entry系统盘20G到40G可选&#xff0c;CPU采用Intel(R) Xeon(R…...

ts 中的keyof 和typeof

作用&#xff1a; keyof&#xff1a;用于获取对象类型的所有键的联合类型。typeof&#xff1a;用于获取变量或表达式的类型。 返回类型&#xff1a; keyof&#xff1a;返回的是一个对象类型的所有键组成的联合类型。typeof&#xff1a;返回的是一个值的类型。 使用场景&#xf…...

每日一题:买卖股票的最佳时机II

给你一个整数数组 prices &#xff0c;其中 prices[i] 表示某支股票第 i 天的价格。 在每一天&#xff0c;你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买&#xff0c;然后在 同一天 出售。 返回 你能获得的 最大 利润 。 示例 1&a…...

nginx安装在linux上

nginx主要用于反向代理和负载均衡&#xff0c;现在简单的说说如何在linux操作系统上安装nginx 第一步&#xff1a;安装依赖 yum install -y gcc-c pcre pcre-devel zlib zlib-devel openssl openssl-devel 第二步&#xff1a; 下载nginx&#xff0c;访问官网&#xff0c;ngin…...

ENSP-旁挂式AC

提醒&#xff1a;如果AC不能成功上线AP&#xff0c;一般问题不会出在AC上&#xff0c;优先关注AC-AP线路上的二层或三层组网的三层交换机 拓扑图 管理VLAN&#xff1a;99 | 业务VLAN&#xff1a;100 注意点&#xff1a; 1.连接AP的接口需要打上pvid为管理vlan的标签 2.AC和…...

如何获取手机root权限?

获取手机的 root 权限通常是指在 Android 设备上获取超级用户权限&#xff0c;这样用户就可以访问和修改系统文件、安装定制的 ROM、管理应用权限等。然而&#xff0c;需要注意的是&#xff0c;获取 root 权限可能会导致手机失去保修、安全性降低以及使系统变得不稳定。在获取 …...

2023年全国青少年信息素养大赛(Python)海南赛区复赛真题

2023年全国青少年信息素养大赛(Python)海南赛区复赛真题第1题,整数加8 题目描述: 输入一个整数,输出这个整数加8 的结果。 输入描述: 输入一行一个正整数。 输出描述: 输出求和的结果。 样例1: 输入: 5 输出: 13 x= int(input()) print(x+8) 第2题,哼哈二将 题目描…...

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする

日语学习-日语知识点小记-构建基础-JLPT-N4阶段(33):にする 1、前言(1)情况说明(2)工程师的信仰2、知识点(1) にする1,接续:名词+にする2,接续:疑问词+にする3,(A)は(B)にする。(2)復習:(1)复习句子(2)ために & ように(3)そう(4)にする3、…...

k8s从入门到放弃之Ingress七层负载

k8s从入门到放弃之Ingress七层负载 在Kubernetes&#xff08;简称K8s&#xff09;中&#xff0c;Ingress是一个API对象&#xff0c;它允许你定义如何从集群外部访问集群内部的服务。Ingress可以提供负载均衡、SSL终结和基于名称的虚拟主机等功能。通过Ingress&#xff0c;你可…...

Day131 | 灵神 | 回溯算法 | 子集型 子集

Day131 | 灵神 | 回溯算法 | 子集型 子集 78.子集 78. 子集 - 力扣&#xff08;LeetCode&#xff09; 思路&#xff1a; 笔者写过很多次这道题了&#xff0c;不想写题解了&#xff0c;大家看灵神讲解吧 回溯算法套路①子集型回溯【基础算法精讲 14】_哔哩哔哩_bilibili 完…...

2.Vue编写一个app

1.src中重要的组成 1.1main.ts // 引入createApp用于创建应用 import { createApp } from "vue"; // 引用App根组件 import App from ./App.vue;createApp(App).mount(#app)1.2 App.vue 其中要写三种标签 <template> <!--html--> </template>…...

转转集团旗下首家二手多品类循环仓店“超级转转”开业

6月9日&#xff0c;国内领先的循环经济企业转转集团旗下首家二手多品类循环仓店“超级转转”正式开业。 转转集团创始人兼CEO黄炜、转转循环时尚发起人朱珠、转转集团COO兼红布林CEO胡伟琨、王府井集团副总裁祝捷等出席了开业剪彩仪式。 据「TMT星球」了解&#xff0c;“超级…...

工程地质软件市场:发展现状、趋势与策略建议

一、引言 在工程建设领域&#xff0c;准确把握地质条件是确保项目顺利推进和安全运营的关键。工程地质软件作为处理、分析、模拟和展示工程地质数据的重要工具&#xff0c;正发挥着日益重要的作用。它凭借强大的数据处理能力、三维建模功能、空间分析工具和可视化展示手段&…...

Rapidio门铃消息FIFO溢出机制

关于RapidIO门铃消息FIFO的溢出机制及其与中断抖动的关系&#xff0c;以下是深入解析&#xff1a; 门铃FIFO溢出的本质 在RapidIO系统中&#xff0c;门铃消息FIFO是硬件控制器内部的缓冲区&#xff0c;用于临时存储接收到的门铃消息&#xff08;Doorbell Message&#xff09;。…...

【Android】Android 开发 ADB 常用指令

查看当前连接的设备 adb devices 连接设备 adb connect 设备IP 断开已连接的设备 adb disconnect 设备IP 安装应用 adb install 安装包的路径 卸载应用 adb uninstall 应用包名 查看已安装的应用包名 adb shell pm list packages 查看已安装的第三方应用包名 adb shell pm list…...

华为OD最新机试真题-数组组成的最小数字-OD统一考试(B卷)

题目描述 给定一个整型数组,请从该数组中选择3个元素 组成最小数字并输出 (如果数组长度小于3,则选择数组中所有元素来组成最小数字)。 输入描述 行用半角逗号分割的字符串记录的整型数组,0<数组长度<= 100,0<整数的取值范围<= 10000。 输出描述 由3个元素组成…...

STM32标准库-ADC数模转换器

文章目录 一、ADC1.1简介1. 2逐次逼近型ADC1.3ADC框图1.4ADC基本结构1.4.1 信号 “上车点”&#xff1a;输入模块&#xff08;GPIO、温度、V_REFINT&#xff09;1.4.2 信号 “调度站”&#xff1a;多路开关1.4.3 信号 “加工厂”&#xff1a;ADC 转换器&#xff08;规则组 注入…...