2018-2019 Russia Open High School Programming Contest

题目链接

Problem:

http://assets.codeforces.com/rounds/1090/a73f8d/en.pdf

Problem A. Company Merging

数列合并花费是将最大值小的数列所有元素加上最大值与最大值大的数列的最大值的差值,求 $n$ 个数列合并的花费

记录每个数列的最大值、数字数量,求出所有数列的最大值依次计算求和即可

#include <bits/stdc++.h>

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr); std::cout.tie(nullptr);

  int n; std::cin >> n;
  std::vector<int> arr(n), cnt(n);
  int tar = 0;
  for (int i = 0, k; i < n; ++i) {
    std::cin >> k;
    cnt[i] = k;
    int max = 0;
    for (int i = 0, x; i < k; ++i) {
      std::cin >> x;
      max = std::max(max, x);
    }
    tar = std::max(tar, max);
    arr[i] = max;
  }

  long long ans = 0;
  for (int i = 0; i < n; ++i) ans += 1ll * (tar - arr[i]) * cnt[i];

  std::cout << ans << '\n';
  return 0;
}

Problem B. LaTeX Expert

根据文章信息给 $\texttt{Latex}$ 的注释排序

将文章内的 $\{*\}$ 信息提取编号与注释对比排序即可

#include <bits/stdc++.h>


int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr); std::cout.tie(nullptr);

  std::string str, art;
  std::vector<std::pair<std::string, int>> vec;
  while (getline(std::cin, str)) {
    if (str == "\\begin{thebibliography}{99}") {
      vec.push_back({str, (int)vec.size()});
      break;
    }
    art += str;
  }

  int tot = 0; bool flag = false;
  std::string name;
  std::map<std::string, int> order;
  for (auto &c : art) {
    if (c == '{') {
      flag = true;
      name.clear();
      continue;
    }
    if (c == '}') {
      order[name] = ++tot;
      flag = false;
    }
    if (flag) name += c;
  }

  bool suc = true;
  while (getline(std::cin, str)) {
    if (str == "\\end{thebibliography}") {
      vec.push_back({str, (int)vec.size()});
      break;
    }
    std::string name; flag = false;
    for (auto &c : str) {
      if (c == '{') {
        flag = true;
        continue;
      }
      if (c == '}') {
        if (order[name] != (int)vec.size()) suc = false;
        vec.push_back({str, order[name]});
        flag = false;
      }
      if (flag) name += c;
    }
  }

  if (suc) {
    std::cout << "Correct" << '\n';
    return 0;
  }

  std::cout << "Incorrect" << '\n';
  std::sort(vec.begin(), vec.end(), [&](std::pair<std::string, int> k1, std::pair<std::string, int> k2) {
    return k1.second < k2.second;
  });
  for (auto &s : vec) std::cout << s.first << '\n';
  return 0;
}

Problem D. Similar Arrays

构造两个数列使得第一个数列由 $1\sim n$ 各不相同的数字组成,第二个数列有且仅有两个数字相同,并且两个数列的 $m$ 个位置比较约束条件结果相同

选择两个没有约束条件的位置对第一个数列随意赋值,对第二个数列将其改为相同得数字

#include <bits/stdc++.h>

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr); std::cout.tie(nullptr);

  int n, m; std::cin >> n >> m;

  std::set<std::pair<int, int>> e;

  for (int i = 1, u, v; i <= m; ++i) {
    std::cin >> u >> v;
    e.insert({u, v});
    e.insert({v, u});
  }

  for (int i = 1; i <= n; ++i) {
    for (int j = i + 1; j <= n; ++j) {
      if (e.find({i, j}) != e.end()) continue;
      std::cout << "YES" << '\n';
      int cur = 1;
      for (int k = 1; k <= n; ++k) {
        if (k == i) {
          std::cout << n << ' ';
          continue;
        }
        if (k == j) {
          std::cout << n - 1 << ' ';
          continue;
        }
        std::cout << cur++ << ' ';
      }
      std::cout << '\n';
      cur = 1;
      for (int k = 1; k <= n; ++k) {
        if (k == i || k == j) {
          std::cout << n << ' ';
          continue;
        }
        std::cout << cur++ << ' ';
      }
      std::cout << '\n';
      return 0;
    }
  }

  std::cout << "NO" << '\n';
  return 0;
}

Problem M. The Pleasant Walk

求无相邻相同元素的最长串长度

循环判断更新一遍即可(签到

#include <bits/stdc++.h>

int main() {
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr); std::cout.tie(nullptr);

  int n, k; std::cin >> n >> k;
  int len = 1, last = -1, ans = 1;
  for (int i = 0, x; i < n; ++i) {
    std::cin >> x;
    if (last == -1) {
      last = x;
      continue;
    }
    if (x == last) len = 1;
    else ++len;
    ans = std::max(ans, len);
    last = x;
  }

  std::cout << ans << '\n';
  return 0;
}
Last modification:April 25th, 2019 at 02:31 pm
如果觉得我的文章对你有用,请随意赞赏

Leave a Comment