题目：http://poj.org/problem?id=1745
题意比较简单，就是给N个数，对除第一个数外其他每个数做加或者减，问最终得到的结果能否被K整除
思路，就是宽搜, 但是要注意的是，我们不能对所有的2^N个状态都进行扩展，事实上把每个数看成一层，在这一层里最多就只有K个有效的状态，然后对这K个有效的状态分别进行下一层的扩展，当扩展到第N层时我们就可以判断是不是可以整除。代码：
#include<cstdio> #include<cstring> #include<queue> using namespace std; int num[10010], used[205]; int N, K; void BFS() { queue<int>Q; memset(used, 0, sizeof(used)); int r = num[0] % K + K;//防止出现负数的下标 used[r] = 1; int cnt = 0; Q.push(r); while(!Q.empty()) { int s = Q.size(); cnt ++; for(int i = 0; i < s; ++ i) { int hd = Q.front(); Q.pop(); if(cnt == N) { if(hd == K) { printf("Divisible\n"); return; } } else { int t = (hd + num[cnt] ) % K + K; if(!used[t]) { Q.push(t); used[t] = 1; } t = (hd - num[cnt]) % K + K; if(!used[t]) { Q.push(t); used[t] = 1; } } } if(cnt == N) { break; } memset(used, 0, sizeof(used)); } printf("Not divisible\n"); } int main() { // freopen("poj1745.txt", "r", stdin); while(scanf("%d%d", &N, &K) != EOF) { for(int i = 0; i < N; ++ i) { scanf("%d", &num[i]); } BFS(); } } |