Codeforces Global Round 19 (cf 1637) A ~ E 题解

A - Sorting Parts

通过这个操作我们可以发现本分割的两部分一定可以sorted, 所以只需要判断连接处是否是sorted, 这个可以通过维护一个前缀最大值和后缀最小值实现, 这样我们枚举一下操作的点, 然后每次 O(1) 判断一下就行

int a[N], mn[N], ma[N];
 
void solve() {
  int n;
  cin >> n;
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
  }
  ma[0] = a[0];
  mn[n - 1] = a[n - 1];
  for (int i = 1, j = n - 2; i < n; ++i, --j) {
    ma[i] = max(a[i], ma[i - 1]);
    mn[j] = min(a[j], mn[j + 1]);
  }
  for (int i = 0; i < n - 1; ++i) {
    if (ma[i] > mn[i + 1]) {
      cout << "YES\n";
      return;
    }
  }
  cout << "NO\n";
}

B - MEX and Array

不难发现, 因为这个公式有c的存在所以即使你能得到一个很大的mex其价值也等同于将这个区间分割成一小块一小块, 有0则有额外的贡献

int a[N];
 
void solve() {
  int n;
  cin >> n;
  for (int i = 0; i < n; ++i) {
    cin >> a[i];
  }
  int ans = 0;
  for (int len = 1; len <= n; ++len) {
    for (int i = 0; i <= n - len; ++i) {
      ans += len;
      for (int j = i; j < i + len; ++j) {
        if (!a[j]) ans++;
      }
    }
  }
  cout << ans << '\n';
}

C - Andrew and Stones

先考虑-1的情况

如果除了第一个和最后一个全为1显然就不能, 无法进行任何操作

其次如果只有三个数且第二个是奇数, 那么此时也无法进行任何操作

其他时候

例如 1 3 1 1

就可以变成 2 1 2 1

再变成 3 2 0 1

因为只要有一个能进行操作就能将另一个不能进行操作的, 就可以传递给另一个不能操作的使其能操作, 具有传递性

那么每个数的贡献其实都是固定的, 所以按顺序计算答案即可

int a[N];
 
void solve() {
  int n;
  cin >> n;
  int flg = 1;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    if (i != 1 && i != n) flg &= a[i] == 1;
  }
  if ((n == 3 && a[2] % 2 == 1) || flg) {
    cout << "-1\n";
    return;
  }
  ll res = 0;
  for (int i = 1; i <= n; ++i) {
    res += (a[i] + 1) / 2;
  }
  cout << res << '\n';
}

D - Yet Another Minimization Problem

先考虑优化合式, 判断其性质

\(\sum\limits_{i = 1}^{n}{\sum\limits_{j = i + 1}^{n}{(a_i + a_j)^2}}\)

将括号打开, 就可以简单观察并将其成两部分一部分是 \(\sum\limits_{i = 1}^{n}{(n - 1) \cdot a_i^2}\) $ 一部分是 $$\sum\limits_{i = 1}^{n}{\sum\limits_{j = i + 1}^{n}{2 \cdot a_ia_j}}$ , 两部分都有系数可以提出来

原题就变成了 \(\sum\limits_{i = 1}^{n}{\sum\limits_{j = i + 1}^{n}{(a_i + a_j)^2}} = (n - 1) \cdot \sum\limits_{i = 1}^{n}{a_i^2} + 2\cdot\sum\limits_{i = 1}^{n}{\sum\limits_{j = i + 1}^{n}{a_ia_j}}\)

第二部分还有待优化, 我们先考虑一个对称情况

\(\sum\limits_{i = 1}^{n}{\sum\limits_{j = 1}^{n}{a_ia_j}}\)

将其展开

\(a_1\cdot a_1 + a_2 \cdot a_1 + \cdots + a_n \cdot a_1\)

\(a_1 \cdot a_2 + a_2 \cdot a_2 + \cdots + a_n \cdot a_2\)

​ \(\vdots\) \(\vdots\) \(\ddots\) \(\vdots\)

\(a_1 \cdot a_n + a_2 \cdot a_n + \cdots + a_n \cdot a_n\)

我们要的是下三角区域或上三角区域, 显然是对称的

因为对称所以就等于整块区域减去对角线再除以 2

整块区域就是\((a_1 + a_2 + \cdots + a_n) \cdot (a_1 + a_2 + \cdots + a_n)\) 就等于 \((\sum\limits_{i = 1}^{n}{a_i})^2\)

而对角线就是\(\sum\limits_{i = 1}^{n}{a_i}^2\)

所以\(\sum\limits_{i = 1}^{n}{\sum\limits_{j = i + 1}^{n}{a_ia_j}} = \dfrac{(\sum\limits_{i = 1}^{n}{a_i})^2 - \sum\limits_{i = 1}^{n}{a_i}^2}{2}\)

带回原式乘上系数可以得到

\(\sum\limits_{i = 1}^{n}{\sum\limits_{j = i + 1}^{n}{(a_i + a_j)^2}} = (n - 1) \cdot \sum\limits_{i = 1}^{n}{a_i^2} + (\sum\limits_{i = 1}^{n}{a_i})^2 - \sum\limits_{i = 1}^{n}{a_i}^2\)

原式就变成

\(\sum\limits_{i = 1}^{n}{\sum\limits_{j = i + 1}^{n}{(a_i + a_j)^2}} = (n - 2) \cdot \sum\limits_{i = 1}^{n}{a_i^2} + (\sum\limits_{i = 1}^{n}{a_i})^2\)

在本题两个数组无论在怎么交换前一部分\((n - 2) \cdot \sum\limits_{i = 1}^{n}{a_i^2}\) 是固定的

我们需要让第二部分最小

可以先 dp 求出所有的可能

bitset<10036> f;
f[0] = 1;
for (int i = 1; i <= n; ++i) f = (f << a[i]) | (f << b[i]);

然后找出最小值即可

for (int i = 0; i <= sum; i++) {
  if (f[i]) {
    ans = min(ans, i * i + (sum - i) * (sum - i));
  }
}

不过也有个结论那就是让他们的和尽量靠近

这一点可以这么考虑\(sum = \sum\limits_{i = 1}^{n}{a_i} + \sum\limits_{i = 1}^{n}{b_i}\)

这个值也是不会随交换而改变的

我们设\(sa = \sum\limits_{i = 1}^{n}{a_i}, sb = \sum\limits_{i = 1}^{n}{b_i}\)

问题就变成了 \(sa + sb = sum\) 为一固定值, 求 \(sa^2 + sb^2\) 的最小值

\(sb = sum - sa\) 带入 \(sa^2 + sb^2\)

得到\(2\cdot sa^2 - 2\cdot sum \cdot sa + sum^2\)

这是一个开口向上对称轴为\(\dfrac{sum}{2}\)的二次函数

所以越是靠近\(\dfrac{sum}{2}\) 值越小, 越远距离越大

我们只需要从我们的所有方案中取最靠近 \(\dfrac{sum}{2}\) 的值

int a[N], b[N];
 
void solve() {
  int n;
  cin >> n;
  int sa = 0, sb = 0;
  int ans = 0;
  for (int i = 1; i <= n; ++i) {
    cin >> a[i];
    sa += a[i];
    ans += a[i] * a[i];
  }
  for (int i = 1; i <= n; ++i) {
    cin >> b[i];
    sb += b[i];
    ans += b[i] * b[i];
  }
  ans *= n - 2;
  int sum = sa + sb;
  bitset<10036> f;
  f[0] = 1;
  for (int i = 1; i <= n; ++i) f = (f << a[i]) | (f << b[i]);
  int to = sa;
  for (int i = 1; i < 10001; ++i) {
    if (f[i]) {
      if (abs(sum - 2 * i) < abs(sum - 2 * to)) to = i;
    }
  }
  ans += to * to + (sum - to) * (sum - to);
  cout << ans << '\n';
}

E - Best Pair

待写题解

F - Towers

待补