Tokitsukaze and Slash Draw
题目描述
在游戏王中有一张魔法卡叫做「一击必杀！居合抽卡」。
简单来说，当你发动这张卡后，你会从卡组最上方抽取一张卡，如果那张卡是「一击必杀！居合抽卡」的情况下，有大概率''一击必杀''打败对手。通常这张卡被玩家们称作''拔刀''。
在游戏王中，许多卡拥有着能够调整卡组中卡片顺序的效果，例如：「魔救」系列。
这个系列的卡大多包含''从自己卡组上面把5张卡翻开，可以...，剩下的卡用喜欢的顺序回到卡组最下面''的效果。也就是说，可以通过「魔救」系列的卡片效果，来调整「一击必杀！居合抽卡」在卡组中的位置。
--- 虽然那天我赢了很多局，但是当他拔刀的那一刻我才发现，他赢我太多了。
''哇哦，用魔救拔刀也太帅了吧''，Tokitsukaze 心里想道。她关闭知乎，打开《Yu-Gi-Oh Master Duel》准备学习如何操作，现在她正在人机练习中。
Tokitsukaze 的卡组有 $n$ 张卡片，她已经知道「一击必杀！居合抽卡」这张卡片是在卡组中从最下面往上数的第 $k$ 张卡片。她挑选了 $m$ 种能够调整卡组中卡片顺序的卡片，第 $i$ 种类型的卡片效果是：把卡组最上方的 $a_i$ 张卡片拿出来按顺序放到卡组最下方。这个效果你可以理解为：首先将一张卡片拿出来，然后把这张卡片放到卡组最下方，这个动作重复做 $a_i$ 次。而发动第 $i$ 种类型的卡片效果，需要支付 $b_i$ 的''cost''。
Tokitsukaze 可以通过一些操作使每种类型的卡片可以发动无限次，她是否能够让「一击必杀！居合抽卡」这张卡片出现在卡组的最上方？如果能，请输出最少需要支付的''cost''，如果不能，请输出 ''-1''（不带引号）。
输入描述:
第一行包含一个整数 $T$ ($1 \leq T \leq 1000$)，表示 $T$ 组测试数据。
对于每组测试数据：
第一行包含三个整数 $n$, $m$, $k$ ($1 \leq n \leq 5000$; $1 \leq m \leq 1000$; $1 \leq k \leq n$)，表示 Tokitsukaze 的卡组有 $n$ 张卡片，她挑选了 $m$ 种能够调整卡组中卡片顺序的卡片，以及「一击必杀！居合抽卡」这张卡片是在卡组中从最下面往上数的第 $k$ 张卡片。
接下来 $m$ 行，每行两个整数 $a_i$, $b_i$ ($1 \leq a_i \leq n$, $1 \leq b_i \leq 10^9$)，表示第 $i$ 种类型的卡片能将卡组最上方的 $a_i$ 张卡片拿出来按顺序放到卡组最下方，并且需要支付 $b_i$ 的"cost"才能发动。
保证 $\sum{n}$ 不超过 $5000$，$\sum{m}$ 不超过 $1000$。
输出描述:
对于每组测试数据，如果 Tokitsukaze 能够让「一击必杀！居合抽卡」这张卡片出现在卡组的最上方，输出一个整数表示最少需要支付的"cost"；否则输出 "-1"（不带引号）。
示例1
输入
2
10 1 7
2 100
10 3 7
2 3
6 1
5 10输出
-1
13说明
第二组测试数据：
最开始「一击必杀！居合抽卡」这张卡片的位置在从下往上数的第 $7$ 张，操作的方式可以是：
使用第 $3$ 种类型的卡片，将位置从 $7$ 移动到 $2$，移动的过程是 $7 \to 8 \to 9 \to 10 \to 1 \to 2$；
使用第 $2$ 种类型的卡片，将位置从 $2$ 移动到 $8$，移动的过程是 $2 \to 3 \to 4 \to 5 \to 6 \to 7 \to 8$；
使用第 $2$ 种类型的卡片，将位置从 $8$ 移动到 $4$，移动的过程是 $8 \to 9 \to 10 \to 1 \to 2 \to 3 \to 4$；
使用第 $2$ 种类型的卡片，将位置从 $4$ 移动到 $10$，移动的过程是 $4 \to 5 \to 6 \to 7 \to 8 \to 9 \to 10$；
所以总共使用了 $1$ 张第 $3$ 种类型的卡片以及 $3$ 张第 $2$ 种类型的卡片，总支付的"cost"为 $1 \cdot 10 + 3 \cdot 1 = 13$。
可以发现无法支付比 $13$ 更少的"cost"使「一击必杀！居合抽卡」这张卡片出现在卡组的最上方，所以答案为 $13$。
解题思路
我赛时的做法与出题人给出的两种做法都不同（）
首先对于任意一种操作，本质上是将目标卡片循环右移 $a_i$ 次，所以对于某种操作方案，操作的顺序并不会影响目标卡片最终的位置。假设第 $i$ 种操作执行了 $c_i$ 次，那么为了使得目标卡片从一开始的第 $k$ 个位置移动到第 $n$ 个位置，执行的操作应该要满足：
\begin{align*}
&\left( k-1 + \sum\limits_{i=1}^{m}{c_i \cdot a_i} \right) \bmod n = n - 1 \\
\Rightarrow &\sum\limits_{i=1}^{m}{c_i \cdot a_i} \equiv n-k \pmod{n}
\end{align*}
所以就可以 dp，看每个 $c_i$ 选多少使得总移动步数在模 $n$ 意义下为 $n-k$ 时总代价最小。定义 $f(i,j)$ 表示执行前 $i$ 个操作使得移动步数模 $n$ 为 $j$ 的所有方案的最小代价。根据第 $i$ 个操作执行的次数进行状态划分，容易知道每个操作实际上最多会执行 $n-1$ 次，因此如果直接转移的话时间复杂度就是 $O(m n^2)$。然后发现这个问题与完全背包很像，考虑能不能用完全背包的方式进行优化。
其中 $f(i,j)$ 与 $f(i, (j - a_i) \bmod n)$ 的状态转移方程分别为：
\begin{align*}
f(i,j) &= \min\left\{ f(i-1, j), \, f(i-1, (j-a_i) \bmod n) + b_i, \, f(i-1, (j-2a_i) \bmod n) + 2b_i, \, \ldots \right\} \\
f(i, (j-a_i) \bmod n) &= \min\left\{ \qquad\qquad\;\;\; f(i-1, (j-a_i) \bmod n), \, \quad\;\;\;\, f(i-1, (j-2a_i) \bmod n) + b_i, \;\; f(i-1, (j-3a_i) \bmod n) + 2b_i, \, \ldots \right\}
\end{align*}
因此就有 $f(i,j) = \min\{ f(i-1,j), \, f(i, (j - a_i) \bmod n) + b_i \}$。但又发现这个转移是存在环的，不过由于边权都是是非负的，因此可以对这个状态转移图跑 Dijkstra。对于当前状态 $f(i,j)$，可以转移到的下一个状态有 $f(i+1, j)$ 和 $f(i, (j + a_i) \bmod n)$，因此每个状态都有两条出边。
最终的答案就是 $f(m, n-k)$。
AC 代码如下，时间复杂度为 $O(mn \log{mn})$：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 5010, M = 1010;
const LL INF = 0x3f3f3f3f3f3f3f3f;
int a[M], b[M];
LL dist[M][N];
bool vis[M][N];
void solve() {
int n, m, k;
scanf("%d %d %d", &n, &m, &k);
for (int i = 1; i <= m; i++) {
scanf("%d %d", a + i, b + i);
}
for (int i = 0; i <= m; i++) {
for (int j = 0; j < n; j++) {
dist[i][j] = INF;
vis[i][j] = false;
}
}
dist[0][0] = 0;
priority_queue<array<LL, 3>> pq;
pq.push({0, 0, 0});
while (!pq.empty()) {
auto p = pq.top();
pq.pop();
if (vis[p[1]][p[2]]) continue;
vis[p[1]][p[2]] = true;
if (p[1] == m && p[2] == n - k) break; // 这个剪枝一定要加，不然会超时，很奇怪
if (p[1] + 1 <= m && dist[p[1] + 1][p[2]] > -p[0]) { // 第一维不能超过m，
dist[p[1] + 1][p[2]] = -p[0];
pq.push({p[0], p[1] + 1, p[2]});
}
if (dist[p[1]][(p[2] + a[p[1]]) % n] > -p[0] + b[p[1]]) {
dist[p[1]][(p[2] + a[p[1]]) % n] = -p[0] + b[p[1]];
pq.push({p[0] - b[p[1]], p[1], (p[2] + a[p[1]]) % n});
}
}
printf("%lld\n", dist[m][n - k] == INF ? -1 : dist[m][n - k]);
}
int main() {
int t;
scanf("%d", &t);
while (t--) {
solve();
}
return 0;
}上面有提到每个操作实际上最多只会执行 $n-1$ 次，因此可以转换成多重背包问题。通过最简单的二进制优化就可以将时间复杂度降到 $O(mn\log{n})$，当然还可以用单调队列来优化，这样就会进一步降到 $O(mn)$，不过单调队列的写法早忘了，这里就偷懒用二进制优化 qwq。
AC 代码如下，时间复杂度为 $O(mn\log{n})$：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 5010, M = 1010;
int a[M], b[M];
LL f[2][N];
void solve() {
int n, m, k;
scanf("%d %d %d", &n, &m, &k);
for (int i = 1; i <= m; i++) {
scanf("%d %d", a + i, b + i);
}
memset(f[0], 0x3f, n + 10 << 3);
f[0][0] = 0;
int s = 0;
for (int i = 1; i <= m; i++) {
int c = n;
for (int k = 1; k <= c; k <<= 1) {
memset(f[++s & 1], 0x3f, n + 10 << 3);
for (int j = 0; j < n; j++) {
f[s & 1][j] = min(f[s - 1 & 1][j], f[s - 1 & 1][((j - k * a[i]) % n + n) % n] + 1ll * k * b[i]);
}
c -= k;
}
if (c) {
memset(f[++s & 1], 0x3f, n + 10 << 3);
for (int j = 0; j < n; j++) {
f[s & 1][j] = min(f[s - 1 & 1][j], f[s - 1 & 1][((j - c * a[i]) % n + n) % n] + 1ll * c * b[i]);
}
}
}
printf("%lld\n", f[s & 1][n - k] == 0x3f3f3f3f3f3f3f3f ? -1 : f[s & 1][n - k]);
}
int main() {
int t;
scanf("%d", &t);
while (t--) {
solve();
}
return 0;
}再给给出出题人建图跑最短路的做法，出题人给出的 dp 做法我看不懂 qwq。
为了方便这里将下标 $1 \sim n$ 映射为 $0 \sim n-1$，问题可以抽象成在模 $n$ 意义下起点为 $k-1$ 终点为 $n-1$ 的最短路问题。当在第 $x$ 个位置时，此时可以通过执行第 $i$ 种操作从 $x$ 移动到 $(x+a_i) \bmod n$。因此对于每个下标 $x \in [0, n-1]$，枚举 $m$ 个操作进行建图，令 $x \to (x+a_i) \bmod n$ 的边权为 $b_i$。然后对这个图跑 Dijkstra 即可。我这里跑的是朴素 Dijkstra 算法。
AC 代码如下，时间复杂度为 $O(nm + n^2)$：
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 5010, M = 1010;
const LL INF = 0x3f3f3f3f3f3f3f3f;
int a[M], b[M];
LL g[N][N];
LL dist[N];
bool vis[N];
void solve() {
int n, m, k;
scanf("%d %d %d", &n, &m, &k);
for (int i = 0; i < m; i++) {
scanf("%d %d", a + i, b + i);
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
g[i][j] = INF;
}
for (int j = 0; j < m; j++) {
int t = (i + a[j]) % n;
g[i][t] = min<LL>(g[i][t], b[j]);
}
}
memset(dist, 0x3f, n + 10 << 3);
dist[k - 1] = 0;
memset(vis, 0, n + 10);
for (int i = 0; i < n; i++) {
int t = -1;
for (int i = 0; i < n; i++) {
if (!vis[i] && (t == -1 || dist[i] < dist[t])) t = i;
}
vis[t] = true;
for (int i = 0; i < n; i++) {
dist[i] = min(dist[i], dist[t] + g[t][i]);
}
}
printf("%lld\n", dist[n - 1] == INF ? -1 : dist[n - 1]);
}
int main() {
int t;
scanf("%d", &t);
while (t--) {
solve();
}
return 0;
}
参考资料
【题解】2024牛客寒假算法基础集训营2：https://ac.nowcoder.com/discuss/1251379/
标签：Draw,卡组,卡片,leq,int,bmod,Tokitsukaze,Slash,一击必杀 From： https://www.cnblogs.com/onlyblues/p/18009569