Codeforces Round 1045 (Div. 2) ABC

Tags:

Codeforces

A. Painting With Two Colors

容易想到根据奇偶性进行讨论。特殊情况是，如果 $b > a$ ，那么 $a$ 的奇偶性不需要考虑，因为它会被 $b$ 覆盖。

void solve() {
  int n, a, b;
  cin >> n >> a >> b;

  if (n & 1) {
    if ((b & 1) && ((a & 1) || (a < b)))
      YES();
    else
      NO();
  } else {
    if ((b % 2 == 0) && (a % 2 == 0 || (a < b)))
      YES();
    else
      NO();
  }
}

B. Add 0 or K

神奇的构造题。

我们要让 $a_i + kc_i \equiv 0 \pmod {g}$ ，也就是 $k c_i \equiv -a_i \pmod g$

要让这个方程比较好处理，我们可以让 $k \equiv -1 \pmod {g}$ ，带入上式得到 $c_i \equiv a_i \pmod {g}$ 。此时有 $k + 1 \equiv 0 \pmod {g}$ ，我们可以直接取 $g = k + 1$

因此可以这么构造，取 $g = k + 1$ , $c_i = a_i \bmod g$ ， $b_i = a_i + k c_i$ 。数组 $b$ 就是答案。

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

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

  int g = k + 1;
  VL c(n + 1);
  For1(i, 1, n) {
    c[i] = a[i] % g;
    a[i] += k * c[i];
    cout << a[i] << ' ';
  }
  cout << '\n';
}

C. Even Larger

这道题目比 B 题简单多了。

容易想到我们需要让所有的偶数位置大于等于左右位置的奇数位置的和。

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

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

  ll ans{};
  for (int i = 2; i <= n; i += 2) {
    int sum = a[i - 1] + a[i + 1];
    if (a[i] >= sum)
      continue;
    int g = sum - a[i];
    ans += g;
    a[i + 1] -= min(g, a[i + 1]);
  }
  cout << ans << '\n';
}