[蓝桥杯][2013年第四届真题]幸运数

题目

题目链接

题解

两种方法：①DFS ②模拟。

先讲大佬的DFS，再讲我的模拟，分别对应代码1和代码2

代码3是根据大佬代码改进的我的模拟。

推荐代码1和代码3！

从幸运数字3开始每次都将“通过幸运数字更新过的数组中当前幸运数字的下一个数字”作为幸运数字继续更新数组。 因此dfs传入幸运数字的下标，对于数组中此下标之前的数不用处理，属于已经得到的幸运数字；而对于此下标之后的数，我们将那些不能被幸运数字整除的索引所对应的数字顺次拼接到幸运数字的下标之后。这样相当于数组中的前若干个数就是我们想要的幸运数字。

耗时140ms

代码2就不讲了，因为写出了个更简洁的代码3。

len表示的是有效数组的长度，代码1dfs函数中的循环要遍历到b，有些数相当于无效了，更新也没用，所以我通过len记录有效数组长度。

在代码简洁的基础上，时间缩短成4ms。

注意一开始都将数组直接赋值为用2更新过的数组，因为2比较特别，用2更新过后数字3跑到2原来的位置上了，还需要通过下标为2的数字更新，与后续更新方式不符，因此为了后面更新的方便，直接将2更新完的数组作为初始数组

大佬的这个拼接的思路太好了，我的代码中就一直在挪位，模拟删除的过程，就他妈离谱，debug都快de死了。

不说了，同学等着我吃火锅呢！886！（滑稽）

代码1

#include
using namespace std;
const int N = 1e6+10;

int a, b, ans, c[N];

void dfs(int x) {
	int y = x;
	
	if(c[x] >= b) return ;
	
	for(int i = x;i >a>>b;
	
	for(int i = 1;i  1) dfs(2);
	
	for(int i = 1;c[i]  a) ans ++;
	
	coutb;
	memset(num, 0x3f, sizeof num);
	
	for(int i = 1;2*i-1