蓝桥备赛指南（12）· 省赛（构造or枚举）

算法：枚举

枚举算法介绍

枚举算法时一种基本的算法思想，它通过穷举所有可能的情况来解决问题。它的基本思想是将问题的解空间中的每个可能的解都枚举出来，并进行验证和比较，找到满足问题条件的最优解或者所有解。

枚举算法适用于问题规模较小、解空间可穷举的情况。它的优点是简单直观，不需要复杂的数学推导，抑郁实现。但是，由于需要穷举所有可能的情况，对于问题规模较大的情况，枚举的时间复杂度可能会非常高，效率较低。

解空间的类型

解空间了意识范围内的所有数字（或二元组、字符串等数据），或者满足某个条件的所有数字。

当然也可以是解空间树，一般可分为子集树和排列数，针对解空间树，需要使用回溯法进行枚举。我们目前使用循环去暴力枚举解空间，具体的解空间类型需要根据题目来理解构造。

循环枚举解空间

1.确定解空间的维度，即问题中需要枚举的变量个数。

2.对于每个变量，确定其可能的取值范围。

3.在循环体内，针对每个可能解进行处理。

例题讲解

习题：1.特别数的和 - 蓝桥云课

代码：

#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 << endl;
  return 0;
}

算法：构造

关于构造呢很难去用模板去解释，只能是题目的积累！！！

习题1：1.小蓝和小桥的挑战 - 蓝桥云课

 题目描述：

小蓝和小桥是游戏世界里的两个好友，他们正在玩一个有趣的挑战。他们手中有一个长度为 nn 的神秘物品序列，每个物品都有一个数字 aiai​ 表示它的价值。他们可以执行以下操作：

• 选择一个物品，并将其价值加 11。

小蓝和小桥希望通过若干次操作使得这个序列的价值之和与价值的积都不为 0。

请你帮他们计算，至少需要执行多少次操作才能完成这个挑战。

题目分析：

乘积不为0的情况：序列中不能存在0，将0修改为1（这一个操作的代价是0的数量）

价值之和不为0的情况：若序列值和不为0则直接输出，若为0，说明序列中一定存在正数和负数，此时将任意正数+1即可。

代码：

const int N = 1e5 + 9;
int a[N];

void solve() {
	int n; cin >> n;
	for(int i = 1; i <= n; ++i) cin >> a[i];
	int ans = 0, sum = 0;
	for (int i = 1; i <= n; ++i) {
		if (a[i] == 0) ans++, a[i] = 1;
	}
	//此时a中不存在0
	for (int i = 1; i <= n; ++i)sum += a[i];
	if (sum) {
		cout << ans << endl;
	}
	else {
		cout << ans + 1 << endl;
	}
}

习题（省赛）·  枚举/构造（重点）

 题目解析：

• 题目要求我们找到0到1e7之间的最大类斐波那契循环数。首先，我们需要理解什么是“类斐波那契”和“循环”。

  例如：

  N=934568 (这是一个六位数)
  

  对应的类斐波那契序列为:
  {9, 3+9, 4+3+9, 5+4+3+9, ...}
  即 {9, 12, 16, 21, ..., }

  如果这个数N会出现在对应类斐波那契序列中，则称该数为类斐波那契循环数。
  在这个例子中，因为9在序列中出现过（作为第一个元素），所以9是一个类斐波那契循环数。

  • “类斐波那契”的定义是这样的：
    对于一个有n位十进制数N = d1d2...dn, 可以生成一个类斐波那契序列S，其中Si表示从第i个位置开始的所有数字之和。

        例如：

N=934568 (这是一个六位数)

对应的类斐波那契序列为:
{9, 3+9, 4+3+9, 5+4+3+9, ...}
即 {9, 12, 16, 21, ..., }

如果这个数N会出现在对应类斐波那契序列中，则称该数为类斐波那契循环数。
在这个例子中，因为9在序列中出现过（作为第一个元素），所以9是一个类斐波那契循环数。

代码：

#include<iostream>
#include<string>
using namespace std;
int dfs(int n)
{

    int N = 0, dfsN[100] = { 0 };
    for (int j = n, k = 7; j != 0;)
    {
        dfsN[k] = j % 10;
        k--;
        j = (j - j % 10) / 10;
        N++;//这个数的位数
    }
    for (int j = 8; j < 100; j++)
    {
        for (int k = 1; k <= N; k++)
        {
            dfsN[j] += dfsN[j - k];
        }
        if (dfsN[j] == n) return 1;
    }
    return 0;
}
int main()
{
    for (int i = 10000000; i >= 1; i--)
    {
        if (dfs(i))
        {
            cout << i << endl;
            return 0;
        }
    }

}
//输出结果为：7913837