枚举（蓝桥练习）
一、枚举算法介绍
枚举算法是一种基本的算法思想，它通过穷举所有可能的情况来解决问题。它的基本思想是将问题的解空间中的每个可能的解都枚举出来，并进行验证和比较，找到满足问题条件的最优解或者所有解。 枚举算法适用于问题规模较小、解空间可穷举的情况。它的优点是简单直观，不需要复杂的数学推导，易于实现。但是，由于需要穷举所有可能的情况，对于问题规模较大的情况，枚举算法的时间复杂度可能会非常高，效率较低。
二、解空间的类型
解空间可以是一个范围内的所有数字(或二元组、字符串等数据)，或者满足某个条件的所有数字。 当然也可以是解空间树，一般可分为子集树和排列树，针对解空间树，需要使用回溯法进行枚举(在后面讲到搜索的时候会讲到)。 我们目前仅使用循环去暴力枚举解空间，具体的解空间类型需要根据题目来理解构造。
三、循环枚举解空间
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。
#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;
}（五、小蓝和小桥的挑战）
#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;
}今天就先到这了！！！
腾讯云开发者
