Codeforces Round 1046 (Div. 2) ABCD

Tags:

Codeforces

A. In the Dream

在一个半场中，最坏情况下胜负情况是 $AABAABAA$ 这种形式。设分数较小的是 $x$ ，那么另外一个人的得分满足 $y \le 2x + 2$

void solve() {
  int a, b, c, d;

  cin >> a >> b >> c >> d;

  auto check = [&](int a, int b) -> bool {
    if (a > b)
      swap(a, b);
    return 2 * a + 2 >= b;
  };

  if (check(a, b) && check(c - a, d - b))
    YES();
  else
    NO();
}

B. Like the Bitset

要求不能有连续的 $k$ 个 1. 构造的时候，先填 0 的位置，尽可能填比较大的数字，剩下的数字填在 1 的位置。

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

  string s;
  cin >> s;
  s = " " + s;

  int cur = 0, cnt = 0;
  bool ok = true;
  VI zeros, ones;

  For1(i, 1, n) {
    if (s[i] == '1') {
      cur++;
      ones.pb(i);
    } else {
      cur = 0;
      zeros.pb(i);
    }

    ckmax(cnt, cur);
    if (cnt >= k) {
      ok = false;
      break;
    }
  }

  if (!ok) {
    NO();
    return;
  }

  int idx = n;
  VI ans(n + 1);
  for (auto x : zeros) {
    ans[x] = idx--;
  }
  for (auto x : ones) {
    ans[x] = idx--;
  }
  YES();
  For1(i, 1, n) { cout << ans[i] << ' '; }
  cout << '\n';
}

C. Against the Difference

设状态 $d_i$ 表示前 $i$ 个位置，最长合法子序列的长度。我们记录每个数字的位置到数组 $b$ 中， $b[x]$ 是 $x$ 出现过的位置的数组。对于位置 $i$ ，如果 $b_{a_i}$ 的长度不小于 $a_i$ ，那么状态转移到 $d_{pre - 1}$ 其中 $pre = b[x][len - a_i]$

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

  VI a(n + 1);
  For1(i, 1, n) cin >> a[i];

  VI d(n + 1);
  VVI b(n + 1);
  int ans = 0;

  For1(i, 1, n) {
    int x = a[i];
    b[x].pb(i);

    int len = SZ(b[x]);
    if (len >= x) {
      int pre = b[x][len - x];
      ckmax(d[i], d[pre - 1] + x);
    }

    ckmax(d[i], d[i - 1]);
    ckmax(ans, d[i]);
  }

  cout << ans << '\n';
}

D. For the Champion

给定的式子 $min(|x_i - c| + |y_i - d|)$ 中的绝对值不好处理。考虑如何去掉绝对值。

从起始位置移动到右下角到 $c_1 = c + 2U, d_1 = d - 2U$ , 其中 $U = 10^9$ . 这样可以保证 $(c_1, d_1)$ 一定在所有点的右下方。

同理，从起始位置移动到右上角 $c_2 = c + 2U, d_2 = d + 2U$ , 其中 $U = 10^9$ . 这样可以保证 $(c_2, d_2)$ 一定在所有点的右上方。

然后可以根据对 $(c_1, d_1)$ 和 $(c_2, d_2)$ 的询问，得到不带绝对值的式子对应的答案。得到二元一次方程组。

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

  vector<PII> a(n + 1);
  int sub = 2e9 + 10, add = -2e9 - 10;

  For1(i, 1, n) {
    cin >> a[i].first >> a[i].second;
    ckmin(sub, a[i].second - a[i].first);
    ckmax(add, a[i].first + a[i].second);
  }

  auto query = [&](char ch, int k) -> ll {
    cout << "? " << ch << ' ' << k << endl;
    ll dis;
    cin >> dis;
    return dis;
  };

  int U = 1e9;
  query('R', U);
  query('R', U);
  query('D', U);
  ll val1 = query('D', U);

  query('U', U);
  query('U', U);
  query('U', U);
  ll val2 = query('U', U);

  ll t = 1LL * val2 + add - 4LL * U, s = 1LL * val1 - sub - 4LL * U;
  ll x = (t + s) / 2, y = t - x;
  cout << "! " << x << ' ' << y << endl;
}