首页 > 其他分享 >2023-02- NOI 春测复习记录

2023-02- NOI 春测复习记录

时间：2023-07-05 12:13:03浏览次数：45  
标签：02 return 春测 int long MAXN 2023 inline dp

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)\) 。
其实还可以用树状数组写，常数更小。

/*
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] \]

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

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

#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;
}

/*
$$
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]
$$
*/

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\}\) 。

/*
節子は そのまま目を覚まさなかった
昭和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\) 很大，于是矩阵快速幂即可。

/*
節子は そのまま目を覚まさなかった
昭和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)\) 的做法，加一个决策单调性就直接过了。

/*
節子は そのまま目を覚まさなかった
昭和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]\) 。

/*
節子は そのまま目を覚まさなかった
昭和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] \}\)

/*
節子は そのまま目を覚まさなかった
昭和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;
}

标签：02,return,春测,int,long,MAXN,2023,inline,dp
From： https://www.cnblogs.com/Iridescent41/p/17528169.html

相关文章

  • 2023-01-26-Poly Template
    尝试强行记忆，尝试失败。。。把最终所有的式子写一遍。约定\(F^{*}(x)\)表示\(\pmod{x^{n/2}}\)意义下的结果，\(F^{R}(x)\)表示系数翻转。\(\mathtt{Summary}\)\(\mathtt{Poly\INV}\)\[G(0)=F(0)'\\G(x)=G^{*}(x)(2-F(x)G^{*}(x))\]\(\mathtt{Poly\Sqrt}\)\[......
  • [HFCTF 2021 Final]easyflask
    根据指引拿到源码，之前访问网页拿到的源码是无缩进的，我还以为是出题人故意这样，后来才知道view-source一下能看到有缩进的源代码。#!/usr/bin/python3.6importosimportpicklefrombase64importb64decodefromflaskimportFlask,request,render_template,sessionapp......
  • 成语积累 20230705
    焚膏继晷：焚：点燃；膏：灯油或蜡烛；继：接续；晷：日影或日光。意思是点燃灯烛来接替日光照明。形容夜以继日的用功读书或努力工作。例句：～，兀兀穷年。鹤唳华亭：表示思念，怀旧之意。亦为慨叹仕途险恶，人生无常之词。例句：但～，贵何似贱；珠沉金谷，富不如贫。拾人牙慧：牙慧：牙齿内剔出的余食。比喻拾取别人......
  • [-002-]-Python3+Unittest+Selenium Web UI自动化测试之显示等待WebDriverWait
    1、WebDriverWait基本用法引入包#文件引入fromselenium.webdriver.support.uiimportWebDriverWaitfromselenium.webdriver.supportimportexpected_conditionsasEC每0.5s定位ID为userid的元素，如果定位成功，执行下面的代码；直至15s超时抛出异常可用来检查页面元素是......
  • 早期癌症筛查测试行业市场现状及未来发展趋势2023
    2023年全球及中国早期癌症筛查测试行业头部企业市场占有率及排名调研报告本文调研和分析全球早期癌症筛查测试发展现状及未来趋势，核心内容如下：（1）全球市场早期癌症筛查测试总体规模，按收入进行了统计分析，历史数据2018-2022年，预测数据2023至2029年。（2）全球市场竞争格局，全球市场头部企......
  • 2023-07-05 Matlab中的数值积分.md
    2023-07-05Matlab中的数值积分Matlab数值积分在《计算方法》一书中有介绍基本的数值分析中的积分方法，我们这里重点关注Matlab是如何帮助我们快速计算数值积分。1.integral簇函数integral簇函数下包含integral,integral2,integral3三个函数，分别对应于一重积分，二重积分和......
  • 【2023-07-02】连岳摘抄
    23:59其实，偶然并不存在，你必须得到某个东西时，它的出现绝非偶然，而是你自己，你自己的渴望和需求将你引向那里。                                                 ——黑塞......
  • Vectorworks 2023 mac|3D建筑设计软件
    Vectorworks2023mac(3D建筑设计软件)是一款全新的三维建筑设计软件，3D建筑设计软件拥有更多的功能，更加实用，更强大！Vectorworks2023mac的主要功能是设计和构建模型和渲染图，Vectorworks2023mac的主要功能还包括在线渲染、动画模拟和3D建模。在Vectorworks2023mac中，您可以进......
  • CMU15-445Project整理(2021Fall)
    本文为CMU15-445(2021Fall)的lab记录。推荐博客：https://blog.csdn.net/twentyonepilots/article/details/120868216，逻辑写得比较清楚CMU-15445官方网页https://15445.courses.cs.cmu.edu/fall2021/assignments.htmlProject#1-BufferPoolTASK#1-LRU剔除策略可以先......
  • 2023.7.4
    今天读了几页《大道至简》，做了几道pta的题目，学习了Java程序的运行，也就是《疯狂Java讲义》1.5.3部分的内容，刚刚启蒙，明天打算再读三节，pta明天多做一些，计划大概8-10个。在语系的过程中遇到一些问题，通过网上查资料解决了问题，今天大概就这样，明天见。......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99