Codeforces Round 1002 (Div. 2)

A. Milya and Two Arrays

A. Milya and Two Arrays

题目描述

给你两个长度为n的数组a和b，a,b中的每个元素都至少出现两次。你可以重新排列a，最后要使得ai+bi的不同种类大于等于3。

解题思路

统计a和b的种类数cnt1,cnt2，因为长度为n且每个种类的数至少出现两次，所以a中每个数贡献的种类数就是出现次数，出现次数，min(
出现次数，cnt2)，只要cnt1∗cnt2>=3就行。赛时没想的很清楚写的cnt1+cnt2>=4，其实一样。

参考代码

void solve() {
  int n;
  std::cin >> n;
  std::set<int> a, b;
  for (int i = 0; i < n; ++ i) {
    int x;
    std::cin >> x;
    a.insert(x);
  }

  for (int i = 0; i < n; ++ i) {
    int x;
    std::cin >> x;
    b.insert(x);
  }

  if (a.size() + b.size() >= 4) {
    std::cout << "YES" << endl;
  } else {
    std::cout << "NO" << endl;
  }
}

---

B. Cost of the Array time limit per test1 second

B. Cost of the Array time limit per test1 second

题目描述

给你一个长度为n数组a和一个偶数k。你要把a分成k份。然后把所有偶数份按顺序拼到一起，得到b，求可以得到的bi!=i的最小的i。

解题思路

我们让所有的k−1份都只占一个位置，第二份占多个位置，看能不能不让1开头，如果有我们可以把前面的1都给第一份，那么答案就是1。否则就全部都是1，那么全部给第二个份，那么答案就是2。
注意要特判n==k的情况

参考代码

void solve() {
  int n, k;
  std::cin >> n >> k;
  std::vector<int> a(n);
  for (int i = 0; i < n; ++ i) {
    std::cin >> a[i];
  }

  if (n == k) {
    for (int i = 1, j = 1; i < n; i += 2, j ++ ) {
      if (a[i] != j) {
        std::cout << j << endl;
        return;
      }
    }

    std::cout << k / 2 + 1 << endl;
    return;
  } else {
    for (int i = 1; i < n - (k - 2); ++ i) {
      if (a[i] != 1) {
        std::cout << 1 << endl;
        return;
      }
    }

    std::cout << 2 << endl;
  }
}

---

C. Customer Service

C. Customer Service

题目描述

给你n个长度为n的数组，你要给每一个数组截断一次，且所有数组截断的位置凑起来正好是一个排列。然后每个数组的值就是截断的后一部分的和。你要让所有数组和的mex最大。

解题思路

记录每个数组的后缀和与后缀长度相等的位置，那么保留这一段位置可以得到一个数字。于是我们从小到大枚举mex只要有一个没有被操作过的数组可以贡献这个值，就可以继续操作，否则就是答案。然后考虑每个值由哪个数组贡献，应该让可以贡献的最大值最小的数组来贡献这个值。因为其他数组都可以贡献更大的值，应该留下来。

参考代码

void solve() {
  int n;
  std::cin >> n;
  std::vector a(n, std::vector<int>(n));
  for (int i = 0; i < n; ++ i) {
    for (int j = 0; j < n; ++ j) {
      std::cin >> a[i][j];
    }
    a[i].push_back(0);
    std::reverse(a[i].begin(), a[i].end());
  }

  std::vector<std::set<std::pair<int, int> > > s(n + 1);
  std::vector<int> b(n);
  for (int i = 0; i < n; ++ i) {
    i64 t = 0;
    for (int j = 0; j <= n; ++ j) {
      t += a[i][j];
      if (j == n || t != j) {
        b[i] = j;
        break;
      }
    }

    for (int j = 0; j < b[i]; ++ j) {
      s[j].insert({b[i], i});
    }
  }

  for (int i = 0; i <= n; ++ i) {
    if (s[i].empty()) {
      std::cout << i << endl;
      return;
    }

    auto [_, x] = *s[i].begin();
    s[i].erase(s[i].begin());
    for (int j = 0; j < b[x]; ++ j) {
      s[j].erase({b[x], x});
    }
  }
}

---

D. Graph and Graph

D. Graph and Graph

题目描述

给你两个由n个顶点的图，你在图一和图二各有一个起点，你每次要在这两个图上移动，假设从图一移动到了u,
图二移动到了v，移动代价是|u−v|。你要进行无限次操作，求操作的最小代价。

解题思路

显然我们让两个图都到一个相同的点u，使得有一个v在图一和图二上都和u有边。那么可以在这两个点上反复横跳，代价是0。否则代价是正无穷。
那么可以考虑最短路，dist[i][j]表示图一在i，图二在j时的最小代价。最后枚举每个i，看有没有一个j使得在两个图上都有边，然后取最小值即可。

参考代码

void solve() {
  int n, s1, s2;
  std::cin >> n >> s1 >> s2;
  -- s1, -- s2;
  std::vector g1(n, std::vector<int>(n));
  std::vector g2(n, std::vector<int>(n));
  std::vector<std::vector<int> > adj1(n);
  std::vector<std::vector<int> > adj2(n);
  int m1, m2;
  std::cin >> m1;
  for (int i = 0; i < m1; ++ i) {
    int u, v;
    std::cin >> u >> v;
    -- u, -- v;
    g1[u][v] = g1[v][u] = 1;
    adj1[u].push_back(v);
    adj1[v].push_back(u);
  }

  std::cin >> m2;
  for (int i = 0; i < m2; ++ i) {
    int u, v;
    std::cin >> u >> v;
    -- u, -- v;
    g2[u][v] = g2[v][u] = 1;
    adj2[u].push_back(v);
    adj2[v].push_back(u);
  }

  const int inf = 1e9;
  std::vector dist(n, std::vector<int>(n, inf));
  std::vector vis(n, std::vector<int>(n));
  using A = std::array<int, 3>;
  std::priority_queue<A, std::vector<A>, std::greater<A> > heap;
  dist[s1][s2] = 0;
  heap.push({0, s1, s2});
  while (heap.size()) {
    auto [_, x, y] = heap.top(); heap.pop();
    if (vis[x][y]) {
      continue;
    }

    for (auto & i : adj1[x]) {
      for (auto & j : adj2[y]) {
        if (dist[i][j] > dist[x][y] + std::abs(i - j)) {
          dist[i][j] = dist[x][y] + std::abs(i - j);
          if (!vis[i][j]) {
            heap.push({dist[i][j], i, j});
          }
        }
      }
    }
  }  

  int ans = inf;
  for (int i = 0; i < n; ++ i) {
    for (int j = 0; j < n; ++ j) {
      if (g1[i][j] && g2[i][j]) {
        ans = std::min(ans, dist[i][i]);
      }
    }
  }

  if (ans == inf) {
    ans = -1;
  }
  std::cout << ans << endl;
}