2021 年 ICPC 陕西省赛的部分题解

2022-06-01

比赛链接

热身赛: https://ac.nowcoder.com/acm/contest/35520
现场赛: https://ac.nowcoder.com/acm/contest/35232

铁牌作伴好还乡.

事实证明还是不要取一些诸如 “写的都不对” 之类的队名, 如果一语成谶就会非常尴尬 (

热身赛

A Square

解题思路

当 $n$ 为 $2$, $3$ 或 $5$ 时结果为 No, 其余都是 Yes. Yes 的情况可以这样构造: 基于样例中 $n = 6$ 的情况, 在下面一行和靠右一行填入一个新的正方形, 这样可以覆盖 $4, 6, 8, \ldots$ 的情况. 对于奇数, 右下角换成 $2 \times 2$ 的正方形就好了, 可以覆盖 $7, 9, 11, \ldots$ 的情况.

代码实现

> 点击显示 / 隐藏

// A
// DeP
#include <cstdio>

int main() {
  int Ti;
  scanf("%d", &Ti);
  while (Ti--) {
    int n;
    scanf("%d", &n);
    printf("%s\n", (n == 2 || n == 3 || n == 5)? "No": "Yes");
  }
  return 0;
}

B CODE

解题思路

难点在于看懂题意 (

注意到至多有一处错误的条件. 得到原串至多修改一个位置的值, 而这个修改位置上的值一定导致, 二进制下为 1 每一位对应位置的值和给定值不同. 比如要修改位置 6, 那么位置 2 和位置 4 的值一定也会变化. 反过来, 如果计算出来有且只有位置 2 和位置 4 的值不匹配, 那么要修改的位置只可能是 6. 找到这个位置然后修改就好了.

代码实现

> 点击显示 / 隐藏

// B
// DeP
#include <cstdio>
#include <cstring>

constexpr int MAXN = 1 << 16 | 1;

int Ti, n;
int A[MAXN], B[MAXN];

int main() {
  scanf("%d%d", &Ti, &n);
  while (Ti--) {
    for (int i = 1; i < (1 << n); ++i)
      scanf("%1d", A + i);
    memset(B, 0, (1 << n) * sizeof(int));
    for (int i = 1; i < (1 << n); ++i) if (i ^ (i & -i)) {
      for (int k = 0; k < n; ++k)
        if ((i >> k) & 1) B[1 << k] ^= A[i];
    }
    int p = 0;
    for (int i = 0; i < n; ++i)
      if (B[1 << i] != A[1 << i]) p |= (1 << i);
    A[p] ^= 1;
    for (int i = 1; i < (1 << n); ++i) printf("%d", A[i]);
    putchar('\n');
  }
  return 0;
}

C Tree

解题思路

记 $f(u)$ 表示 $u$ 子树中的结点在这个子树中深度的最大值. 原树中一点 $u$ 的所有儿子, 在二叉树中一定是一条链. 直觉上让链上结点的 $f(v)$ 递减时答案是最优的, 排序然后贪心就好了.

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

代码实现

> 点击显示 / 隐藏

// C
// DeP
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

constexpr int MAXN = 1e5 + 5;

int n;
vector<int> G[MAXN];

int f[MAXN], T[MAXN][2];

void dfs(int u) {
  if (G[u].size() == 0)
    return void(f[u] = 1);
  for (auto &v: G[u]) dfs(v);
  sort(G[u].begin(), G[u].end(), [](int i, int j) {
      return f[i] > f[j] || (f[i] == f[j] && i < j);
    });
  T[u][0] = *G[u].begin();
  for (size_t i = 0; i + 1 < G[u].size(); ++i) {
    int v0 = G[u][i], v1 = G[u][i + 1];
    T[v0][1] = v1;
  }
  for (size_t i = 0; i < G[u].size(); ++i) {
    int v = G[u][i];
    f[u] = max(f[u], f[v] + (int) i + 1);
  }
}

int main() {
  scanf("%d", &n);
  for (int fa, u = 2; u <= n; ++u)
    scanf("%d", &fa), G[fa].push_back(u);
  dfs(1);
  printf("%d\n", f[1]);
  for (int i = 1; i <= n; ++i)
    printf("%d %d\n", T[i][0], T[i][1]);
  return 0;
}

正式赛

A SegmentTree

解题思路

首先代码的问题在于访问了线段树上每一个结点的左右儿子, 并认为数组越界了就算出错. 此时问题可转化为求解 $\frac{n(n+1)}{2}$ 个区间内有多少个区间在查询时会越界.

对于线段树上一个结点 $u$, 如果访问到 $u$ 时越界, 那么 $u$ 一定代表一个单独的位置, 将这个位置记作 $p$. 如果 $u$ 为父亲的左儿子, 那么所有以 $p$ 为右端点的区间在查询时都会越界, 因为一定会访问到 $u$. 同理, 如果是父亲的右儿子, 对应的则是以 $p$ 为左端点的区间. 据此计算可能越界的区间个数就好了.

记每组数据不满足条件的区间有 $x_i$ 个, 最终答案为

$\prod_{i = 1}^T \left(1 - \frac{x_i}{\frac{n_i (n_i + 1)}{2}}\right) ^ {q_i}$

代码实现

> 点击显示 / 隐藏

// A
// DeP
#include <cstdio>
#include <algorithm>
using namespace std;

typedef long long LL;
constexpr int MAXN = 1e5 + 5, P = 1e9 + 7;

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

int n, q;
int fr[MAXN], fl[MAXN];

namespace SGT {
#define lc (nd << 1)
#define rc (nd << 1 | 1)
  void build(int nd, int L, int R, bool left) {
    if (L == R) {
      if (nd >= 2 * n)
        left? ++fr[R]: ++fl[L];
      return;
    }
    int Mid = (L + R) / 2;
    build(lc, L, Mid, true);
    build(rc, Mid + 1, R, false);
  }
#undef lc
#undef rc
}

int main() {
  int ti, ans = 1;
  scanf("%d", &ti);
  while (ti--) {
    scanf("%d%d", &n, &q);

    fill(fr, fr + n + 1, 0);
    fill(fl, fl + n + 1, 0);
    SGT::build(1, 1, n, false);
    int s = 0;
    for (int i = 1; i <= n; ++i) {
      if (fl[i] > 0) s = (s + n - i + 1) % P;
      if (fr[i] > 0) s = (s + i) % P;
    }
    for (int i = 1; i <= n; ++i)
      fl[i] = (fl[i - 1] + fl[i]) % P;
    for (int r = 1; r <= n; ++r)
      if (fr[r] > 0)
        s = (s - fl[r] + P) % P;

    int p = (1 - (LL) s * fpow((LL) n * (n + 1) / 2 % P, P - 2) % P + P) % P;
    ans = (LL) ans * fpow(p, q) % P;
  }
  printf("%d\n", ans);
  return 0;
}

C GCD

解题思路

对于整数 $d$, 如果 $d$ 能成为 GCD 则区间 $[l, r]$ 内存在大于 $k$ 个 $d$ 的倍数. 即

$\lfloor \frac{r}{d} \rfloor - \lfloor \frac{l - 1}{d} \rfloor \geq k$

利用数论分块计算就好了. 时间复杂度 $O(\sqrt{r})$.

代码实现

> 点击显示 / 隐藏

// C
// DeP
#include <iostream>
using namespace std;

typedef long long LL;

int main() {
  LL L, R, K, ans = 0;
  cin >> L >> R >> K;
  --L;
  for (LL d1 = 1, d2; d1 <= L; d1 = d2 + 1) {
    d2 = min(R / (R / d1), L / (L / d1));
    if (R / d1 - L / d1 >= K)
      ans += d2 - d1 + 1;
  }
  for (LL d1 = L + 1, d2; d1 <= R; d1 = d2 + 1) {
    d2 = R / (R / d1);
    if (R / d1 >= K)
      ans += d2 - d1 + 1;
  }
  cout << ans << '\n';
  return 0;
}

D Disease

解题思路

考虑枚举每一个深度 $d$, 然后计算 disaster value 为 $d$ 的概率. 此时需要保证, 深度等于 $d$ 的结点要么不感染, 要么感染之后不传给自己的父亲, 但一定存在一个已经感染的结点. 深度小于 $d$ 的结点不会自下而上地被感染, 保证其不会自发地感染就好了.

因此只需要关心向上的感染. 记 $f(u)$ 此种限制下 $u$ 被感染的概率, 则有

$f(u) = \frac{p_u}{q_u} + \left(1 - \frac{p_u}{q_u}\right) \prod_{v \in \mathrm{son}(u)}\left(1 - \frac{a}{b} f(v)\right)$

记

$m(d) = \prod_{\mathrm{depth}(u) = d} \left( 1 - \frac{p_u}{q_u} \right)$

同时记 $\mathrm{pre}(u)$ 表示结点 $u$ 到其父亲那条边对应的 $\frac{a}{b}$. 最后答案为

$\sum_{d} d \cdot \left(\prod_{\mathrm{depth}(u) = d} \Big( 1 - \mathrm{pre}(u) \cdot f(u) \Big) - \prod_{\mathrm{depth}(u)=d} \Big(1 - f(u)\Big) \right) \prod_{k = 1}^{d - 1} m(k)$

预处理逆元之后的时间复杂度可以做到 $O(n)$, 不过多个快速幂的 log 也不影响什么.

代码实现

> 点击显示 / 隐藏

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

typedef long long LL;
constexpr int MAXN = 1e5 + 5, P = 1e9 + 7;

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

int n, mxd;
LL f[MAXN], g[MAXN], h[MAXN], p[MAXN], m[MAXN], pre[MAXN];

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

  inline void init() {
    memset(head, -1, sizeof head), eidx = 1;
  }
  inline void addEdge(int u, int v, int w) {
    edges[++eidx] = (Edge){ head[u], v, w }, head[u] = eidx;
  }
}

void dfs(int u, int fa, int d) {
  using namespace Graph;
  mxd = max(mxd, d);
  LL s = 1;
  for (int v, i = head[u]; ~i; i = edges[i].nxt) {
    if ((v = edges[i].v) == fa) continue;
    pre[v] = edges[i].w;
    dfs(v, u, d + 1);
    s = s * (1 - pre[v] * f[v] % P + P) % P;
  }
  f[u] = (p[u] + (1 - p[u] + P) % P * (1 - s + P) % P) % P;
  g[d] = g[d] * (1 - pre[u] * f[u] % P + P) % P;
  h[d] = h[d] * (1 - f[u] + P) % P;
  m[d] = m[d] * (1 - p[u] + P) % P;
}

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

  scanf("%d", &n);
  for (int pu, qu, u = 1; u <= n; ++u) {
    scanf("%d%d", &pu, &qu);
    p[u] = (LL) pu * fpow(qu, P - 2) % P;
  }
  for (int u, v, a, b, i = 1; i < n; ++i) {
    scanf("%d%d%d%d", &u, &v, &a, &b);
    int w = (LL) a * fpow(b, P - 2) % P;
    Graph::addEdge(u, v, w), Graph::addEdge(v, u, w);
  }

  for (int d = 0; d <= n; ++d)
    g[d] = h[d] = m[d] = 1;
  dfs(1, 0, 1);

  LL ans = 0;
  for (int d = 1; d <= mxd; ++d) {
    ans = (ans + (g[d] - h[d] + P) % P * m[d - 1] % P * d % P) % P;
    m[d] = m[d - 1] * m[d] % P;
  }
  printf("%lld\n", ans);
  return 0;
}

E swapping game

解题思路

对 $q$ 分奇偶讨论. 对于奇数, 随着操作次数的增加, $q$ 一直向右移动, 到位置 $n$ 后改向左移动, 直到位置 $1$, 周而复始且周期为 $2n$. 偶数则类似. 根据 $k$ 的大小分类讨论就好了.

代码实现

> 点击显示 / 隐藏

// E
// DeP
#include <iostream>
using namespace std;

int main() {
  int Ti;
  cin >> Ti;
  while (Ti--) {
    int n, k, q;
    cin >> n >> k >> q;
    k %= 2 * n;
    if (q & 1) {
      if (k <= n - q) {
        cout << q + k << '\n';
      } else if (k <= 2 * n - q) {
        cout << n - (k - (n - q)) + 1 << '\n';
      } else {
        cout << k - (2 * n - q) << '\n';
      }
    } else {
      if (k <= q - 1) {
        cout << q - k << '\n';
      } else if (k <= n + q - 1) {
        cout << k - (q - 1) << '\n';
      } else {
        cout << n - (k - (n + q - 1)) + 1 << '\n';
      }
    }
  }
  return 0;
}

I Rabbit

解题思路

首先考虑 $a_i$ 中含有 0 的情况. 显然, 当 0 数量大于 1 时无论去除哪个数 Cute Value 都是 0, 当 0 数量为 1 时只有去掉 0 才能改变 Cute Value, 因此这两种情况的答案分别为 0, 1.

对于 $a_i$ 中不含 0 的情况, 统计 1 的出现次数 $c_1$, 答案即为 $n - c_1$.

代码实现

> 点击显示 / 隐藏

// I
// DeP
#include <cstdio>
#include <algorithm>
using namespace std;

constexpr int MAXN = 1e5 + 5;

int n;
int A[MAXN];

int main() {
  scanf("%d", &n);
  int c0 = 0, c1 = 0;
  for (int i = 1; i <= n; ++i) {
    scanf("%d", A + i);
    if (A[i] == 0) ++c0;
  }
  if (c0 == 0) {
    sort(A + 1, A + 1 + n);
    n = unique(A + 1, A + 1 + n) - A - 1;
    for (int i = 1; i <= n; ++i)
      if (A[i] == 1) ++c1;
    printf("%d\n", n - c1);
  } else {
    printf("%d\n", c0 == 1);
  }
  return 0;
}

J Cube

解题思路

模拟就好了.

代码实现

> 点击显示 / 隐藏

// J
// DeP
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

struct pii {
  int a, b;

  pii() = default;
  pii(int _a, int _b) {
    if (_a > _b) swap(_a, _b);
    a = _a, b = _b;
  }

  bool operator < (const pii &rhs) const {
    return a < rhs.a || (a == rhs.a && b < rhs.b);
  }
  bool operator != (const pii &rhs) const {
    return *this < rhs || rhs < *this;
  }
};

struct Cube {
  vector<pii> v;

  Cube() = default;
  Cube(vector<pii> _v) {
    sort(_v.begin(), _v.end()), v = _v;
  }

  bool operator == (const Cube& rhs) const {
    if (v.size() != rhs.v.size())
      return false;
    for (size_t i = 0; i < v.size(); ++i)
      if (v[i] != rhs.v[i]) return false;
    return true;
  }
};

Cube convert(const vector<int> &v) {
  pii a = pii(v[4], v[6]), b = pii(v[5], (v[7] > 0)? v[7]: v[11]);
  int c1 = 0, c2 = 0;
  for (size_t i = 0; i < 4; ++i)
    if (v[i] > 0) { c1 = v[i]; break; }
  for (size_t i = 8; i < 12; ++i)
    if (v[i] > 0) { c2 = v[i]; break; }
  return Cube({a, b, pii(c1, c2)});
}

int main() {
  vector<int> c0(12), c1(12);
  for (size_t i = 0; i < 12; ++i)
    cin >> c0[i];
  for (size_t i = 0; i < 12; ++i)
    cin >> c1[i];
  cout << ((convert(c0) == convert(c1))? "YES": "NO") << '\n';
  return 0;
}

DepletedPrism's Blog

2021 年 ICPC 陕西省赛的部分题解

热身赛

A Square

解题思路

代码实现

B CODE

解题思路

代码实现

C Tree

解题思路

代码实现

正式赛

A SegmentTree

解题思路

代码实现

C GCD

解题思路

代码实现

D Disease

解题思路

代码实现

E swapping game

解题思路

代码实现

I Rabbit

解题思路

代码实现

J Cube

解题思路

代码实现