「Summary」 NOI 春测前复习记录

Posted on Edited on

To say goodbye is to die a little.

由于不可抗拒力，复习计划咕咕咕了。
也不一定呢？

P4755

link

关键在于要发现暴力的复杂度是对的。
好像这个方法叫做 $\max$ 分治，首先可以建一个大根的笛卡尔树，然后只需要对该点的管辖区间进行计算就可以了。
具体做法是直接以最大值的点 $u$ 分成 $[l, u)$ 和 $(u, r]$ 两个区间，于是可以枚举较小的一个区间，用主席树查询另外一边小于 $\lfloor \frac{a_u}{a_i} \rfloor$ 的数的个数。
为什么这样的复杂度是对的呢？可以仿照启发式合并的思路，每次区间的长度都在 $\frac{n}{2}$ 以内，于是总的复杂度为 $\Theta(\frac{n}{2}\log^2)$ 。
其实还可以用树状数组写，常数更小。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
/*
Stars in the sky, floating in darkness, soon I will fly faster than Light.
See through my eyes, time standing down, onward to space, engines stand by.
Sense loss of time Nebula’s blurring, lights flashing by Worlds Unknown.
Imminent approach, sensors reacting, soon I’m through faster Than Light.
Suddenly stop Readings come in, nothing in sight Sun glowing bright.
*/
#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target("avx2,fma")
#include <map>
#include <cstdio>
#include <iostream>
#include <algorithm>
#define LL long long
#define ULL unsigned long long
using namespace std;
const int MAXN = 1e5 + 5;
const int INF = 0x3f3f3f3f;

template <typename T>
inline void read(T& x) {
  x = 0; int f = 1; char c = getchar(); while (c < '0' || c > '9') { if (c == '-') f = -f; c = getchar(); }
  while (c >= '0' && c <= '9') { x = (x << 3) + (x << 1) + (c ^ 48), c = getchar(); } x *= f;
}
template <typename T, typename... Args>
inline void read (T &x, Args&... Arg) { read (x), read (Arg...); }
template <typename T>
inline T Abs(T x) { return x < 0 ? -x : x; }
template <typename T>
inline T Max(T x, T y) { return x > y ? x : y; }
template <typename T>
inline T Min(T x, T y) { return x < y ? x : y; }

int n, len, cnt, a[MAXN], b[MAXN];
LL res;

int ind(int x) { return upper_bound(b, b + len + 1, x) - b; }
struct CartesianTree {
  int sta[MAXN], tp, root;
  struct Node { int l, r; } s[MAXN << 2];
  void build(int n, int val[]) {
    int maxl = -INF;
    val[sta[tp]] = INF;
    for (int i = 1; i <= n; i++) {
      bool flag = false;
      if (val[i] > maxl) maxl = val[i], root = i;
      while (val[i] > val[sta[tp]]) tp--, flag = true;
      s[sta[tp]].r = i;
      if (flag) s[i].l = sta[tp + 1];
      sta[++tp] = i;
    }
  }
} ct;
struct FenwickTree {
  int s[MAXN];
  int lowbit(int x) { return x & -x; }
  void update(int pos, int delta) { for (int i = pos; i <= n; i += lowbit(i)) s[i] += delta; }
  int query(int pos) {
    int res = 0;
    for (int i = pos; i; i -= lowbit(i)) res += s[i];
    return res;
  }
} ft;

void operate(int l, int r, int u, int opt) {
  for (int i = l; i <= r; i++) {
    int pos = ind(b[a[u]] / b[a[i]]);
    if (pos) res += opt * ft.query(pos - 1);
  }
}
void dfs(int u, int l, int r) {
  if (u == 0) return;
  if (u - l > r - u) operate(u, r, u, -1), dfs(ct.s[u].l, l, u - 1), ft.update(a[u], 1), operate(u, r, u, +1), dfs(ct.s[u].r, u + 1, r);
  else operate(l, u, u, -1), dfs(ct.s[u].r, u + 1, r), ft.update(a[u], 1), operate(l, u, u, +1), dfs(ct.s[u].l, l, u - 1);
}

int main() {

  read(n);
  for (int i = 1; i <= n; i++) read(a[i]), b[i] = a[i];

  sort(b + 1, b + 1 + n), len = unique(b + 1, b + 1 + n) - b - 1;
  for (int i = 1; i <= n; i++) a[i] = lower_bound(b + 1, b + 1 + len, a[i]) - b;

  ct.build(n, a);
  dfs(ct.root, 1, n);
  printf("%lld\n", res);

  return 0;
}

AGC 026 D

link

首先最小值分治，考虑怎么从下一层转移过来。
定义 $dp_{u, 0/1}$ 在 $u$ 的子树中，其中 $0/1$ 表示这两个相邻的块是否是同样的颜色，的方案数，如果是，那么这一层只能取反，否则可以相同，可以取反，设这一层的最小值有 $m$ 个，矩形高是 $x$ 。

$$ dp[u][0] = 2^{x} \times \Pi_{v\in son_u} dp[v][0] \\ dp[u][1] = 2^{empty_u} \times \Pi_{v\in son_u}(dp[v][1] + dp[v][0]) + (2^{x} - 2) \times \Pi_{v\in son_u} dp[v][0] $$

第一个式子是说，考虑枚举每个高度初始的颜色，本层有唯一的状态，且上一层的任何状态都能合法地转移下来。

第二个式子第一项的意思是最小值的位置初始可以任意染色，如果儿子黑白相间那么初始有复制和取反两种选择，否则只能取反；第二项是计算当前还是黑白相间的染色方案，由于初始两种颜色不同的黑白相间方案各被第一项计算了一次，所以要减去。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
using namespace std;
const int MAXN = 1e2 + 5;
const int INF = 0x3f3f3f3f;
const int Mod = 1e9 + 7;

int n, h[MAXN];

struct Resault {
    LL re, su;
    Resault() {}
    Resault(LL Re, LL Su) { re = Re, su = Su; }
} ans;

LL qpow(LL x, int y) {
    LL res = 1;
    while (y) {
        if (y & 1) res = res * x % Mod;
        x = x * x % Mod;
        y >>= 1;
    }
    return res;
}

/*
{%raw%}$$
dp[u][0] = 2^{x} \times \Pi_{v\in son_u} dp[v][0] \\
dp[u][1] = 2^{empty_u} \times \Pi_{v\in son_u}(dp[v][1] + dp[v][0]) + (2^{x} - 2) \times \Pi_{v\in son_u} dp[v][0]
$${%endraw%}
*/

Resault dfs(int l, int r, int dep); 

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%d", &h[i]);
    ans = dfs(1, n, 0);
    printf("%lld\n", ans.su);
    return 0;
}

Resault dfs(int l, int r, int last) {
    // printf("%d %d\n", l, r);
    if (l > r) {
        return Resault(1, 0); 
    }
    int minl = INF;
    for (int i = l; i <= r; i++) { minl = min(minl, h[i]); }
    int height = minl - last;
    int part[MAXN];
    memset(part, 0, sizeof(part));
    int cnt = 0;
    part[++cnt] = l - 1;
    for (int i = l; i <= r; i++) {
        if (h[i] == minl) {
            part[++cnt] = i;
        }
    }
    part[++cnt] = r + 1;
    // for (int i = 1; i <= cnt; i++) {
    //     printf("--%d", part[i]);
    // }
    // printf("\n");
    Resault now(1ll, 1ll);
    for (int i = 1; i < cnt; i++) {
        Resault tmp = dfs(part[i] + 1, part[i + 1] - 1, minl);
        now.re = (now.re * tmp.re) % Mod;
        now.su = (now.su * (tmp.re + tmp.su)) % Mod;
    }
    Resault res(0, 0);
    res.re = (qpow(2ll, height)) * now.re % Mod;
    res.su = ((qpow(2ll, height) - 2) * now.re % Mod + (qpow(2ll, cnt - 2)) * now.su % Mod) % Mod;
    return res;
}

CF1083E

ez

算是复习一下斜率优化的板子，首先按 $x$ 升序排了之后可以写出式子 $dp_{i} = \max\{dp_{j} + (x_i - x_j)y_i - w_i\}$ 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
/*
節子は そのまま目を覚まさなかった
昭和20年9月21日夜 僕は死んだ
昭和20年 僕は死んだ
節子は そのまま目を覚まさなかった
昭和20年9月21日夜 僕は死んだ
僕は死んだ 昭和20年 She never woke up
僕は死んだ She never woke up She never woke up
September 21st 節子は
September 21st She never woke up
September 21st，1945，that was the night I died
*/
#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target("avx2,fma")
#include <cstdio>
#include <iostream>
#include <algorithm>
#define LL long long
#define ULL unsigned long long
using namespace std;
const int MAXN = 1e6 + 5;

template <typename T>
inline void read(T& x) {
  x = 0; int f = 1; char c = getchar(); while (c < '0' || c > '9') { if (c == '-') f = -f; c = getchar(); }
  while (c >= '0' && c <= '9') { x = (x << 3) + (x << 1) + (c ^ 48), c = getchar(); } x *= f;
}
template <typename T, typename... Args>
inline void read (T &x, Args&... Arg) { read (x), read (Arg...); }
template <typename T>
inline T Abs(T x) { return x < 0 ? -x : x; }
template <typename T>
inline T Max(T x, T y) { return x > y ? x : y; }
template <typename T>
inline T Min(T x, T y) { return x < y ? x : y; }

int n, head, tail, q[MAXN];
struct Point { LL x, y, w; } a[MAXN];
LL res, dp[MAXN];

double X(int pos) { return a[pos].x; }
double Y(int pos) { return dp[pos]; }
double slope(int u, int v) { return (Y(v) - Y(u)) / ((X(v) - X(u))); }

int main() {

  read(n);
  for (int i = 1; i <= n; i++) read(a[i].x, a[i].y, a[i].w);
  sort(a + 1, a + 1 + n, [](const Point& p, const Point& q) { return p.x < q.x; });

  for (int i = 1; i <= n; i++) {
    while (head < tail && slope(q[head], q[head + 1]) >= a[i].y) head++;
    dp[i] = a[i].x * a[i].y - a[i].w;
    int j = q[head];
    dp[i] = Max(dp[i], dp[j] + (a[i].x - a[j].x) * a[i].y - a[i].w);
    while (head < tail && slope(q[tail - 1], q[tail]) <= slope(q[tail], i)) tail--;
    q[++tail] = i;
    res = Max(res, dp[i]);
  }
  printf("%lld\n", res);

  return 0;
}

CF1152F2

装压 与 矩乘

改变我们对问题的描述，或者说是改变我们生成这个序列的方式，因为一个一个往后面放是难以实现的，联想到 nyh 以前给我讲的一道题， ABC267G 。

ABC267G 计数的方式是按值从小往大考虑每个数字能够放的位置的个数，这样计数的依据是限制在于相邻两个数的数值，而这道题一样是，限制是 $\forall i \in [2, k] a_i \le a_{i - 1} + m$ 。

于是我们也这样去计数，从小到大依次枚举每个数能放的位置，其实我们只要知道这个已经生成的数列中有多少个 $a_i \in [i - m, i]$ 就可以了（放在这些数后面），我们注意到 $k$ 与 $n$ 不等价，并且 $k$ 非常小，于是可以用 $i$ 当前数字， $j$ 生成的序列的长度， $S$ 值在 $[i - m, i]$ 的数的装压。

为什么这样的转移非常妙呢，在于用到了 $m \le 4$ 这个关键的限制，意思是说我们不用考虑 $(0, i - m]$ 以前的数。

写出方程

$$ dp_{i, j, S} \times (\mathrm{popcnt(S) + 1}) \rightarrow dp_{i + 1, j + 1, ((S << 1) + 1) \& (2^m - 1)} \\ dp_{i, j, S} \rightarrow dp_{i + 1, j, ((S << 1) + 1) \& (2^m-1)} $$

然而 $n$ 很大，于是矩阵快速幂即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
/*
節子は そのまま目を覚まさなかった
昭和20年9月21日夜 僕は死んだ
昭和20年 僕は死んだ
節子は そのまま目を覚まさなかった
昭和20年9月21日夜 僕は死んだ
僕は死んだ 昭和20年 She never woke up
僕は死んだ She never woke up She never woke up
September 21st 節子は
September 21st She never woke up
September 21st，1945，that was the night I died
*/
#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target("avx2,fma")
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
#define ULL unsigned long long
using namespace std;
const int MAXM = 8;
const int Mod = 1e9 + 7;

template <typename T>
inline void read(T& x) {
  x = 0; int f = 1; char c = getchar(); while (c < '0' || c > '9') { if (c == '-') f = -f; c = getchar(); }
  while (c >= '0' && c <= '9') { x = (x << 3) + (x << 1) + (c ^ 48), c = getchar(); } x *= f;
}
template <typename T, typename... Args>
inline void read (T &x, Args&... Arg) { read (x), read (Arg...); }
template <typename T>
inline T Abs(T x) { return x < 0 ? -x : x; }
template <typename T>
inline T Max(T x, T y) { return x > y ? x : y; }
template <typename T>
inline T Min(T x, T y) { return x < y ? x : y; }

int n, k, m, tot;

struct Matrix {
  LL a[1 << MAXM][1 << MAXM];
  Matrix operator * (const Matrix& oth) const {
    Matrix res;
    memset(res.a, 0, sizeof(res.a));
    for (int i = 0; i <= tot; i++)
      for (int j = 0; j <= tot; j++)
        for (int k = 0; k <= tot; k++)
          res.a[i][j] = (res.a[i][j] + a[i][k] * oth.a[k][j] % Mod) % Mod;
    return res;
  }
} f, ans;

int main() {

  read(n, k, m), tot = k << m;
  for (int i = 0; i < k; i++) {
    for (int s = 0; s < (1 << m); s++) {
      int nxt = (s << 1) & ((1 << m) - 1);
      int cnt = __builtin_popcount(s) + 1;
      f.a[(i << m) + s][(i << m) + nxt] = 1;
      if (i == k - 1) f.a[(i << m) + s][tot] = cnt;
      else f.a[(i << m) + s][((i + 1) << m) + nxt + 1] = cnt;
    }
  }
  ans.a[0][0] = 1, f.a[tot][tot] = 1;
  while (n) {
    if (n & 1) ans = ans * f;
    f = f * f;
    n >>= 1;
  }
  printf("%lld\n", ans.a[0][tot]);

  return 0;
}

GYM 102984 F

复习决策单调性

第一眼看到题有点懵，但是注意到数据范围里面有一句 $C_j \ge C_{j + 1}$ ，意思是你连击得越长之后你的加成会越小（什么垃圾音游）。
然后有一个非常平凡的 $\Theta(n^2k)$ 的做法，加一个决策单调性就直接过了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
/*
節子は そのまま目を覚まさなかった
昭和20年9月21日夜 僕は死んだ
昭和20年 僕は死んだ
節子は そのまま目を覚まさなかった
昭和20年9月21日夜 僕は死んだ
僕は死んだ 昭和20年 She never woke up
僕は死んだ She never woke up She never woke up
September 21st 節子は
September 21st She never woke up
September 21st，1945，that was the night I died
*/
#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target("avx2,fma")
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define int long long
#define LL long long
#define ULL unsigned long long
using namespace std;
const int MAXN = 2e3 + 5;

template <typename T>
inline void read(T& x) {
  x = 0; int f = 1; char c = getchar(); while (c < '0' || c > '9') { if (c == '-') f = -f; c = getchar(); }
  while (c >= '0' && c <= '9') { x = (x << 3) + (x << 1) + (c ^ 48), c = getchar(); } x *= f;
}
template <typename T, typename... Args>
inline void read (T &x, Args&... Arg) { read (x), read (Arg...); }
template <typename T>
inline T Abs(T x) { return x < 0 ? -x : x; }
template <typename T>
inline T Max(T x, T y) { return x > y ? x : y; }
template <typename T>
inline T Min(T x, T y) { return x < y ? x : y; }

int n, m, p, a[MAXN], c[MAXN], dp[MAXN][MAXN], sum[MAXN][MAXN], res;

void dfs(int pos, int l, int r, int ql, int qr) {
  if (l > r) return;
  int mid = (l + r) >> 1, k = 0;
  for (int i = ql; i < mid - 1; i++) {
    if (dp[pos - 1][i] + sum[i + 1][mid - 1] + p > dp[pos][mid])
      dp[pos][mid] = dp[pos - 1][i] + sum[i + 1][mid - 1] + p, k = i;
  }
  dfs(pos, l, mid - 1, ql, k), dfs(pos, mid + 1, r, k, qr);
}

signed main() {

  read(n, m, p);
  for (int i = 1; i <= n; i++) read(a[i]);
  for (int i = 1; i <= n; i++) read(c[i]);

  memset(dp, 0xcf, sizeof(dp));
  dp[0][0] = 0;
  for (int l = 1; l <= n; l++)
    for (int r = l; r <= n; r++)
      sum[l][r] = sum[l][r - 1] + a[r] * c[r - l + 1];

  for (int i = 1; i <= n + 1; i++) {
    dfs(i, i + 1, n + 1, i - 1, n - 1);
    for (int j = i; j <= n + 1; j++) dp[i][j] = Max(dp[i][j], dp[i - 1][j - 1]);
    if (n + 1 - i <= m) res = Max(res, dp[i][n + 1]);
  }

  printf("%lld\n", res);

  return 0;
}

PA 2019 Runda 1 Muzyka pop

数位 dp ？ 但是这个分层很妙

注意到和二进制有关，依然拆开考虑，所以我们考虑每一层的贡献就可以了，然后建出 trie 。
对于一个满点来说，两个儿子也都是满点。
对于最后一个节点到根路径上的点，可能会没有右儿子，那么左儿子是非满点（并不是说下面不满，因为这样难考虑，我们只把最后的那个所在的都拉出来分一类特殊处理），只能全部放到右儿子；也有可能有满左儿子且有非满右节点，右节点贡献一倍的 $a[k+1,r]$ 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
/*
節子は そのまま目を覚まさなかった
昭和20年9月21日夜 僕は死んだ
昭和20年 僕は死んだ
節子は そのまま目を覚まさなかった
昭和20年9月21日夜 僕は死んだ
僕は死んだ 昭和20年 She never woke up
僕は死んだ She never woke up She never woke up
September 21st 節子は
September 21st She never woke up
September 21st，1945，that was the night I died
*/
#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target("avx2,fma")
#include <cstdio>
#include <iostream>
#include <algorithm>
#define LL long long
#define ULL unsigned long long
#define int long long
using namespace std;
const int MAXN = 2e2 + 5;
const LL INF = 1e18;

template <typename T>
inline void read(T& x) {
  x = 0; int f = 1; char c = getchar(); while (c < '0' || c > '9') { if (c == '-') f = -f; c = getchar(); }
  while (c >= '0' && c <= '9') { x = (x << 3) + (x << 1) + (c ^ 48), c = getchar(); } x *= f;
}
template <typename T, typename... Args>
inline void read (T &x, Args&... Arg) { read (x), read (Arg...); }
template <typename T>
inline T Abs(T x) { return x < 0 ? -x : x; }
template <typename T>
inline T Max(T x, T y) { return x > y ? x : y; }
template <typename T>
inline T Min(T x, T y) { return x < y ? x : y; }

int n, m;
LL dp[MAXN][MAXN][MAXN], a[MAXN], pre[MAXN], g[MAXN][MAXN][MAXN];
bool vis[MAXN][MAXN][MAXN], mp[MAXN][MAXN][MAXN];

LL dfs(int dep, int l, int r) {
  if (l > r) return 0;
  if (!dep) return l == r ? 0 : -INF;
  if (r - l + 1 > (1ll << dep)) return -INF;
  if (vis[dep][l][r]) return dp[dep][l][r];
  vis[dep][l][r] = 1, dp[dep][l][r] = -INF;
  for (int i = l - 1; i <= r; i++) dp[dep][l][r] = Max(dp[dep][l][r], dfs(dep - 1, l, i) + dfs(dep - 1, i + 1, r) + pre[r] - pre[i]);
  return dp[dep][l][r];
}
LL query(int dep, int l, int r) {
  if (l > r) return 0;
  if (!dep) return l == r ? 0 : -INF;
  if (mp[dep][l][r]) return g[dep][l][r];
  mp[dep][l][r] = 1, g[dep][l][r] = -INF;
  if ((m >> (dep - 1)) & 1) {
    for (int i = l - 1; i <= r; i++) g[dep][l][r] = Max(g[dep][l][r], dfs(dep - 1, l, i) + query(dep - 1, i + 1, r) + pre[r] - pre[i]);
    return g[dep][l][r];
  } else return g[dep][l][r] = query(dep - 1, l, r);
}

signed main() {

  read(n, m);
  for (int i = 1; i <= n; i++) read(a[i]), pre[i] = pre[i - 1] + a[i];
  LL tmp = m, dep = 0;
  while (tmp) dep++, tmp >>= 1ll;

  printf("%lld\n", query(dep, 1, n));

  return 0;
}

HDU 6331

经典？
加深了对至少限制的理解。
我会根号分治？
因为维数有三位，就不写下标了。

定义 $dp_0[k][i][j]$ 表示从 $i$ 走到 $j$ 恰好 $2^k$ 步的最短路，$dp_1[k][i][j]$ 表示从 $i$ 走到 $j$ 至少 $2^k$ 步的最短路， $dis[i][j]$ 表示从 $i$ 到 $j$ 的最短路。

$$ dp_0[k][i][j] = \min\{dp_0[k - 1][i][j] + dp_0[k - 1][l][j]\} \\ dp_1[k][i][j] = \min\{dp_0[k][i][j] + dis[l][j] \} $$

然而这样复杂度并不对，需要根号分治，定义 $M = \sqrt{m}$ ，重新定义这些 $dp$ 的含义， $dp_0[k][i][j] (k \le M)$ 表示从 $i$ 到 $j$ 恰好 $k$ 步的最短路，$dp_1[k][i][j] (k \le \lfloor \frac{m}{M} \rfloor)$ 表示从 $i$ 到 $j$ 恰好走了 $kM$ 步的最短距离，$dp_2[k][i][j] (k \le M)$ 表示从 $i$ 到 $j$ 走了至少 $k$ 步的最短路。

转移如下

$$ dp_0[k][i][j] = \min\{ dp_0[k - 1][i][l] + dis[l][r] \} \\ dp_1[k][i][j] = \min\{ dp_1[k - 1][i][l] + dp_0[M][l][j] \} \\ dp_2[k][i][j] = \min\{ dp_0[k][i][j] + dis[l][j] \} $$

最后把答案用 $dp_1$ 和 $dp_2$ 拼出来就可以了。

$res = \min\{ dp_1[k / M][i][l] + dp_2[k \% M][l][j] \}$ 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
/*
節子は そのまま目を覚まさなかった
昭和20年9月21日夜 僕は死んだ
昭和20年 僕は死んだ
節子は そのまま目を覚まさなかった
昭和20年9月21日夜 僕は死んだ
僕は死んだ 昭和20年 She never woke up
僕は死んだ She never woke up She never woke up
September 21st 節子は
September 21st She never woke up
September 21st，1945，that was the night I died
*/
#pragma GCC optimize("Ofast,no-stack-protector")
#pragma GCC target("avx2,fma")
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
#define ULL unsigned long long
using namespace std;
const int MAXN = 55;
const int MAXM = 1e2 + 5;
const int siz = 1e2;
const int INF = 0x3f3f3f3f;

template <typename T>
inline void read(T& x) {
  x = 0; int f = 1; char c = getchar(); while (c < '0' || c > '9') { if (c == '-') f = -f; c = getchar(); }
  while (c >= '0' && c <= '9') { x = (x << 3) + (x << 1) + (c ^ 48), c = getchar(); } x *= f;
}
template <typename T, typename... Args>
inline void read (T &x, Args&... Arg) { read (x), read (Arg...); }
template <typename T>
inline T Abs(T x) { return x < 0 ? -x : x; }
template <typename T>
inline T Max(T x, T y) { return x > y ? x : y; }
template <typename T>
inline T Min(T x, T y) { return x < y ? x : y; }

int t, n, m, q, d[MAXN][MAXN], dis[MAXN][MAXN], dp[MAXM][MAXN][MAXN], dp1[MAXM][MAXN][MAXN], dp2[MAXM][MAXN][MAXN];

int main() {

	read(t);
	while (t--) {

		read(n, m);
		memset(d, 0x3f, sizeof(d));
		for (int i = 1, u, v, w; i <= m; i++)
			read(u, v, w), d[u][v] = Min(d[u][v], w);

		memset(dp, 0x3f, sizeof(dp));
		for (int i = 1; i <= n; i++) dp[0][i][i] = 0;
		for (int k = 1; k <= siz; k++)
			for (int i = 1; i <= n; i++)
				for (int j = 1; j <= n; j++)
					for (int l = 1; l <= n; l++)
						dp[k][i][j] = Min(dp[k][i][j], dp[k - 1][i][l] + d[l][j]);

		memset(dp1, 0x3f, sizeof(dp1));
		for (int i = 1; i <= n; i++) dp1[0][i][i] = 0;
		for (int k = 1; k <= siz; k++)
			for (int i = 1; i <= n; i++)
				for (int j = 1; j <= n; j++)
					for (int l = 1; l <= n; l++)
						dp1[k][i][j] = Min(dp1[k][i][j], dp1[k - 1][i][l] + dp[siz][l][j]);

		memset(dis, 0x3f, sizeof(dis));
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++) dis[i][j] = d[i][j];
		for (int i = 1; i <= n; i++) dis[i][i] = 0;
		for (int k = 1; k <= n; k++)
			for (int i = 1; i <= n; i++)
				for (int j = 1; j <= n; j++)
					dis[i][j] = Min(dis[i][j], dis[i][k] + dis[k][j]);

		memset(dp2, 0x3f, sizeof(dp2));
		for (int k = 0; k <= siz; k++)
			for (int i = 1; i <= n; i++)
				for (int j = 1; j <= n; j++)
					for (int l = 1; l <= n; l++)
						dp2[k][i][j] = Min(dp2[k][i][j], dp[k][i][l] + dis[l][j]);

		read(q);
		for (int i = 1, u, v, k; i <= q; i++) {
			read(u, v, k);
			int ind1 = k / siz, ind2 = k % siz, res = INF;
			for (int l = 1; l <= n; l++) res = Min(res, dp1[ind1][u][l] + dp2[ind2][l][v]);
			if (res == INF) printf("-1\n");
			else printf("%d\n", res);
		}

	}

  return 0;
}
The End
「Ô mon âme, n'aspire pas à la vie immortelle, mais épuise le champ du possible.」