Educational Codeforces Round 184 ABCD1

Tags:

Codeforces

A. Alice and Bob

取每个点只得 1 分，也就是让 Bob 能够取得的值最多。
我们发现我们总是可以让 Bob 取 $a + 1$ 或者 $a - 1$ . 我们只需要求出在这两种情况下，Bob 能够取得的数量是多少。这可以使用二分。

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

  VI a(n);
  For(i, 0, n) cin >> a[i];

  int bscore = -1, ans = -1;
  int tmp = n - (upper_bound(a.begin(), a.end(), x) - a.begin());
  if (ckmax(bscore, tmp))
    ans = x + 1;

  tmp = n - (a.end() - lower_bound(a.begin(), a.end(), x));
  if (ckmax(bscore, tmp))
    ans = x - 1;
  cout << ans << '\n';
}

B. Drifting Away

如果出现了以下几种情况，那么可以无限循环：
- **, ><, >*, *<
通过观察和模拟，我们发现如果没有无限循环，那么字符串中最多只有一个 *。如果出现了一次 >，那么它的右侧只能出现 >，不能再出现其他字符。如果出现了一次 <，那么它的左侧只能出现 <，不能出现其他字符。
总结一下，其实就是求字符串中，最长连续相同的子字符串的长度。
特殊判断一下字符串中只含有一个 * 的情况，这种情况在样例中已经给出了。

void solve() {
  string s;
  cin >> s;

  int n = SZ(s);
  bool ok = false;

  For(i, 0, n - 1) {
    if ((s[i] == '>' && s[i + 1] == '<') || (s[i] == '>' && s[i + 1] == '*') ||
        (s[i] == '*' && s[i + 1] == '<') || (s[i] == '*' && s[i + 1] == '*')) {
      ok = true;
      break;
    }
  }

  if (ok) {
    cout << "-1\n";
    return;
  }

  int cnt = 0;
  For(i, 0, n) {
    if (s[i] == '*')
      cnt++;
  }

  int cur = 1, ans = 1;
  char ch = s[0];

  For(i, 1, n) {
    if (s[i] == s[i - 1]) {
      cur++;
    } else {
      if (ckmax(ans, cur)) {
        ch = s[i - 1];
      }
      cur = 1;
    }
  }
  ckmax(ans, cur);

  if (n > 1)
    ans += cnt;
  cout << ans << '\n';
}

C. Range Operation

很有意思的一道题目。
当区间 $[l, r]$ 变化的时候， $l + r$ 也会变化，很难找到单调性，也就是找不到贪心的性质。不妨从增量的角度考虑。
如果选择的区间是 $[l, r]$ ，数组和的增量是 $\Delta_{1} = (l + r) len - sum(l, r)$ ，其中 $len = r - l + 1$ .
如果把区间往右扩展一个位置变成 $[l, r + 1]$ , 数组和的增量是 $\Delta_2 = (l + r + 1)(len + 1) - sum(l, r + 1) = \Delta_1 + 2(r + 1) - a_{r + 1}$
我们发现一个很整齐的形式： $2(r + 1) - a_{r + 1}$
也就是说，把区间往右扩展一位，它的增量恰好就是 $2(r + 1) - a_{r + 1}$ 。也就是说每一个位置的贡献是 $2i - a_i$ 。
设数组 $b_i = 2i - a_i$ ，因为我们只能进行最多一次操作，也就是我们只需要取一段区间，使得这个区间的贡献最大，也就是取一段连续的 $b_i$ ，使得区间和最大。这是线性 DP 的例题：“求最大子数组和”。

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

  VL a(n + 1), b(n + 1);
  ll sum{};
  For1(i, 1, n) {
    cin >> a[i];
    sum += a[i];
    b[i] = 2 * i - a[i];
  }

  VL d(n + 1);
  ll ans = 0;
  For1(i, 1, n) {
    d[i] = max(b[i], d[i - 1] + b[i]);
    ckmax(ans, d[i]);
  }

  ans = ans + sum;
  cout << ans << '\n';
}

D1. Removal of a Sequence (Easy Version)

很有意思的一道题目。

如果要从删除掉了哪些数字的角度考虑，可能就有点复杂了。

这道题目的操作次数比较少，我们可以从全部操作完之后，剩下了多少个数字的角度考虑。对于给定的范围 $[1, n]$ ，操作完之后，剩下多少个数字是比较容易求出来的。

我们对 $n$ 进行二分，如果操作完之后，剩下的数字个数 $\ge k$ ，说明 $n$ 是合法的。我们找到最小的 $n$ ，此时 $n$ 就是答案。

void solve() {
  ll x, y, k;
  cin >> x >> y >> k;

  auto check = [&](ll p) -> bool {
    For(i, 0, x) { p -= p / y; }
    return p >= k;
  };

  ll l = 1, r = 1e12, mid;
  while (l < r) {
    mid = (l + r) / 2;
    if (check(mid))
      r = mid;
    else
      l = mid + 1;
  }
  if (check(r))
    cout << r << '\n';
  else
    cout << "-1\n";
}