JSOI 2019 简要题解

2020-05-13

JSOI 都是好题, 还不毒瘤.

「JSOI2019」精准预测

题目链接

https://loj.ac/problem/3101

解题思路

这是一道 2-SAT 题.

首先有一个朴素的想法, 对于每个时刻 $t$ 每个火星人 (?) $x$, 拆为两个点 $(x, t, 0)$, $(x, t, 1)$, 分别代表生存和死亡. 那么由题意有连边

$(x, t + 1, 0) \rightarrow (x, t, 0) \\ (x, t, 1) \rightarrow (x, t + 1, 1)$

论据: “火星人是不能够复活的”.

对于预测 $0$, 有连边

$(x, t, 1) \rightarrow (y, t + 1, 1) \\ (y, t + 1, 0) \rightarrow (x, t, 0)$

后者来源为 2-SAT 的性质, 下文同理.

对于预测 $1$, 有连边

$(x, t, 0) \rightarrow (y, t, 1) \\ (y, t, 0) \rightarrow (x, t, 1)$

对于计算答案, 可看作统计点 $(x, T + 1, 0)$ 到达其余形同 $(y, T + 1, 1)$ 点的个数, 即有向图传递闭包, 可利用 bitset 优化复杂度. 同时, 建出的图一定是一个 DAG, 直接 DFS 一遍即可. ~~当然跑强连通分量也是可以的.~~

同时要注意 $(x, T + 1, 0)$ 可达 $(x, T + 1, 1)$ 的情况, 打标记特判即可.

此时得到了时间复杂度为 $O(\frac{Tnm}{w})$, 空间复杂度为 $O(Tnm)$ 的优秀做法, 令人感到快乐.

注意实际有用处的点只有 $2 (n + 2m)$ 个, 即每次预测涉及的点, 以及 $T + 1$ 时刻计算答案的部分. 同时, 可以利用分块求解的技巧. 设块大小为 $B$, 每次只统计块大小 $B$ 规模的答案, 将每次计算后得出的结果合并即可.

综上, 时间复杂度 $O(\frac{n}{B} \cdot \frac{m(n + m)}{w})$, 空间复杂度 $O\big(B(n + m)\big)$, 此处的 $B$ 可取 $10 ^ 4$.

代码实现

> 点击显示 / 隐藏

// LOJ #3101
// DeP
#include <bitset>
#include <cctype>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;

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

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;

const int MAXN = 5e4 + 5, MAXM = 1e5 + 5, BLOCK = 1e4;
const int MAXV = (MAXN + 2 * MAXM) << 1, MAXE = MAXV + MAXM * 2;

struct Evnt {
  int opt, t, x, y;
  Evnt() = default;
  Evnt(int _opt, int _t, int _x, int _y): opt(_opt), t(_t), x(_x), y(_y) { }
} A[MAXM];

int n, m, T;
int Ans[MAXN], GG[MAXV], vis[MAXV], clk;

bitset<BLOCK> f[MAXV], g;
vector<int> Time[MAXN], Idx[2][MAXN];

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

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

  void dfs(int u) {
    if (vis[u] == clk) return;
    vis[u] = clk;
    for (int v, i = head[u]; ~i; i = edges[i].nxt)
      dfs(v = edges[i].to), f[u] |= f[v];
  }
}

inline int ps(const vector<int>& p, const int& t) {
  return lower_bound(p.begin(), p.end(), t) - p.begin();
}
inline int idx(const int& c, const int& u, const int& p) {
  return Idx[c][u][p];
}

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

  read(T), read(n), read(m);
  for (int c, t, x, y, i = 1; i <= m; ++i) {
    read(c), read(t), read(x), read(y);
    A[i] = Evnt(c, t, x, y);
    Time[x].push_back(t), Time[y].push_back(t + (c == 0));
  }

  int uidx = 0;
  for (int u = 1; u <= n; ++u) Time[u].push_back(T + 1);
  for (int u = 1; u <= n; ++u) {
    vector<int>& Tu = Time[u];
    sort(Tu.begin(), Tu.end());
    Tu.erase(unique(Tu.begin(), Tu.end()), Tu.end());
    for (size_t i = 0; i < Tu.size(); ++i)
      Idx[0][u].push_back(++uidx), Idx[1][u].push_back(++uidx);
    for (size_t i = 0; i + 1 < Idx[0][u].size(); ++i)
      Graph::AddEdge(idx(0, u, i + 1), idx(0, u, i));
    for (size_t i = 0; i + 1 < Idx[1][u].size(); ++i)
      Graph::AddEdge(idx(1, u, i), idx(1, u, i + 1));
  }

  for (int i = 1; i <= m; ++i) {
    int x = A[i].x, y = A[i].y, t = A[i].t;
    if (A[i].opt == 0) {
      int px = ps(Time[x], t), py = ps(Time[y], t + 1);
      Graph::AddEdge(idx(1, x, px), idx(1, y, py));
      Graph::AddEdge(idx(0, y, py), idx(0, x, px));
    }
    if (A[i].opt == 1) {
      int px = ps(Time[x], t), py = ps(Time[y], t);
      Graph::AddEdge(idx(0, x, px), idx(1, y, py));
      Graph::AddEdge(idx(0, y, py), idx(1, x, px));
    }
  }

  for (int L = 1; L <= n; L += BLOCK) {
    int R = min(n, L + BLOCK - 1);
    ++clk, g.reset();
    for (int u = 1; u <= uidx; ++u) f[u].reset();

    for (int i = L; i <= R; ++i)
      for (const int& u: Idx[1][i]) f[u].set(i - L);
    for (int i = 1; i <= n; ++i) {
      int u = Idx[0][i].back();
      if (vis[u] != clk) Graph::dfs(u);
    }

    for (int i = L; i <= R; ++i) {
      int u = Idx[0][i].back();
      if (f[u][i - L]) g.set(i - L), GG[i] = true;
    }
    for (int u, i = 1; i <= n; ++i) if (!GG[i])
      u = Idx[0][i].back(), Ans[i] += (f[u] | g).count();
  }

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

「JSOI2019」神经网络

题目链接

https://loj.ac/problem/3102

解题思路

~~这是一道不知道为什么就是写了很久调了很久的题 (~~

首先有一个重要的性质, 哈密顿回路经过的树边, 一定不是同一棵树上相邻的链组成的. 换言之, 树上相邻两条链在哈密顿回路上并不相邻. 根据这个性质, 可对于每棵树求出分出 $k$ 条链的方案数, 再利用容斥原理计算答案.

接下来的问题分作两部分

计算每个树中, 分出 $k$ 条链的方案数.

(其实是一个很经典的树形 DP, 譬如「九省联考 2018」林克卡特树的某档部分分.)

设 $g(u, k, s)$ 表示 $u$ 的子树内, 总共组成 $k$ 条完整的链, 且包含节点 $u$ 的链状态为 $s$ 的方案数. 其中 $s \in \{ 0, 1, 2 \}$, 分别形同 ., /, /\, 也就是节点 $u$ 在子树一侧的链中保留的度数.

同时, 认为只有形成 $s = 2$ 的局面才认为是一条完整的链, 也就是说, $s = 0, 1$ 的情况并未计入总链数. 那么有初值

转移则枚举形成链条数即可, 具体式子可参考代码. 大体上讲, 转移分作两类
1. 儿子 $v$ 已形成一条完整的链, 此时直接合并到 $u$.
2. 儿子 $v$ 未形成完整的链, 此时需找到 $u$ 中对应状态合并.
注意在合适的时机更新 size 以保证时间复杂度, 以及在合并两条 $1$ 类链时, 要考虑到哈密顿回路上两条链顺序不同的影响, 乘 $2$ 作为系数.
容斥计算答案.

先忽略回路的影响, 计算哈密顿通路的个数. 记当前树中分出链个数为 $i$ 的方案数为 $f_i$, 那么根据容斥原理, 可得出当前树组成哈密顿通路个数的 EGF 为
$\sum_{i = 1} ^ n i!\ f_i \sum_{j = 1} ^ i (-1) ^ {i - j} \binom{i - 1}{i - j} \frac{x ^ j}{j!}$
稍微解释一下. 考虑用补集交计算集合交. 枚举 $j$ 表示当前的 $i$ 条链, 包含 $j$ 部分在哈密顿通路上不相邻, 剩余 $i - j$ 部分相邻. 此时不相邻的 $j$ 部分在合并 EGF 时需去除标号影响, 因此乘系数 $\frac{1}{j!}$.

交换枚举顺序, 得到
$\sum_{i = 1} ^ n \left( \frac{1}{i!} \sum_{j = i} ^ n j!\ f_j \binom{j - 1}{j - i} \right) x ^ i$
在得出 $f_i$ 之后容易在 $O(n ^ 2)$ 的时间复杂度内计算. 对于 $m$ 棵树的情况, 直接将每棵树的 EGF 相乘就好了.

记上述结果为 $H(x) = \sum\limits_{k = 0} ^ \infty \dfrac{h_k}{k!} x ^ k$, 考虑圆排列公式, 得到满足哈密顿回路限制时的 EGF 为
$F(x) = \sum_{k = 0} ^ \infty \frac{(k - 1)!}{k!} h_k \cdot x ^ k = \sum_{k = 0} ^ \infty \frac{h_k}{k} x ^ k$
对 $F(x)$ 对应数列的每一项求和即可.

时间复杂度为 $O\Big(\left(\sum k_i\right) ^ 2\Big)$, 瓶颈在于树形 DP.

代码实现

> 点击显示 / 隐藏

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

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

typedef long long LL;
const int MAXN = 5e3 + 5, P = 998244353;

int fac[MAXN], ifac[MAXN], inv[MAXN];

inline int C(const int& n, const int& m) {
  return (n < m)? 0: 1LL * fac[n] * ifac[m] % P * ifac[n - m] % P;
}

void PolyPre(int N) {
  inv[1] = 1;
  for (int i = 2; i <= N; ++i)
    inv[i] = 1LL * inv[P % i] * (P - P / i) % P;
  ifac[0] = fac[0] = 1;
  for (int i = 1; i <= N; ++i) {
    fac[i] = 1LL * i * fac[i - 1] % P;
    ifac[i] = 1LL * inv[i] * ifac[i - 1] % P;
  }
}

int Mul(int* f, const int& n, int* g, const int& m, int* h) {
  static int A[MAXN];
  memset(A, 0, (n + m - 1) * sizeof (int));
  for (int i = 0; i < n; ++i)
    for (int j = 0; j < m; ++j)
      A[i + j] = (A[i + j] + 1LL * f[i] * g[j] % P) % P;
  memcpy(h, A, (n + m - 1) * sizeof (int));
  return n + m - 1;
}

int m, n;
int f[MAXN], h[MAXN], g[3][MAXN][MAXN];

namespace Graph {
  struct Edge { int nxt, to; } edges[MAXN << 1];
  int head[MAXN], size[MAXN], eidx;

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

  void dfs(int u, int fa) {
    static LL tmp[3][MAXN];
    size[u] = 1;
    g[0][u][0] = g[1][u][0] = g[2][u][1] = 1;
    g[0][u][1] = g[1][u][1] = g[2][u][0] = 0;
    for (int v, e = head[u]; ~e; e = edges[e].nxt) {
      if ((v = edges[e].to) == fa) continue;
      dfs(v, u);
      for (int i = 0; i <= size[u]; ++i)
        for (int j = 0; j <= size[v]; ++j) {
          tmp[0][i + j] += 1LL * g[0][u][i] * g[2][v][j] % P;
          tmp[1][i + j] += 1LL * g[1][u][i] * g[2][v][j] % P;
          tmp[1][i + j] += 1LL * g[0][u][i] * g[1][v][j] % P;
          tmp[2][i + j] += 1LL * g[2][u][i] * g[2][v][j] % P;
          tmp[2][i + j + 1] += 2LL * g[1][u][i] * g[1][v][j] % P;
        }
      size[u] += size[v];
      for (int j = 0; j < 3; ++j)
        for (int i = 0; i <= size[u]; ++i)
          g[j][u][i] = tmp[j][i] % P, tmp[j][i] = 0;
    }
  }
}

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

  int dh = 0;
  h[dh++] = 1, PolyPre(MAXN - 1);
  for (int k = 1; k <= m; ++k) {
    scanf("%d", &n), Graph::init();
    for (int u, v, i = 1; i < n; ++i)
      scanf("%d%d", &u, &v), Graph::AddEdge(u, v), Graph::AddEdge(v, u);
    Graph::dfs(1, 0);
    for (int i = 1; i <= n; ++i) {
      int s1 = 0;
      for (int j = i; j <= n; ++j) {
        int s0 = 1LL * fac[j] * g[2][1][j] % P * C(j - 1, i - 1) % P;
        s1 = (s1 + (((j - i) & 1)? P - s0: s0)) % P;
      }
      f[i] = 1LL * s1 * ifac[i] % P;
    }
    dh = Mul(f, n + 1, h, dh, h);
  }

  int ans = 0;
  for (int k = 1; k < dh; ++k)
    ans = (ans + 1LL * fac[k - 1] * h[k] % P) % P;
  printf("%d\n", ans);
  return 0;
}

「JSOI2019」节日庆典

题目链接

https://loj.ac/problem/3103

解题思路

这是一道串串题, 但是同市面上套数据结构的串串题不大相同.

题目所求即对一个串 $S$ 的每个前缀, 求最小循环表示的开始位置. 如果有多个, 输出最小的.

首先不加证明地给出两个性质

对于前缀 $S_{1 \ldots k}$, 我们称能够成为该前缀最小循环表示开始位置的位置为候选点.

对于两个位置 $i < j$. 如果 $\mathrm{LCP}(S_{i\ldots n}, S_{j\ldots n}) \le k - j$, 那么 $i$, $j$ 之间肯定有一个不是候选点.

对于两个位置 $i < j$, 假设 $\mathrm{LCP}(S_{i\ldots n}, S_{j\ldots n}) > k - j$, 如果有 $k - j \le j - i$, 那么 $j$ 不是候选点.

摘抄自官方题解, 同时官方题解有具体证明. ~~UOJ 用户群有售 (雾~~. 也可以参考 yhx-12243 的证明.

利用性质 1 时, 假定已经维护出前缀 $S_{1 \ldots k-1}$ 的候选点集合, 那么该集合内元素一定满足 $\mathrm{LCP}(S_{i \ldots n}, S_{j \ldots n}) > (k - 1) - j$. 现在新加入位置 $S_k$, 只需比较 $S_{i + (k - j)}$, $S_{k}$ 的字典序大小即可.

借助于性质 2, 可以得到候选点个数不会超过 $O(\log n)$, 那么大力维护候选点集合就好了.

而对于候选点, 可通过 Z-Algorithm 比较循环同构串字典序. 因为其本质是在比较整个串和该串的某个后缀的 LCP. 同时要注意超过长度 $n$, 又从 $1$ 开始的部分.

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

代码实现

> 点击显示 / 隐藏

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

const int MAXN = 3e6 + 5;

void Z(char* s, const int& n, int* z) {
  z[1] = 0;
  for (int L = 0, R = 0, i = 2; i <= n; ++i) {
    z[i] = (i < R)? min(R - i + 1, z[i - L + 1]): 0;
    while (i + z[i] <= n && s[z[i] + 1] == s[i + z[i]])
      ++z[i];
    if (i + z[i] - 1 > R)
      L = i, R = i + z[i] - 1;
  }
}

int n;
char S[MAXN];

vector<int> f;
int z[MAXN], Ans[MAXN];

inline int scmp(const int& p, const int& lgt) {
  if (z[p] >= lgt) return 0; // same
  return (S[z[p] + 1] < S[p + z[p]])? 1: -1;
}

inline int check(const int& i, const int& j, const int& k) { // i < j
  int c1 = scmp(i + (k - j + 1), j - i);
  if (c1 != 0) return (c1 > 0)? j: i;
  int c2 = scmp(j - i + 1, i - 1);
  if (c2 != 0) return (c2 > 0)? i: j;
  return i;
}

int main() {
#ifndef ONLINE_JUDGE
  freopen("data/celebrate2.in", "r", stdin);
#endif
  scanf("%s", S + 1);

  n = (int) strlen(S + 1), Z(S, n, z);
  for (int k = 1; k <= n; ++k) {
    vector<int> g(1, k); // j
    for (const int& i: f) { // i
      // s[i + k - j] >= s[k]
      while (g.size() > 0 && S[i + k - g.back()] < S[k])
        g.pop_back();
      if (!g.size() || S[i + k - g.back()] == S[k]) {
        // k - j >= j - i --> 2j <= k + i
        while (g.size() > 0 && 2 * g.back() <= k + i)
          g.pop_back();
        g.push_back(i);
      }
    }
    f = g;
    int& j = Ans[k]; j = -1;
    for (const int& i: f)
      j = (j == -1)? i: check(i, j, k);
  }

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

DepletedPrism's Blog

JSOI 2019 简要题解

「JSOI2019」精准预测

题目链接

解题思路

代码实现

「JSOI2019」神经网络

题目链接

解题思路

代码实现

「JSOI2019」节日庆典

题目链接

解题思路

代码实现