经验总结

  1. 首页 > 生活 > >

Div. 2 Codeforces Round #823 A-D( 二 )

生活百科


也可以直接桶排序 。
时间复杂度 \(O(n \log n)\)
空间复杂度 \(O(n)\)
代码#include <bits/stdc++.h>#define ll long longusing namespace std;bool solve() {string s;cin >> s;int mi = 10;for (int i = s.size() - 1;i >= 0;i--) {if (s[i] - '0' <= mi) mi = s[i] - '0';else s[i] = min(s[i] + 1, '9' + 0);}sort(s.begin(), s.end());cout << s << '\n';return true;}int main() {std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t--) {if (!solve()) cout << -1 << '\n';}return 0;}D题解知识点：构造 。
注意到操作不会改变无序对 \((a_i, b_{ n - i + 1 })\) 数量以及种类 。
引理：\(a = b\) ，当且仅当无序对是回文的 。

充分性：
当 \(a = b\) 时，如果 \(i\) 处存在一组无序对 \((x, y)\) ，则必然会在 \(n-i+1\) 产生相同一组无序对 \((y, x)\) ，除非当 \(n\) 为奇数时，可以在中间产生一个元素相同的无序对 \((x,x)\) ，因此 \(a = b\) 时，无序对必然成回文状 。
必要性：
当无序对是回文的，则第 \(i\) 组无序对 \((x,y)\) 可以对应第 \(n-i+1\) 组无序对 \((y,x)\) ，即 \(a_i = b_i\) ,所以 \(a = b\)。
充要条件：YES 当且仅当无序对 \((a_i, b_{ n - i + 1 })\) 中元素不同的无序对有偶数个，元素相同的无序对仅在 \(n\) 为奇数时至多 \(1\) 种有奇数个 。
充分性：
根据引理，显然满足右边条件 。
必要性：
显然没有任何限制时，给出的无序对条件能排列成回文的，现在尝试证明其必然可构造无序对回文 。
注意到操作 \(k = i\) 可以使得 \(a[1 \cdots k]\) 和 \(b[k\cdots n]\) 交换位置，即 \((a[k], b[n - k + 1])\) 这一组无序对被置换到了 \(1\) 号位置，同时 \((a[1],b[n])\) 这一组无序对被置换到了 \(i\) 号位置，但这不会改变 \(a[k+1 \cdots n]\) 和 \(b[1\cdots k-1]\) 的顺序，即第 \(k+1\) 到 \(n\) 组无序对及其实际元素顺序没有改变 。因此，如果我们想要将无序对通过操作变成一个我们想要的顺序，可以从右往左构造 。
假设 \(i+1\) 到 \(n\) 的无序对都安排好了，现在 \(i\) 号位置想要 \(j (j\leq i)\) 号位置的无序对时，可以先 \(k=j\) ，将 \(j\) 号替换到 \(1\) 号，然后 \(k=i\) ，将 \(1\) 号替换 \(i\) 号，过程中 \(i+1 \cdots n\) 的无序对不会改变，包括实际元素顺序 。
上述操作最后结果是无序对 \(j\) 替换到 \(i\) ，且 \(j\) 号无序对元素的实际顺序不会改变 。但如果我们希望实际元素的顺序也发生改变，我们可以加一个步骤 \(k = 1\) 在中间，即通过 \(k = j, k = 1, k = i\) 替换 \(i\) 号后的 \(j\) 号元素实际顺序与原来是相反的，这也是为什么我们只需要知道无序对顺序即可，因为元素实际顺序是可以随时改变的 。
通过上述操作我们可以实现无序对的任意排列，以及无序对实际元素的顺序 。因此无序对满足回文条件时，必然可以构造出无序对回文 。于是根据引理，得到 \(a = b\)。
时间复杂度 \(O(n)\)
空间复杂度 \(O(n)\)
代码#include <bits/stdc++.h>#define ll long longusing namespace std;string a, b;int cnt[26][26];bool solve() {memset(cnt, 0, sizeof(cnt));int n;cin >> n;string a, b;cin >> a >> b;for (int i = 0;i < n;i++) {int x = a[i] - 'a', y = b[n - 1 - i] - 'a';if (x > y) swap(x, y);cnt[x][y]++;}bool ok = true;int esum = 0;for (int i = 0;i < 26;i++) {for (int j = i;j < 26;j++) {if (i == j) esum += cnt[i][j] & 1;else ok &= !(cnt[i][j] & 1);}}if (ok && esum <= (n & 1)) cout << "YES" << '\n';else cout << "NO" << '\n';return true;}int main() {std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);int t = 1;cin >> t;while (t--) {if (!solve()) cout << -1 << '\n';}return 0;}

经验总结扩展阅读


上一篇：英雄联盟老鼠会说哪些话

下一篇：爬山作文