「CF1251X」Educational Codeforces Round 75
A. Broken Keyboard
如果有一个字母连续出现奇数次，则它是正常的，模拟
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 |
#include<map> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define pa pair<int,int> #define ll long long #define inf 1000000000 #define mod 1000000007 using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } string s; int main() { int T = read(); while(T--) { cin >> s; char c = s[0]; int cnt = 1; bool val[26] = {0}; for(int i = 1; i < s.length(); i++) { if(s[i] == c) cnt++; else { if(cnt & 1) val[c - 'a'] = 1; c = s[i]; cnt = 1; } } if(cnt & 1) val[c - 'a'] = 1; for(int i = 0; i < 26; i++) if(val[i]) printf("%c", char('a' + i)); puts(""); } return 0; } |
B. Binary Palindromes
由于可以随意交换，那么优先把短的 string 变成回文，需要消耗 len / 2 对字符
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 |
#include<map> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define pa pair<int,int> #define ll long long #define inf 1000000000 #define mod 1000000007 using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int T, n; vector<int> l; int main() { T = read(); while(T--) { n = read(); string s; int cnt[2] = {0}; l.clear(); for(int i = 1; i <= n; i++) { cin >> s; for(int i = 0; i < s.length(); i++) cnt[s[i] - '0']++; l.push_back(s.length() / 2); } int ans = 0, sum = cnt[0] / 2 + cnt[1] / 2; sort(l.begin(), l.end()); for(int i = 0; i < l.size(); i++) if(sum - l[i] >= 0) { sum -= l[i]; ans++; } printf("%d\n", ans); } return 0; } |
C. Minimize The Integer
最后能得到的字符串满足 所有奇数的相对顺序不变 且 所有偶数的相对顺序不变，从左到右依此贪心
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 |
#include<map> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define pa pair<int,int> #define ll long long #define inf 1000000000 #define mod 1000000007 using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int T; string s; vector<int> v0, v1; int main() { T = read(); while(T--) { cin >> s; v0.clear(); v1.clear(); for(int i = 0; i < s.length(); i++) { int x = s[i] - '0'; if(x & 1) v1.push_back(x); else v0.push_back(x); } int l = 0, r = 0; while(l < v0.size() || r < v1.size()) { if(l == v0.size()) { printf("%d", v1[r]); r++; } else if(r == v1.size()) { printf("%d", v0[l]); l++; } else if(v0[l] > v1[r]) { printf("%d", v1[r]); r++; } else { printf("%d", v0[l]); l++; } } puts(""); } return 0; } |
D. Salary Changing
二分中位数 mid，按薪水左端点排序
左端点从大到小考虑，让前 n / 2 + 1 个人 薪水 >= mid，其它人取左端点，并判断合法性
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 |
#include<map> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define pa pair<ll, ll> #define ll long long #define inf 1000000000 #define mod 1000000007 using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int T, n; ll s; pa a[200005]; bool check(ll x) { int p = n / 2 + 1; ll sum = 0; for(int i = n; i >= 1; i--) if(a[i].second >= x && p > 0) { sum += max(x, a[i].first); p--; } else sum += a[i].first; if(sum > s)return 0; if(p > 0)return 0; return 1; } int main() { T = read(); while(T--) { n = read(); s = read(); for(int i = 1; i <= n; i++) { ll l = read(), r = read(); a[i] = make_pair(l, r); } sort(a + 1, a + n + 1); ll l = 0, r = s, ans = 0; while(l <= r) { ll mid = (l + r) >> 1; if(check(mid)) l = mid + 1, ans = mid; else r = mid - 1; } cout << ans << endl; } return 0; } |
E2. Voting (Hard Version)
这个贪心很不好想，按 m 排序，可以算一下比每个人 m 更大的那些人中，至少要贿赂多少人
假设排序后的 m 序列是 1 3 3 4 5 7 7 7
令 b_i = m_i – i + 1，即 1 2 1 1 1 2 1 0，表示说，第 i 个人往后的人里，至少要贿赂 b_i 个人
从右往左，维护一个 multiset，贿赂最便宜的人
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 |
#include<map> #include<set> #include<cmath> #include<ctime> #include<queue> #include<cstdio> #include<vector> #include<bitset> #include<cstring> #include<iostream> #include<algorithm> #define pa pair<ll, ll> #define ll long long #define inf 1000000000 #define mod 1000000007 using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int T, n; int b[200005]; struct data{ int m, p; }a[200005]; bool cmp(data x, data y) { if(x.m == y.m) return x.p > y.p; return x.m < y.m; } multiset<int> st; int main() { T = read(); while(T--) { n = read(); for(int i = 1; i <= n; i++) a[i].m = read(), a[i].p = read(); sort(a + 1, a + n + 1, cmp); st.clear(); st.insert(0); for(int i = 1; i <= n; i++) b[i] = max(0, a[i].m - i + 1); int cnt = 0; ll ans = 0; for(int i = n; i >= 1; i--) { st.insert(a[i].p); while(cnt < b[i]) { int tmp = *st.upper_bound(0); st.erase(st.upper_bound(0)); ans += tmp; cnt++; } } cout << ans << endl; } return 0; } |
Subscribe
计数器 9793084
OI 课件=>
OI 课件=>