这题很明显是签到题，可我比赛时却没做出，赤裸裸的爆零了，真悲剧……
看了题解后才知道直接暴搜就行，只是需要把它们从大到小排序后再搜，我当时就没想到。。。不想再多说了
一开始我直接枚举所有情况：
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std; int b[],a; inline bool ok(const vector<int> &v, int a) {
int len = v.size();
for(int i = len - ; i >= ; --i)
if(a % v[i] == ) return ;
else a %= v[i];
return ;
} int main() {
int t,n;
scanf("%d",&t);
while(t--) {
scanf("%d %d",&n,&a);
for(int i = ; i < n; ++i)
scanf("%d",b + i);
sort(b, b + n);
int limit = ( << n) - ;
bool flag = ;
for(int i = ; i <= limit; ++i) {
vector<int> v;
for(int j = ; ( << j) <= i; ++j)
if(i & ( << j)) v.push_back(b[j]);
if(ok(v, a)) {
printf("%d\n",v.size());
flag = ;
break;
}
}
if(flag == ) puts("-1");
}
return ;
}
可是却发现 700+ms，出奇的慢，于是我试下直接的深搜，竟然 78ms，果然够快！
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
const int inf = 0x3fffffff; int b[],ans,n; void dfs(int id, int num, int a) {
if(a == ) {
ans = min(ans, num);
return ;
}
if(id > n) return ; dfs(id + , num + , a % b[id]);
dfs(id + , num, a);
} inline bool cmp(int x, int y) {
return x > y;
} int main() {
int t, a;
scanf("%d",&t);
while(t--) {
scanf("%d %d",&n,&a);
for(int i = ; i <= n; ++i)
scanf("%d",b + i);
sort(b + , b + n + , cmp);
ans = inf;
dfs(, , a);
printf("%d\n",ans == inf ? -: ans);
}
return ;
}
在网上看到有个位压的比我第一个版本快多了：
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int const MAX = << ;
int const INF = 0x3fffffff;
int b[], sta[MAX]; int lowbit(int x)
{
return x & (-x);
} bool cmp(int a, int b)
{
return a > b;
} int main()
{
int T;
scanf("%d", &T);
while(T --)
{
memset(sta, , sizeof(sta));
int n, a;
scanf("%d %d", &n, &a);
for(int i = ; i <= n; i++)
scanf("%d", &b[i]);
sort(b + , b + n + , cmp);
for(int i = ; i <= n; i++)
sta[ << (i - )] = b[i];
int cnt, ans = INF;
for(int i = ; i < ( << n); i++)
{
int tmp = a;
cnt = ;
for(int j = i; j > ; j -= lowbit(j))
{
tmp %= sta[lowbit(j)];
cnt ++;
}
if(tmp == )
ans = min(ans, cnt);
}
if(ans == INF)
printf("-1\n");
else
printf("%d\n", ans);
}
}
虽然爆零，但比赛还是得坚持打。