2021-12-26 模拟赛总结

貌似是 DP 专场呢哭

考场部分简结

上来先看题，扫了一眼， $T1$ 贪心， $T2, T3$ 没看出来，再看 $T4$ ，这不关路灯吗？

处于对 DP 的恐惧，并没有先写 $T4$ ，先看 $T1$ ，写了半天发现假掉了，根据 S2OJ 数据原则，假贪心分低不了，再写 $T2$ ， $DP$ 想假了，真棒！打了爆搜走人。切了 $T4$ ，打了个 $T3$ $30'$ 状压，取整写错了， $30 -> 10$ ，最终得分 :

$50' + 40' + 10' + 100' = 200'$

题解部分

90岁的张哥哥

题目大意：

给定一个长度为 $n$ 的序列和一个长度为 $m$ 的栈，求字典序最小的出栈序。

题目正解：

贪心 + 数据结构

题目思路：

要进行 $k$ 次操作，每次操作重复几个步骤。

设当前区间 $[l, r]$ 中的最小元素的位置为 $x$ 。
求出 $[x + 1, r]$ 的最小值，设为 $Min$ 。
弹出当前栈顶直至 $stc[top] > Min$ 。
将 $[l, x - 1]$ 加入栈中，将 $l$ 设为 $x + 1$ ， $r = \min(r + 1, n)$ ，开始进行下一轮操作。

其中前 $m$ 个数和最后 $m$ 个数要进行特殊处理。

找最小值可以用线段树或者 $ST$ 表维护。

时间复杂度：

$O(nlogn)$

题目代码：

// Code By CloudySky
#include <bits/stdc++.h>
// #define int long long
namespace IO  // namespace IO
using namespace IO;
const int inf = 2e9;
const int Maxn = 3e5 + 10;
using namespace std;

int a[Maxn], lg[Maxn], St[Maxn][30], Min, x;

void St_init(int n) {
  lg[1] = 0;
  for (int i = 2; i <= n; ++i) lg[i] = lg[i >> 1] + 1;
  for (int i = 1; i <= n; ++i) St[i][0] = a[i];
  for (int ln = 1; ln <= lg[n]; ++ln) {
    for (int l = 1; l + (1 << ln) - 1 <= n; ++l)
      St[l][ln] = min(St[l][ln - 1], St[l + (1 << (ln - 1))][ln - 1]);
  }
}

int query(int l, int r) {
  int k = lg[(r - l + 1)];
  return min(St[l][k], St[r - (1 << k) + 1][k]);
}

int stc[Maxn], top;

signed main() {
  int n = read(), m = read();
  for (int i = 1; i <= n; ++i)
    a[i] = read();
  St_init(n);
  // 特殊处理前 m 个数。
  Min = query(1, m), x;
  for (int i = 1; i <= m; ++i) {
    if (a[i] == Min) {
      x = i; break;
    }
    stc[++top] = a[i];
  }
  print(a[x], ' ');
  // 遍历序列，贪心
  for (int r = m + 1; r <= n; ++r) {
    Min = query(x + 1, r);            // 求得最小值
    while (top && stc[top] <= Min)    // 和栈顶比较
      print(stc[top--], ' ');         // 弹栈
    else
      for (x = x + 1; x <= r; ++x) {  // 将 [l, x - 1] 加入栈中，同时找到 x
        if (a[x] == Min) {
          print(a[x], ' '); break;
        }
        stc[++top] = a[x];
      }
  }
  // 特殊处理后 m 个数。这里 i 只是单纯的枚举次数，不再有其他含义。
  for (int i = 1; i <= m - 1; ++i) {
    Min = inf;
    if (x + 1 <= n) Min = query(x + 1, n);
    while (top && stc[top] <= Min)
      print(stc[top--], ' ');
    else
      for (x = x + 1; x <= n; ++x) {
        if (a[x] == Min) {
          print(a[x], ' '); break;
        }
        stc[++top] = a[x];
      }
  }
  return 0;
}

[2016NOIP福建夏令营]迷宫

题目大意：

给定一个 $N\times N$ 的矩阵，每个格子内有且仅有大写字母。求从左上角只向右或向下走，并且路径是回文，最终到达右下角的方案数，对 $281474976710656$ 取模。

题目正解：

线性 DP

题目思路：

想要判断回文，常用的方法就是记录路径，但是发现这道题状态必然开不下。所以换一种思路。

如果想要走回文，可以抽象理解为你在左上角，我在右下角，你走一步，我走一步，且我们走的格子值必须相同，最终在中间某点交会。

就有点传纸条那味了。

可以发现想要记录状态，有以下几个要素： $x1, y2, x2, y2, i$ 其中 $i$ 为步数。

根据只能向右或向下走的规则，只需要记录 $k, x1, x2$ ，其他的信息就可以推知。

设 $f_{i, x1, x2}$ 表示一共走了 $i$ 步，两个人横坐标分别为 $x1, x2$ 的方案数。

枚举时，枚举甲和乙的步数 $i$ ，以及甲乙分别行走的横坐标数 $j, k$ ，常数 $sum$ 为从左上到右下的总步数，其他信息就可以推得：

$x1 = j, y1 = i - x1, x2 = n - k + 1, y2 = sum - i - x2$

转移方程细节较多，但挺直观，直接参见代码即可。

然后发现第一维可以滚动掉。

时间复杂度：

$O(n^3)$

题目代码：

// Code By CloudySky
#include <bits/stdc++.h>
#define int long long
namespace IO  // namespace IO
using namespace IO;
const int Maxn = 510;
const int P = 281474976710656;
using namespace std;

char s[Maxn][Maxn];
int f[2][Maxn][Maxn];

signed main() {
  int n = read ();
  for (int i = 1; i <= n; ++i)
    cin >> (s[i] + 1);
  f[0][1][n] = 1;
  int sum = n * 2 + 2, u = 0;
  for (int i = 2; i <= n + 1; ++i) {
    u ^= 1, memset (f[u], 0, sizeof (f[u]));                        // 滚动数组
    for (int j = 1; j < i; ++j) {
      for (int k = 1; k < i; ++k) {
        int X1 = j, Y1 = i - X1, X2 = n - k + 1, Y2 = sum - i - X2;    // 计算坐标
        if (s[X1][Y1] != s[X2][Y2]) continue;
        if (s[X1][Y1 + 1] == s[X2][Y2 - 1])
          (f[u][X1][X2] += f[u ^ 1][X1][X2]) %= P;                  // 甲向下走，乙向上走
        if (s[X1 + 1][Y1] == s[X2 - 1][Y2])
          (f[u][X1 + 1][X2 - 1] += f[u ^ 1][X1][X2]) %= P;          // 甲向右走，乙向左走
        if (s[X1][Y1 + 1] == s[X2 - 1][Y2])
          (f[u][X1][X2 - 1] += f[u ^ 1][X1][X2]) %= P;              // 甲向下走，乙向左走
        if (s[X1 + 1][Y1] == s[X2][Y2 - 1])
          (f[u][X1 + 1][X2] += f[u ^ 1][X1][X2]) %= P;              // 甲向右走，乙向上走
      }
    }
  }
  int ans = 0;
  for (int i = 1; i <= n; ++i)
    (ans += f[u ^ 1][i][i]) %= P;                                   // 统计总贡献
  print (ans);
  return 0;
}

[FJWC2017]恐狼后卫

题目大意：

有 $n$ 个手牌，每个手牌有三个属性 $a, b, h$ 表示这个手牌攻击力为 $a$ ，可以给旁边手牌攻击力加成为 $b$ ，生命值为 $b$ 。手牌生命值为 0 后自动消失，其他牌补位。

你的攻击力为 $m$ 。求击败所有手牌消耗的最小生命值。

题目正解：

区间 $DP$

题目思路：

拿到题第一反应没头绪，但数据范围不大，没思路那就区间 $DP$ 吧，区间 $DP$ 是个好东西。

设 $f_{l, r}$ 表示杀死区间 $[l ,r]$ 的最小花费，显然 $f_{l, l}$ 为 $(a_{l} + b_{l - 1} + b_{l + 1}) \times \left\lceil\dfrac{h_l}{m}\right\rceil$ 。

考虑枚举 $k$ ，表示先杀死 $[l, k - 1]$ 和 $[k + 1, r]$ 最后击杀 $k$ 的最小花费。

$f_{l, r} = \min_{k = l}^{r}(f_{l, k - 1} + f_{k + 1, r} + (a_{k} + b_{l - 1} + b_{r + 1}) \times \left\lceil\dfrac{h_k}{m}\right\rceil)$

时间复杂度：

$O(n^3)$

题目代码：

// Code By CloudySky
#include <bits/stdc++.h>
#define int long long
namespace IO  // namespace IO
using namespace IO;
const int Maxn = 410, inf = 2e18;
using namespace std;

struct Wolf {
  int a, b, h;
} x[Maxn];

int n, m, f[Maxn][Maxn];

inline int check (int l, int p, int r) {
  int kk = x[p].a + x[l].b + x[r].b;
  return (x[p].h + m - 1) / m * kk;
}

signed main() {
  n = read (), m = read ();
  for (int i = 1; i <= n; ++i) {
    x[i] = (Wolf) {read (), read (), read ()};
  }
  for (int i = 1; i <= n; ++i)
    for (int j = i; j <= n; ++j)
      f[i][j] = inf;
  for (int i = 1; i <= n; ++i)
    f[i][i] = check (i - 1, i, i + 1);                          // 初始化 DP 数组
  for (int ln = 2; ln <= n; ++ln) {
    for (int l = 1; l + ln - 1 <= n; ++l) {
      int r = l + ln - 1;
      for (int k = l; k <= r; ++k) {
        f[l][r] = min (f[l][r], f[l][k - 1] + f[k + 1][r] + check (l - 1, k, r + 1));  // 枚举断点，转移
      }
    }
  }
  print (f[1][n]);
  return 0;
}

Trainman’s Travel

题目大意:

有 $N + 1$ 个坐标，其中你的坐标为 $p$ ，你需要指定一个顺序，依次经过剩下的 $N$ 个点，求出最小时间和。

题目正解：

区间 $DP$

题目思路：

首先你发现这道题不能通过枚举断点来转移，因为走过 $l, r$ 所用的时间并不等价于 $[l, k]$ 和 $[k + 1, r]$ 的时间和。

考虑如果你经过了区间 $[l, r]$ 那么你在到 $l - 1$ 和 $r + 1$ 所用的时间是和你当前所在左右端点有关的。

所以考虑设状态 $f_{l, r, 0/1}$ 表示你走过了区间 $[l, r]$ ，你当前在左/右端点的最小时间。

这样转移就比较容易了。

$f_{l, r, 0} = \min(f_{l + 1, r, 0} + (r - l + 1) \times (a_{l + 1} - a_l), f_{l + 1, r, 1} + (r - l + 1) \times (a_r - a_l))$

$f_{l, r, 1} = \min(f_{l, r - 1, 1} + (r - l + 1) \times (a_r - a_{r - 1}), f_{l, r - 1, 0} + (r - l + 1) \times (a_r - a_l))$

时间复杂度：

$O(n^2)$

题目代码：

// Code By CloudySky
#include <bits/stdc++.h>
#define int long long
#define inf 0x3f3f3f3f3f3f3f3f
namespace IO {
inline int read() {
  int x = 0, f = 1; char c = getchar();
  while (c < '0' || c > '9') { if (c == '-') f = -1; c = getchar(); }
  while (c >= '0' && c <= '9') { x = x * 10 + (c ^ 48); c = getchar(); }
  return x * f;
}
void print_n(int x) {
  if (x > 9) print_n(x / 10);
  putchar(x % 10 + '0');
}
inline void print(int x, char s = '\n') {
  if (x < 0) putchar('-'), x = -x;
  print_n(x), putchar(s);
}
}  // namespace IO
using namespace IO;
const int Maxn = 1e3 + 10;
using namespace std;

int a[Maxn], f[Maxn][Maxn][2];

signed main() {
  int n = read (), p = read ();
  for (int l = 1; l <= n + 1; ++l) {
    for (int r = 1; r <= n + 1; ++r) {
      f[l][r][0] = f[l][r][1] = inf;
    }
  }
  for (int i = 1; i <= n; ++i) 
    a[i] = read ();
  a[n + 1] = p;
  sort (a + 1, a + n + 2);
  n = unique (a + 1, a + n + 2) - a - 1;
  p = lower_bound (a + 1, a + n + n, p) - a;
  f[p][p][0] = f[p][p][1] = 0;
  for (int len = 2; len <= n; ++len) {
    for (int l = 1; l + len - 1 <= n; ++l) {
      int r = l + len - 1;
      f[l][r][0] = min (f[l + 1][r][0] + (n - len + 1) * (a[l + 1] - a[l]), f[l + 1][r][1] + (n - len + 1) * (a[r] - a[l]));
      f[l][r][1] = min (f[l][r - 1][1] + (n - len + 1) * (a[r] - a[r - 1]), f[l][r - 1][0] + (n - len + 1) * (a[r] - a[l]));
    }
  }
  print (min (f[1][n][0], f[1][n][1]));
  return 0;
}

本文作者：CloudySky
写作时间： 2021-12-26
最后更新时间： 2021-12-26
遵循协议： BY-NC-SA

CloudySky || AFO

永远相信美好的事情即将发生。

2021-12-26 模拟赛总结

考场部分简结

题解部分

90岁的张哥哥

题目大意：

题目正解：

题目思路：

时间复杂度：

题目代码：

[2016NOIP福建夏令营]迷宫

题目大意：

题目正解：

题目思路：

时间复杂度：

题目代码：

[FJWC2017]恐狼后卫

题目大意：

题目正解：

题目思路：

时间复杂度：

题目代码：

Trainman’s Travel

题目大意:

题目正解：

题目思路：

时间复杂度：

题目代码：