蓝桥杯备赛-复习和模拟赛

复习

1.选素数:线性筛

• 思路：根据题目规律分析出求f(n) = n-pmax+1,n不为素数，接下来就是利用线性筛来求每个数的pmax了。模板还是比较好记的。
• 总结：代码长度不长，主要要根据规律分析出如何求解的x以及知道利用线性筛求数的最大质因子。

2.单源最短路：dijkstra

• 思路：主要采用链式前向星和优先队列来实现单源最短路的更新，模板的写法要非常熟悉。

3.字符迁移：差分

• 思路：连续一段区间加一个数就是差分的特点，cha[l]+=k,cha[r+1]-=k,然后前差分数组的前缀和就是最终原数组。写一个示例数组就能很清晰地理清两者的关系了。
• 注意：%不要在差分求解的过程中进行，会打乱数组。在原数组求解出来之后在对应进行%运算。

强者挑战赛11：

A玩偶购买：

• 分类讨论，一些细节要多多注意，通过几次调试过了。但是正式比赛的时候一定要细心细心再细心，多多输出中间条件来测试。

B数学魔法家：

• 两种情况，主要是前导零的情况要进行特殊处理，多加测试，做出来了。

C矿石样本分析：

• map存储来实现快速查找，注意两个矿石的值不能相同，题目的限定条件最好还是写下来，不容易忘记。修改了一次最终通过了。

D拔苗助长：

• 考察完全平方数的唯一分解定律，它分解为多个质数相乘，那么质数的系数一定是偶数。选任意两个数相乘为完全平方数，那么它们对应的质因子的和应该为偶数，当出现在一个数内出现了奇数次x的质数时，需要进行操作，它们要么全变成偶数（x次），要么把剩余的全变成奇数（n-x）,两者取较小值。
• 还是有点晕晕，结合具体的例子来看会清晰很多。评论区翻到的代码太厉害了。尤其是分解质因子这里很巧妙！

unordered_map<int, int> mp;
for(int i = 1; i <= n; i++){
	for(int j = 2;j*j<=a[i]; j++){
		int cnt = 0;
		while(a[i]%j==0){
			a[i]/=j;
			cnt++;
		}
		if(cnt%2==1){
			mp[j]++;
		}
	}
	if(a[i]!=1){
		mp[a[i]]++;
	}
}

• 另外，线性筛还可以用来求最小质因子