「题解」Codeforces Round 979 (Div. 2)

before

\(A \sim D\) 的题解

A. A Gift From Orangutan

Problem

A. A Gift From Orangutan

Sol&Code

\(c_i - b_i\) 最大就是 \(a\) 的最大值减最小值。将 \(a\) 的最大值 \(x\) 和最小值 \(y\) 放到头两位即可得到答案 \((x - y)(n - 1)\)。

#include <bits/stdc++.h>

#define M 10001
#define N 100001

typedef long long ll;
typedef std::pair<int, int> pii;

int T, n, a[N];

int main() {
  scanf("%d", &T);
  while (T--) {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    std::sort(a + 1, a + n + 1);
    printf("%lld\n", 1ll * (a[n] - a[1]) * (n - 1));
  }
  return 0;
}

B. Minimise Oneness

Problem

B. Minimise Oneness

Sol&Code

\(f(t)\) 的值等于 \(t\) 中零的个数。可以构造 \(t\) 开头仅一位 \(1\) 其余位都为 \(0\)，\(1\) 增多或者 \(0\) 在 \(1\) 两侧的话 \(g(t)\) 增长比较快。

#include <bits/stdc++.h>

#define M 10001
#define N 100001

typedef long long ll;
typedef std::pair<int, int> pii;

int T, n;

int main() {
  scanf("%d", &T);
  while (T--) {
    scanf("%d", &n);
    if (n == 1) puts("0");
    else {
      putchar('1');
      for (int i = 1; i < n; ++i) putchar('0');
      puts("");
    }
  }
  return 0;
}

C. A TRUE Battle

Problem

C. A TRUE Battle

Sol&Code

手玩几组数据发现当且仅当两头至少有一个 \(1\) 或者有两个 \(1\) 相邻会得到 True。

#include <bits/stdc++.h>

int T, n;
std::string s;

int main() {
  scanf("%d", &T);
  while (T--) {
    scanf("%d", &n);
    std::cin >> s;
    bool okay = false;
    if (s[0] == '1' || s[n - 1] == '1') { puts("YES"); continue; }
    for (int i = 0; i < n - 1; ++i) {
      if (s[i] == '1' && s[i + 1] == s[i]) { okay = true; break; }
    }
    puts(okay ? "YES" : "NO");
  }
  return 0;
}

D. QED's Favorite Permutation

Problem

D. QED's Favorite Permutation

Sol&Code

考虑题目限制发现，LR 这样的段使得 L 以左的数不能到达 R 以右，R 以右的数不能到达 L 以左。

考虑到是 L 还是 R 是在变化的，则考虑不变的数字。

对于不在正确位置的数字，将其交换过程中需要经过的区间做一下标记。全部标记完后查看被标记的隔断 LR 的数量有多少。在后续的变化中维护这个数量。标记可以使用差分。注意变化中维护的细节。

#include <bits/stdc++.h>

#define M 10001
#define N 200002

typedef long long ll;
typedef std::pair<int, int> pii;

std::string s;
int T, n, q, a[N], b[N];

int main() {
  scanf("%d", &T);
  while (T--) {
    scanf("%d %d", &n, &q);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    std::cin >> s;
    for (int i = 1; i <= n; ++i) b[i] = 0;
    for (int i = 1; i <= n; ++i) {
      if (a[i] != i) {
        if (i < a[i]) ++b[i], --b[a[i]];
        else ++b[a[i]], --b[i];
      }
    }
    for (int i = 1; i <= n; ++i) b[i] = b[i - 1] + b[i];
    int cnt = 0;
    for (int i = 0; i < n - 1; ++i) {
      if (s[i] == 'L' && s[i + 1] == 'R' && b[i + 1] > 0) ++cnt;
    }
    for (int i = 1, x; i <= q; ++i) {
      scanf("%d", &x);
      if (x == n) continue;
      if (s[x - 1] == 'L') {
        if (s[x] == 'R' && b[x] > 0) --cnt;
        s[x - 1] = 'R';
        if (x - 2 >= 0 && s[x - 2] == 'L' && b[x - 1] > 0) ++cnt;
      } else if (s[x - 1] == 'R') {
        if (s[x] == 'R' && b[x] > 0) ++cnt;
        s[x - 1] = 'L';
        if (x - 2 >= 0 && s[x - 2] == 'L' && b[x - 1] > 0) --cnt;
      }
      if (cnt == 0) puts("YES");
      else puts("NO");
    }
  }
  return 0;
}

After

• D 从不变的方向思考可能比较简单。

D 写的太着急了，虽然方法大体正确但是细节上出了好多错 XD。