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

点击量：163

   找规律啊……

目录

题目描述

对于任意一个整数数列，我们可以在每两个整数中间任意放一个符号’+’或’-‘，这样就可以构成一个表达式，也就可以计算出表达式的值。比如，现在有一个整数数列：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;
}