Educational Codeforces Round 75 ABCD题解

A. Broken Keyboard

Description

给出一串小写字母字符序列，连续出现两次的字母为坏掉的，按字典序输出所有没有坏掉的字母。

Solution

模拟暴力删除字母，注意相同字母的去重。

  1 #include <algorithm>
  2 #include <cctype>
  3 #include <cmath>
  4 #include <cstdio>
  5 #include <cstdlib>
  6 #include <cstring>
  7 #include <iostream>
  8 #include <map>
  9 #include <numeric>
 10 #include <queue>
 11 #include <set>
 12 #include <stack>
 13 #if __cplusplus >= 201103L
 14 #include <unordered_map>
 15 #include <unordered_set>
 16 #endif
 17 #include <vector>
 18 #define lson rt << 1, l, mid
 19 #define rson rt << 1 | 1, mid + 1, r
 20 #define LONG_LONG_MAX 9223372036854775807LL
 21 #define pblank putchar(' ')
 22 #define ll LL
 23 using namespace std;
 24 typedef long long ll;
 25 typedef long double ld;
 26 typedef unsigned long long ull;
 27 typedef pair<int, int> P;
 28 int n, m, k;
 29 const int maxn = 1e5 + 10;
 30 template <class T>
 31 inline T read()
 32 {
 33     int f = 1;
 34     T ret = 0;
 35     char ch = getchar();
 36     while (!isdigit(ch))
 37     {
 38         if (ch == '-')
 39             f = -1;
 40         ch = getchar();
 41     }
 42     while (isdigit(ch))
 43     {
 44         ret = (ret << 1) + (ret << 3) + ch - '0';
 45         ch = getchar();
 46     }
 47     ret *= f;
 48     return ret;
 49 }
 50 template <class T>
 51 inline void write(T n)
 52 {
 53     if (n < 0)
 54     {
 55         putchar('-');
 56         n = -n;
 57     }
 58     if (n >= 10)
 59     {
 60         write(n / 10);
 61     }
 62     putchar(n % 10 + '0');
 63 }
 64 template <class T>
 65 inline void writeln(const T &n)
 66 {
 67     write(n);
 68     puts("");
 69 }
 70 int vis[26];
 71 int main(int argc, char const *argv[])
 72 {
 73 #ifndef ONLINE_JUDGE
 74     freopen("in.txt", "r", stdin);
 75     // freopen("out.txt", "w", stdout);
 76 #endif
 77     cin >> n;
 78     vector<char> res;
 79     res.clear();
 80     while (n--)
 81     {
 82         res.clear();
 83         string cur;
 84         cin >> cur;
 85         int sz = cur.size();
 86         if (sz == 1)
 87         {
 88             cout << cur << "
";
 89             continue;
 90         }
 91         int i = 0;
 92         if (cur[0] != cur[1])
 93         {
 94             i = 1;
 95             res.emplace_back(cur[0]);
 96         }
 97         else
 98             i = 2;
 99 
100         cur += " ";
101         for (; i < sz; i++)
102             if (cur[i] == cur[i + 1])
103                 i++;
104             else
105                 res.emplace_back(cur[i]);
106         sort(res.begin(), res.end());
107         auto cend = unique(res.begin(), res.end());
108         for (auto it = res.begin(); it != cend; it++)
109             cout << *it;
110         cout << "
";
111     }
112     return 0;
113 }

View Code

B. Binary Palindromes

Description

给出n个01串，串与串之间，串内可以任意交换，求最大能构成多少个回文串。

Solution

考场降智，想到了记录01个数以及奇数长度的串个数，但是最后结论出了问题，忘记考虑偶数个奇数长度的串情况

记录所有串中0出现的次数zero，1出现的次数one

记录奇数长度串的个数odd

对于全是偶数串的情况，如果0和1的个数都是偶数则必定可以构成n个回文串，而0和1为奇数则会由一个串不能构成，答案为n-1

对于含有奇数长度串的情况，如果odd是奇数，那么总的字母数一定是奇数，$odd(zero+one)$,

显然我们先拿出odd个数的0或者1来填充字符串中间，子问题就是构造n个偶数长度的回文串，而剩下的必定能满足one和zero都是偶数，答案为n

对于odd为偶数的情况，$even(one+zero)$,显然按照奇数情况考虑，一定能将zero和one全变为偶数，答案为n

  1 #include <algorithm>
  2 #include <cctype>
  3 #include <cmath>
  4 #include <cstdio>
  5 #include <cstdlib>
  6 #include <cstring>
  7 #include <iostream>
  8 #include <map>
  9 #include <numeric>
 10 #include <queue>
 11 #include <set>
 12 #include <stack>
 13 #if __cplusplus >= 201103L
 14 #include <unordered_map>
 15 #include <unordered_set>
 16 #endif
 17 #include <vector>
 18 #define lson rt << 1, l, mid
 19 #define rson rt << 1 | 1, mid + 1, r
 20 #define LONG_LONG_MAX 9223372036854775807LL
 21 #define pblank putchar(' ')
 22 #define ll LL
 23 using namespace std;
 24 typedef long long ll;
 25 typedef long double ld;
 26 typedef unsigned long long ull;
 27 typedef pair<int, int> P;
 28 int n, m, k;
 29 const int maxn = 1e5 + 10;
 30 template <class T>
 31 inline T read()
 32 {
 33     int f = 1;
 34     T ret = 0;
 35     char ch = getchar();
 36     while (!isdigit(ch))
 37     {
 38         if (ch == '-')
 39             f = -1;
 40         ch = getchar();
 41     }
 42     while (isdigit(ch))
 43     {
 44         ret = (ret << 1) + (ret << 3) + ch - '0';
 45         ch = getchar();
 46     }
 47     ret *= f;
 48     return ret;
 49 }
 50 template <class T>
 51 inline void write(T n)
 52 {
 53     if (n < 0)
 54     {
 55         putchar('-');
 56         n = -n;
 57     }
 58     if (n >= 10)
 59     {
 60         write(n / 10);
 61     }
 62     putchar(n % 10 + '0');
 63 }
 64 template <class T>
 65 inline void writeln(const T &n)
 66 {
 67     write(n);
 68     puts("");
 69 }
 70 char s[100][100];
 71 int len[100];
 72 int z[100], o[100];
 73 int main(int argc, char const *argv[])
 74 {
 75 #ifndef ONLINE_JUDGE
 76     freopen("in.txt", "r", stdin);
 77     // freopen("out.txt", "w", stdout);
 78 #endif
 79     int t;
 80     cin >> t;
 81     while (t--)
 82     {
 83         cin >> n;
 84         int zz = 0, oo = 0, o = 0;
 85         for (int i = 0; i < n; i++)
 86         {
 87             string s;
 88             cin >> s;
 89             len[i] = s.size();
 90             if (len[i] & 1)
 91                 ++o;
 92             for (int j = 0; j < len[i]; j++)
 93                 if (s[j] == '0')
 94                     ++zz;
 95                 else
 96                     ++oo;
 97         }
 98         int res = 0;
 99         if (o || zz % 2 == 0)
100             res = n;
101         else
102             res = n - 1;
103         writeln(res);
104     }
105     return 0;
106 }

View Code

C. Minimize The Integer

Description

给出一个长度为n的数字串，奇偶性不同的相邻两数可以交换，求交换后的最小值。

Solution

奇数和奇数不能交换位置，偶数和偶数可以交换位置

也就是说奇/偶数序列的先后关系是一定的,而我们要做的就是将奇偶序列重新合并，类似归并排序的合并两个子序列

  1 #include <algorithm>
  2 #include <cctype>
  3 #include <cmath>
  4 #include <cstdio>
  5 #include <cstdlib>
  6 #include <cstring>
  7 #include <iostream>
  8 #include <map>
  9 #include <numeric>
 10 #include <queue>
 11 #include <set>
 12 #include <stack>
 13 #if __cplusplus >= 201103L
 14 #include <unordered_map>
 15 #include <unordered_set>
 16 #endif
 17 #include <vector>
 18 #define lson rt << 1, l, mid
 19 #define rson rt << 1 | 1, mid + 1, r
 20 #define LONG_LONG_MAX 9223372036854775807LL
 21 #define pblank putchar(' ')
 22 #define ll LL
 23 #define fast ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
 24 using namespace std;
 25 typedef long long ll;
 26 typedef long double ld;
 27 typedef unsigned long long ull;
 28 typedef pair<int, int> P;
 29 int n, m, k;
 30 const int maxn = 1e5 + 10;
 31 template <class T>
 32 inline T read()
 33 {
 34     int f = 1;
 35     T ret = 0;
 36     char ch = getchar();
 37     while (!isdigit(ch))
 38     {
 39         if (ch == '-')
 40             f = -1;
 41         ch = getchar();
 42     }
 43     while (isdigit(ch))
 44     {
 45         ret = (ret << 1) + (ret << 3) + ch - '0';
 46         ch = getchar();
 47     }
 48     ret *= f;
 49     return ret;
 50 }
 51 template <class T>
 52 inline void write(T n)
 53 {
 54     if (n < 0)
 55     {
 56         putchar('-');
 57         n = -n;
 58     }
 59     if (n >= 10)
 60     {
 61         write(n / 10);
 62     }
 63     putchar(n % 10 + '0');
 64 }
 65 template <class T>
 66 inline void writeln(const T &n)
 67 {
 68     write(n);
 69     puts("");
 70 }
 71 void solve(const string &s)
 72 {
 73     string res, odd, even;
 74     res.clear(), odd.clear(), even.clear();
 75     int len = s.size();
 76     for (int i = 0; i < len; i++)
 77         if (s[i] & 1)
 78             odd += s[i];
 79         else
 80             even += s[i];
 81     int sz1 = odd.size(), sz2 = even.size();
 82     int i = 0, j = 0;
 83     while (i < sz1 && j < sz2)
 84     {
 85         if (odd[i] < even[j])
 86             cout << odd[i++];
 87         else
 88             cout << even[j++];
 89     }
 90     while (i < sz1)
 91         cout << odd[i++];
 92     while (j < sz2)
 93         cout << even[j++];
 94     cout << "
";
 95 }
 96 int main(int argc, char const *argv[])
 97 {
 98 #ifndef ONLINE_JUDGE
 99     freopen("in.txt", "r", stdin);
100     // freopen("out.txt", "w", stdout);
101 #endif
102     fast;
103     int t;
104     cin >> t;
105     while (t--)
106     {
107         string s;
108         cin >> s;
109         solve(s);
110     }
111     return 0;
112 }

View Code

D. Salary Changing

Description

给出n个闭区间，一个上限s，在每个区间里取一个数使得这些数的和不大于上限s且其中位数最大。

Solution

二分答案中位数x

先按照左端点排序，将区间划分成三种情况，$l:$严格小于x，$r:$严格大于x，$mid:$包含x

对于第一,二种区间，直接累加区间左值,记录对应种类区间取数的次数$l,r$

如果l或者大于n/2，则中位数不可能是x，fail

我们要的结果应当是$l=r=n/2 and sum leq s$

接下来考虑第三种区间

从左往右遍历，满足区间排序的情况下，如果$l lt n/2，sum+=now.l$，否则如果$r lt n/2$，$sum+=x$

这样的取法满足sum最小且中位数为check值

  1 #include <algorithm>
  2 #include <cctype>
  3 #include <cmath>
  4 #include <cstdio>
  5 #include <cstdlib>
  6 #include <cstring>
  7 #include <iostream>
  8 #include <map>
  9 #include <numeric>
 10 #include <queue>
 11 #include <set>
 12 #include <stack>
 13 #if __cplusplus >= 201103L
 14 #include <unordered_map>
 15 #include <unordered_set>
 16 #endif
 17 #include <vector>
 18 #define lson rt << 1, l, mid
 19 #define rson rt << 1 | 1, mid + 1, r
 20 #define LONG_LONG_MAX 9223372036854775807LL
 21 #define pblank putchar(' ')
 22 #define ll LL
 23 #define fastIO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
 24 using namespace std;
 25 typedef long long ll;
 26 typedef long double ld;
 27 typedef unsigned long long ull;
 28 typedef pair<ll, ll> P;
 29 int n, m, k;
 30 const int maxn = 2e5 + 10;
 31 template <class T>
 32 inline T read()
 33 {
 34     int f = 1;
 35     T ret = 0;
 36     char ch = getchar();
 37     while (!isdigit(ch))
 38     {
 39         if (ch == '-')
 40             f = -1;
 41         ch = getchar();
 42     }
 43     while (isdigit(ch))
 44     {
 45         ret = (ret << 1) + (ret << 3) + ch - '0';
 46         ch = getchar();
 47     }
 48     ret *= f;
 49     return ret;
 50 }
 51 template <class T>
 52 inline void write(T n)
 53 {
 54     if (n < 0)
 55     {
 56         putchar('-');
 57         n = -n;
 58     }
 59     if (n >= 10)
 60     {
 61         write(n / 10);
 62     }
 63     putchar(n % 10 + '0');
 64 }
 65 template <class T>
 66 inline void writeln(const T &n)
 67 {
 68     write(n);
 69     puts("");
 70 }
 71 vector<P> seg;
 72 ll s;
 73 int dep;
 74 int vis[maxn];
 75 inline int check(ll cur)
 76 {
 77     int l = 0, r = 0, mid = 0;
 78     ll sum = 0;
 79     memset(vis, 0, sizeof(int) * (n + 1));
 80     for (int i = 0; i < n; i++)
 81     {
 82         if (seg[i].first <= cur && seg[i].second >= cur)
 83             ++mid;
 84         else if (seg[i].second < cur)
 85         {
 86             vis[i] = 1;
 87             ++l;
 88             sum += seg[i].first;
 89         }
 90         else if (seg[i].first > cur)
 91         {
 92             ++r;
 93             vis[i] = 1;
 94             sum += seg[i].first;
 95         }
 96     }
 97     if (l > dep || r > dep)
 98         return 0;
 99     for (int i = 0; i < n; i++)
100         if (l < dep && !vis[i])
101             ++l, sum += seg[i].first;
102         else if (r < dep && !vis[i])
103             ++r, sum += cur;
104     sum += cur;
105     return sum <= s;
106 }
107 int main(int argc, char const *argv[])
108 {
109 #ifndef ONLINE_JUDGE
110     freopen("in.txt", "r", stdin);
111     // freopen("out.txt", "w", stdout);
112 #endif
113     int t = read<int>();
114     while (t--)
115     {
116         seg.clear();
117         n = read<int>();
118         s = read<ll>();
119         dep = n >> 1;
120         for (int i = 1; i <= n; i++)
121         {
122             ll x = read<ll>(), y = read<ll>();
123             seg.emplace_back(x, y);
124         }
125         sort(seg.begin(), seg.end());
126         ll l = seg[dep].first, r = s;
127         ll res = -1;
128         while (l <= r)
129         {
130             ll mid = l + r >> 1;
131             if (check(mid))
132             {
133                 l = mid + 1;
134                 res = mid;
135             }
136             else
137                 r = mid - 1;
138         }
139         writeln(res);
140     }
141     return 0;
142 }

View Code

熬夜掉分场