这是。。。本机AC提交RE?(
by The_KOG @ 2019-04-18 11:24:38
@[坐山客](/space/show?uid=73983) 我也是啊兄弟求助同
by 渺小的Mastar @ 2019-05-03 21:10:52
```cpp
#include <queue>
#include <bitset>
#include <cstdio>
#include <cstring>
#include <iostream>
#define ll long long
#define rgi register unsigned int
#define mst(a, b) memset(a, b, sizeof(a))
using namespace std;
inline int read()
{
int x = 0, f = 1;
char c = getchar();
for (; !isdigit(c); c = getchar())
if (c == '-')
f = -1;
for (; isdigit(c); c = getchar())
x = (x << 3) + (x << 1) + c - '0';
return x * f;
}
bitset<1010> ban;
ll a, b, k, maxd, st, from, ans[1010], v[1010];
inline int gcd(int a, int b)
{
return b ? gcd(b, a % b) : a;
}
inline int get_first(int a, int b)
{
rgi i = 1;
while (b > a * i)
i++;
return i;
}
bool better(int d)
{
for (rgi i = d; i >= 0; --i)
if (v[i] != ans[i])
return ans[i] == -1 || v[i] < ans[i];
return false;
}
bool DFS(int d, int from, ll aa, ll bb)
{
if (d == maxd)
{
if (bb % aa) //已经到最大深度了如果还不可以的话就就gg
return false;
v[d] = bb / aa;
if (better(d))
memcpy(ans, v, sizeof(ll) * (d + 1));
return true;
}
bool ok = false;
from = max(from, get_first(aa, bb));
for (rgi i = from; bb * (maxd + 1 - d) > i * aa; ++i) //剪枝
{
if (ban[i])
continue;
v[d] = i;
ll b2 = bb * i;
ll a2 = aa * i - bb;
ll g = gcd(a2, b2);
if (DFS(d + 1, i + 1, a2 / g, b2 / g))
ok = true;
}
return ok;
}
void IDASTAR()
{
short ok = 1;
for (maxd = 0;; maxd++)
{
mst(ans, -1);
if (DFS(0, get_first(a, b), a, b))
{
ok = 1;
break;
}
}
printf("1/%lld", ans[0]);
for (rgi i = 1; i <= maxd; ++i)
printf("+1/%lld", ans[i]);
puts("");
}
int main()
{
int cas = 0, t = read();
for (; t; t--)
{
a = read(), b = read(), k = read();
ban.reset();
for (rgi i = 0; i < k; ++i)
ban[read()] = 1;
printf("Case %lld: %lld/%lld=", ++cas, a, b);
IDASTAR();
}
return 0;
}
```
by 渺小的Mastar @ 2019-05-03 21:11:43
@[渺小的Mastar](/space/show?uid=140659) 因为不能选的质数可能很大，所以你不能用数组存，要用集合存
by Infiltrator @ 2019-05-04 08:32:01
@[坐山客](/space/show?uid=73983) 哦哦我wa的不是这个问题
我后来发现了谢谢
by 渺小的Mastar @ 2019-05-04 09:53:37
这说明oj有问题（逃
by lzxy @ 2019-07-29 18:34:02