Educational Codeforces Round 75 (Rated for Div. 2) A~E2_过后投放

网络投稿 02-07 4697

Educational Codeforces Round 75 (Rated for Div. 2) A~E2 A. Broken Keyboard

链接

#include<bits/stdc++.h> using namespace std; int st[30]; int main() { int T; cin >> T; while (T--) { string s; cin >> s; for (int i = 0; i < s.length();) { if (s[i] == s[i + 1]) { i += 2; continue; } st[s[i] - 'a'] = 1;i++; } for (int i = 0; i < 26; i++) { if (st[i]) { cout << (char)('a' + i);st[i] = 0; } }cout << endl; } return 0; } B. Binary Palindromes

链接

#include<bits/stdc++.h> using namespace std; void solve() { int n; cin >> n; int idx = 0, cnt = 0; for (int i = 1; i <= n; i++) { string s; cin >> s; int len = s.length(); if (len % 2) idx++; for (int j = 0; j < len; j++) { if (s[j] == '1') cnt++; } } if (cnt % 2) { if (idx) cout << n << endl; else cout << n - 1 << endl; }else cout << n << endl; } int main() { int T; cin >> T; while (T--) { solve(); } return 0; } C. Minimize The Integer

链接题意：给出一个长度为 3 ? 1 0 5 3*10^5 3?105的数字，你可以交换相邻的数，但是他们的奇偶性要不同，求能换出来的最小的数字，保留前缀0 思路：不难看出，同类型不能交换，所以我们顺序存下每个类型的数字，然后输出每个里面更小的那个就行

#include<bits/stdc++.h> using namespace std; void solve() { string s; cin >> s; queue<int> odd, even; int len = s.length(); for (int i = 0; i < len; i++) { if ((s[i] - '0') & 1) odd.push(s[i] - '0'); else even.push(s[i] - '0'); } while (!odd.empty() && !even.empty()) { if (odd.front() > even.front()) {cout << even.front();even.pop();} else {cout << odd.front();odd.pop();} } while (!odd.empty()) {cout << odd.front();odd.pop();} while (!even.empty()) {cout << even.front();even.pop();} cout << endl; } int main() { int T; T = 1; cin >> T; while (T--) solve(); return 0; } D. Salary Changing

链接题意：给出总共的钱数，和人数，每个人的工资在 l i 和 r i l_i和r_i li?和ri?之间，现在要让他们工资的中位数最大，求出最大的中位数思路：二分答案，贪心的求就行

#include<bits/stdc++.h> using namespace std; #define int long long int n, s; struct Node {int l, r;}a[200010]; bool cmp(Node a, Node b) { if (a.l == b.l) return a.r > b.r; return a.l > b.l; } int all; bool check(int x) { int num = 0; for (int i = 1; i <= n; i++) { if (a[i].l > x) num++; } if (num >= n / 2 + 1) return true; int cnt = 0; int sum = all; if (cnt >= n / 2 + 1) {return true;} int idx = cnt + 1; while (sum <= s && idx <= n + 1) { if (cnt == n / 2 + 1) return true; if (idx == n + 1) return false; if (a[idx].r < x) {idx++; continue;} cnt++; sum += max((x - a[idx].l), 0ll); idx++; }return false; } void solve() { all = 0; cin >> n >> s; for (int i = 1; i <= n; i++) {cin >> a[i].l >> a[i].r; all += a[i].l;} sort(a + 1, a + 1 + n, cmp); int l = 0, r = 1e9+1, ans = 0; while (l < r) { int mid = l + r >> 1; if (check(mid)) {ans = mid, l = mid + 1;} else r = mid; } cout << ans << endl; cout << endl; } signed main() { int T; cin >> T; while (T--) solve(); return 0; } E. Voting

链接题意：给出每个人的m和p，意思是，你可以花费p购买他，或者等你获得了m个人后自动获取他，问获得全部人最小的花费思路：感觉是个有点经典的贪心，首先对于需要人数相同的，一定是先买钱少的，对于需要人数多的，我们可以假设在他之前的所有人已经获得再来获得他，所以对于这种人数，优先买钱少的直到足够多，我们把所有需要购买的放进一个set，每次取小的出来买就行

#include<bits/stdc++.h> using namespace std; #define int long long void solve() { int n; cin >> n; vector<int> a[n + 1]; multiset<int> st; for (int i = 1; i <= n; i++) { int x, y; cin >> x >> y; a[x].push_back(y); } int idx = n; int buy = 0, ans = 0; for (int i = n; i >= 1; i--) { idx -= a[i].size(); int need = i - idx; for (int j = 0; j < a[i].size(); j++) { st.insert(a[i][j]); } while(buy < need) { ans += (*st.begin()); st.erase(st.begin()); buy++; } } cout << ans << endl; cout << endl; } signed main() { int T; cin >> T; while (T--) solve(); return 0; }