2020-2021:teams:too_low:cf659_hj

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

--- 2020-2021:teams:too_low:cf659_hj [2020/07/31 17:59]
jim 创建
+++ 2020-2021:teams:too_low:cf659_hj [2020/07/31 18:12] (当前版本)
jim [B1 & B2]
@@ 行 42: / 行 42: @@
 ** 题解 **  设波浪高度为k-0-k，维护到达位置i时，可能的波浪时间范围[l, r]。位置i+1时，波浪的范围为[l+1, r+1]和 [k - (D - d[i]), k + (D - d[i])]的交，如果长度为0则不可游到。特别的，如果D大于d[i]+k则时间范围为[0,2k-1]，即整个长度
+特别要注意D - d[i]小于0的情况。这里pretest没有测结果B2 System test的时候WA了
 <hidden>
@@ 行 94: / 行 96: @@
 </code>
  </hidden>
+===== C =====
+** 题意 ** 给定AB两个a-t组成的字符串，每次可以将A字符串的一种字符改成另一种比其大的字符。求将A字符串改为B字符串的最小步数。如果不存在解输出-1
+** 题解 ** 可以等效为建立一个字符构成的有向图。从t至a遍历字符，如果a-c需要连边而存在b-c的边，则选择连a-b的边。
+<hidden>
+<code cpp>
+#include <bits/stdc++.h>
+using namespace std;
+int main() {
+    int t = 0;
+    cin >> t;
+    while (t--) {
+        int n;
+        cin >> n;
+        string a, b;
+        cin >> a >> b;
+        bool ok = true;
+        for (int i = 0; i < n; ++i) {
+            if (a[i] > b[i]) {
+                ok = false;
+                break;
+            }
+        }
+        if (!ok) {
+            cout << -1 << endl;
+            continue;
+        }
+        set<int> to[22] = {};
+        int toa[22][22] = {};
+        bool have[22] = {};
+        for (int i = 0; i < n; ++i) {
+            if (a[i] != b[i]) {
+                to[a[i] - 'a'].insert(b[i] - 'a');
+                toa[a[i] - 'a'][b[i] - 'a'] = 1;
+            }
+        }
+        int cnt = 0;
+        bool passed[22];
+        for (int i = 19; i >= 0; --i) {
+            if (to[i].empty())continue;
+            bool hh = false;
+            for (int j = 19; j > i; j--) {
+                bool ha = false;
+                for (int k : to[j]) {
+                    if (toa[i][k]) {
+                        ha = true;
+                        break;
+                    }
+                }
+                if (toa[i][j]) {
+                    ha = true;
+                }
+                if (ha) {
+                    to[i].insert(j);
+                    for (int k : to[j]) {
+                        to[i].insert(k);
+                        toa[i][k] = 0;
+                    }
+                    toa[i][j] = 1;
+                    to[i].insert(j);
+                    hh = true;
+                }
+            }
+            for (int j = 0; j < 20; ++j) {
+                cnt += toa[i][j];
+            }
+        }
+        cout << (cnt) << endl;
+    }
+}
+</code>
+</hidden>

2020-2021/teams/too_low/cf659_hj.1596189583.txt.gz · 最后更改: 2020/07/31 17:59 由 jim