题目链接
https://www.luogu.org/problemnew/show/P1356
分析
这道题一个很显然的想法就是$f[i][j]$表示能否利用前$i$个数进行运算得到$j$,但是这意味着你可能需要一个庞大的$bool$数组加上较大的时间复杂度.
于是根据同余的性质我们用$f[i][j]$表示能否利用前$i$个数进行运算得到膜$k$等于$j$的一个数,这样我们只需要一个大小为$f[max_n][max_k]$的数组以及$O(mnk)$的时间复杂度
然而有个问题,就是前面的运算可能得到一个负数,$C++$数组下标是不资瓷负数的,怎么办呢.
我们就用$f[i][j]$表示能否利用前$i$个数进行运算得到绝对值膜$k$等于$j$的一个数,这样就可以方便起见将所有数转化为非负数来处理
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49
| #include <cstdio> #include <cstring> #include <algorithm> #include <cctype> #include <cstdlib> #include <cmath> #define ll long long #define ri register int using std::min; using std::abs; using std::max; template <class T>inline void read(T &x){ x=0;int ne=0;char c; while(!isdigit(c=getchar()))ne=c=='-'; x=c-48; while(isdigit(c=getchar()))x=(x<<3)+(x<<1)+c-48; x=ne?-x:x;return ; } const int maxn=10005; const int inf=0x7fffffff; int f[maxn][105]; int a[maxn],cnt=0; int n,k,T; int main(){ read(T); while(T--){ read(n),read(k); memset(f,0,sizeof(f)); cnt=0; for(ri i=1;i<=n;i++){ read(a[i]); a[i]=abs(a[i]%k); } f[0][0]=1; for(ri i=1;i<=n;i++){ for(ri j=0;j<=k;j++){ f[i][j]|=f[i-1][(j+a[i])%k]; f[i][j]|=f[i-1][abs(j-a[i])]; } } if(f[n][k]||f[n][0])puts("Divisible"); else puts("Not divisible"); } return 0; }
|