自己做网站用哪个软件,网站建设公司宣传词,开网站需要准备什么,量个网站一个域名题目描述
有108个村庄排在一条公路上#xff0c;依次编号为0~108-1#xff0c;相邻村庄距离为1#xff0c;其中有n个村庄居住着牛牛#xff0c;居住着牛牛的村庄从小到大依次为a0~an-1#xff0c;其中保证a00. 现在需要建设车站#xff0c;有两个要求必须被满足#xf…题目描述
有108个村庄排在一条公路上依次编号为0~108-1相邻村庄距离为1其中有n个村庄居住着牛牛居住着牛牛的村庄从小到大依次为a0~an-1其中保证a00. 现在需要建设车站有两个要求必须被满足 1、每个有牛牛居住的村庄必须修建车站。 2、相邻车站的距离必须为1或为某个质数。 现给出n和a数组求需要建设车站的最小数量。
题解
纪念我第一次做这种题以前都是做竞赛题 题目看似杂乱无序但其实冥冥中都遵循着规律 没错就是哥德巴赫猜想 哥德巴赫猜想: 任一大于2的偶数都可写成两个素数之和 所以我们可以将题目总结为 1.当两站之间距离为素数那两站之间就不用修站了就光算上第二个站所修的num 2.如果两站之间距离不为素数但是为偶数然后偶数可以写成两个素数之和也就是在两个站中间存在一个位置将距离分为两个素数距离所以num2 3.如果不是素数也不是偶数。又因为奇数奇数偶数并且2是唯一的偶数的素数所以如果距离-2是素数的话就说明中间可以放一个站将距离分为2和另一个素数如果不能就要放两个站才可以分别是num2num3 4.每个站本身也要算上 ok撒花✿✿ヽ(°▽°)ノ✿
代码
class Solution {
public:/*** * param n int整型 * param a int整型一维数组 * param aLen int a数组长度* return int整型*/bool iff(int n){if(n1)return 1;if(n2)return 1;for(int i2;isqrt(n);i){if(n%i0)return 0;}return 1;}int work(int n, int* a, int aLen) {// write code hereint num0;for(int i1;iaLen;i){int lena[i]-a[i-1];if(iff(len))num;else if(len%20)num2;else if(len%21){if(iff(len-2))num2;else num3;}}num1;int sumnum;return sum;}
};
