本文涉及知识点

C++贪心

[蓝桥杯 2022 国 A] 最大公约数

【C++数论 质因数分解】2654. 使数组所有元素变成 1 的最少操作次数|1928 几乎相同

题目描述

给定一个数组，每次操作可以选择数组中任意两个相邻的元素 $x,y$ 并将其中的一个元素替换为 $\gcd (x,y)$，其中 $\gcd (x,y)$ 表示 $x$ 和 $y$ 的最大公约数。请问最少需要多少次操作才能让整个数组只含 $1$。

输入格式

输入的第一行包含一个整数 $n$，表示数组长度。

第二行包含 $n$ 个整数 $a_1,a_2,\dots ,a_n$，相邻两个整数之间用一个空格分隔。

输出格式

输出一行包含一个整数，表示最少操作次数。如果无论怎么操作都无法满足要求，输出 $-1$。

样例 #1

样例输入 #1

3
4 6 9

样例输出 #1

4

提示

【评测用例规模与约定】

• 对于 $30\%$ 的评测用例，$n\le 500$，$a_i\le 1000$；
• 对于 $50\%$ 的评测用例，$n\le 5000$，$a_i\le 10^6$；
• 对于所有评测用例，$1\le n\le 10^5$，$1\le a_i\le 10^9$。

蓝桥杯 2022 国赛 A 组 D 题。

贪心 子数组公约数

gcd(1,x)=1。如果已经存在1，则需要的次数是非1的数量。第1个1向左右传染，其它1向右传染。
如果不存在1，求子数组公约数，找到最短为1的子数组。时间复杂度：O(nlongm) m=max(nums) 。$\forall$ i, gcd(nums[i…j],nums[j])顶多只有logM种值。
结果为：最短gcd位1字数组长度-1+n-1。

代码

核心代码

#include <iostream>
#include <sstream>
#include <vector>
#include<map>
#include<unordered_map>
#include<set>
#include<unordered_set>
#include<string>
#include<algorithm>
#include<functional>
#include<queue>
#include <stack>
#include<iomanip>
#include<numeric>
#include <math.h>
#include <climits>
#include<assert.h>

#include <bitset>
using namespace std;



template<class T = int>
vector<T> Read(int n,const char* pFormat = "%d") {
	vector<T> ret;
	T d ;
	while (n--) {
		scanf(pFormat, &d);
		ret.emplace_back(d);
	}
	return ret;
}

template<class T = int>
vector<T> Read( const char* pFormat = "%d") {
	int n;
	scanf("%d", &n);
	vector<T> ret;
	T d;
	while (n--) {
		scanf(pFormat, &d);
		ret.emplace_back(d);
	}
	return ret;
}

string ReadChar(int n) {
	string str;
	char ch;
	while (n--) {
		do
		{
			scanf("%c", &ch);
		} while (('\n' == ch));
			str += ch;
	}
	return str;
}

class CRangCal {
public:
	template<class _Pr, class T = int>
	static vector<vector<pair<T, int>>> RangCal(const vector<T>& nums, _Pr pr) {
		vector<vector<pair<int, int>>> vNumIndex(nums.size());
		for (int i = 0; i < nums.size(); i++) {
			if (i) {
				for (const auto& [preNum, preIndex] : vNumIndex[i - 1]) {
					auto iNew = pr(preNum, nums[i]);
					if (vNumIndex[i].empty() || (vNumIndex[i].back().first != iNew)) {
						vNumIndex[i].emplace_back(make_pair(iNew, preIndex));
					}
					else {
						vNumIndex[i].back().second = preIndex;
					}
				}
			}
			if (vNumIndex[i].empty() || (vNumIndex[i].back().first != nums[i])) {
				vNumIndex[i].emplace_back(make_pair(nums[i], i));
			}
			else {
				vNumIndex[i].back().second = i;
			}
		}
		return vNumIndex;// nums[x…i]的异或值（不重复）及索引。重复值保留索引大的。x∈ \in∈[0,x]。
	}
};

class Solution {
public:
	int minOperations(vector<int>& nums) {
		const int N = nums.size();
		auto res = CRangCal::RangCal(nums, [&](int i1, int i2) {return gcd(i1, i2); });
		int iMinLen = INT_MAX / 2;
		for (int i = 0; i < res.size(); i++) {
			for (const auto& [val, inx] : res[i]) {
				if (1 == val) { iMinLen = min(iMinLen, i - inx + 1); }
			}
		}
		if (1 == iMinLen) { return N - count(nums.begin(), nums.end(), 1); }
		if (iMinLen > N) { return -1; }
		return N - 1 + iMinLen - 1;
	}
};

int main() {
#ifdef _DEBUG
	freopen("a.in", "r", stdin);
#endif // DEBUG
	int x,n;
	scanf("%d", &n);
	vector<int> a = Read<int>(n);
	auto res = Solution().minOperations(a);
	cout << res << std::endl;
	return 0;
}

单元测试

vector<int> nums;
		TEST_METHOD(TestMethod11)
		{
			nums = { 2, 6, 3, 4 };
			auto res = Solution().minOperations(nums);
			AssertEx(4, res);
		}
		TEST_METHOD(TestMethod12)
		{
			nums = { 2,10,6,14 };
			auto res = Solution().minOperations(nums);
			AssertEx(-1, res);
		}
		TEST_METHOD(TestMethod13)
		{
			nums = { 6,10,15 };
			auto res = Solution().minOperations(nums);
			AssertEx(4, res);
		}
		TEST_METHOD(TestMethod14)
		{
			nums = { 4,6,9 };
			auto res = Solution().minOperations(nums);
			AssertEx(4, res);
		}
		TEST_METHOD(TestMethod15)
		{
			nums = { 1,1,1 };
			auto res = Solution().minOperations(nums);
			AssertEx(0, res);
		}

扩展阅读

我想对大家说的话
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
有效学习：明确的目标 及时的反馈 拉伸区（难度合适） 专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛
失败+反思=成功 成功+反思=成功

视频课程

先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

测试环境

操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用**C++**实现。