洛谷 P1356 数列的整数性 题解【DP】【背包】【同余】

作者: wjyyy 分类: 二进制,同余,数学,滚动数组,背包,解题报告 发布时间: 2018-07-09 15:33

点击量:17

 

   找规律啊……

 

题目描述

对于任意一个整数数列,我们可以在每两个整数中间任意放一个符号’+’或’-‘,这样就可以构成一个表达式,也就可以计算出表达式的值。比如,现在有一个整数数列:17,5,-21,-15,那么就可以构造出8个表达式:

17+5+(-21)+15=16
17+5+(-21)-15=-14
17+5-(-21)+15=58
17+5-(-21)-15=28
17-5+(-21)+15=6
17-5+(-21)-15=-24
17-5-(-21)+15=48
17-5-(-21)-15=18

对于一个整数数列来说,我们能通过如上的方法构造出不同的表达式,从而得到不同的数值,如果该数值能够被k整除的话,那么我们就称该数列能被k整除。 在上面的例子中,该数列能被7整除(17+5+(-21)-15=-14),但不能被5整除。现在你的任务是,判断某个数列是否能被某数整除。

 

输入输出格式

输入格式:

第一行是一个整数m,表示有m个子任务。接下来就是m个子任务的描述。 每个子任务有两行。第一行是两个整数n和k(1<=n<=10000,2<=k<=100),n和k中间有一个空格。n 表示数列中整数的个数;k就是需要你判断的这个数列是否能被k整除。第二行是数列的n个整数,整数间用空格隔开,每个数的绝对值都不超过10000。

 

输出格式:

输出文件应有m行,依次对应输入文件中的m个子任务,若数列能被k 整除则输出 “Divisible”,否则输出 “Not divisible” ,行首行末应没有空格。

 

输入输出样例

输入样例#1:
2
4 7
17 5 -21 15
4 5
17 5 -21 15
输出样例#1:
Divisible
Not divisible

题解:

   一开始以为每个剩余系都成偶数,再让成单数的配对就行了,但是好像不可做。。。于是就改成DP背包了。

 

   类似一个01背包,实则是’-1,1’背包,选了增加,不选减少,f[i][k]用布尔型存储前i个数是否可以拼成余数为k的结果。每次i从i-1为true的地方转移,分别加减赋true。因为每次只从i-1转移过来,并且前一层的状态是不能跨层的,所以是可以用滚动数组把第一维压掉的。在这一题里负数和正数是等价的,负数的+与正数的-是一样的。

 

Code:

#include<cstdio>
#include<cstring>
bool f[2][105];
int main()
{
    memset(f,false,sizeof(f));
    f[0][0]=true;
    int m,u;
    scanf("%d",&m);
    while(m--)
    {
        memset(f,false,sizeof(f));
        f[0][0]=true;
        int n,k;
        scanf("%d%d",&n,&k);
        for(int i=1;i<=n;i++)
        {
            memset(f[i&1],false,sizeof(f[i&1]));
            scanf("%d",&u);
            for(int j=0;j<k;j++)
                if(f[i&1^1][j])
                {
                    f[i&1][((j+u)%k+k)%k]=true;//注意负数下标
                    f[i&1][((j-u)%k+k)%k]=true;
                }
        }
        if(f[n&1][0])
            puts("Divisible");
        else
            puts("Not divisible");
    }
    return 0;
}

 

说点什么

avatar
  Subscribe  
提醒
/* */