Codeforces Round #715 (Div. 2)
A - Average Height
int main() {
IOS;
for (cin >> _; _; --_) {
cin >> n; VI a[2];
rep (i, 1, n) cin >> m, a[m & 1].pb(m);
if (a[0].size() < a[1].size()) swap(a[1], a[0]);
for (auto &i : a[0]) cout << i << ' ';
for (auto &i : a[1]) cout << i << ' '; cout << '\n';
}
return 0;
}
B - TMT Document
int main() {
IOS;
for (cin >> _; _; --_) {
cin >> n >> s + 1; int x = 0, y = 0, z = 0;
rep (i, 1, n) {
if (s[i] == 'T') {
if (y) --y, ++z;
else ++x;
} else {
if (x) --x, ++y;
else --z, y += 2;
}
if (z < 0) break;
}
cout << (z >= 0 && x == 0 && y == 0 ? "YES\n" : "NO\n");
}
return 0;
}
C - The Sports Festival
经典的区间dp
ll f[N][N];
int main() {
IOS; cin >> n; memset(f, 0x3f, sizeof f);
rep (i, 1, n) cin >> a[i], f[i][i] = 0; sort(a + 1, a + 1 + n);
rep (l, 2, n) rep (i, 1, n - l + 1)
f[i][i + l - 1] = min(f[i][i + l - 2], f[i + 1][i + l - 1]) + a[i + l - 1] - a[i];
cout << f[1][n];
return 0;
}
D - Binary Literature
让某两个串公用\(n\)个\(0\) or \(1\) 即可
pair<int, string> a[3];
int main() {
IOS;
for (cin >> _; _; --_) {
cin >> n >> a[0].se >> a[1].se >> a[2].se;
a[0].fi = a[1].fi = a[2].fi = 0;
rep (i, 1, n * 2) rep (j, 0, 2) a[j].fi += a[j].se[i] == '1';
sort(a, a + 3, [](pair<int, string>& a, pair<int, string>& b) { return a.fi < b.fi; });
char c = '1'; string t;
if (a[1].fi < n) swap(a[0], a[2]), c = '0';
int i, j;
for (i = 0, j = 0; max(i, j) < 2 * n; t += c, ++i, ++j) {
while (i < a[1].se.size() && a[1].se[i] != c) t += a[1].se[i++];
while (j < a[2].se.size() && a[2].se[j] != c) t += a[2].se[j++];
}
while (i < 2 * n) t += a[1].se[i++];
while (j < 2 * n) t += a[2].se[j++];
while (t.size() < 3 * n) t += c;
if (t.size() > 3 * n) t.pop_back();
cout << t << '\n';
}
return 0;
}
E - Almost Sorted
设\(a(n)\)表示长度为\(n\)的序列有几种排列
显然\(a(0) = a(1) = 1\)
注意到, 我们只能反转连续的一段, 毕竟要约束\(a_i + 1 \leqslant a_{i + 1}\)
故\(a(n) = \sum_i^{n - 1} a(i)\) 即 \(a(n) = 2^n\)
爆精度? \(k <= 1e18\) 求道某个\(a(n) >= 1e18\) 不就好了
然后就是找位置即可
int main() {
IOS; a[1] = a[0] = 1;
rep(i, 2, 1e5) {
a[i] = a[i - 1] << 1;
if (a[i] <= 0 || a[i] >= 1e18) break;
}
for (cin >> _; _; --_) {
ll k; cin >> n >> k; set<int> st;
if (a[n] > 0 && k > a[n]) { cout << "-1\n"; continue; }
rep(i, 1, n) st.insert(i);
per(i, n, 1) {
if (a[i - 1] <= 0 || a[i - 1] >= k) cout << *st.begin() << ' ', st.erase(st.begin());
else {
int l = *st.begin(), r = l;
while (a[i - 1] < k)
k -= a[i-- - 1], ++r;
per(i, r, l) cout << i << ' ', st.erase(st.begin());
}
}
cout << '\n';
}
return 0;
}