Codeforces Round 1044 (Div. 2) ABCD

Tags:

Codeforces

A. Redstone?

列公式发现要求最后一个齿轮的大小要和第一个齿轮的大小一样。也就是要求数组中存在出现至少两次的数字。

void solve() {
  int n;
  cin >> n;

  vector<int> a(n + 1), vis(120);
  bool ok = false;
  For1(i, 1, n) {
    cin >> a[i];
    if (vis[a[i]]) {
      ok = true;
    }
    vis[a[i]] = true;
  }
  if (ok)
    YES();
  else
    NO();
}

B. Villagers

为了让总花费最小，把数组排序，选择最大的两个，让这两个元素和解。这样从大到小两两配对即可。

void solve() {
  int n;
  cin >> n;

  vector<int> a(n + 1);
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  sort(a.begin() + 1, a.begin() + 1 + n);
  ll ans{};
  for (int i = n; i >= 1; i -= 2) {
    ans += a[i];
  }
  cout << ans << '\n';
}

C. The Nether

以每个节点作为起点询问，容易找到最大路径的长度 $len$

考虑如何找到路径的第二个节点，设这个节点是 $p$ ，那么以 $p$ 开头的最长路径必然是 $len - 1$ , 并且以 $start$ 作为起点， $p$ 作为终点，路径长度需要恰好是 2.

在第一遍询问的过程中，我们可以记录每个长度对应的点的列表。我们就可以容易找到 $len - 1$ 对应的点，然后以 $start$ 为起点， $p$ 作为另外一个点询问，找答案恰好是 2 的元素。依此类推，可以找到所有的 $len$ 个点。

问题的关键：我们发现第二遍询问的过程中，每个点最多只会被询问一次。所以这个做法是正确的。

void solve() {
  int n;
  cin >> n;

  auto query = [&](int start) -> int {
    cout << "? " << start << " " << n;
    for (int i = 1; i <= n; i++) {
      cout << " " << i;
    }
    cout << endl;

    int len;
    cin >> len;
    return len;
  };
  auto query2 = [&](int p1, int p2) -> bool {
    cout << "? " << p1 << " 2 " << p1 << ' ' << p2 << endl;
    int len;
    cin >> len;
    return len == 2;
  };

  map<int, vector<int>> mp;
  int mx = 0;
  for (int i = 1; i <= n; i++) {
    int len = query(i);
    mp[len].push_back(i);
    ckmax(mx, len);
  }

  vector<int> ans;
  int p1 = mp[mx][0], len = mx;
  ans.push_back(p1);
  for (int i = len - 1; i >= 1; i--) {
    for (auto v : mp[i]) {
      if (query2(p1, v)) {
        ans.push_back(v);
        p1 = v;
        break;
      }
    }
  }

  cout << "! " << mx;
  for (auto i : ans) {
    cout << " " << i;
  }
  cout << endl;
}

D. Chicken Jockey

有趣的 DP 题

注意到我们需要造成的伤害总量是固定的，总伤害分为两个部分：坠落伤害和普攻伤害。我们需要最大化坠落伤害，最小化普攻伤害。

设 $d_i$ 代表，消灭前 $i$ 个元素，需要的普攻伤害的最小值。

对于位置 $i$ ，如果要对它造成坠落伤害，我们需要考虑前 $i - 1$ 个位置。直接对 $i$ 造成坠落伤害的时刻，一定是 $i - 1$ 消失的时刻。

最简单的情况是，直接杀掉 $i - 1$ ，此时状态转移是 $d_{i - 2} + a_{i - 1} + max(0, a_i - (i - 1))$

另外一种情况是，不直接杀掉 $i - 1$ , 总之我们需要让前 $i - 1$ 给被消灭，此时只剩下第 $i - 1$ 个元素，第 $i$ 个元素的坠落伤害只有 1. 而消灭前 $i - 1$ 个元素的最小代价，恰好是我们的状态定义，这是一个子问题，因此状态转移是 $d_i = d_{i - 1} + (a_i - 1)$

void solve() {
  int n;
  cin >> n;

  VI a(n + 1);
  for (int i = 1; i <= n; i++)
    cin >> a[i];

  VL d(n + 1, INFL);
  d[0] = 0;
  d[1] = a[1];

  For1(i, 2, n) {
    d[i] = d[i - 1] + a[i] - 1;
    ckmin(d[i], d[i - 2] + a[i - 1] + max(0, a[i] - (i - 1)));
  }

  cout << d[n] << '\n';
}