Codeforces Round #715 (Div. 2)
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了 Codeforces Round #715 (Div. 2),小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含2453字,纯文字阅读大概需要4分钟。
内容图文
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;
}
内容总结
以上是互联网集市为您收集整理的 Codeforces Round #715 (Div. 2)全部内容,希望文章能够帮你解决 Codeforces Round #715 (Div. 2)所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。