Skip to content

ABC 266

比赛链接

A - Middle Letter

输出字符串的中间字符（长度保证为奇数），下标从 0 开始，那么中间字符的位置就是 \(\lfloor s.size() / 2\rfloor\)。

B - Modulo Number

直接输出 \((N \bmod 998244353 + 998344353) \bmod 998244353\) 即可。

C - Convex Quadrilateral

使用叉积判断两条向量夹角是否大于 180 度。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
void solve() {
  int n = 4;
  vector<int> x(n), y(n);
  for(int i = 0; i < n; i++) {
    cin >> x[i] >> y[i];
  }
  auto check = [&](PII a, PII b) {
    return a.first * b.second - a.second * b.first < 0;
  };
  for(int i = 0; i < n; i++) {
    int j = (i + 1) % 4, k = (j + 1) % 4;
    if(check(make_pair(x[j] - x[i], y[j] - y[i]), make_pair(x[k] - x[j], y[k] - y[j]))) {
      cout << "No\n";
      return;
    }
  }
  cout << "Yes\n";
}

D - Snuke Panic (1D)

经典 DP，d[t][i] 表示 t 时刻处于 i 位置的最大收益。设 a[t][i] 表示 t 时刻处于 i 位置的增益，那么有转移方程：

\(d[t][i] = max(d[t - 1][i], d[t - 1][i - 1], d[t-1][i+1]) + a[t][i]\)

但本题中大部分 \(a[t][i]\) 都是 0，所以可以不按照 t 每次递增 1 的速度来转移。

在 \(T_{i-1}\) 到 \(T_i\) 时刻，最多走 \(x = {T_i} - T_{i-1}\) 步，所以对于 \(T_i\) 时刻的每个位置 \(i\) 遍历 \([i-x, i+x]\) 中的每一个位置尝试转移即可。

复杂度 \(O(N)\)，具体实现时可以使用滚动数组来压缩。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
void solve() {
  int n; cin >> n;
  vector<ll> d(5, LLONG_MIN);
  d[0] = 0;
  int cur_t = 0;
  while(n --) {
    int t, x, a;
    cin >> t >> x >> a;
    auto f = d;
    for(int i = 0; i < 5; i++) {
      for(int j = 0; j < 5; j++) {
        if(abs(i - j) <= t - cur_t) {
          f[i] = max(f[i], d[j]);
        }
      }
    }
    f[x] += a;
    d = f;
    cur_t = t; 
  }
  cout << *max_element(d.begin(), d.end()) << "\n";
}

E - Throwing the Die

概率期望题，设 \(d[i]\) 为最多投 \(i\) 的期望，易得 \(d[1] = 3.5\)。

对于 \(d[2]\)：

  1. 如果第一次投的结果是 1,2,3，会接着投第二次，而第二次的期望仍然是 3.5。这部分的贡献是 \(3 / 6 * 3.5\)
  2. 而如果第二次投到 4,5,6 这些值因为都大于 3.5，所以不会投第二次，这部分的贡献是 \(1/6*(4 + 5 + 6)\)

所以 \(d[2] = 3 / 6 * 3.5 + 1 / 6 * (4 + 5 + 6) = 4.25\)

类似的，假设已经知道 \(d[i - 1]\)，那么求解 \(d[i]\) 时，第一次投出的结果大于 \(d[i - 1]\) 则不会投第二次，否则会接着投第二次。所以转移方程为：

\[d[i] = (\lfloor d[i - 1] \rfloor /6) * d[i-1] + 1 / 6 * ((6-\lfloor d[i-1]\rfloor)+\cdots + 6)\]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
void solve() {
  int n; cin >> n;
  vector<double> d(n + 1);
  d[1] = 3.5;
  for(int i = 2; i <= n; i++) {
    int cnt = 0, sum = 0;
    for(int j = 6; j > d[i - 1]; j--) {
      cnt ++;
      sum += j;
    }
    d[i] = 1.0 * (6 - cnt) / 6 * d[i - 1] + 1.0 * sum / 6;
  }
  cout << fixed << setprecision(10) << d[n] << '\n';
}

F - Well-defined Path Queries on a Namori

给定的图是一个基环树。只要查询的两个点不经过环，答案就是 Yes。这条性质也等价于，这两个点在以基环树的环点为根的子树上。

首先找到基环树的环，然后以环上每个点为根去跑 DFS（过程中不经过环上其他点），被同次 DFS 遍历到的点同属于一颗子树。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
void solve() {
  int n; cin >> n;
  vector<vector<int>> g(n);
  for(int i = 0; i < n; i++) {
    int u, v; cin >> u >> v; u--; v--;
    g[u].push_back(v); g[v].push_back(u);
  }

  vector<int> ins(n), stk, inc(n), id(n);
  bool flag = false; // 标记环是否被找到

  function<void(int, int)> dfs = [&](int x, int fa) {
    if(flag) return;
    ins[x] = 1; stk.push_back(x);
    for(auto &y : g[x]) {
      if(y == fa) continue;
      if(ins[y]) {
        flag = true;
        int k = x;
        while(stk.size() && stk.back() != y) {
          inc[stk.back()] = 1; // 记录该点在环上
          stk.pop_back();
        }
        inc[y] = 1;
        return;
      } else {
        dfs(y, x);
        if(flag) return;
      }
    }
    ins[x] = 0;
    stk.pop_back();
  };
  dfs(0, -1);

  function<void(int, int, int)> get = [&](int x, int fa, int idx) {
    id[x] = idx;
    for(auto &y : g[x]) {
      if(y == fa || inc[y]) continue;
      get(y, x, idx);
    }
  };
  for(int i = 0; i < n; i++) {
    if(inc[i]) {
      get(i, -1, i);
    }
  }
  int q; cin >> q;
  while(q--) {
    int u, v; cin >> u >> v; u --; v--;
    if(id[u] == id[v]) cout << "Yes\n";
    else cout <<"No\n";
  }
}

G - Yet Another RGB Sequence

组合计数题

k 个 RG 可以等价于新的字符 K，它与 B 都没有其他限制。K 和 B 的放置方法有 \(C(K + B, K)\) 种。

现在相当于将 R 和 G 插入到 B + K + 1 个空上去，R 和 G 可以放在一起，但是 G 必须放在 R 的前面。

这部分的计算方法等同于将 n 个相同的物品放在不同的 m 个盒子里，答案是 C(n + m - 1, m - 1)，因此答案为 C(R - K + B + K, B + K) * C(G - K + B, B + K)

最终答案就是 C(K + B, K) * C(R + B, B + K) * C(G + B, B + K)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
using ll = long long;
constexpr int P = 998244353;
// assume -P <= x < 2P
int norm(int x) { if (x < 0) x += P; else if (x >= P) x -= P; return x; }
// 快速幂
template <class T> T power(T a, int b) { T res = 1; for (; b; b /= 2, a *= a) { if (b % 2) { res *= a; } } return res; }
struct Int {
    int x;
    Int(int x = 0) : x(norm(x)) {}
    int val() const { return x; }
    Int operator-() const { return Int(norm(P - x)); }
    Int inv() const { assert(x != 0); return power(*this, P - 2); }
    Int &operator*=(const Int &rhs) { x = ll(x) * rhs.x % P; return *this; }
    Int &operator+=(const Int &rhs) { x = norm(x + rhs.x); return *this; }
    Int &operator-=(const Int &rhs) { x = norm(x - rhs.x); return *this; }
    Int &operator/=(const Int &rhs) { return *this *= rhs.inv(); }
    friend Int operator*(const Int &lhs, const Int &rhs) { Int res = lhs; res *= rhs; return res; }
    friend Int operator+(const Int &lhs, const Int &rhs) { Int res = lhs; res += rhs; return res; }
    friend Int operator-(const Int &lhs, const Int &rhs) { Int res = lhs; res -= rhs; return res; }
    friend Int operator/(const Int &lhs, const Int &rhs) { Int res = lhs; res /= rhs; return res; }
    friend ostream& operator << (ostream& out, const Int &x) { out << x.val(); return out; }
};

constexpr int N = 3E6 + 5;
Int fac[N], inv[N];
Int C(int A, int B){ return fac[A] * inv[B] * inv[A - B]; }

void solve() {
  int n = N - 1;
  fac[0] = 1;
  for(int i = 1; i <= n; i++) fac[i] = fac[i-1] * i;
  inv[n] = fac[n].inv();
  for(int i = n - 1; i >= 0; i--) inv[i] = inv[i+1] * (i + 1);

  int R, G, B, K;
  cin >> R >> G >> B >> K;
  cout << C(K + B, K) * C(R + B, B + K) * C(G + B, B + K) << "\n";
}
本文访问 次