Educational Codeforces Round 99 (Rated for Div. 2)

A. Strange Functions

读懂题即可（或者快速看一下样例解释）,直接输出字符串长度即可。

  1. void solve() {
  2.     string s;
  3.     cin >> s;
  4.     cout << s.length() << endl;
  5. }

B. Jumps

这是一个数轴移动问题，按题意推导一下就好

  1. void solve() {
  2.     int x;  cin >> x;
  3.     int cnt = 0;
  4.     while (cnt * (cnt + 1) < (x << 1)) cnt++;
  5.     if (cnt * (cnt + 1) / 2 == x + 1)  cnt++;
  6.     cout << cnt << endl;
  7. }

C. Ping-pong

题意是Alice 和 Bob 开始玩击球游戏，但他们只有 x 和 y 个体力，每次发球和击回都要消耗一点体力，问怎么应对才能使两方的赢数最大

根据样例解释，其实对Bob而言只要我不回第一球，那么后面都会是Bob赢。那么就很简单了，次数为 Educational Codeforces Round 99 (Rated for Div. 2) （A ~ F）个人题解 - 图1

  1. void solve() {
  2.     int x, y;
  3.     cin >> x >> y;
  4.     cout << x - 1 << " " << y << endl;
  5. }

D. Sequence and Swaps

这道题一开始想简单了，正确思路是先判断是否已经排序好了，如果是的话直接输出0，不然把x插入每个位置进行尝试，即计算逆序，每次都进行最小值判断。

AC代码 ↓

  1. void solve() {
  2.     int n, x;
  3.     cin >> n >> x;
  4.     vector<int> a(n);
  5.     for (int i = 0; i < n; ++i)
  6.         cin >> a[i];
  7.     int ans = n + 1;
  8.     if (is_sorted(a.begin(), a.end())){//STL函数，判断是否有序
  9.           cout << 0 << endl;
  10.         return;
  11.     }
  12.     for (int i = 0; i < n; ++i) {
  13.         vector<int> b(a);
  14.         b[i] = x;
  15.         sort(b.begin(), b.end());
  16.         int cur = x, cnt = 0;
  17.         bool f = true;
  18.         for (int j = 0; j < n; ++j) {
  19.             if (a[j] != b[j]) {
  20.                 ++cnt;
  21.                 if (cur == b[j] && b[j] < a[j])
  22.                     cur = a[j];
  23.                 else
  24.                     f = false;
  25.             }
  26.         }
  27.         if (f)
  28.             ans = min(ans, cnt);
  29.     }
  30.     if (ans > n)
  31.         ans = -1;
  32.     cout << ans << "\n";
  33. }

E. Four Points

Educational Codeforces Round 99 (Rated for Div. 2) （A ~ F）个人题解 - 图2

直接去写的话感觉很麻烦，这里思路借鉴了rank2的大神的代码：转化为复数处理。

对标样例模拟就清楚了。

  1. void solve() {
  2.     ll ans = 1e18;
  3.     pair<int, int> p[4];
  4.     for (int i = 0; i < 4; ++i)
  5.         cin >> p[i].first >> p[i].second;
  6.     sort(p, p + 4);
  7.     do {
  8.         vector<int> cand{0};
  9.         for (int i = 0; i < 2; ++i)
  10.             for (int j = 0; j < 2; ++j) {
  11.                 cand.push_back(p[2 + j].first - p[i].first);
  12.                 cand.push_back(p[2 * j + 1].second - p[2 * i].second);
  13.             }
  15.         for (auto d : cand) {
  16.             if (d < 0)
  17.                 continue;
  18.             ll res = 0;
  19.             int x[4], y[4];
  20.             for (int i = 0; i < 4; ++i)
  21.                 tie(x[i], y[i]) = p[i];  //转化为复数处理
  22.             x[2] -= d, x[3] -= d;
  23.             y[1] -= d, y[3] -= d;
  24.             sort(x, x + 4), sort(y, y + 4);
  25.             for (int i = 0; i < 4; ++i) {
  26.                 res += abs(x[i] - x[1]);
  27.                 res += abs(y[i] - y[1]);
  28.             }
  29.             ans = min(res, ans);
  30.         }
  31.     } while (next_permutation(p, p + 4));
  32.     cout << ans << endl;
  33. }

F. String and Operations

贴一下dalao代码作为学习

  1. void update(std::string& a, const std::string& b) {
  2.     if (a.empty() || a > b)
  3.         a = b;
  4. }
  5. void solve() {
  6.     int n, k;
  7.     std::cin >> n >> k;
  8.     std::string a, b;
  9.     std::cin >> a;
  10.     b = a;
  11.     for (int i = 0; i < n; ++i) {
  12.         if (b[i] == 'a' + k - 1)
  13.             b[i] = 'a';
  14.         else if (b[i] != 'a')
  15.             --b[i];
  16.     }
  17.     std::string dp[2][2];
  18.     dp[0][0] = a;
  19.     int cur = 0;
  20.     for (int i = 0; i < n; ++i) {
  21.         cur ^= 1;
  22.         dp[cur][0] = dp[cur][1] = "";
  23.         if (!dp[!cur][0].empty()) {
  24.             auto& s = dp[!cur][0];
  25.             update(dp[cur][0], s);
  26.             if (i > 0) {
  27.                 std::swap(s[i], s[i - 1]);
  28.                 update(dp[cur][0], s);
  29.                 std::swap(s[i], s[i - 1]);
  30.             }
  31.             if (i + 1 < n) {
  32.                 std::swap(s[i], s[i + 1]);
  33.                 update(dp[cur][1], s);
  34.                 std::swap(s[i], s[i + 1]);
  35.             }
  36.             s[i] = b[i];
  37.             update(dp[cur][0], s);
  38.         }
  39.         if (!dp[!cur][1].empty()) {
  40.             auto& s = dp[!cur][1];
  41.             update(dp[cur][0], s);
  42.             if (i > 1) {
  43.                 std::swap(s[i - 1], s[i - 2]);
  44.                 update(dp[cur][0], s);
  45.                 std::swap(s[i - 1], s[i - 2]);
  46.             }
  47.             s[i - 1] = b[i];
  48.             update(dp[cur][0], s);
  49.         }
  50.     }
  51.     std::cout << dp[cur][0] << "\n";
  52. }

G. Forbidden Value

最后一道题似乎是线段树 + DP ? 看完题没啥思路。。。（老菜鸡了）