SNOI 2019 简要题解

2020-05-15

这套题我做过, 我记得不是很水的吗?

from 某神仙

「SNOI2019」字符串

题目链接

https://loj.ac/problem/3095

解题思路

这是一道小清新字符串题.

可以观察到一个性质: 对于串 $s_i$, $s_j$ 之间的比较, 只需比较原串 $a_{i\ldots j}$ 的部分即可, 因为只有这部分两串不同.

先考虑任意两相邻字符不同的情况. 此时若有 $a_{i + 1} < a_i$, 则一定有 $s_i < s_j (i < j)$. 也就是在比较 $s_i$ 和 $s_j$ 的过程中, $a_{i + 1}$ 一定是第一次两串不同的位置, $a_i$ 和 $a_{i + 1}$ 的大小决定了 $s_i$ 和 $s_j$ 的大小关系.

此时从后向前扫描串 $a$. 每加入一个位置 $i$ 时, 可以直接得出 $s_i$ 和已加入串的大小关系, 利用双端队列维护排序后的结果即可.

接着考虑相邻相同字符的影响. 如果 $i$, $j$ 都在相同字符的范围之内, 即 $a_{i \ldots j}$ 相同, 那么 $s_i$ 和 $s_j$ 的顺序只能通过 $i$, $j$ 大小决定. 对于此种情况, 直接将所有相邻相同字符合并为一个位置, 对合并后的结果利用上述方法排序, 在内部按照编号大小排序就好了.

时间复杂度 $O(n)$.

代码实现

> 点击显示 / 隐藏

// LOJ #3095
// DeP
#include <deque>
#include <cstdio>
#include <vector>
using namespace std;

const int MAXN = 1e6 + 5;

int n, ns;
char a[MAXN], s[MAXN];

deque<int> Q;
vector<int> Idx[MAXN];
int idx[MAXN], Ans[MAXN];

int main() {
#ifndef ONLINE_JUDGE
  freopen("string/s3.in", "r", stdin);
#endif
  scanf("%d%s", &n, a + 1);

  for (int j, i = 1; i <= n; i = j + 1) {
    j = i;
    while (j < n && a[i] == a[j + 1]) ++j;
    s[++ns] = a[i];
    for (int k = i; k <= j; ++k)
      Idx[ns].push_back(k);
  }

  Q.push_front(ns);
  for (int i = ns - 1; i; --i)
    if (s[i + 1] < s[i]) Q.push_front(i); else Q.push_back(i);
  int c = 0;
  for (const int& v: Q) idx[++c] = v;
  for (int rnk = 0, i = 1; i <= c; ++i) {
    const int& u = idx[i];
    for (const int& v: Idx[u]) Ans[++rnk] = v;
  }

  for (int i = 1; i <= n; ++i)
    printf("%d%c", Ans[i], " \n"[i == n]);
  return 0;
}

「SNOI2019」数论

题目链接

https://loj.ac/problem/3096

解题思路

考虑到 $P$, $Q$ 的顺序对答案没有影响, 不妨令 $P \le Q$.

如果不断枚举 $x$, 则 $x$ 在模 $P$, $Q$ 意义下的值一定会出现循环, 且循环节长度 $l$ 为

$l = \frac{\operatorname{lcm}(P, Q)}{P} = \frac{Q}{\gcd(P, Q)}$

考虑到若 $x$ 满足 $\left( x \bmod P \in A \right) \land \left( x \bmod Q \in B \right)$, 那么 $x$ 一定能表示为 $x = A_i + k \cdot P$ 的形式, 注意到 $Q$ 的值并不是很大, 可以统计出模 $Q$ 意义下所有环的权值, 最后对于每个 $A_i$ 统计答案.

枚举 $x$ 在模 $Q$ 意义下的值, 并标记集合 $B$ 中的元素, 记其权值为 $1$. 找出所有环, 并记环的权值为环内元素权值的和.

形象地说, 每个环就是在图上, 由点 $x$ 向点 $(x + P) \bmod Q$ 连边, 找环的过程就是一遍 DFS.

最后考虑如何统计答案. 注意到 $x \in [0, T)$, 那么 $k \le \lfloor \frac{T - 1 - A_i}{P} \rfloor$. 此时 $x$ 会经过 $\lfloor \frac{k}{l} \rfloor$ 次完整的环, 同时剩余 $k \bmod l$ 的步数尚未行走.

对于完整的环, 直接记录环上权值总和即可; 对于剩余的部分, 可记录环上权值的前缀和统计. 为避免跨过最后一个节点的讨论, 直接将环上元素复制一遍接到原有环的后面再统计前缀和.

时间复杂度 $O(n)$.

代码实现

> 点击显示 / 隐藏

// LOJ #3096
// DeP
#include <cctype>
#include <cstdio>
#include <vector>
using namespace std;

namespace IO {
  const int MAXSIZE = 1 << 18 | 1;
  char buf[MAXSIZE], *p1, *p2;

  inline int Gc() {
    return p1 == p2 &&
      (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2)? EOF: *p1++;
  }
  template<typename T> inline void read(T& x) {
    x = 0; int f = 0, ch = Gc();
    while (!isdigit(ch)) f |= ch == '-', ch = Gc();
    while (isdigit(ch)) x = x * 10 + ch - '0', ch = Gc();
    if (f) x = -x;
  }
}
using IO::read;

typedef long long LL;
const int MAXN = 1e6 + 5;

int gcd(int a, int b) { return !b? a: gcd(b, a % b); }

int P, Q, n, m; LL T;
int A[MAXN], B[MAXN];

vector<int> Cyc[MAXN], s[MAXN];
int val[MAXN], w[MAXN], pos[MAXN], col[MAXN];

inline int sum(const int& u, const int& lgt) { // (pos_u, pos_u + lgt]
  return s[col[u]][pos[u] + lgt] - s[col[u]][pos[u]];
}

int main() {
#ifndef ONLINE_JUDGE
  freopen("number/s2.in", "r", stdin);
#endif
  read(P), read(Q), read(n), read(m), read(T);
  for (int i = 1; i <= n; ++i) read(A[i]);
  for (int i = 1; i <= m; ++i) read(B[i]);

  if (P > Q) swap(P, Q), swap(n, m), swap(A, B);

  int nC = 0, lgt = Q / gcd(P, Q);
  for (int i = 1; i <= m; ++i) val[B[i]] = 1;
  for (int x = 0; x < Q; ++x) if (!col[x]) {
    ++nC;
    for (int u = x; col[u] != nC; u = (u + P) % Q)
      col[u] = nC, Cyc[nC].push_back(u);
    for (const int& v: Cyc[nC])
      w[nC] += val[v];
  }

  for (int c = 1; c <= nC; ++c) {
    for (size_t i = 0; i < Cyc[c].size(); ++i)
      pos[Cyc[c][i]] = i;
    size_t limit = Cyc[c].size() - 1;
    for (size_t i = 0; i < limit; ++i) Cyc[c].push_back(Cyc[c][i]);
    s[c].resize(Cyc[c].size());
    for (size_t i = 0; i < Cyc[c].size(); ++i)
      s[c][i] = ((i > 0)? s[c][i - 1]: 0) + val[Cyc[c][i]];
  }

  LL ans = 0;
  for (int i = 1; i <= n; ++i) {
    const int& a = A[i];
    LL k = (T - 1 - a) / P;
    ans += (k / lgt) * w[col[a]] + sum(a, k % lgt) + val[a];
  }

  printf("%lld\n", ans);
  return 0;
}

「SNOI2019」通信

题目链接

https://loj.ac/problem/3097

解题思路

首先有一个共计 $O(n ^ 2)$ 条边的网络流做法:

设源汇分别为 $S$, $T$, 同时将每个点 $i$ 拆为两点 $x_i$, $y_i$. 连边

$S \rightarrow x_i$, 容量为 $1$, 费用为 $0$.
$S \rightarrow y_i$, 容量为 $1$, 费用为 $W$.
$y_i \rightarrow T$, 容量为 $1$, 费用为 $0$.
对于满足 $i < j$ 的点, $x_i \rightarrow y_j$, 容量为 $1$, 费用为 $\lvert a_i - a_j \lvert$.

考虑如何优化. 注意到建边的瓶颈处, 也就是最后一组连边, 和 $a_i$ 的值有关. 有一个思路为, 对于每一个 $a_i$, 都建一个新点, 按大小顺序在新点间建来回两条边, 容量为 $\infty$, 费用为 $\lvert a_{i + 1} - a_i \rvert$. 同时对于每个 $x_i$ 二分到其所在权值代表的位置 $p$, 连边 $p \rightarrow x_i$; 同理有 $p’ \rightarrow y_i$.

不过这样的方式有很大的缺陷, 即无法确定从 $x_i$ 到达 $a_i$ 位置的流量, 是否一定流向编号较大的 $y_j$.

考虑用分治解决这个问题. 设当前分治区间为 $[L, R]$, 记 $M$ 为区间中点. 那么只令 $[L, M]$ 范围内的点向新点连边, 新点向 $(M, R]$ 范围内的点连边. 此时边数为 $O(n \log n)$.

代码实现

SPFA 的队列还是用 STL 好.

> 点击显示 / 隐藏

// LOJ #3097
// DeP
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long LL;
const int MAXN = 1e3 + 5, MAXV = MAXN << 6, MAXE = MAXV * 6;

const int INF = 0x3f3f3f3f;
const LL INFLL = 0x3f3f3f3f3f3f3f3fLL;

int n, W, S, T;
int A[MAXN], B[MAXN], nB;

namespace Graph {
  struct Edge { int nxt, to, cap, flow, cost; } edges[MAXE << 1];
  int head[MAXV], eidx;

  inline void init() { memset(head, -1, sizeof head), eidx = 1; }
  inline void AddEdge(int from, int to, int c, int w) {
    edges[++eidx] = (Edge){ head[from], to, c, 0, w }, head[from] = eidx;
    edges[++eidx] = (Edge){ head[to], from, 0, 0, -w }, head[to] = eidx;
  }
}

namespace MCMF {
  using namespace Graph;
  LL d[MAXV];
  int cur[MAXV], vis[MAXV], Time;

  bool SPFA() {
    queue<int> Q;
    memset(d, 0x3f, sizeof d);
    Q.push(S);
    d[S] = 0, vis[S] = ++Time;
    while (!Q.empty()) {
      int u = Q.front(); Q.pop();
      vis[u] = Time - 1;
      for (int i = head[u]; ~i; i = edges[i].nxt) {
        const Edge& e = edges[i];
        if (d[e.to] > d[u] + e.cost && e.cap > e.flow) {
          d[e.to] = d[u] + e.cost;
          if (vis[e.to] != Time) Q.push(e.to), vis[e.to] = Time;
        }
      }
    }
    return d[T] < INFLL;
  }

  int DFS(int u, int a, LL& cost) {
    if (u == T || !a) return a;
    vis[u] = Time;
    int f, flow = 0;
    for (int& i = cur[u]; ~i; i = edges[i].nxt) {
      Edge& e = edges[i];
      if (vis[e.to] != Time && d[e.to] == d[u] + e.cost &&
          (f = DFS(e.to, min(a, e.cap - e.flow), cost)) > 0) {
        cost += f * e.cost;
        flow += f, a -= f, e.flow += f, edges[i ^ 1].flow -= f;
        if (!a) break;
      }
    }
    return flow;
  }

  LL MCMF() {
    LL ret = 0;
    while (SPFA()) {
      do {
        memcpy(cur, head, sizeof cur);
        ++Time, DFS(S, INF, ret);
      } while (vis[T] == Time);
    }
    return ret;
  }
}

int uidx;
inline int idx(const int& type, const int& u) {
  return (type == 2)? uidx + u: type * n + u;
}

void solve(int L, int R) {
  if (L == R)
    return;
  int Mid = (L + R) / 2;
  solve(L, Mid), solve(Mid + 1, R);
  nB = 0;
  for (int i = L; i <= R; ++i) B[++nB] = A[i];
  sort(B + 1, B + 1 + nB);
  nB = unique(B + 1, B + 1 + nB) - B - 1;
  for (int i = 1; i < nB; ++i) {
    Graph::AddEdge(idx(2, i), idx(2, i + 1), INF, B[i + 1] - B[i]);
    Graph::AddEdge(idx(2, i + 1), idx(2, i), INF, B[i + 1] - B[i]);
  }
  for (int i = L; i <= R; ++i) {
    int p = lower_bound(B + 1, B + 1 + nB, A[i]) - B;
    if (i <= Mid) // [L, Mid] --> (Mid, R]
      Graph::AddEdge(idx(0, i), idx(2, p), 1, 0);
    else
      Graph::AddEdge(idx(2, p), idx(1, i), 1, 0);
  }
  uidx += nB;
}

int main() {
#ifndef ONLINE_JUDGE
  freopen("input.in", "r", stdin);
#endif
  Graph::init();

  scanf("%d%d", &n, &W);
  for (int i = 1; i <= n; ++i) scanf("%d", A + i);

  uidx = 2 * n, solve(1, n);
  S = 0, T = uidx + 1;
  for (int i = 1; i <= n; ++i) {
    Graph::AddEdge(idx(1, i), T, 1, 0);
    Graph::AddEdge(S, idx(0, i), 1, 0), Graph::AddEdge(S, idx(1, i), 1, W);
  }

  printf("%lld\n", MCMF::MCMF());
  return 0;
}

「SNOI2019」纸牌

题目链接

https://loj.ac/problem/3098

解题思路

常规计数题.

注意到题目给定的两方案相同的定义, “两组牌相同当且仅当它们含有的每一种牌数量都相同”, 那么相同牌组成的顺子不超过 $2$ 组, 因为超过两组就将多余部分视为刻子.

于是 DP 时直接记录顺子个数即可. 具体的, 设 $f(i, j, k)$ 表示处理完前 $i$ 种牌, 其中有形如 $(i - 1, i, i + 1)$ 的顺子 $j$ 组, 形如 $(i, i + 1, i + 2)$ 的顺子 $k$ 组. 转移时需考虑 $a_i$ 的限制, 此时将 “初始有 $a_i$ 张 $k_i$ 号牌” 的限制看作 “$k_i$ 号牌至少选择 $a_i$ 张”, 同时对于未限制的牌有 $a_i = 0$.

具体地, 记 $s = i + j + k$, 表示 $i + 1$ 参与组成的顺子个数. 有转移

$f(i + 1, k, s) = \begin{cases} f(i, j, k) \cdot \left(\lfloor \dfrac{c - s}{3} \rfloor + 1\right) & s \ge a_{i + 1} \\ f(i, j, k) \cdot \left(\lfloor \dfrac{c - \left(s + 3 \cdot \lceil \frac{a_{i + 1} - s}{3} \rceil\right) }{3} \rfloor + 1\right) & s < a_{i + 1}\end{cases}$

其中 $s \le C$.

笼统地解释一下, 就是在选择 $i + 1$ 号牌时, 如果不满足限制就选择刻子, 否则不选择刻子.

可以发现, 在 $a_i$ 一定时, 这个转移个第一维关系不大, 那么可以用一 $9 \times 9$ 的矩阵描述这个转移, 同时利用矩阵快速幂加速运算.

将 $a_i \neq 0$ 的位置称作关键点, 那么关键点个数为 $X$. 预先处理出 $a_i = 0$ 的情况, 转移两关键点之间的部分; 每次根据 $a_i$ 值重构转移矩阵, 转移关键点位置.

时间复杂度 $O(X \log n)$, 同时带有矩阵乘法的常数.

代码实现

注意 $k_i$ 的取值范围, 需要 long long.

> 点击显示 / 隐藏

// LOJ #3098
// DeP
#include <cstdio>
#include <cstring>
using namespace std;

typedef long long LL;
const int MAXM = 9, P = 998244353;

struct Matrix {
  int g[MAXM][MAXM];
  Matrix() { init(); }
  inline void unit() {
    for (int i = 0; i < MAXM; ++i) g[i][i] = 1;
  }
  inline void init() { memset(g, 0, sizeof g); }
  Matrix operator * (const Matrix& rhs) const {
    Matrix ret;
    for (int i = 0; i < MAXM; ++i)
      for (int k = 0; k < MAXM; ++k) if (g[i][k] != 0)
        for (int j = 0; j < MAXM; ++j) if (rhs.g[k][j] != 0)
          ret.g[i][j] = (ret.g[i][j] + 1LL * g[i][k] * rhs.g[k][j] % P) % P;
    return ret;
  }
} f, g, h;

Matrix fpow(Matrix base, LL b) {
  Matrix ret; ret.unit();
  while (b > 0) {
    if (b & 1) ret = ret * base;
    base = base * base, b >>= 1;
  }
  return ret;
}

LL n, K; int X, C;

int main() {
#ifndef ONLINE_JUDGE
  freopen("input.in", "r", stdin);
#endif
  scanf("%lld%d%d", &n, &C, &X);

  for (int i = 0; i < 3; ++i)
    for (int j = 0; j < 3; ++j)
      for (int k = 0; k < 3; ++k) {
        int s = i + j + k;
        if (s <= C) h.g[3 * i + j][3 * j + k] = (C - s) / 3 + 1;
      }
  LL lst = 0;
  f.g[0][0] = 1;
  for (int a, i = 1; i <= X; ++i) {
    scanf("%lld%d", &K, &a);
    g.init(), f = f * fpow(h, K - lst - 1);
    for (int j = 0; j < 3; ++j)
      for (int k = 0; k < 3; ++k)
        for (int l = 0; l < 3; ++l) {
          int s = j + k + l;
          if (s < a) s = s + ((a - s + 2) / 3) * 3;
          if (s <= C) g.g[3 * j + k][3 * k + l] = (C - s) / 3 + 1;
        }
    f = f * g, lst = K;
  }
  f = f * fpow(h, n - lst);

  printf("%d\n", f.g[0][0]);
  return 0;
}

「SNOI2019」积木

题目链接

https://loj.ac/problem/3099

解题思路

还是 yhx-12243 的题解更为清晰明朗.

注意到题目中并未要求给出的操作数最少, 只需构造出长度限制可被接受的操作序列即可.

由上述题解的解释, 每次移动空白格的位置, 本质是找环和沿环行走的过程. 每次保证移动后, 有一个位置和最终状态匹配即可, 此时每个位置只会被搜索到一次.

时间复杂度 $O(nm)$, 构造的操作序列长度为 $2nm$.

代码实现

一些实现的技巧参考了 PaperCloud.

> 点击显示 / 隐藏

// LOJ #3099
// DeP
#include <cstdio>
#include <cassert>
#include <cstring>
using namespace std;

#define DEBUG(args...) fprintf(stderr, ##args)

const int dx[] = { 0, 0, 1, -1 }, dy[] = { 1, -1, 0, 0 }, nxt[][2] = {
  { 0, 1 }, { 1, 0 }, { 2, 3 }, { 3, 2 }
};
const int MAXN = 2e3 + 5, SIGMA = 256;

struct Point {
  int x, y;
  Point() = default;
  Point(int _x, int _y): x(_x), y(_y) { }
  bool operator != (const Point& rhs) const {
    return x != rhs.x || y != rhs.y;
  }
};

int n, m;
char S[MAXN], Ans[MAXN];

Point os, ot;
bool vis[MAXN][MAXN];
int MS[MAXN][MAXN], MT[MAXN][MAXN];

Point InitMap(int (*A)[MAXN]) {
  static int Map[SIGMA];
  Map['o'] = -1, Map['<'] = 0, Map['>'] = 1, Map['n'] = 2, Map['u'] = 3;

  Point ret(-1, -1);
  for (int i = 1; i <= n; ++i) {
    scanf("%s", S + 1);
    for (int j = 1; j <= m; ++j) {
      A[i][j] = Map[(int) S[j]];
      if (S[j] == 'o') ret = Point(i, j);
    }
  }
  return ret;
}

inline void move(const int& k) { // os --> n1 --> n2
  Point n1 = Point(os.x + dx[k], os.y + dy[k]),
        n2 = Point(n1.x + dx[MS[n1.x][n1.y]], n1.y + dy[MS[n1.x][n1.y]]);
  MS[os.x][os.y] = nxt[k][0], os = n2;
  MS[n1.x][n1.y] = nxt[k][1], MS[n2.x][n2.y] = -1;
  putchar("RLDU"[k]);
}
inline void augment(const Point& p) {
  while (os != p) move(MT[os.x][os.y]);
}

void dfs(const Point& p) {
  if (vis[p.x][p.y])
    return;
  vis[p.x][p.y] = true;
  for (int k = 0; k < 4; ++k) { // os --> n1 --> n2
    Point n1 = Point(p.x + dx[k], p.y + dy[k]);
    if (n1.x < 1 || n1.x > n || n1.y < 1 || n1.y > m || vis[n1.x][n1.y])
      continue;
    Point n2 = Point(n1.x + dx[MT[n1.x][n1.y]], n1.y + dy[MT[n1.x][n1.y]]);
    if (MS[n1.x][n1.y] != MT[n1.x][n1.y])
      move(k), augment(n2), move(MT[n2.x][n2.y]);
    move(k), vis[n1.x][n1.y] = true;
    dfs(n2), move(MT[n2.x][n2.y]);
  }
}

int main() {
#ifndef ONLINE_JUDGE
  freopen("input.in", "r", stdin);
#endif
  scanf("%d%d", &n, &m);
  os = InitMap(MS), ot = InitMap(MT);
  augment(ot), dfs(os), putchar('\n');
  return 0;
}

DepletedPrism's Blog

SNOI 2019 简要题解

「SNOI2019」字符串

题目链接

解题思路

代码实现

「SNOI2019」数论

题目链接

解题思路

代码实现

「SNOI2019」通信

题目链接

解题思路

代码实现

「SNOI2019」纸牌

题目链接

解题思路

代码实现

「SNOI2019」积木

题目链接

解题思路

代码实现

「SNOI2019」网络

题目链接

解题思路