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]，即整个长度 | ** 题解 ** 设波浪高度为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> | <hidden> | ||
| 行 94: | 行 96: | ||
| </code> | </code> | ||
| </hidden> | </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
