https://codeforces.com/contest/1251/problem/C
题目大意
给出一个数字字符组成的字符串 $S \ (|S| \le 3 \times 10 ^ 5)$，允许任意次交换相邻的奇偶性不同的字符，问最后的得出的可以包含前导零的最小数字是多少。
简要题解
这题挺典，首先同种奇偶性的字符的相对关系是无法改变的，因为通过相邻交换，如果两个字符顺序发生变化，一定先相邻再交换过，而这是不被允许的。于是我们有了两个顺序固定的序列，用这两个序列产生一个最优解。注意一般如果两个序列不是有序的，无法通过简单的双路归并得到字典序最小的结果，因为对于两个队列开头相同的情况，我们需要比较两个前缀的大小决定谁先被选，但是这题没有这个问题，因为奇数和偶数是总可以在队列头比出大小关系的。
复杂度
$T$：$O(n)$
$S$：$O(n)$
代码实现
#include <bits/stdc++.h>
using namespace std;
int io_=[](){ ios::sync_with_stdio(false); cin.tie(nullptr); return 0; }();
using LL = long long;
using ULL = unsigned long long;
using LD = long double;
using PII = pair<int, int>;
using VI = vector<int>;
using MII = map<int, int>;
template<typename T> void cmin(T &x,const T &y) { if(y<x) x=y; }
template<typename T> void cmax(T &x,const T &y) { if(x<y) x=y; }
template<typename T> bool ckmin(T &x,const T &y) {
return y<x ? (x=y, true) : false; }
template<typename T> bool ckmax(T &x,const T &y) {
return x<y ? (x=y, true) : false; }
template<typename T> void cmin(T &x,T &y,const T &z) {// x<=y<=z
if(z<x) { y=x; x=z; } else if(z<y) y=z; }
template<typename T> void cmax(T &x,T &y,const T &z) {// x>=y>=z
if(x<z) { y=x; x=z; } else if(y<z) y=z; }
// mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
// mt19937_64 rnd_64(chrono::system_clock::now().time_since_epoch().count());
/*
---------1---------2---------3---------4---------5---------6---------7---------
1234567890123456789012345678901234567890123456789012345678901234567890123456789
*/
void solve() {
string s; cin >> s;
string odd, even;
for (char c : s) {
if ((c - '0') & 1) {
odd += c;
} else {
even += c;
}
}
string ans;
int n = odd.size(), m = even.size();
int i = 0, j = 0;
while (i < n && j < m) {
if (odd[i] < even[j]) {
ans += odd[i++];
} else {
ans += even[j++];
}
}
while (i < n) ans += odd[i++];
while (j < m) ans += even[j++];
cout << ans << '\n';
}
int main() {
int t = 1;
cin >> t;
while (t--) {
solve();
}
return 0;
}
Next: [CF] B. Binary Palindromes - Educational Codeforces Round 75 (Rated for Div. 2)