其实就是一道简单的搜索题。
从小往大+BFS可以保证最少O(n)的复杂度。
#include <cstdio> #include <iostream> #include <fstream> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #include <queue> #define rep(i, l, r) for(int i=l; i<=r; i++) #define down(i, l, r) for(int i=l; i>=r; i--) #define maxn 5678 #define MAX 1<<30 using namespace std; int n, c, m, bn[maxn][509]; char s[5]; bool b[16]; queue <int> q; void Init() { rep(i, 0, 15) b[i] = 0; rep(i, 0, maxn-1) bn[i][0] = 0; while (!q.empty()) q.pop(); } int main() { int t; scanf("%d", &t); while (t--) { Init(); scanf("%d%d%d", &n, &c, &m); rep(i, 1, m) { scanf("%s", s); if (s[0] <= '9') b[s[0]-'0'] = 1; else b[s[0]-'A'+10] = 1; } if (n == 0) { if (b[0]) printf("0 "); else printf("give me the bomb please "); continue; } rep(i, 1, 15) if (b[i] && !bn[i%n][0]) { bn[i%n][0] = 1; bn[i%n][1] = i; q.push(i%n); } while (!q.empty() && !bn[0][0]) { int x = q.front(); q.pop(); if (bn[x][0] == 500) continue; rep(i, 0, 15) if (b[i] && !bn[(x*c+i)%n][0]) { int y = (x*c+i)%n; rep(j, 1, bn[x][0]) bn[y][j+1] = bn[x][j]; bn[y][1] = i; bn[y][0] = bn[x][0]+1; q.push(y); } } if (bn[0][0]) { down(i, bn[0][0], 1) if (bn[0][i] <= 9) printf("%c", bn[0][i]+'0'); else printf("%c", bn[0][i]-10+'A'); printf(" "); } else printf("give me the bomb please "); } }