BJOI 2018 简要题解

2020-06-01

这是 6 月份还在写省选题的悲惨故事.

BJOI 2018 Day 1 官方题解: http://qmqmqm.blog.uoj.ac/blog/3515.

「BJOI2018」求和

题目链接

https://loj.ac/problem/2491

解题思路

注意到只有查询操作, 那么直接对所有可能的 $k$ 计算当前点到根的累计点权和 $s_k$. 对于一次查询 $u$, $v$, 所求即为

$s_k(u) + s_k(v) - s_k(\mathrm{LCA}(u,\ v)) - s_k\big( \mathrm{pre}(\mathrm{LCA}(u,\ v)) \big)$

直接求就好了. ~~原来难点在求 LCA 啊~~ (雾

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

代码实现

> 点击显示 / 隐藏

// LOJ #2491
// DeP
#include <cctype>
#include <cstdio>
#include <cstring>
#include <algorithm>
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 = 3e5 + 5, MAXK = 51, P = 998244353;

int n, q;
int pre[MAXN];

namespace Graph {
  struct Edge { int nxt, to; } edges[MAXN << 1];
  int head[MAXN], 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;
  }
}

namespace HLD {
  using namespace Graph;
  int depth[MAXN], size[MAXN], son[MAXN], topfa[MAXN];
  int val[MAXK][MAXN], s[MAXK][MAXN];

  void dfs1(int u, int fa) {
    depth[u] = depth[fa] + 1;
    pre[u] = fa, size[u] = 1, son[u] = -1;
    val[0][u] = 1, s[0][u] = s[0][fa] + 1;
    for (int i = 1; i < MAXK; ++i) {
      val[i][u] = 1LL * val[i - 1][u] * depth[u] % P;
      s[i][u] = (s[i][fa] + val[i][u]) % P;
    }
    for (int v, i = head[u]; ~i; i = edges[i].nxt) {
      if ((v = edges[i].to) == fa) continue;
      dfs1(v, u), size[u] += size[v];
      if (son[u] == -1 || size[v] > size[son[u]]) son[u] = v;
    }
  }

  void dfs2(int u, int top) {
    topfa[u] = top;
    if (~son[u]) dfs2(son[u], top);
    for (int v, i = head[u]; ~i; i = edges[i].nxt)
      if ((v = edges[i].to) != pre[u] && v != son[u]) dfs2(v, v);
  }

  inline void solve(int rt = 1) {
    depth[0] = -1, dfs1(rt, 0), dfs2(rt, rt);
  }

  inline int LCA(int u, int v) {
    while (topfa[u] != topfa[v]) {
      if (depth[topfa[u]] < depth[topfa[v]]) swap(u, v);
      u = pre[topfa[u]];
    }
    return (depth[u] > depth[v])? v: u;
  }
}

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

  read(n);
  for (int u, v, i = 1; i < n; ++i) {
    read(u), read(v);
    Graph::AddEdge(u, v), Graph::AddEdge(v, u);
  }
  HLD::solve(1);

  read(q);
  for (int u, v, k; q; --q) {
    read(u), read(v), read(k);
    int l = HLD::LCA(u, v), *s = HLD::s[k];
    printf("%lld\n", (((LL) s[u] + s[v] - s[l] - s[pre[l]]) % P + P) % P);
  }
  return 0;
}

「BJOI2018」二进制

题目链接

https://loj.ac/problem/2492

解题思路

考虑到重排操作, 那么某个区间是否可以组成 $3$ 的倍数和区间中 $0$ 和 $1$ 的个数有关.

记区间内 $0$ 的个数为 $s_0$, $1$ 的个数为 $s_1$, 先考虑哪些情况无法组成 $3$ 的倍数.

$s_1$ 为 $1$, 其余位置都是 $0$.

此时无论如何重排, 所得结果都是 $2$ 的幂次, 不是 $3$ 的倍数.
$s_1$ 为奇数, 且 $s_0 < 2$.

逐位考虑二进制下的每一位 $1$, 单独拿出来在模 $3$ 意义下的值为 $1$ 或 $2$. 如果要构造出 $3$ 的倍数, 那么一定要将 $1$ 和 $2$ 两两配对. 也就可以得到, $s_1$ 为偶数时一定有解.

如果 $s_1$ 为奇数时, 若 $s_2 \ge 2$, 则可构造出 $(10101)_2 = (21)_{10}$, 其余 $0$ 放在高位, $1$ 放在低位, 从而组成 $3$ 的倍数. 而其余情况不存在类似的构造方案.

那么我们可以用所有子区间的个数减去不合法的子区间个数来计算答案, 同时, 为了避免重复计算, 认为情况 1 中 $s_0 \ge 2$. 现在的问题在于如何统计无法重排为 $3$ 的倍数的子区间个数.

考虑 DP, 对于每个区间

设 $f_L(i)$, $i \in \{ 0, 1, 2 \}$ 分别表示强制包含该区间左端点的, 满足区间内 $s_1 = 1$, 且 $s_0$ 满足 $s_0 = 0$ / $s_0 = 1$ / $s_0 \ge 2$ 的子区间个数.

$g_L(i, j)$, $i,j \in \{ 0, 1 \}$ 表示强制包含该区间左端点的, 满足区间内 $s_0 = i$, $s_1$ 奇偶性为 $j$ 的子区间个数.

同理有 $f_R(i)$, $g_R(i, j)$. 转移则直接按照定义合并两个区间, 需要维护每个区间靠左连续 $0$ 个数, 以及靠右连续 $0$ 个数, 并统计跨过两个区间的答案.

注意到有修改操作, 那么用线段树维护转移即可. 时间复杂度 $O(m \log n)$.

硬要解释的话, 这道题可以算是序列上的动态 DP?

代码实现

> 点击显示 / 隐藏

// LOJ #2492
// DeP
#include <cctype>
#include <cstdio>
#include <algorithm>
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 == '0', 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 = 1e5 + 5;

inline LL binom2(int n) { return 1LL * n * (n - 1) / 2; }

int n, q;
int A[MAXN];

#define lc (nd << 1)
#define rc (nd << 1 | 1)
namespace SGT {
  struct Node {
    int s, s0, s1, l0, r0;
    LL fl[3], fr[3], gl[2][2], gr[2][2];

    Node() { clear(); }
    Node(const int& v) {
      clear();
      if (v) fl[0] = fr[0] = gl[0][1] = gr[0][1] = s = s1 = 1;
      else gl[1][0] = gr[1][0] = s0 = l0 = r0 = 1;
    }

    inline void clear() {
      s = s0 = s1 = l0 = r0 = 0;
      for (int i = 0; i < 3; ++i) fl[i] = fr[i] = 0;
      for (int i = 0; i < 2; ++i)
        for (int j = 0; j < 2; ++j) gl[i][j] = gr[i][j] = 0;
    }
  } dat[MAXN << 2];

  Node operator + (const Node& A, const Node& B) {
    Node ret;
    for (int i = 0; i < 3; ++i) {
      ret.fl[i] += A.fl[i], ret.fr[i] += B.fr[i];
      if (A.s1 == 0) ret.fl[min(2, i + A.s0)] += B.fl[i];
      if (B.s1 == 0) ret.fr[min(2, i + B.s0)] += A.fr[i];
    }
    if (A.s1 == 1 && B.l0 > 0)
      ++ret.fl[min(2, A.s0 + B.l0)], ret.fl[2] += B.l0 - 1;
    if (B.s1 == 1 && A.r0 > 0)
      ++ret.fr[min(2, B.s0 + A.r0)], ret.fr[2] += A.r0 - 1;
    for (int i = 0; i < 2; ++i)
      for (int j = 0; j < 2; ++j) {
        ret.gl[i][j] += A.gl[i][j], ret.gr[i][j] += B.gr[i][j];
        if (i >= A.s0) ret.gl[i][j] += B.gl[i - A.s0][j ^ (A.s1 & 1)];
        if (i >= B.s0) ret.gr[i][j] += A.gr[i - B.s0][j ^ (B.s1 & 1)];
      }

    ret.l0 = (A.s1 == 0)? A.l0 + B.l0: A.l0;
    ret.r0 = (B.s1 == 0)? B.r0 + A.r0: B.r0;
    ret.s1 = A.s1 + B.s1, ret.s0 = A.s0 + B.s0, ret.s = A.s + B.s;

    ret.s += A.gr[0][0] * (B.gl[0][1] + B.gl[1][1]);
    ret.s += A.gr[0][1] * (B.gl[0][0] + B.gl[1][0]);
    ret.s += A.gr[1][0] * B.gl[0][1] + A.gr[1][1] * B.gl[0][0];
    if (A.r0 > 0)
      ret.s += (A.r0 - 1) * B.fl[0] + A.r0 * (B.fl[1] + B.fl[2]);
    if (B.l0 > 0)
      ret.s += (B.l0 - 1) * A.fr[0] + B.l0 * (A.fr[1] + A.fr[2]);
    return ret;
  }

  void maintain(int nd) { dat[nd] = dat[lc] + dat[rc]; }

  void build(int nd, int L, int R) {
    if (L == R) return void( dat[nd] = A[L] );
    int Mid = (L + R) / 2;
    build(lc, L, Mid), build(rc, Mid + 1, R);
    maintain(nd);
  }

  void Mdy(int nd, int L, int R, const int& p, const int& v) {
    if (L == R) return void( dat[nd] = Node(v) );
    int Mid = (L + R) / 2;
    if (p <= Mid) Mdy(lc, L, Mid, p, v); else Mdy(rc, Mid + 1, R, p, v);
    maintain(nd);
  }

  Node Qry(int nd, int L, int R, const int& opL, const int& opR) {
    if (opL <= L && R <= opR) return dat[nd];
    int Mid = (L + R) / 2;
    if (opR <= Mid) return Qry(lc, L, Mid, opL, opR);
    if (opL > Mid) return Qry(rc, Mid + 1, R, opL, opR);
    return Qry(lc, L, Mid, opL, opR) + Qry(rc, Mid + 1, R, opL, opR);
  }
}
#undef lc
#undef rc

int main() {
#ifndef ONLINE_JUDGE
  freopen("input.in", "r", stdin);
#endif
  read(n);
  for (int i = 1; i <= n; ++i) read(A[i]);

  SGT::build(1, 1, n);

  read(q);
  for (int opt, L, R; q; --q) {
    read(opt), read(L);
    switch (opt) {
      case 1:
        A[L] ^= 1, SGT::Mdy(1, 1, n, L, A[L]);
        break;
      case 2:
        read(R);
        printf("%lld\n", binom2(R - L + 2) - SGT::Qry(1, 1, n, L, R).s);
        break;
      default: fprintf(stderr, "ERR\n");
    }
  }
  return 0;
}

「BJOI2018」染色

题目链接

https://loj.ac/problem/2493

解题思路

容易发现, 对于不是二分图的无向图, 其答案一定为 NO. 此后只需讨论二分图, 也就是只存在偶环的图.

但不是所有二分图答案都为 YES. 例如样例 1 中的完全二分图 $K_{3, 3}$.

对于有一个公共点的两个偶环, 存在一种构造方案使其一定不合法. 这也就意味着, 如果存在度数 $> 3$ 的点, 则答案为 NO. 同时, 度数为 $1$ 的点并不影响答案, 可直接删去.

图中不同的连通块之间互不影响. 现在依次考虑每一个连通块, 剩余的情况有

不同其他环有交点的偶环.

无论给定何种颜色集合, pupil 都可构造出颜色交替的合法方案.
存在两个度数为 $3$ 的点.

此时两个度数为 $3$ 的点之间三条不相交的路径. 当且仅当这三条路径长满足 “2 - 2 - 偶数” 的形式时 pupil 一定内构造出合法方案.

详尽具体的证明可参考官方题解, 或是 zxyoi 的题解.

~~其实证明也就是给出某种方案将不合法的情况卡掉…~~

实现则直接根据以上性质判断. 时间复杂度 $O(n \log n + m)$, 可能会因实现不同而有不同 (

代码实现

> 点击显示 / 隐藏

// LOJ #2493
// DeP
#include <cctype>
#include <cstdio>
#include <vector>
#include <cstring>
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;

const int MAXN = 1e4 + 5, MAXM = 2e4 + 5;

int n, m;
vector<int> G[MAXN];
int deg[MAXN]; bool vis[MAXN];

namespace DSU {
  int fa[MAXN];

  inline void init() {
    for (int i = 1; i <= n; ++i) fa[i] = i;
  }
  inline int findfa(int u) {
    return (fa[u] == u)? u: fa[u] = findfa(fa[u]);
  }
  inline void join(int u, int v) {
    u = findfa(u), v = findfa(v);
    if (u != v) fa[u] = v;
  }
}

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

  inline void init() {
    eidx = 1;
    for (int i = 1; i <= n; ++i)
      G[i].clear(), deg[i] = 0, head[i] = -1, vis[i] = false;
  }
  inline void AddEdge(int from, int to) {
    edges[++eidx] = (Edge){ head[from], to }, head[from] = eidx;
    ++deg[to];
  }

  void Toposort() {
    static int Q[MAXN], h, t;
    Q[h = 1] = t = 0;
    for (int u = 1; u <= n; ++u)
      if (deg[u] == 1) vis[u] = true, Q[++t] = u;
    while (h <= t) {
      int u = Q[h++];
      for (int v, i = head[u]; ~i; i = edges[i].nxt) {
        if (vis[v = edges[i].to]) continue;
        if ((--deg[v]) == 1) vis[v] = true, Q[++t] = v;
      }
    }
    for (int i = 2; i <= eidx; i += 2) {
      int u = edges[i ^ 1].to, v = edges[i].to;
      if (!vis[u] && !vis[v]) DSU::join(u, v);
    }
  }
}

bool check() {
  Graph::Toposort();
  for (int u = 1; u <= n; ++u)
    G[DSU::findfa(u)].push_back(u);
  for (int u = 1; u <= n; ++u) {
    if (DSU::fa[u] != u || G[u].size() <= 1) continue;
    int c = 0, x = -1, y = -1;
    for (const int& v: G[u]) {
      if (deg[v] > 3) return false;
      if (deg[v] == 3) {
        if (++c == 1) x = v; else y = v;
      }
    }
    if (c == 1 || c > 2) return false;
    if (c == 0 && G[u].size() % 2 == 1) return false;
    if (c != 2) continue;
    if (G[u].size() % 2 == 0) return false; // 2 - 2 - Even
    int e = 0;
    for (const int& v: G[u]) if (v != x && v != y) {
      int l = 0;
      for (int w, i = Graph::head[v]; ~i; i = Graph::edges[i].nxt)
        if ((w = Graph::edges[i].to) == x || w == y) ++l;
      if (l == 2) ++e;
    }
    if (e < 2) return false;
  }
  return true;
}

int main() {
#ifndef ONLINE_JUDGE
  freopen("input.in", "r", stdin);
#endif
  int Ti; read(Ti);
  while (Ti--) {
    read(n), read(m);

    Graph::init(), DSU::init();
    for (int u, v, i = 1; i <= m; ++i) {
      read(u), read(v);
      Graph::AddEdge(u, v), Graph::AddEdge(v, u);
    }

    puts(check()? "YES": "NO");
  }
  return 0;
}

「BJOI2018」双人猜数游戏

不明真相的吃瓜群众直呼内行.

题目链接

https://loj.ac/problem/2511

解题思路

似乎更像是一道传统题?

首先可以观察到, Bob 和 Alice 确定答案的依据为, 自己已知的答案集合时候在对手看来是否是唯一的. 每次对手回答知道 / 不知道, 都能在自己的答案集合中排除一些结果. 剩余结果唯一时则得到了答案.

可能有些抽象, 对于样例 1 的模拟可参考 An_Account 的题解.

考虑用 DP 模拟这个过程. 设 $f(i, m, n)$ 表示当前在第 $i$ 轮, 已经说出 $i - 1$ 次不知道时, $(m, n)$ 是否能确定为答案. 那么最终答案需满足 $f(t + 1, m, n)$ 能够确定为答案.

显然有转移 $f(i, m, n) = f(i - 2, m, n)$, 表示之前能够确定, 再下一回合仍可确定.

对于 Bob, 转移则直接枚举 $m + n$ 的合法整数分解, 判断是否唯一存在恰好一组 $(x, y)$ 满足 $x + y = m + n$ 且 $f(i - 1, x, y)$ 为假, 也就是上一次猜测中并不能确定. Alice 则类似.

还有一种边界情况. 注意到题目要求 “ 一共说了 $t$ 次 ‘不知道’ 以后两个人都知道 $m$ 和 $n$ 是多少了”, 要排除一个人知道, 但另一个人却不知道的情况. 再进行一次类似的转移, 要求其在第 $t + 1$ 轮猜出, 且第 $t - 1$ 轮并不确定.

答案中 $m$, $n$ 上界并未给定, 但所有数据都可以在较短的时间内求出.

代码实现

可以适当调整 MAXM 或 MAXN 可以在正确性和时间内平衡. 有时候会 RE, 不用管就是了 (

> 点击显示 / 隐藏

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

const int MAXM = 1e4 + 5, MAXN = 5e2 + 5, MAXT = 20;

int s, t;
char First[MAXT];

bool f[MAXT][MAXM][MAXM];

bool check1(int m, int n, const int& i) { // Bob
  int cnt = 0, ax = -1, ay = -1;
  for (int x = s; 2 * x <= m + n; ++x) {
    int y = m + n - x;
    if (i == 1 || !f[i - 1][x][y]) {
      ++cnt, ax = x, ay = y;
      if (cnt == 2) return false;
    }
  }
  return cnt == 1 && ax == m && ay == n;
}

bool check2(int m, int n, const int& i) { // Alice
  int cnt = 0, ax = -1, ay = -1;
  for (int x = s; x * x <= m * n; ++x) if (m * n % x == 0) {
    int y = m * n / x;
    if (i == 1 || !f[i - 1][x][y]) {
      ++cnt, ax = x, ay = y;
      if (cnt == 2) return false;
    }
  }
  return cnt == 1 && ax == m && ay == n;
}

bool check1(int m, int n) {
  int cnt = 0, ax = -1, ay = -1;
  for (int x = s; 2 * x <= m + n; ++x) {
    int y = m + n - x;
    if (f[t + 1][x][y] && !f[t - 1][x][y]) {
      ++cnt, ax = x, ay = y;
      if (cnt == 2) break;
    }
  }
  return cnt == 1 && ax == m && ay == n;
}

bool check2(int m, int n) {
  int cnt = 0, ax = -1, ay = -1;
  for (int x = s; x * x <= m * n; ++x) if (m * n % x == 0) {
    int y = m * n / x;
    if (f[t + 1][x][y] && !f[t - 1][x][y]) {
      ++cnt, ax = x, ay = y;
      if (cnt == 2) break;
    }
  }
  return cnt == 1 && ax == m && ay == n;
}

int main() {
  scanf("%d%s%d", &s, First, &t);

  int fst = (First[0] == 'B'); // Alice: 0, Bob: 1

  for (int i = 1; i <= t + 1; ++i)
    for (int m = s; 2 * m < MAXN; ++m)
      for (int n = m; n < MAXN; ++n) {
        if (i > 1) f[i][m][n] |= f[i - 2][m][n];
        f[i][m][n] |= ((i & 1) ^ fst)? check2(m, n, i): check1(m, n, i);
      }
  // for (int sum = 2 * s; ; ++sum)
  for (int sum = 2 * s; sum < MAXM; ++sum)
    for (int m = s; 2 * m <= sum; ++m) {
      int n = sum - m;
      if (f[t + 1][m][n] && !(f[t][m][n] || f[t - 1][m][n])) {
        if ((t & 1) ^ fst) {
          if (!check2(m, n)) continue;
        } else {
          if (!check1(m, n)) continue;
        }
        return printf("%d %d\n", m, n), 0;
      }
    }

  puts("-1 -1");
  return 0;
}

「BJOI2018」链上二次求和

题目链接

https://loj.ac/problem/2512

解题思路

设 $s_i$ 表示 $a_i$ 的前缀和, $f_i$ 表示 $s_i$ 的前缀和.

对于每次询问, 其答案为

$\sum_{i = L} ^ R \sum_{j = i} ^ n ( s_j - s_{j - i} )= \sum_{i = L} ^ R (f_n - f_{i - 1} - f_{n - i})$

利用线段树维护 $f_i$ 部分和即可在 $O(\log n)$ 的时间复杂度内计算答案.

关键在于每次修改对 $f_i$ 的影响. 设当前修改区间为 $[L, R]$, 增加值为 $d$.

对于每个位置 $i$, 其被覆盖次数为公差为 $1$ 的等差数列, 令 $s(n) = \sum\limits_{k = 1} ^ n k = \frac{1}{2} n (n + 1)$. 整理可得

$f_i = \begin{cases} d \cdot s(i - L + 1) & i \in [L, R] \\ d \cdot s(R - L + 1) + d (i - R) (R - L + 1) & i \in (R, n] \end{cases}$

上式可表示为 $a i ^ 2 + bi + c$ 的形式. 利用线段树维护标记 $a$, $b$, $c$ 更新 $f_i$ 的部分和即可.

时间复杂度 $O(m \log n)$, 常数较大.

注意操作 1 中并未限定 $u \le v$…

代码实现

苟活在现代编译器的底层优化之下…

> 点击显示 / 隐藏

// LOJ #2512
// DeP
#include <cctype>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
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 = 2e5 + 5, P = 1e9 + 7, iv2 = 500000004, iv6 = 166666668;

inline int Fix(int a) { return a + (a >> 31 & P); }
inline int pls(int a, int b) { return Fix(a + b - P); }
inline int mns(int a, int b) { return Fix(a - b); }

struct Z {
  int x;

  Z() { x = 0; }
  Z(int _x): x(_x) { }

  Z operator + (const Z& rhs) const { return Z(pls(x, rhs.x)); }
  Z operator - (const Z& rhs) const { return Z(mns(x, rhs.x)); }
  Z operator * (const Z& rhs) const { return Z(1LL * x * rhs.x % P); }
  Z operator / (const int& rhs) const {
    if (rhs == 2) return *this * Z(iv2);
    if (rhs == 6) return *this * Z(iv6);
    abort();
  }
  Z operator += (const Z& rhs) { return *this = *this + rhs; }
  Z operator -= (const Z& rhs) { return *this = *this - rhs; }
  bool operator < (const Z& rhs) const { return x < rhs.x; }
  bool operator > (const Z& rhs) const { return rhs < *this; }
};

inline Z s0(Z L, Z R) { return R - L + 1; };
inline Z s1(Z n) { return (n > 0)? n * (n + 1) / 2: 0; }
inline Z s1(Z L, Z R) { return s1(R) - s1(L - 1); }
inline Z s2(Z n) { return (n > 0)? n * (n + 1) * (n * 2 + 1) / 6: 0; }
inline Z s2(Z L, Z R) { return s2(R) - s2(L - 1); }

int n, q;
int A[MAXN]; Z f[MAXN];

#define lc (nd << 1)
#define rc (nd << 1 | 1)
namespace SGT {
  Z s[MAXN << 2], ta[MAXN << 2], tb[MAXN << 2], tc[MAXN << 2];

  inline void maintain(int nd) { s[nd] = s[lc] + s[rc]; }

  inline void push(int nd, int L, int R, Z va, Z vb, Z vc) {
    ta[nd] += va, tb[nd] += vb, tc[nd] += vc;
    s[nd] += s2(L, R) * va + s1(L, R) * vb + s0(L, R) * vc;
  }
  inline void pushdown(int nd, int L, int R) {
    if (ta[nd] > 0 || tb[nd] > 0 || tc[nd] > 0) {
      int Mid = (L + R) / 2;
      push(lc, L, Mid, ta[nd], tb[nd], tc[nd]);
      push(rc, Mid + 1, R, ta[nd], tb[nd], tc[nd]);
      ta[nd] = tb[nd] = tc[nd] = 0;
    }
  }

  void build(int nd, int L, int R) {
    if (L == R)
      return void( s[nd] = f[L] );
    int Mid = (L + R) / 2;
    build(lc, L, Mid), build(rc, Mid + 1, R);
    maintain(nd);
  }

  void Mdy(int nd, int L, int R, int opL, int opR, Z va, Z vb, Z vc) {
    if (opL <= L && R <= opR)
      return push(nd, L, R, va, vb, vc);
    int Mid = (L + R) / 2;
    pushdown(nd, L, R);
    if (opL <= Mid) Mdy(lc, L, Mid, opL, opR, va, vb, vc);
    if (opR > Mid) Mdy(rc, Mid + 1, R, opL, opR, va, vb, vc);
    maintain(nd);
  }

  Z Qry(int nd, int L, int R, int opL, int opR) {
    if (opL <= L && R <= opR) return s[nd];
    int Mid = (L + R) / 2;
    pushdown(nd, L, R);
    if (opR <= Mid) return Qry(lc, L, Mid, opL, opR);
    if (opL > Mid) return Qry(rc, Mid + 1, R, opL, opR);
    return Qry(lc, L, Mid, opL, opR) + Qry(rc, Mid + 1, R, opL, opR);
  }
}
#undef lc
#undef rc

int main() {
#ifndef ONLINE_JUDGE
  freopen("input.in", "r", stdin);
#endif
  read(n), read(q);
  for (int i = 1; i <= n; ++i)
    read(A[i]), f[i] = f[i - 1] + A[i];

  for (int i = 1; i <= n; ++i) f[i] += f[i - 1];
  SGT::build(1, 0, n);

  for (int opt, L, R, v; q; --q) {
    static Z d, l;
    read(opt), read(L), read(R);
    if (L > R) swap(L, R);
    switch (opt) {
      case 1:
        read(v), d = v, l = R - L + 1;
        SGT::Mdy(1, 0, n, L, R,
            d / 2, d * mns(3, 2 * L) / 2, d * (Z(L) * L - 3 * L + 2) / 2);
        if (R < n)
          SGT::Mdy(1, 0, n, R + 1, n, 0, d * l, d * l * ((l + 1) / 2 - R));
        break;
      case 2:
        d = SGT::Qry(1, 0, n, n, n) * (R - L + 1);
        d -= SGT::Qry(1, 0, n, L - 1, R - 1) + SGT::Qry(1, 0, n, n - R, n - L);
        printf("%d\n", d.x);
        break;
      default: fprintf(stderr, "ERR\n");
    }
  }
  return 0;
}

「BJOI2018」治疗之雨

题目链接

https://loj.ac/problem/2513

解题思路

这是一道常规期望题.

设 $f_i$ 表示第一个数值为 $i$ 时, 成为最小值 $0$ 的期望步数. 记 $p_{i, j}$ 表示第一个数由 $i$ 变为 $j$ 的概率, 则有

$f_i = \begin{cases} \sum\limits_{j = 1} ^ {i + 1} p_{i, j} (f_j + 1) = 1 + \sum\limits_{j = 1} ^ {i + 1} p_{i, j} f_j & i < n \\ \sum\limits_{j = 1} ^ n p_{i, j} (f_j + 1) = 1 + \sum\limits_{j = 1} ^ n p_{i, j} f_j & i = n \end{cases}$

为计算 $p_{i, j}$, 首先设 $g_i$ 表示在一次操作中, 第一个数减少 $i$ 的概率, 则有

$g_i = \frac{\binom{k}{i} m ^ {k - i} }{(m + 1) ^ k}$

也就是讨论 $k$ 次减小的去向. 注意此处并没有关注边界情况, 在计算 $p_{i, j}$ 的时候会考虑这一点.

$g_i$ 可以在 $O(n)$ 的时间内递推求解. 此时 $p_{i, j}$ 可表示为

$p_{i, j} = \begin{cases} g_{i - j} & i = n \\ \frac{1}{m + 1} g_0 & j = i + 1 \\ \frac{1}{m + 1} g_{i - j + 1} + \frac{m}{m + 1} g_{i - j} & j < i \end{cases}$

现在就可以用高斯消元求解 $f_i$ 了. 朴素做法的时间复杂度为 $O(n ^ 3)$.

注意到本体中高斯消元的矩阵比较特殊, 在形式上类似于下三角矩阵. 那么每次将 $A_{i, i}$ 带入到其余行化简时, 有效的位置只有 $O(1)$ 个, 且完成带入后第 $n$ 行可直接确定 $f_n$. 接着利用 $f_n$ 从下向上依次回代即可解出原方程组. 此时的时间复杂度为 $O(n ^ 2)$.

同时要注意一些情况的特判, 诸如 $k = 0$, $m = 0$…

时间复杂度 $O(T n ^ 2)$.

代码实现

> 点击显示 / 隐藏

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

const int MAXN = 1505, P = 1e9 + 7;

int fpow(int base, int b) {
  int ret = 1;
  while (b > 0) {
    if (b & 1) ret = 1LL * ret * base % P;
    base = 1LL * base * base % P, b >>= 1;
  }
  return ret;
}

inline int inv(int x) { return fpow(x, P - 2); }

int n, p, m, K;
int ivm1;
int f[MAXN], g[MAXN], A[MAXN][MAXN];

inline int prb(int i, int j) {
  if (i == n) return g[i - j];
  if (j == i + 1) return 1LL * ivm1 * g[0] % P;
  return 1LL * ivm1 * (g[i - j + 1] + 1LL * m * g[i - j] % P) % P;
}

int solve() {
  if (K == 0) return -1;
  if (m == 0) {
    if (K == 1) return -1;
    int ret = 0;
    while (p > 0) p += (p < n), p -= K, ++ret;
    return ret;
  }

  g[0] = fpow(1LL * m * ivm1 % P, K);
  for (int i = 1; i <= min(n + 1, K); ++i) {
    int s = 1LL * (K - i + 1) * inv(1LL * m * i % P) % P;
    g[i] = 1LL * g[i - 1] * s % P;
  }

  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= min(i + 1, n); ++j)
      A[i][j] = (A[i][j] - prb(i, j) + P) % P;
    A[i][n + 1] = 1, A[i][i] = (A[i][i] + 1) % P;
  }

  for (int i = 1; i <= n; ++i) {
    int d = inv(A[i][i]);
    A[i][i] = 1, A[i][n + 1] = 1LL * A[i][n + 1] * d % P;
    if (i < n) A[i][i + 1] = 1LL * A[i][i + 1] * d % P;
    for (int j = i + 1; j <= n; ++j) { // i < n
      A[j][i + 1] = (A[j][i + 1] - 1LL * A[j][i] * A[i][i + 1] % P + P) % P;
      A[j][n + 1] = (A[j][n + 1] - 1LL * A[j][i] * A[i][n + 1] % P + P) % P;
      A[j][i] = 0;
    }
  }
  for (int i = n; i; --i) {
    int d = 1LL * A[i - 1][i] * A[i][n + 1] % P;
    A[i - 1][n + 1] = (A[i - 1][n + 1] - d + P) % P, A[i - 1][i] = 0;
  }

  return A[p][n + 1];
}

int main() {
#ifndef ONLINE_JUDGE
  freopen("input.in", "r", stdin);
#endif
  int Ti;
  scanf("%d", &Ti);
  while (Ti--) {
    scanf("%d%d%d%d", &n, &p, &m, &K);
    ivm1 = inv(m + 1);
    printf("%d\n", solve());

    memset(g, 0, (min(n + 1, K) + 1) * sizeof (int));
    for (int i = 1; i <= n; ++i)
      A[i][i] = 0, A[i][n + 1] = 0;
  }
  return 0;
}

后记

要退役了, 感觉再不做点 NOI 就没有机会了 = =

去写 NOI 的题了.

DepletedPrism's Blog

BJOI 2018 简要题解

「BJOI2018」求和

题目链接

解题思路

代码实现

「BJOI2018」二进制

题目链接

解题思路

代码实现

「BJOI2018」染色

题目链接

解题思路

代码实现

「BJOI2018」双人猜数游戏

题目链接

解题思路

代码实现

「BJOI2018」链上二次求和

题目链接

解题思路

代码实现

「BJOI2018」治疗之雨

题目链接

解题思路

代码实现

后记