Fork me on GitHub

Educational Codeforces Round 75题解

意外感觉还挺友善的?

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
#include<bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int T;
cin >> T;
while ( T-- ) {
string s;
cin >> s;
int len = s.size ();
map < char , bool > ans;
char las = '.';
int num = 0;
for ( int i = 0 ; i <= len ; i++ ){
if ( las != s[i] ) {
if ( num % 2 == 1 )
ans[las] = 1;
las = s[i];
num = 1;
}
else
num++;
}
for ( int i = ( int ) 'a' ; i <= ( int ) 'z' ; i++ )
if ( ans[(char)i] == 1 )
cout << ( char ) i;
cout << endl;
}
return 0;
}//

Binary Palindromes

思路

发现如果可以根据题目中给的条件来交换的话,那么原问题可以等价为给你若干个$1$和$0$,然后能对于某些给定的长度,最多能拼出多少回文串.
发现如果我们要构造串的话,那么在前$len/i$(向下取整)个位置,我们不用考虑什么其他的条件,只需要每次选择一个剩余数量大的然后$-2$即可.
然后我们发现如果我们要构造的串的长度为奇数的话,中间的那个用什么是个问题,我们考虑一下,因为我们在构造过程的第一步中要拿出两个来构造,那么如果剩余数量是奇数一定会比剩余数量是偶数更劣.
而奇数$-1=$偶数,所以如果有剩余个数是奇数的话,我们拿出一个奇数的来$-1$,否则选择一个剩余数量多的构造.

代码

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
#include <bits/stdc++.h>
using namespace std;
int len[55];
int main(){
ios :: sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int T;
cin >> T;
while ( T-- ) {
memset ( len , 0 , sizeof ( len ) );
int NumZ = 0 , NumO = 0;
int n;
cin >> n;
for ( int i = 1 ; i <= n ; i++ ) {
string s;
cin>>s;
len[i] = s.size();
for ( int j = 0 ; j < len[i] ; j++ )
if ( s[j] == '0' )
NumZ++;
else
NumO++;
}
sort ( len + 1 , len + 1 + n );
int ans = 0;
for ( int i = 1 ; i <= n ; i++ ) {
for ( int j = 1 ; j <= len[i] / 2 ; j++ ) {
if ( NumO > NumZ )
NumO -= 2;
else
NumZ -= 2;
}
if ( len[i] % 2 == 1 )
if ( NumO >= 1 && NumO % 2 == 1 )
NumO--;
else if ( NumZ >= 1 && NumZ % 2 == 1 )
NumZ--;
else {
if ( NumO > NumZ )
NumO -= 1;
else
NumZ -= 1;
}
if ( NumZ >= 0 && NumO >= 0 )
ans++;
}
cout << ans << endl;
}
return 0;
}

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
#include<bits/stdc++.h>
using namespace std;
string s;
int main ( void ) {
ios :: sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int T;
cin >> T;
while ( T-- ) {
cin >> s;
int len = s.size ();
queue < int > qu[2];
for ( int i = 0 ; i < len ; i++ )
if ( ( ( int ) s[i] - '0' ) % 2 == 0 )
qu[0].push ( ( int ) s[i] - '0' );
else
qu[1].push ( ( int ) s[i] - '0' );
qu[0].push ( 11 );
qu[1].push ( 11 );
for ( int i = 1 ; i <= len ; i++ ) {
if ( qu[0].front () < qu[1].front () ) {
cout << qu[0].front ();
qu[0].pop ();
}
else if ( qu[0].front () > qu[1].front () ) {
cout << qu[1].front ();
qu[1].pop ();
}
}
cout << endl;
}
return 0;
}

Salary Changing

思路

发现可以二分这个$mid$,然后我们考虑怎么$check$.
对于某个区间$[l,r]$,如果$r>=mid$,那么说明在这个区间中我们可以取到$mid$.
然后我们把能取到$mid$的区间全部取到$mid$,发现如果大于$mid$的区间刚好为$(n+1)/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
53
54
55
56
57
58
59

#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>
using namespace std;

const int INF = 1e9 + 5;

struct Node {
int L, R;
bool operator<(const Node &other) const {
return L < other.L;
}
};

int N, H;
long long S;
vector<Node> v;

bool possible(int median) {
long long sum = 0;
for (Node &s : v)
sum += s.L;
int count = 0;
for (int i = N - 1; i >= 0 && count < H; i--)
if (v[i].R >= median) {
sum += max(median - v[i].L, 0);
count++;
}
return count == H && sum <= S;
}

int main() {
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int T;
cin >> T;
while (T--) {
cin >> N >> S;
H = (N + 1) / 2;
v.resize(N);
for ( Node &s : v )
cin >> s.L >> s.R;
sort ( v.begin() , v.end () );
int l = 0, r = INF , ans;
while ( l <= r ) {
int mid = ( l + r ) / 2;
if ( possible ( mid ) ) {
ans = mid;
l = mid + 1;
}
else
r = mid - 1;
}
cout << ans << '\n';
}
return 0;
}
因为知道了自己是多么的菜,所以才要更加努力去追求那个永远也不可能实现的梦想

本文标题:Educational Codeforces Round 75题解

文章作者:KRrrrrrrrr

发布时间:2019年10月25日 - 11:10

最后更新:2019年10月25日 - 16:10

原始链接:http://krrrr.xyz/2019/10/25/Edu75/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。