题解：P8199 [传智杯 #4 决赛] 游戏

题意：略，详见题面。 关键词：模拟。 参考难度：绿。 解析：依照题意模拟即可。 对于每种武器开一个 use 数组表示他们使用子弹的编号，即可快速判断某种弹药是不是「无用的」； 可以维护一个变量 last 表示目前背包的剩余空间，在捡物资时，先将物资捡起来并更新 last，然后在 时，枚举所有的物资，找到最符合要求的并扔掉即可。 设 表示 是否是「被用到的」弹药，则 比 「更应该」被扔掉当且仅当 或者 且 ，其中 表示 最后被捡起的时间。 需要注意的是：使用浮点数进行运算可能产生精度误差，因此可以将容量和占用空间都乘 ，这样就可以全部使用整形运算了。 std 的长度为 69 行，2.5k。 (C++) #include #include #include

const int maxn = 105;

int n, m, s, t, w1, w2, lst;

std ::array<std::array<int, maxn>, maxn> type, a, b, vis; std ::array<int, maxn> tm, arr, cnt; const std::array<int, 5> dx{0, -1, 1, 0, 0}, dy{0, 0, 0, -1, 1}; const std::array<int, 10> use{0, 14, 14, 14, 14, 15, 15, 15, 16, 16}, level{5, 2, 2, 3, 4, 2, 3, 3, 1, 1}; const std::array<int, 17> weight{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 50, 40, 30, 20, 2, 1, 5};

inline bool used(int x) { return x && ((x <= 13) ? true : (use[w1] == x || use[w2] == x)); } inline bool cmp(const int x, const int y) { return tm[x] > tm[y]; }

void work(int curx, int cury) { vis [curx][cury] = true; if (type[curx][cury] == 17) { if (cnt[use[w1]] >= a[curx][cury]) { cnt [use[w1]] -= a[curx][cury]; lst += a[curx][cury] * weight[use[w1]]; } else if (cnt[use[w2]] >= b[curx][cury]) { cnt [use[w2]] -= b[curx][cury]; lst += b[curx][cury] * weight[use[w2]]; } else { std ::cout << curx << ' ' << cury << '\n'; exit(0); } } else if (type[curx][cury] < 10) { if (level[w1] > level[type[curx][cury]]) w1 = type[curx][cury]; else if (level[w1] < level[type[curx][cury]] && level[w2] > level[type[curx][cury]]) w2 = type[curx][cury]; } else { lst -= a[curx][cury] * weight[type[curx][cury]]; for (int i = 0; lst < 0; i = 0) { for (int p = 10; p < 17; ++p) if (cnt[p]) if ((!cnt[i]) || (used(p) < used(i)) || ((used(p) == used(i)) && (tm[p] > tm[i]))) i = p; int tmp = std::min(cnt[i], (-lst) / weight[i] + ((lst % weight[i]) ? 1 : 0)); lst += tmp * weight[i]; cnt [i] -= tmp; } tm [type[curx][cury]] = t; cnt [type[curx][cury]] += a[curx][cury]; } }

int main() { std ::cin >> n >> m >> s >> t; lst = s *= 10; for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) { std ::cin >> type[i][j] >> a[i][j]; if (type[i][j] == 17) std ::cin >> b[i][j]; } tm .fill(998244353); work(1, 1); --t; for (int op, curx = 1, cury = 1; ~t; --t) { std ::cin >> op; if (vis[curx += dx[op]][cury += dy[op]]) continue; work(curx, cury); } for (int i = 10; i < 17; ++i) arr[i] = i; std ::sort(arr.begin() + 10, arr.begin() + 17, cmp); std ::cout << w1 << '\n' << w2 << '\n'; for (int i = 1; i < 17; ++i) if (cnt[arr[i]] != 0) std ::cout << arr[i] << ' ' << cnt[arr[i]] << '\n'; }  题外话：本题构造数据的方法是：随机修改 std 若干处，然后和正确的 std 对拍，拍出一组加一组。