枚举（蓝桥练习）（反倍数、特别数的和、找到最多的数、小蓝的漆房、小蓝和小桥的挑战）

目录

一、枚举算法介绍

二、解空间的类型

三、循环枚举解空间

四、例题

（一、反倍数）

（二、特别数的和）

（三、找到最多的数）

（四、小蓝的漆房）

（五、小蓝和小桥的挑战）

一、枚举算法介绍

枚举算法是一种基本的算法思想，它通过穷举所有可能的情况来解决问题。它的基本思想是将问题的解空间中的每个可能的解都枚举出来，并进行验证和比较，找到满足问题条件的最优解或者所有解。
枚举算法适用于问题规模较小、解空间可穷举的情况。它的优点是简单直观，不需要复杂的数学推导，易于实现。但是，由于需要穷举所有可能的情况，对于问题规模较大的情况，枚举算法的时间复杂度可能会非常高，效率较低。

二、解空间的类型

解空间可以是一个范围内的所有数字(或二元组、字符串等数据)，或者满足某个条件的所有数字。
当然也可以是解空间树，一般可分为子集树和排列树，针对解空间树，需要使用回溯法进行枚举(在后面讲到搜索的时候会讲到)。
我们目前仅使用循环去暴力枚举解空间，具体的解空间类型需要根据题目来理解构造。

三、循环枚举解空间

1.首先确定解空间的维度，即问题中需要枚举的变量个数。例如当题目要求的是满足条件的数字时，我们可以循环枚举某个范围内的数字。如果要求的是满足条件的二元组，我们可以用双重循环分别枚举第一个和第二个变量，从而构造出一个二元组。
2.对于每个变量，确定其可能的取值范围。这些范围可以根据问题的性质和约束条件来确定。
这一步往往是时间复杂度优化的关键。
3.在循环体内，针对每个可能解进行处理。可以进行问题的验证、计算、输出等操作

四、例题

（一、反倍数）

用户登录

题目描述
给定三个整数 a,b,c，如果一个整数既不是 a的整数倍也不是b的整数倍还不是 c的整数倍，则这个数称为反倍数。
请问在 1至 n 中有多少个反倍数。
输入描述
输入的第一行包含一个整数 n。
第二行包含三个整数 a,b,c，相邻两个数之间用一个空格分隔。其中，1≤n<1000000，1≤a≤n,1≤b≤n,1≤c≤n
输出描述
输出一行包含一个整数，表示答案。

#define  _CRT_SECURE_NO_WARNINGS 1
#include<bits/stdc++.h>
using namespace std; // 使用std命名空间，以便直接使用cout、cin等，而不是std::cout、std::cin

int a, b, c;

bool f(int x)
{
    return x % a != 0 && x % b != 0 && x % c != 0;
}

int main()
{
    int n; cin >> n;
    cin >> a >> b >> c;
    int ans = 0;
    for (int i = 1; i <= n; ++i)
    {
        if (f(i))ans ++;
    }
    cout << ans << '\n';
    return 0;
}

（二、特别数的和）

用户登录

题目描述
小明对数位中含有 2、0、1、9的数字很感兴趣(不包括前导 0)，在1到40 中这样的数包括 1、2、9、10 至 32、39 和 40，共 28 个，他们的和是574。
请问，在1到n中，所有这样的数的和是多少?
输入描述
输入格式:
输入一行包含两个整数 n(1≤n≤ 104)
输出描述
输出一行，包含一个整数，表示满足条件的数的和。

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

bool f(int x)
{
    while (x)
    {
        int y = x % 10; //个位数
        if (y == 2 || y == 0 || y == 1 || y == 9)return true;
        x /= 10; //缩小十倍,向下取整
    }
    return false;
}

int main()
{
    int n; cin >> n;
    int ans = 0;
    for (int i = 1; i <= n; ++i)
    {
        if (f(i))ans += i;
    }
    cout << ans << '\n';
    return 0;
}

（三、找到最多的数）

用户登录

题目描述
小明对数位中含有 2、0、1、9的数字很感兴趣(不包括前导 0)，在1到40 中这样的数包括 1、2、9、10 至 32、39 和 40，共 28 个，他们的和是574。
请问，在1到n 中，所有这样的数的和是多少?
输入描述
输入格式:
输入一行包含两个整数n(1≤n≤ 104)

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

bool f(int x)
{
    while (x)
    {
        int y = x % 10;
        if (y == 2 || y == 0 || y == 1 || y == 9)return true;
        x /= 10;
    }
    return false;
}

int main()
{
    int n; cin >> n;
    int ans = 0;
    for (int i = 1; i <= n; ++i)
    {
        if (f(i))ans += i;
    }
    cout << ans << '\n';
    return 0;
}

（四、小蓝的漆房）

用户登录

问题描述
小蓝是一位有名的漆匠，他的朋友小桥有一个漆房，里面有一条长长的走廊，走廊两旁有许多相邻的房子，每间房子最初被涂上了一种颜色。
小桥来找小蓝，想让他把整个走廊都涂成同一个颜色。小蓝告诉小桥，他每天只能涂一段长度为ん的区间。对于每个区间，他可以选择将其中的房子重新涂上任何一种颜色，或者保持原来的颜色不变
小桥想知道小蓝至少要涂几天，才能让整个走廊变得美丽。
请帮助小桥解决这个问题。
输入格式
第一行包含一个整数t(1< 100)，表示测试用例的数量.
每个测试用例的第一行包含两个整数 n 和 k(1 ≤ k≤n< 104)，第二行包含几 个整数 a1,a2,···,an(1 < ai< 60)，分别表示每个房子最初的颜色。
保证所有测试用例中 n 的总和不超过 10000。

首先，我们可以枚举整个走廊需要被涂上的颜色。因为颜色的种类数最多只有 60，所以我们可以尝试枚举每一种颜色。

对于每种颜色，我们需要计算涂上它需要的最少天数。我们可以从左到右遍历每个房子，如果该房子的颜色不是当前正在涂的颜色，那么我们就从该房子开始，向右涂 k 个房子，直到将该区间都涂上目标颜色。具体来说，我们可以用另一个数组 b 来记录当前的涂漆情况，每次枚举涂漆区间时，都将 b 数组中对应的区间涂成目标颜色。

在涂漆过程中，我们需要记录涂漆的天数 cnt，每当涂漆颜色发生变化时，我们就需要增加一天。最终，我们可以对所有颜色涂上所需的天数取最小值，该最小值即为答案。

综上所述，解题步骤如下：

  1. 枚举整个走廊需要被涂上的颜色；
  2. 对于每种颜色，计算涂上它需要的最少天数：从左到右遍历每个房子，如果该房子的颜色不是当前正在涂的颜色，那么就从该房子开始，向右涂 k 个房子，直到将区间涂上目标颜色，同时记录涂漆天数 cnt，每当涂漆颜色发生变化时，增加一天；
  3. 将所有颜色涂上所需的天数取最小值，即为答案。
#include <bits/stdc++.h>

void solve(const int &Case) {
    int n, k;
    std::cin >> n >> k;
    std::vector<int> a(n);
    for (auto &x: a)std::cin >> x; //range-for-each
    int ans = n + 1; // 初始化答案ans为一个大于n的值，以便后续取最小值  
    for (int c = 1; c <= 60; c++) {//枚举最终颜色
        int ret = 0;//存放当前最终颜色
        for (int i = 0; i < n; i++) {
            if (a[i] != c) { 
            // 如果出现一个与最终颜色不同的位置, 则贪心地选择该位置为染色的起点
                //i,i + 1,i + 2,...,i +k - 1 都会被立刻染成最终颜色
                ret++;
                i = i + k - 1;
            }
        }
        ans = std::min(ans, ret);
    }
    std::cout << ans << '\n';
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    int T = 1;
    std::cin >> T;
    for (int i = 1; i <= T; i++)solve(i);
    return 0;
}

（五、小蓝和小桥的挑战）

用户登录

解题思路

这道题的解题思路比较简单，具体步骤如下：

  1. 读入测试数据的数量 t，对于每组测试数据，读入物品数量 n 和物品价值 1,2,⋯,a1​,a2​,⋯,an​。

  2. 统计价值为 0 的物品个数 z，并计算物品的价值和 sum。如果序列中存在 00，则我们需要对所有的 0 进行一次操作，使得其变为 1，这样才能保证价值积不为 0。因此，我们至少需要进行 z 次操作。

  3. 对于经过操作后的序列，统计其所有元素的和 sum。如果sum≠0，则此时的序列已经满足题目要求，输出操作次数 z 即可。

  4. 如果 sum=0，则我们需要对任意一个 ai​>0，并对其进行一次操作，使得 ai​++，因为只要序列中存在正整数，我们就可以利用这些正整数来使得序列的价值积不为 00。如果序列中不存在 ai​>0，则我们需要对任意一个元素进行一次操作，使得序列中至少有一个非 0 的元素，然后再按照上述方法进行操作。因此，此时的操作次数为 z+1。

#define  _CRT_SECURE_NO_WARNINGS 1
#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10;
int a[N], t, n;
int main()
{
	cin >> t;
	while (t--)
	{
		cin >> n;
		int sum = 0, z = 0;
		for (int i = 1; i <= n; ++i)
		{
			cin >> a[i],sum += a[i];
			if (!a[i])++z;//如果a[i] == 0,执行一次操作
		}
		sum += z;//输入的数 + 执行加一后的次数
		if (sum == 0)//如果和为0
		cout << z + 1 << '\n';
		else cout << z << '\n';
	}
	return 0;
}

 乘积和加法的和都不为0
 如果只考虑乘积不为0
 如果乘积为0,则说明存在零(zero)元素
 此时的答案一定是所有零(zero)元素都加一
 如果只考虑加法为0, 那么随便选择一个数加一
 回到原问题, 同时考虑乘法和加法
 1.乘积为0, 且加法也为0
 此时将所有零(zero)元素加一即可
 2.乘积为0, 加法不为0
 2.1.乘积为0, 加法不等于零(zero)元素的个数的相反数
 此时将所有零(zero)元素加一即可
 2.2.乘积为0, 加法等于零(zero)元素的个数的相反数
 此时将所有0元素加一后, 再选择一个数加一
 3.乘积不为0,加法为0
 此时将某个正数加一即可
 4.乘积不为0,加法也不为0
 不动

#include <bits/stdc++.h>
void solve(const int &case)
{
  int n;
  std::cin >> n;
  int zeroCount = 0, sum = 0; // zeroCount 记录0的个数，sum 记录所有整数的和  
    for (int i = 0; i < n; i++) {  
        int x;  
        std::cin >> x; // 输入一个整数  
        if (x == 0) zeroCount++; // 如果输入的整数是0，zeroCount自增  
        sum += x; // 将输入的整数累加到sum上  
    }  
    // 如果存在0，则至少需要zeroCount次操作将0变为非0数（每次操作可以将一个0变成任意非0数）  
    // 如果不存在0，但所有数的和为0，则至少需要1次操作（将所有数同时加上一个非0数）  
    // 如果既不存在0，所有数的和也不为0，则不需要操作  
    if (zeroCount > 0) {  
        std::cout << zeroCount << '\n'; // 输出将0变成非0数的最少操作次数  
    } else if (sum == 0) {  
        std::cout << 1 << '\n'; // 输出将所有数和变成非0数的最少操作次数（1次）  
    } else {  
        std::cout << 0 << '\n'; // 不需要操作，直接输出0  
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);// 取消读入输出的同步流, 取消后不能使用 scanf和printf
    int T = 1;
    std::cin >> T;
    for (int i = 1; i <= T; i++)solve(i);
    return 0;
}

今天就先到这了！！！

看到这里了还不给博主扣个：
⛳️ 点赞☀️收藏 ⭐️ 关注！

你们的点赞就是博主更新最大的动力！
有问题可以评论或者私信呢秒回哦。

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

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

相关文章

Linpmem：一款功能强大的Linux物理内存提取工具

Linpmem：一款功能强大的Linux物理内存提取工具

关于Linpmem Linpmem是一款功能强大的Linux物理内存提取工具&#xff0c;该工具专为x64 Linux设计&#xff0c;可以帮助广大研究人员在执行安全分析过程中快速读取Linux物理内存数据。 该工具类似Windows下的Winpmem&#xff0c;Linpmem不是一个传统的内存转储工具&#xff0…
阅读更多...
scons，一个实用的 Python 构建工具！

scons，一个实用的 Python 构建工具！

目录 前言 什么是SCons库&#xff1f; 安装SCons库 使用SCons库 SCons库的功能特性 1. 基于Python的构建描述语言 2. 自动化依赖管理 3. 多种构建环境支持 SCons库的应用场景 1. C/C项目构建 2. Python项目构建 3. 嵌入式系统开发 4. 持续集成环境 5. 跨平台项目构建 总…
阅读更多...
如何实现无公网ip远程访问本地安卓Termux部署的MySQL数据库【内网穿透】

如何实现无公网ip远程访问本地安卓Termux部署的MySQL数据库【内网穿透】

文章目录 前言1.安装MariaDB2.安装cpolar内网穿透工具3. 创建安全隧道映射mysql4. 公网远程连接5. 固定远程连接地址 前言 Android作为移动设备&#xff0c;尽管最初并非设计为服务器&#xff0c;但是随着技术的进步我们可以将Android配置为生产力工具&#xff0c;变成一个随身…
阅读更多...
【InternLM 实战营笔记】大模型评测

【InternLM 实战营笔记】大模型评测

随着人工智能技术的快速发展&#xff0c; 大规模预训练自然语言模型成为了研究热点和关注焦点。OpenAI于2018年提出了第一代GPT模型&#xff0c;开辟了自然语言模型生成式预训练的路线。沿着这条路线&#xff0c;随后又陆续发布了GPT-2和GPT-3模型。与此同时&#xff0c;谷歌也…
阅读更多...
Failed to build tree: parent link [base_link] of joint [lidar_joint] not found

Failed to build tree: parent link [base_link] of joint [lidar_joint] not found

参考&#xff1a; Failed to build tree: parent link [base_link] of joint 在古月居gazebo 的基础教程里&#xff0c;运行古月居的mbot的launch文件报错&#xff0c;小机器人不出现。 主要原因是提供的xacro文件的宏定义没有放在xacro的命名空间。 解决&#xff1a; 将<mb…
阅读更多...
Linux系统编程之线程互斥锁的使用方法

Linux系统编程之线程互斥锁的使用方法

文章目录 一、Linux上线程开发互斥锁概要二、创建及销毁互斥锁2.1 示例&#xff1a;主线程等待两个线程退出&#xff0c;1线程和2线程打印信息 三、互斥量的初始化问题 一、Linux上线程开发互斥锁概要 互斥量&#xff08;mutex&#xff09;从本质上来说是一把锁&#xff0c;在…
阅读更多...
小白水平理解面试经典题目leetcode 606. Construct String from Binary Tree【递归算法】

小白水平理解面试经典题目leetcode 606. Construct String from Binary Tree【递归算法】

Leetcode 606. 从二叉树构造字符串 题目描述 例子 小白做题 坐在自习室正在准备刷题的小白看到这道题&#xff0c;想想自己那可是没少和白月光做题呢&#xff0c;也不知道小美刷题刷到哪里了&#xff0c;这题怎么还没来问我&#xff0c;难道是王谦谦去做题了&#xff1f; 这…
阅读更多...
Dockerfile（6） - EXPOSE 指令详解

Dockerfile（6） - EXPOSE 指令详解

EXPOSE 通知 Docker 容器在运行时监听指定的网络端口 EXPOSE 端口号 EXPOSE 端口号/协议 默认协议是 TCP 同时在 TCP、UDP 上暴露端口 EXPOSE 80/tcp EXPOSE 80/udp EXPOSE 原理 个人理解&#xff1a;EXPOSE 暴露的端口更像是指明了该容器提供的服务需要用到的端口EXPOSE…
阅读更多...
【比较mybatis、lazy、sqltoy、lambda、操作数据 】操作批量新增、分页查询

【比较mybatis、lazy、sqltoy、lambda、操作数据 】操作批量新增、分页查询

orm框架使用Lambda性能比较 环境&#xff1a; idea jdk17 spring boot 3.0.7 mysql 8.0测试条件常规对象 orm 框架是否支持xml是否支持 Lambda对比版本mybatis☑️☑️3.5.4sqltoy☑️☑️5.2.98lazy✖️☑️1.2.3-JDK17 数据库表(含有唯一性索引s_u) CREATE TABLE sys_u…
阅读更多...
机器学习｜线性回归

机器学习｜线性回归

线性回归是尝试使用一条直线去拟合出图上的节点。 e i e_i ei​为第i个点构成的误差&#xff0c;使用平方的好处一是可以避免正负抵消&#xff0c;二是平方有利于放大大于1的误差的影响&#xff0c;同时缩小误差小于1的影响。 将平方项进行展开&#xff0c;以w作为变元&…
阅读更多...
Floyd算法、Dijkstra算法、基础拓扑排序

Floyd算法、Dijkstra算法、基础拓扑排序

Floyd算法 Dijkstra算法 基础拓扑排序
阅读更多...
简单了解B树和B+树

简单了解B树和B+树

目录 B树 B树 B树和B树的结构示意图 总结 B树和B树是两种非常重要的树状数据结构&#xff0c;它们广泛应用于数据库和文件系统的索引结构中。这两种数据结构能够帮助我们高效地管理、查询以及更新大量的数据。下面&#xff0c;我将简单介绍它们,以及他们之间的区别。 B树 B…
阅读更多...
内存飙高问题如何排查？

内存飙高问题如何排查？

目录 1、查看日志 2、查看GC情况 3、分析堆内存对象占用情况 4、分析堆内存快照文件 内存飙高如果发生在java进程上&#xff0c;一般情况是因为创建了大量对象导致&#xff0c;持续飙高说明垃圾回收跟不上对象创建的速度&#xff0c;或者内存泄漏导致对象无法被回收&#x…
阅读更多...
unity学习（42）——创建（create）角色脚本（panel）——UserHandler（收）+CreateClick（发）——服务器收包2

unity学习（42）——创建（create）角色脚本（panel）——UserHandler（收）+CreateClick（发）——服务器收包2

1.解决上一次留下的问题&#xff1a; log和reg的时候也有session&#xff0c;输出看一下这两个session是同一个不&#xff1a; 实测结果reg log accOnline中的session都是同一个对象&#xff0c;但是getAccid时候的session就是另一个了。 测试结果&#xff0c;说明在LogicHan…
阅读更多...
小程序中使用echarts地图

小程序中使用echarts地图

一、下载并安装echarts 1、下载echarts-for-weixin组件 echarts-for-weixin项目提供了一个小程序组件&#xff0c;用这种方式可以在小程序中方便地使用 ECharts。 下载ec-canvas项目&#xff08;下载地址&#xff09; ​​ 注意&#xff1a;下载的 ec-canvas 中的echarts的版本…
阅读更多...
嵌入式怎么学？工程师学习路线都在这

嵌入式怎么学？工程师学习路线都在这

在嵌入式系统领域&#xff0c;硬件与软件工程师是不可或缺的重要支柱&#xff0c;分别承担着不同的职责和角色&#xff0c;但两者又紧密相连&#xff0c;共同构成了嵌入式系统的核心。今天本文将详细探讨工程师需要学什么&#xff0c;希望对小伙伴们有所帮助。 嵌入式硬件工程师…
阅读更多...
iOS App冷启动优化：Before Main阶段

iOS App冷启动优化：Before Main阶段

iOS应用冷启动时&#xff0c;在 UIApplicationMain(argc, argv, nil, appDelegateClassName)方法执行前&#xff0c;主要经历以下阶段&#xff1a; 1. 执行exec&#xff08;&#xff09;启动应用程序进程 2. 加载可执行文件&#xff0c;即将应用程序的Mach-O文件加载到内存…
阅读更多...
QT C++实践|超详细数据库的连接和增删改查操作|附源码

QT C++实践|超详细数据库的连接和增删改查操作|附源码

0&#xff1a;前言 &#x1faa7; 什么情况需要数据库? 1 大规模的数据需要处理&#xff08;比如上千上万的数据量&#xff09;2 需要把数据信息存储起来&#xff0c;无论是本地还是服务上&#xff0c;而不是断电后数据信息就消失了。 如果不是上面的原因化&#xff0c;一般…
阅读更多...
Linux系统中make/Makefile的介绍

Linux系统中make/Makefile的介绍

文章目录 前言一、make命令二、makefile功能介绍1.makefile文件的编写格式2.hello.c文件内容3.makefile文件4.安装make命令 总结 前言 在linux系统中&#xff0c;我们对项目文件进行处理的时候会不方便&#xff0c;因此我们需要对文件的编译进行自动化处理。 下面就是在Linux系…
阅读更多...
Linux第67步_linux字符设备驱动_注册和注销

Linux第67步_linux字符设备驱动_注册和注销

1、字符设备注册与注销的函数原型” /*字符设备注册的函数原型*/ static inline int register_chrdev(unsigned int major,\ const char *name, \ const struct file_operations *fops) /* major:主设备号&#xff0c;Limnux下每个设备都有一个设备号&#xff0c;设备号分…
阅读更多...
最新文章

Copyright @ 2022~2023