Codeforces Round 956 Div 2 and ByteRace 2024 个人题解

A. Array Divisibility

题目大意

构造一个长为 $n$ 的序列，使得对于所有 $k$ $(1\le k \le n)$ ，序列中所有位置为 $k$ 的倍数的数的和也是 $k$ 的倍数.

解题思路

显然，构造序列 $1,2,...,n$ 即可.

代码

#include <bits/stdc++.h>

using namespace std;

void solve() {
  int n;
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cout << i << " \n"[i == n];
  }
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);

  int tc = 1;
  cin >> tc;
  while (tc--) {
    solve();
  }

  return 0;
}

B. Corner Twist

题目大意

给定两个 $n$ 行 $m$ 列的矩阵 $a,b$，矩阵内的数仅可能为 $0,1,2$ ，问是否能通过若干次操作，使得 $a$ 变成 $b$.

操作如下：在 $a$ 中选定一个子矩阵，该子矩阵的某一对对角上的数加 $1$ 并对 $3$ 取模，另一对对角上的数加 $2$ 并对 $3$ 取模，其他数保持不变.

解题思路

我们考虑该操作本质上是什么. 对于一次操作，该操作对同一行的某两个数在模 $3$ 意义下分别 $+1$ 和 $-1$ ，同一列同理. 也就是说，该操作不会改变某一行或某一列的数在模 $3$ 意义下的和，因此我们只需要分别 check 矩阵 $a$ 和 $b$ 对应的每一行和每一列所有数在模 $3$ 意义下的和是否相同即可.

代码

#include <bits/stdc++.h>

using namespace std;

void solve() {
  int n, m;
  cin >> n >> m;
  vector<string> a(n), b(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }
  for (int i = 0; i < n; i++) {
    cin >> b[i];
  }

  bool ok = true;
  for (int i = 0; i < n; i++) {
    int cnt = 0;
    for (int j = 0; j < m; j++) {
      cnt += (a[i][j] - b[i][j]);
    }
    if ((cnt % 3 + 3) % 3) {
      ok = false;
    }
  }
  for (int j = 0; j < m; j++) {
    int cnt = 0;
    for (int i = 0; i < n; i++) {
      cnt += (a[i][j] - b[i][j]);
    }
    if ((cnt % 3 + 3) % 3) {
      ok = false;
    }
  }
  cout << (ok ? "YES\n" : "NO\n");
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);

  int tc = 1;
  cin >> tc;
  while (tc--) {
    solve();
  }

  return 0;
}

C. Have Your Cake and Eat It Too

题目大意

给 $3$ 个长度为 $n$ 的序列且 $3$ 个序列的所有元素之和都相等，记为 $tot$，以相同的分割方式将 $3$ 个序列分别分割成 $3$ 段，分别编号为 $1,2,3$ ，每个序列分别选出一段出来，不能选择编号相同的段，要求每一段的和都要大于等于 $\lceil \frac{tot}{3} \rceil$ .

解题思路

对于选择段的先后顺序，一共只有 $3!$ 种选择方法，暴力 check 每一种选择方法是否能保证选出的每一段的元素之和能够大于等于 $\lceil \frac{tot}{3} \rceil$ 即可.

代码

#include <bits/stdc++.h>

using namespace std;
using i64 = long long;

vector<vector<int>> order{{1, 2, 3}, {1, 3, 2}, {2, 1, 3},
                          {2, 3, 1}, {3, 1, 2}, {3, 2, 1}};

void solve() {
  int n;
  cin >> n;
  vector a(4, vector<int>(n + 1));
  i64 tot = 0;
  for (int i = 1; i <= 3; i++) {
    for (int j = 1; j <= n; j++) {
      cin >> a[i][j];
      tot += a[i][j];
    }
  }
  tot /= 3;

  bool ok = false;
  vector<pair<int, int>> ans(4);
  for (auto &vec : order) {
    int pos = 1;
    vector<int> res;
    for (auto &o : vec) {
      i64 now = 0;
      for (; pos <= n;) {
        now += a[o][pos];
        pos++;
        if (now >= (tot + 2) / 3) {
          res.push_back(pos);
          break;
        }
      }
    }
    if (res.size() == 3) {
      ok = true;
      for (int cnt = 0; auto &o : vec) {
        if (cnt == 0) {
          ans[o] = {1, res[0] - 1};
        } else if (cnt == 1) {
          ans[o] = {res[0], res[1] - 1};
        } else {
          ans[o] = {res[1], n};
        }
        cnt++;
      }
      break;
    }
  }

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

  for (int i = 1; i <= 3; i++) {
    cout << ans[i].first << " " << ans[i].second << " ";
  }
  cout << "\n";
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);

  int tc = 1;
  cin >> tc;
  while (tc--) {
    solve();
  }

  return 0;
}

D. Swap Dilemma

题目大意

给定两个序列 $a,b$ ，每个序列中的元素各不相同，问是否可能通过若干次操作后使得两序列相同.

操作如下：选择序列 $a$ 中位置为 $l,r$ 的两个数进行交换，并在序列 $b$ 中选择位置为 $p,q$ 的两个数进行交换，要求 $r-l=q-p$ .

解题思路

显然若一个序列包含另一个序列没有的数则一定不能得到相同的序列. 注意到，任意交换操作都可以被替换为若干次对相邻元素的交换操作，因此我们可以仅交换位置连续的数（即 $r-l=1$），然后，我们考虑能否将两个序列都转化成有序的序列，而每个序列所需的操作次数即为该序列中的逆序对数，若两个序列中的逆序对数之差为偶数，那么我们一定可以把两个序列都变成有序序列.

代码

#include <bits/stdc++.h>

using namespace std;
using i64 = long long;

struct Fenwick {
  int n_;
  vector<i64> c;
  Fenwick(int n) : n_(n) { c.resize(n_ + 1); }

  i64 query(int x) {
    i64 res = 0;
    for (; x; x -= (x & -x)) {
      res += c[x];
    }
    return res;
  }

  void modify(int x, int d) {
    for (; x <= n_; x += (x & -x)) {
      c[x] += d;
    }
  }
};

void solve() {
  int n;
  cin >> n;
  map<int, int> cnta, cntb;
  vector<int> a(n + 1), b(n + 1);
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    cnta[a[i]]++;
  }
  for (int i = 1; i <= n; i++) {
    cin >> b[i];
    cntb[b[i]]++;
  }

  if (cnta != cntb) {
    cout << "NO\n";
    return;
  }

  auto va = a, vb = b;
  sort(va.begin() + 1, va.end());
  sort(vb.begin() + 1, vb.end());
  for (int i = 1; i <= n; i++) {
    a[i] = lower_bound(va.begin(), va.end(), a[i]) - va.begin();
    b[i] = lower_bound(vb.begin(), vb.end(), b[i]) - vb.begin();
  }

  Fenwick ca(n), cb(n);
  i64 resa = 0, resb = 0;
  for (int i = n; i >= 1; i--) {
    resa += ca.query(a[i]);
    ca.modify(a[i], 1);
  }
  for (int i = n; i >= 1; i--) {
    resb += cb.query(b[i]);
    cb.modify(b[i], 1);
  }

  cout << (abs(resa - resb) % 2 == 0 ? "YES\n" : "NO\n");
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);

  int tc = 1;
  cin >> tc;
  while (tc--) {
    solve();
  }

  return 0;
}

E. I Love Balls

题目大意

给定 $n$ 个球，其中前 $k$ 个为特殊球，每个球都有权值，Alice 和 Bob 随机轮流取球，如果取到特殊球则可以继续取，如果取到普通球则进入对方回合. 最终每人的得分为各自取到的所有球的权值和. 问两人最终得分的期望分别是多少.

解题思路

首先一个关键的观察是，每个人的回合一定仅取得至多一个普通球，且以该普通球结尾（除非把球取完了），也就是说，每个人取得的普通球个数是确定的，设 $m=n-k$ 为普通球个数，则 Alice 一定取得 $p=\lceil \frac{m}{2} \rceil$ 个普通球，Bob 一定取得 $q=m-p$ 个普通球.

我们先单独考虑每个普通球的贡献，每个普通球被取得的概率分别为 $\frac{p}{m}$ 和 $\frac{q}{m}$ ，因此所有普通球对 Alice 得分的贡献之和为 $\sum_{i=k+1}^{n} \frac{p}{m} \cdot a_i = \frac{p}{m} \cdot \sum_{i=k+1}^{n} a_i$ , 同理可得所有普通球对 Bob 得分的贡献为 $\frac{q}{m}\cdot \sum_{i=k+1}^{n}a_i$ .

之后我们考虑特殊球的贡献，我们依然考虑每个球的贡献，我们已经考虑完了所有普通球的贡献，由于从一个序列中随机取球等价于从一个随机的该序列的排列中按顺序取球，问题可以转化成，有 $m$ 个普通球作为 “隔板” ，要将一个特殊球放在 $m+1$ 个空位中的某个空位，在奇数空位表示在 Alice 回合被拿走，在偶数空位表示在 Bob 回合被拿走，因此该球 $i$ 对 Alice 的贡献为 $\frac{\lceil \frac{m+1}{2} \rceil }{m+1} \cdot a_i$，对 Bob 的贡献为 $\frac{m+1-\lceil \frac{m+1}{2} \rceil }{m+1} \cdot a_i$ . 因此所有特殊球对 Alice 得分的贡献之和为 $\sum_{i=1}^{k} \frac{\lceil \frac{m+1}{2} \rceil}{m+1} \cdot a_i = \frac{\lceil \frac{m+1}{2} \rceil}{m+1} \cdot \sum_{i=1}^{k} a_i$ , 同理可得所有普通球对 Bob 得分的贡献为 $\frac{m+1-\lceil \frac{m+1}{2} \rceil }{m+1}\cdot \sum_{i=1}^{k}a_i$ .

代码

#include <bits/stdc++.h>

using namespace std;
using i64 = long long;
const int mod = 1e9 + 7;

i64 binpow(i64 a, i64 b) {
  i64 res = 1;
  while (b) {
    if (b & 1) {
      res = res * a % mod;
    }
    a = a * a % mod;
    b >>= 1;
  }
  return res;
}

void solve() {
  int n, k;
  cin >> n >> k;
  vector<int> a(n + 1);
  i64 sum1 = 0, sum2 = 0;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    if (i <= k) {
      sum1 += a[i];
    } else {
      sum2 += a[i];
    }
  }
  sum1 %= mod, sum2 %= mod;

  i64 ans1 = 0, ans2 = 0;
  int m = n - k;
  ans1 += (m + 1) / 2 * binpow(m, mod - 2) % mod * sum2 % mod;
  ans2 += m / 2 * binpow(m, mod - 2) % mod * sum2 % mod;

  ans1 += (m + 1 + 1) / 2 * binpow(m + 1, mod - 2) % mod * sum1 % mod;
  ans2 += (m + 1 - (m + 1 + 1) / 2) * binpow(m + 1, mod - 2) % mod * sum1 % mod;
  ans1 %= mod, ans2 %= mod;

  cout << ans1 << " " << ans2 << "\n";
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);

  int tc = 1;
  cin >> tc;
  while (tc--) {
    solve();
  }

  return 0;
}