做了一个半钟头，贡献了n个wa和rte，终于ac了。题目还是比较有意思的，在算术式里插加减号，使结果被某个数整除。而且是那么的像bfs......我的dp写的一如既往的烂，而且中途还测试了一下c里%的用法。

其实这些题的做法大同小异，都是用一个数组来表示当前可能达到的状态情况，达到置1，然后在下一步搜索这个数组中上一步的情况，然后再加以处理。只是这个题数据可能比较BT一点。

还有对memcpy的赋值不理解，http://www.kfbb.cn/blog/blogview.asp?logID=482，导致我后来又wa了n次。

#include <cstdio>
#include <string>

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

int main()
{
 int i, j, u;
 //freopen("div.16", "r", stdin);
 //freopen("in.txt", "r", stdin);
 scanf("%d", &m);
 for(i = 0; i < m; i ++)
 {
  memset(a, 0, sizeof(a));
  memset(b, 0, sizeof(b));
  if(i) printf("\n");
  scanf("%d %d", &n, &k);
  
  int t;
  scanf("%d", &t);
  t %= k;
  if(t < 0) t += k;
  a[t] = 1;  
  for(j = 1; j < n; j ++)
  {
   scanf("%d", &t);
   for(u = 0; u < k; u ++)
   {
    if(a[u])
    {
     int l = (u + t) % k;
     int r = (u - t) % k;
     if(l < 0) l += k;
     if(r < 0) r += k;
     b[l] = 1;
     b[r] = 1;
    }
   }
   //memset(a, 0, sizeof(a));
   memcpy(a, b, sizeof(b));
   memset(b, 0, sizeof(b));
  }
  if(a[0])
   printf("Divisible\n");
  else
   printf("Not divisible\n");
 }
 return 0;
}

评论