# Educational Codeforces Round 75

2022年11月23日
0 收藏 466 点赞 4,264 浏览 11518 个字

## Contest Info

Solved A B C D E1 E2 F
6/7 O O O O O O
• O 在比赛中通过
• Ø 赛后通过
• ! 尝试了但是失败了
• – 没有尝试

## Solutions

### A. Broken Keyboard

view code
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")#include <bits/stdc++.h>#define fi first#define se second#define endl "\n"using namespace std;using db = double;using ll = long long;using ull = unsigned long long;using pII = pair <int, int>;using pLL = pair <ll, ll>;constexpr int mod = 1e9 + 7;template <class T1, class T2> inline void chadd(T1 &x, T2 y) { x += y; while (x >= mod) x -= mod; while (x < 0) x += mod; }template <class T1, class T2> inline void chmax(T1 &x, T2 y) { if (x < y) x = y; }template <class T1, class T2> inline void chmin(T1 &x, T2 y) { if (x > y) x = y; }inline int rd() { int x; cin >> x; return x; }template <class T> inline void rd(T &x) { cin >> x; }template <class T> inline void rd(vector <T> &vec) { for (auto &it : vec) cin >> it; }#define dbg(x...) do { cout << "\033[32;1m" << #x << " -> "; err(x); } while (0)void err() { cout << "\033[39;0m" << endl; }template <class T, class... Ts> void err(const T& arg, const Ts&... args) { cout << arg << ' '; err(args...); }template <template<typename...> class T, typename t, typename... A>void err(const T <t> &arg, const A&... args) { for (auto &v : arg) cout << v << ' '; err(args...); }inline void pt() { cout << endl; }template <class T, class... Ts> void pt(const T& arg, const Ts&... args) { cout << arg << ' '; pt(args...); }template <template<typename...> class T, typename t, typename... A>void pt(const T <t> &arg, const A&... args) { for (auto &v : arg) cout << v << ' '; pt(args...); }ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }inline ll qpow(ll base, ll n) { ll res = 1; while (n) { if (n & 1) res = res * base % mod; base = base * base % mod; n >>= 1; } return res; }//headconstexpr int N = 1e5 + 10;int n, cnt[30]; string s;void run() {cin >> s;memset(cnt, -1, sizeof cnt);for (int i = 0, len = s.size(), num = 0; i <= len; ++i) {if (i == len) {if (num & 1) {cnt[s[i - 1] - 'a'] = 1;}} else if (i && s[i] != s[i - 1]) {if (num & 1) {cnt[s[i - 1] - 'a'] = 1;}num = 0;}++num;}for (int i = 0; i < 26; ++i) if (cnt[i] > 0)cout << char(i + 'a');cout << endl;}int main() {ios::sync_with_stdio(false);cin.tie(nullptr); cout.tie(nullptr);cout << fixed << setprecision(20);int _T = rd();while (_T--) run();return 0;}

### B. Binary Palindromes

view code
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")#include <bits/stdc++.h>#define fi first#define se second#define endl "\n"using namespace std;using db = double;using ll = long long;using ull = unsigned long long;using pII = pair <int, int>;using pLL = pair <ll, ll>;constexpr int mod = 1e9 + 7;template <class T1, class T2> inline void chadd(T1 &x, T2 y) { x += y; while (x >= mod) x -= mod; while (x < 0) x += mod; }template <class T1, class T2> inline void chmax(T1 &x, T2 y) { if (x < y) x = y; }template <class T1, class T2> inline void chmin(T1 &x, T2 y) { if (x > y) x = y; }inline int rd() { int x; cin >> x; return x; }template <class T> inline void rd(T &x) { cin >> x; }template <class T> inline void rd(vector <T> &vec) { for (auto &it : vec) cin >> it; }#define dbg(x...) do { cout << "\033[32;1m" << #x << " -> "; err(x); } while (0)void err() { cout << "\033[39;0m" << endl; }template <class T, class... Ts> void err(const T& arg, const Ts&... args) { cout << arg << ' '; err(args...); }template <template<typename...> class T, typename t, typename... A>void err(const T <t> &arg, const A&... args) { for (auto &v : arg) cout << v << ' '; err(args...); }inline void pt() { cout << endl; }template <class T, class... Ts> void pt(const T& arg, const Ts&... args) { cout << arg << ' '; pt(args...); }template <template<typename...> class T, typename t, typename... A>void pt(const T <t> &arg, const A&... args) { for (auto &v : arg) cout << v << ' '; pt(args...); }ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }inline ll qpow(ll base, ll n) { ll res = 1; while (n) { if (n & 1) res = res * base % mod; base = base * base % mod; n >>= 1; } return res; }//headconstexpr int N = 1e5 + 10;int n, cnt[2], len[110];void run() {n = rd();cnt[0] = cnt[1] = 0;for (int i = 1; i <= n; ++i) {string s; cin >> s;len[i] = s.size();for (auto &c : s) ++cnt[c - '0'];}sort(len + 1, len + 1 + n);int res = 0;for (int i = 1; i <= n; ++i) {if (len[i] & 1) {if (cnt[0] & 1) {--cnt[0];} else if (cnt[1] & 1) {--cnt[1];} else if (cnt[0]) {--cnt[0];} else if (cnt[1]) {--cnt[1];} else {break;}--len[i];}if (len[i] > cnt[0]) {if (cnt[0] & 1) {len[i] = len[i] - cnt[0] + 1;cnt[0] = 1;} else {len[i] -= cnt[0];cnt[0] = 0;}} else {cnt[0] -= len[i];len[i] = 0;}if (len[i] > cnt[1]) {if (cnt[1] & 1) {len[i] = len[i] - cnt[1] + 1;cnt[1] = 1;} else {len[i] -= cnt[1];cnt[1] = 0;}} else {cnt[1] -= len[i];len[i] = 0;}if (len[i]) break;++res;}pt(res);}int main() {ios::sync_with_stdio(false);cin.tie(nullptr); cout.tie(nullptr);cout << fixed << setprecision(20);int _T = rd();while (_T--) run();return 0;}

### C. Minimize The Integer

view code
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")#include <bits/stdc++.h>#define fi first#define se second#define endl "\n"using namespace std;using db = double;using ll = long long;using ull = unsigned long long;using pII = pair <int, int>;using pLL = pair <ll, ll>;constexpr int mod = 1e9 + 7;template <class T1, class T2> inline void chadd(T1 &x, T2 y) { x += y; while (x >= mod) x -= mod; while (x < 0) x += mod; }template <class T1, class T2> inline void chmax(T1 &x, T2 y) { if (x < y) x = y; }template <class T1, class T2> inline void chmin(T1 &x, T2 y) { if (x > y) x = y; }inline int rd() { int x; cin >> x; return x; }template <class T> inline void rd(T &x) { cin >> x; }template <class T> inline void rd(vector <T> &vec) { for (auto &it : vec) cin >> it; }#define dbg(x...) do { cout << "\033[32;1m" << #x << " -> "; err(x); } while (0)void err() { cout << "\033[39;0m" << endl; }template <class T, class... Ts> void err(const T& arg, const Ts&... args) { cout << arg << ' '; err(args...); }template <template<typename...> class T, typename t, typename... A>void err(const T <t> &arg, const A&... args) { for (auto &v : arg) cout << v << ' '; err(args...); }inline void pt() { cout << endl; }template <class T, class... Ts> void pt(const T& arg, const Ts&... args) { cout << arg << ' '; pt(args...); }template <template<typename...> class T, typename t, typename... A>void pt(const T <t> &arg, const A&... args) { for (auto &v : arg) cout << v << ' '; pt(args...); }ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }inline ll qpow(ll base, ll n) { ll res = 1; while (n) { if (n & 1) res = res * base % mod; base = base * base % mod; n >>= 1; } return res; }//headconstexpr int N = 3e5 + 10;int n; char s[N];void out(vector <int> &vec) {cout << vec.back();vec.pop_back();}void run() {vector <int> vec[2];cin >> (s + 1);for (int i = 1; s[i]; ++i) {int num = s[i] - '0';vec[num & 1].push_back(num);}reverse(vec[0].begin(), vec[0].end());reverse(vec[1].begin(), vec[1].end());while (!vec[0].empty() || !vec[1].empty()) {if (vec[0].empty()) {out(vec[1]);} else if (vec[1].empty()) {out(vec[0]);} else {if (vec[0].back() < vec[1].back()) {out(vec[0]);} else {out(vec[1]);}}}cout << endl;}int main() {ios::sync_with_stdio(false);cin.tie(nullptr); cout.tie(nullptr);cout << fixed << setprecision(20);int _T; cin >> _T;while (_T--) run();return 0;}

### D. Salary Changing

view code
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")#include <bits/stdc++.h>#define fi first#define se second#define endl "\n"using namespace std;using db = double;using ll = long long;using ull = unsigned long long;using pII = pair <int, int>;using pLL = pair <ll, ll>;constexpr int mod = 1e9 + 7;template <class T1, class T2> inline void chadd(T1 &x, T2 y) { x += y; while (x >= mod) x -= mod; while (x < 0) x += mod; }template <class T1, class T2> inline void chmax(T1 &x, T2 y) { if (x < y) x = y; }template <class T1, class T2> inline void chmin(T1 &x, T2 y) { if (x > y) x = y; }inline int rd() { int x; cin >> x; return x; }template <class T> inline void rd(T &x) { cin >> x; }template <class T> inline void rd(vector <T> &vec) { for (auto &it : vec) cin >> it; }#define dbg(x...) do { cout << "\033[32;1m" << #x << " -> "; err(x); } while (0)void err() { cout << "\033[39;0m" << endl; }template <class T, class... Ts> void err(const T& arg, const Ts&... args) { cout << arg << ' '; err(args...); }template <template<typename...> class T, typename t, typename... A>void err(const T <t> &arg, const A&... args) { for (auto &v : arg) cout << v << ' '; err(args...); }inline void pt() { cout << endl; }template <class T, class... Ts> void pt(const T& arg, const Ts&... args) { cout << arg << ' '; pt(args...); }template <template<typename...> class T, typename t, typename... A>void pt(const T <t> &arg, const A&... args) { for (auto &v : arg) cout << v << ' '; pt(args...); }ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }inline ll qpow(ll base, ll n) { ll res = 1; while (n) { if (n & 1) res = res * base % mod; base = base * base % mod; n >>= 1; } return res; }//headconstexpr int N = 2e5 + 10;int n; ll s;pII a[N];bool check(ll x) {int l = 0, r = 0;ll remind = s;for (int i = 1; i <= n; ++i) {if (a[i].se < x) {remind -= a[i].fi;++l;} else if (a[i].fi > x) {remind -= a[i].fi;++r;}}if (l > n / 2 || r > n / 2) return false;for (int i = 1; i <= n; ++i) {if (a[i].fi <= x && a[i].se >= x) {if (l < n / 2) {++l;remind -= a[i].fi;} else {remind -= x;}}}return remind >= 0;}void run() {cin >> n >> s;for (int i = 1; i <= n; ++i) a[i].fi = rd(), a[i].se = rd();sort(a + 1, a + 1 + n);ll l = a[n / 2 + 1].fi, r = 1e9, res = l;while (r - l >= 0) {ll mid = (l + r) >> 1;if (check(mid)) {res = mid;l = mid + 1;} else {r = mid - 1;}}pt(res);}int main() {ios::sync_with_stdio(false);cin.tie(nullptr); cout.tie(nullptr);cout << fixed << setprecision(20);int _T = rd();while (_T--) run();return 0;}

### E2. Voting (Hard Version)

view code
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")#include <bits/stdc++.h>#define fi first#define se second#define endl "\n"using namespace std;using db = double;using ll = long long;using ull = unsigned long long;using pII = pair <int, int>;using pLL = pair <ll, ll>;constexpr int mod = 1e9 + 7;template <class T1, class T2> inline void chadd(T1 &x, T2 y) { x += y; while (x >= mod) x -= mod; while (x < 0) x += mod; }template <class T1, class T2> inline void chmax(T1 &x, T2 y) { if (x < y) x = y; }template <class T1, class T2> inline void chmin(T1 &x, T2 y) { if (x > y) x = y; }inline int rd() { int x; cin >> x; return x; }template <class T> inline void rd(T &x) { cin >> x; }template <class T> inline void rd(vector <T> &vec) { for (auto &it : vec) cin >> it; }#define dbg(x...) do { cout << "\033[32;1m" << #x << " -> "; err(x); } while (0)void err() { cout << "\033[39;0m" << endl; }template <class T, class... Ts> void err(const T& arg, const Ts&... args) { cout << arg << ' '; err(args...); }template <template<typename...> class T, typename t, typename... A>void err(const T <t> &arg, const A&... args) { for (auto &v : arg) cout << v << ' '; err(args...); }inline void pt() { cout << endl; }template <class T, class... Ts> void pt(const T& arg, const Ts&... args) { cout << arg << ' '; pt(args...); }template <template<typename...> class T, typename t, typename... A>void pt(const T <t> &arg, const A&... args) { for (auto &v : arg) cout << v << ' '; pt(args...); }ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }inline ll qpow(ll base, ll n) { ll res = 1; while (n) { if (n & 1) res = res * base % mod; base = base * base % mod; n >>= 1; } return res; }//headconstexpr int N = 2e5 + 10;int n; vector <vector<int>> vec;ll gao(int x) {ll tot = 0;priority_queue <int, vector<int>, less<int>> pq;for (int i = 1; i <= n; ++i) {for (auto &it : vec[i]) pq.push(it);if (i >= x) {if (pq.empty()) return 0;tot += pq.top(); pq.pop();}}return tot;}void run() {n = rd();vec.clear(); vec.resize(n + 1);ll tot = 0;for (int i = 1, m, p; i <= n; ++i) {m = rd(); p = rd();vec[m + 1].push_back(p);tot += p;}int l = 1, r = n; ll Max = 0;while (r - l >= 0) {int mid = (l + r) >> 1;ll tmp = gao(mid);chmax(Max, tmp);//dbg(l, r, mid, Max);if (tmp > 0) {r = mid - 1;} else {l = mid + 1;}}pt(tot - Max);}int main() {ios::sync_with_stdio(false);cin.tie(nullptr); cout.tie(nullptr);cout << fixed << setprecision(20);int _T = rd();while (_T--) run();return 0;}

python开发_常用的python模块及安装方法

Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接：http://www.codeforces.com/contest/660/problem/CDes…

zengkefu@server1:/usr/src\$ uname -aLinux server1 4.10.0-19-generic #21…

Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式，并且由于涉及到要把拍到的照片显…

Struts的使用