我是靠谱客的博主 勤恳烤鸡,最近开发中收集的这篇文章主要介绍sql判断整除_ybt1195 判断整除(自己立的flag,跪着也要打完),觉得挺不错的,现在分享给大家,希望可以做个参考。

概述

ybt1195 判断整除

【题目描述】

一个给定的正整数序列,在每个数之前都插入+号或−号后计算它们的和。比如序列: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

【输出】

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

【输入样例】

3 2

1 2 4

【输出样例】

NO

【题解】

首先,先看题干中的例子,可以看出,组合后的结果的符号与整除于否无关,所以就不用考虑一半的情况。

再者,序列中的数字,能影响答案的,并不是整个数,而是它模k的值罢了,所以对数据进行处理,缩小数据。

for(int i=1;i<=n;i++) {

cin>>tmp;

tmp%=k;//预处理

a[i]=tmp;

}

接下来,就到了简化问题的时间

由1,2,4来分析,如果从1开始加入序列,那么1可以被1整除

接下来2加入,这样就有1和3(结果只取绝对值)两个数可以整除

再接下来是4,这样子1,3,5,7就都符合整除规则了。

所以我们就想到(题解就说道)

可以从头开始,一个一个来(让元素入列)

因为元素越多,组合方式是以指数级爆炸的,又因为如此多的组合的结果有大量重复,所以说就想到(题解说)可以以k为数组的第二维,只要枚举余数,就可以将复杂度控制到可控范围。

那么,就可以用bool变量fi,j表示前i个数是否可以被j整除(1可以,0不可以)

如果要转移到fi,j的状态,那么就要在前i-1个数已经入列的基础上再加第i个数,而第i个数又只有正和负两种情况所以便只考虑是由加第i个数和减第i个数就好了。

要想加ai得到余数为j的情况,那么前i-1个数必须满足余数可以为j-ai

反之,若减ai得到余数可以为j,那么前i-1个数必须满足余数可以为j+ai

所以,要想ai入列后,余数为j,那么上述两个条件满足一个就好。

列出方程:fi,j=fi-1,j-ai||fi-1,j+ai

(不过为了防止爆数组,要控制j+-ai的数据在k的范围内,所以要+k然后%k)

边界条件:f0,0=1(0个元素,结果为零,所以不管k为多少,余数都为零)

代码打出来是这样的:

#include

#include

using namespace std;

int a[10005],n,k,tmp;

bool f[10005][105];

int main() {

cin>>n>>k;

memset(a,0,sizeof(a));

for(int i=1;i<=n;i++) {

cin>>tmp;

tmp%=k;

a[i]=tmp;

}

f[0][0]=1;//边界

for(int i=1;i<=n;i++) {

for(int j=0;j

f[i][j]=(f[i-1][(j-a[i]+k)%k]||f[i-1][(j+a[i]+k)%k]);//递推

}

}

if(f[n][0]){

cout<

}

else{

cout<

}

return 0;

}

Ps:因为本题转移时调用的数组的第二维较为随机,所以就不会懒得滚动数组了······

感谢题解

最后

以上就是勤恳烤鸡为你收集整理的sql判断整除_ybt1195 判断整除(自己立的flag,跪着也要打完)的全部内容,希望文章能够帮你解决sql判断整除_ybt1195 判断整除(自己立的flag,跪着也要打完)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(54)

评论列表共有 0 条评论

立即
投稿
返回
顶部