跳转至

Codeforces Round #824 (Div. 2)

1735C - Phase Shift

Solution

构造一组合法映射使得满足解即可。

  • 若当前字母 \(c_1\) 未映射
    • 题目要求字典序最小
      • 则按字典序找一个最小的未被使用的字母 \(c_2\)
    • 判断合法性
      • 非法的充要条件:
        • \(c_1\) 和 \(c_2\) 在相同的集合
        • 该集合的大小 \(< 26\)
    • 合法的条件:
      • \(c_1\) 和 \(c_2\) 不同的集合
        • 自然想到并查集来判断
    • \(c_1\) 和 \(c_2\) 相同的集合
      • 此时该集合的大小 \(== 26\)
  • 使用已有映射

时间复杂度: \(O(t * 26^2)\)

Code

#include <bits/stdc++.h>

using namespace std;
using i64 = long long;

template <typename T = int>
struct DSU {
  int n;
  vector<T> f, sz;
  DSU(int n) : n(n), f(n), sz(n, 1) { iota(f.begin(), f.end(), 0); }

  int find(int x) { return f[x] == x ? x : f[x] = find(f[x]); }

  int leader(int x) {
    while (x != f[x]) x = f[x] = f[f[x]];
    return x;
  }

  bool same(int x, int y) { return find(x) == find(y); }

  bool merge(int x, int y) {
    x = find(x), y = find(y);
    if (x == y) return false;
    if (sz[x] > sz[y]) swap(x, y);
    sz[y] += sz[x];
    f[x] = y;
    return true;
  }

  int size(int x) { return sz[find(x)]; }
};

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

  DSU dsu(26);
  vector<int> used(26), f(26, -1);
  string s;

  for (auto& c : t) {
    int x = c - 'a';
    if (f[x] == -1) {
      for (int i = 0; i < 26; i++) {
        if (!used[i] && dsu.merge(x, i)) {
          used[i] = true;
          f[x] = i;
          break;
        }
      }
      if (f[x] == -1) {
        for (int i = 0; i < 26; i++) {
          if (!used[i]) {
            used[i] = true;
            f[x] = i;
            break;
          }
        }
      }
    }
    s += char('a' + f[x]);
  }

  cout << s << '\n';
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cout << fixed << setprecision(20);

  int t;
  cin >> t;

  while (t--) {
    solve();
  }

  return 0;
}

1735D - Meta-set

Solution

重要性质：

5张不同的牌最多只能有2种 meta-set，其中有一张牌为共享卡。

证明:

  • 假设
    • 共享卡为\(A\),
    • \(S_1\{B_1, B_2\}, S_2\{C_1, C_2\}\) 和 \(A\) 匹配。
  • \(k = 1\) 的情况：
    • \(F_A = x, x\in\{0, 1, 2\}\)
    • 若 \(S_1\) 与\(F_A\) 相同，则 \(S_2\) 必然与 \(F_A\) 互补
    • \(\therefore S_1,S_2\) 不可能构成 meta-set
  • \(k > 1\)，至少存在某一维和上述一样，在那个维度下满足上述证明

对于两张固定的卡而言，他只有一种配对的卡。 - 暴力枚举两张卡，将和其配对的卡的贡献\(+1\)。

每张卡的贡献为 \(\tbinom{cnt}{2}\)

时间复杂度: \(O(n^2 * k)\)

Code

#include <bits/stdc++.h>

using namespace std;
using i64 = long long;

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cout << fixed << setprecision(20);

  int n, m;
  cin >> n >> m;

  vector<vector<int>> c(n, vector<int>(m));
  map<int, int> pos;

  for (int i = 0; i < n; i++) {
    int x = 0;
    for (int j = 0; j < m; j++) {
      cin >> c[i][j];
      x = x * 3 + c[i][j];
    }
    pos[x] = i;
  }

  vector<int> cnt(n);
  for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
      int x = 0;
      for (int k = 0; k < m; k++) {
        x = x * 3 + (c[i][k] == c[j][k] ? c[i][k] : (0 ^ 1 ^ 2 ^ c[i][k] ^ c[j][k]));
      }
      if (pos.count(x)) {
        cnt[pos[x]]++;
      }
    }
  }

  i64 ans = 0;
  for (int i = 0; i < n; i++) {
    ans += cnt[i] * (cnt[i] - 1) / 2;
  }

  cout << ans << '\n';

  return 0;
}

1735E - House Planning

Soltuion

给定的数组是无序的

  • \(distance(p1, p2)\) 可能的个数最大有 \(2n\) 种，无非是 \(d_1[0] + d_2[i]\) 或 \(abs(d_1[0] - d_2[i])\)。

对于固定的 \(distance(p1, p2) = w\)

  1. \(max(d_1, d_2) = x > w\) 即房间在 \(line_{p_1, p_2}\) 外
    • 我们找到\(max(d_1, d_2) = x\)，如果这个数在 \(d_1\) 中，那么 \(d_2\) 中必然有一个 \(x - w\)
  2. \(max(d_1, d_2) = x \le w\) 即房间在 \(line_{p_1, p_2}\) 上
    • 充要条件：
      • \(d_1\) 中第 \(k\) 小的数 + \(d_2\) 中第 \(k\) 大的数 \(== w\)

为什么 \(1\) 中要从最大的数开始枚举?

  • 保证删另外一个集合的数的顺序是正确的

时间复杂度: \(O(n^2 * logn)\)

Code

#include <bits/stdc++.h>

using namespace std;
using i64 = long long;

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

  vector<vector<int>> d(2, vector<int>(n));
  for (int i = 0; i < 2; i++) {
    for (auto& x : d[i]) {
      cin >> x;
    }
    ranges::sort(d[i]);
  }

  auto check = [&](vector<int>& p) {
    int w = abs(p[0] - p[1]);

    vector<multiset<int>> s(2);
    for (int i = 0; i < 2; i++) {
      s[i] = multiset<int>(d[i].begin(), d[i].end());
    }

    vector<int> ans;

    while (!s[0].empty() && !s[1].empty() &&
           max(*s[0].rbegin(), *s[1].rbegin()) > w) {
      int u = 0, v = 1;
      if (*s[0].rbegin() < *s[1].rbegin()) {
        swap(u, v);
      }
      int x = *s[u].rbegin();
      if (!s[v].count(x - w)) {
        return false;
      }
      s[u].erase(s[u].find(x));
      s[v].erase(s[v].find(x - w));
      ans.emplace_back(u == 0 ? p[0] + x : p[1] - x);
    }

    while (!s[0].empty()) {
      int x = *s[0].begin();
      int y = *s[1].rbegin();
      if (x + y != w) {
        return false;
      }
      ans.emplace_back(p[0] + x);
      s[0].erase(s[0].begin());
      s[1].erase(prev(s[1].end()));
    }

    int mi = ranges::min(ans);
    int offset = mi < 0 ? -mi : 0;

    cout << "YES\n";
    for (int i = 0; i < n; i++) {
      cout << ans[i] + offset << " \n"[i == n - 1];
    }
    cout << p[0] + offset << ' ' << p[1] + offset << '\n';

    return true;
  };

  for (int i = 0; i < n; i++) {
    for (int j = 0; j < 2; j++) {
      vector<int> p{0, abs(d[0][0] + (j == 0 ? d[1][i] : -d[1][i]))};
      if (check(p)) {
        return;
      }
    }
  }

  cout << "NO\n";
}

int main() {
  cin.tie(nullptr)->sync_with_stdio(false);
  cout << fixed << setprecision(20);

  int t;
  cin >> t;

  while (t--) {
    solve();
  }

  return 0;
}