题目链接：点击打开链接
#include #include #include #include #include typedef unsigned long long ll; using namespace std; const int N = 400 + 1; const int M = 200000 + 1; int t[N], w[N], g[51][M], ans[N], dep; ll d[M]; map id; char ch; void get(int& z) { while ((ch = getchar()) > '9' || ch < '0'); z = ch - '0'; while ((ch = getchar()) >= '0' && ch <= '9') z = z * 10 + ch - '0'; } int main() { for (ll i = 1; i <= 50; ++i) id[1ll << i] = i; int cas, n, m, x, y; ll v, mx = (1ll << 51) - 1; get(cas); while (cas -- > 0) { memset(d, 0, sizeof d); d[0] = 1; memset(g, -1, sizeof g); get(n); get(m); for (int i = 0; i < n; ++i) { get(w[i]); get(t[i]); for (int j = M - t[i] - 1; j >= 0; --j) if (d[j] > 0) { v = d[j + t[i]]; d[j + t[i]] |= (d[j] << w[i]) & mx; v = v ^ d[j + t[i]]; while (v > 0) { if (v & 1) { v = v & (v - 1); continue; } x = id[v & (v - 1) ^ v]; g[x][j + t[i]] = i; v = v & (v - 1); } } //g[w[i]][t[i]] = i; } while (m -- > 0) { get(x); get(y); if (g[x][y] >= 0) { dep = 0; while (x > 0 && y > 0) { ans[dep++] = g[x][y]; x -= w[ans[dep - 1]]; y -= t[ans[dep - 1]]; } for (int i = dep - 1; i >= 0; --i) { if (i == 0) printf("%d\n", ans[i] + 1); else printf("%d ", ans[i] + 1); } } else puts("No solution!"); } } return 0; }