ABC 267

比赛链接

A - Saturday

模拟，switch 或者 if 输出即可。

B - Split?

较难的模拟，首先预存 5 列的 ID 值，然后枚举两列，看是否有 1，并且中间存在一列无 1。

void solve() {
  string s;
  cin >> s;
  s = "0" + s;
  if(s[1] == '1') {
    cout << "No\n";
    return;
  }
  vector<vector<int>> a = {
    {7},
    {4},
    {8, 2},
    {5, 1},
    {9, 3},
    {6},
    {10}
  };
  for(int i = 0; i < a.size(); i++) {
    int cnt = 0;
    for(auto &x : a[i]) if(s[x] == '1') cnt ++;
    if(cnt == 0) continue;
    bool flag = false;
    for(int j = i + 1; j < a.size(); j++) {
      cnt = 0;
      for(auto &x : a[j]) if(s[x] == '1') cnt ++;
      if(cnt == 0) flag = true;
      else if(flag) {
        cout << "Yes\n";
        return;
      }
    }
  }
  cout << "No\n";
}

C - Index × A(Continuous ver.)

设当前右端点为 \(i\)，\(sum = \sum_{j=1}^Mj*A_{i-M+j}\)，在往右移动到 \(i + 1\) 时，\(sum\) 需要更新为 \(sum - A_{i-M+j} + M * A_{i + 1}\)。

时间复杂度为 \(O(n)\)。

void solve() {
  int n, m;
  cin >> n >> m;
  vector<ll> a(n + 1);
  for(int i = 1; i <= n; i++) cin >> a[i];
  ll res = LLONG_MIN, sum = 0, cur = 0;
  for(int i = 1; i <= n; i++) {
    sum += a[i];
    if(i <= m) {
      cur += a[i] * i;
    } else {
      cur += a[i] * m;
    }

    if(i >= m) {
      res = max(res, cur);
      cur -= sum;
      sum -= a[i - m + 1];
    }
  }
  cout << res << "\n";
}

D - Index × A(Not Continuous ver.)

DP, 设 \(d[i][j]\) 表示在前 \(i\) 个元素中，选择了 \(j\) 个元素的最大值。

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

时间复杂度为 \(O(nm)\)。

void solve() {
  int n, m;
  cin >> n >> m;
  vector<ll> a(n + 1);
  vector<vector<ll>> d(n + 1, vector<ll>(m + 1, - (1ll << 60)));
  for(int i = 1; i <= n; i++) cin >> a[i];
  d[0][0] = 0;
  for(int i = 1; i <= n; i++) {
    d[i][0] = 0;
    for(int j = 1; j <= m; j++) {
      d[i][j] = max(d[i - 1][j], d[i - 1][j - 1] + a[i] * j);
    }
  }
  cout << d[n][m] << "\n";
}

E - Erasing Vertices 2

二分 \(mid\)，度数不超过 \(mid\) 的点可以放入队列，依次删去，每次删除一个点时，更新它相邻点的度数，如果更新后小于等于 \(mid\)，则放入队列。每个点不重复入队，如果最后所有点都被消除，则返回 true，否则返回 false。

时间复杂度为 \(O(M\log M)\)。

void solve() {
  int n, m;
  cin >> n >> m;
  vector<vector<int>> g(n);
  vector<int> a(n), del(n);
  vector<ll> sum(n);
  for(int i = 0; i < n; i++) cin >> a[i];
  for(int i = 0; i < m; i++) {
    int u, v; cin >> u >> v;
    u --; v--; g[u].push_back(v); g[v].push_back(u);
  }
  for(int x = 0; x < n; x ++) {
    for(auto &y : g[x]) sum[x] += a[y];
  }
  ll l = 0, r = *max_element(sum.begin(), sum.end());
  auto check = [&](ll mid) {
    queue<int> q;
    vector<int> v(n);
    auto c = sum;
    int cnt = 0;
    for(int i = 0; i < n; i++) {
      if(c[i] <= mid) {
        q.push(i);
        v[i] = 1;
      }
    }
    while(q.size()) {
      int x = q.front(); q.pop();
      cnt ++;
      for(auto &y : g[x]) {
        c[y] -= a[x];
        if(v[y] == 0 && c[y] <= mid) {
          q.push(y);
          v[y] = 1;
        }
      }
    }
    return cnt == n;
  };

  while(l < r) {
    ll mid = (l + r) >> 1;
    if(check(mid)) r = mid;
    else l = mid + 1;
  }
  cout << l << "\n";
}

F - Exactly K Steps

首先把树的直径找出来，对于树的直径上的点，可以很容易的知道答案。然后对于每个直径上的点做 DFS，遍历不在直径上的点，建立倍增数组，类似 LCA 的求解方式。可以很容易对不在直径上的任意点求解 \(k\) 级祖先。

因此，对于所有点都可以求出 \(k\) 步之外的点。

时间复杂度为 \(O(n\log n)\)。

Note

但是注意到，找到直径两端点 \(s,t\) 后，可以直接从 \(s\) 和 \(t\) 分别做 DFS 建立倍增数组。就不需要再区分是否是直径上的点了。

代码采用了较为复杂的方法，封装了一个求解直径的函数。可以返回直径上的所有点，传入的实参中记录着距离。

struct Edge {
  int src, to;
  long long w;
  Edge(int src_, int to_, long long w_) : src(src_), to(to_), w(w_) { }
  Edge(int to_, long long w_) : src(-1), to(to_), w(w_) { }
  Edge(int to_) : src(-1), to(to_), w(1) { }
  bool operator<(const Edge other) const { return w < other.w; }
};

vector<int> get_diameter(const vector<vector<Edge>> &tree, vector<ll>& dist) {
  int n = tree.size();
  vector<int> pre(n), vis(n);
  auto bfs = [&](int s) {
    fill(dist.begin(), dist.end(), 0);
    fill(vis.begin(), vis.end(), 0);
    fill(pre.begin(), pre.end(), 0);
    queue<int> que;
    int res = s;

    que.push(s); vis[s] = 1;
    while(que.size()) {
      int x = que.front(); que.pop();
      res = x;

      for(auto &edge : tree[x]) {
        if(vis[edge.to]) continue;
        dist[edge.to] = dist[x] + edge.w;
        que.push(edge.to);
        vis[edge.to] = 1;
        pre[edge.to] = x;
      }
    }
    return res;
  };

  int s = bfs(0);
  int t = bfs(s);
  vector<int> diameter = {t};
  while(t != s) {
    t = pre[t];
    diameter.push_back(t);
  }
  reverse(diameter.begin(), diameter.end());
  return diameter;
}

void solve() {
  int n;
  cin >> n;
  vector<vector<Edge>> g(n);
  for(int i = 0; i < n - 1; i ++) {
    int u, v; cin >> u >> v; u --; v --;
    g[u].push_back(Edge(v, 1));
    g[v].push_back(Edge(u, 1));
  }
  vector<ll> d(n);

  auto dia = get_diameter(g, d);
  int lg = log2(n);
  vector<vector<int>> f(n, vector<int>(lg + 1));
  vector<int> anc(n), dep(n), idx(n, -1);

  function<void(int, int)> dfs = [&](int x, int fa) {
    for(auto &e : g[x]) {
      int y = e.to;
      if(y == fa || idx[y] != -1) continue;
      dep[y] = dep[x] + 1;
      anc[y] = anc[x];
      f[y][0] = x;
      dfs(y, x);
    }
  };
  for(int i = 0; i < dia.size(); i++) idx[dia[i]] = i;
  for(int i = 0; i < dia.size(); i++) {
    int x = dia[i];

    anc[x] = x;
    dfs(x, -1);
  }

  for(int j = 1; j <= lg; j++) {
    for(int i = 0; i < n; i++) {
      f[i][j] = f[f[i][j - 1]][j - 1];
    }
  }

  int q; cin >> q;
  while(q --) {
    int u, k;
    cin >> u >> k; u --;
    if(idx[u] == -1) {
      if(dep[u] >= k) {
        for(int i = lg; i >= 0; i--) {
          if(k >> i & 1) u = f[u][i];
        }
        cout << u + 1 << "\n";
        continue;
      } else {
        k -= dep[u];
        u = anc[u];
      }
    }

    if(idx[u] >= k) cout << dia[idx[u] - k] + 1 << "\n";
    else if(idx[u] + k < dia.size()) cout << dia[idx[u] + k] + 1 << "\n";
    else cout << "-1\n";
  }
}

本文访问 次