noi基本算法 动态规划 判断整除

来源：深圳童程童美信息学培训学校时间：2023/12/1 10:28:46

　　一个给定的正整数序列，在每个数之前都插入+号或-号后计算它们的和。比如序列：1、2、4共有8种可能的序列：

　　(+1) + (+2) + (+4) = 7

　　(+1) + (+2) + (-4) = -1

　　(+1) + (-2) + (+4) = 3

　　(+1) + (-2) + (-4) = -5

　　(-1) + (+2) + (+4) = 5

　　(-1) + (+2) + (-4) = -3

　　(-1) + (-2) + (+4) = 1

　　(-1) + (-2) + (-4) = -7

　　所有结果中至少有一个可被整数k整除，我们则称此正整数序列可被k整除。例如上述序列可以被3、5、7整除，而不能被2、4、6、8……整除。注意：0、-3、-6、-9……都可以认为是3的倍数。

　　输入

　　输入的行包含两个数：N(2 < N < 10000)和k(2 < k< 100)，其中N代表一共有N个数，k代表被除数。第二行给出序列中的N个整数，这些整数的取值范围都0到10000之间(可能重复)。

　　输出

　　如果此正整数序列可被k整除，则输出YES，否则输出NO。(注意：都是大写字母)

　　样例输入

　　3 2

　　1 2 4

　　样例输出

　　NO

　　下面介绍三种思路：

　　思路一：对余数的所有可能值进行递推(原创)

　　内存：268kB 时间：17ms

　　这种思路接近于桶排法。

　　/*作者：宇宙猎手*/

　　/*written by Yu Zhou Hunter*/

　　#include

　　using namespace std;

　　int m,n,a,b[100],j;

　　bool c[100];

　　int main()

　　{

　　cin>>m>>n;

　　for(int i=0;i

　　{

　　cin>>a;

　　a%=n;

　　for(int i=0;i<100;i++)c[i]=0;

　　for(int i=0;i<100;i++)

　　{

　　if(b[i]||i==0)c[(b[i]+a)%n]=1,c[(b[i]+n-a)%n]=1,b[i]=0;

　　else break;

　　}

　　j=0;

　　for(int i=0;i<100;i++)if(c[i])b[j++]=i;

　　if(j==n)

　　{

　　cout<<"YES";

　　return 0;

　　}

　　}

　　if(b[0])cout<<"NO";

　　else cout<<"YES";

　　return 0

尊重原创文章，转载请注明出处与链接：http://www.peixun360.com/2476/news/686846/违者必究！ 以上就是深圳童程童美信息学培训学校 小编为您整理 noi基本算法 动态规划 判断整除的全部内容。