Fork me on GitHub

CodeForces round585题解

1ffe06568610857a04dd1a5cea3a2936.jpg

A.

傻逼题,暴力枚举即可(我也就只会傻逼题了)

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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
#include <map>
#include <set>
#include <cmath>
#include <cctype>
#include <ctime>
#include <vector>
#include <cstdlib>
#include <stack>
#define ll long long
#define pll std::pair<int,int>
#define MP std::make_pair
#define fi first
#define se second
#define oo 2147483647
#define PI 3.141592653590
#define rint register int
#define F(i,a,b) for(rint i=a;i<=b;i++)
#define D(i,a,b) for(rint i=a;i>=b;i--)
#define G(i,a,b,c) for(rint a=head[b];a;a=c[a].next)

inline int _read () {int s = 0 , w = 1;char ch = getchar ();while ( ch > '9' || ch < '0' ) { if ( ch == '-' ) w = -1; ch = getchar ();}while ( ch >= '0' && ch <= '9' ) { s = s * 10 + ch - '0'; ch = getchar ();}return s * w;}
template < class T > inline void read ( T &x ) {T s = 0 , w = 1;char ch = getchar ();while ( ch > '9' || ch < '0' ) { if ( ch == '-' ) w = -1; ch = getchar ();}while ( ch >= '0' && ch <= '9' ) { s = s * 10 + ch - '0'; ch = getchar ();}x = s * w;return;}
template < class T , typename ...Argc > inline void read ( T &x , Argc &...Args ) {read ( x );read ( Args... );return;}
template < class T > inline T max ( T x , T y ) {return x > y ? x : y;}
template < class T > inline T min ( T x , T y ) {return x < y ? x : y;}
template < class T > inline void abs ( T x ) {return x > 0 ? x : -x;}
template < typename T > void write ( T x ) {if ( x < 0 ) x = -x , putchar ( '-' );if ( x > 9 ) write ( x / 10 );putchar ( x % 10 + 48 );return;}
template < typename T > void writeln ( T x ) {write ( x ); printf ("\n"); }
template < class T > inline T gcd ( T x , T y ) {if ( x < y ) swap ( x , y );if ( !y ) return x;return gcd ( y , x % y );}
template < class T > inline T ksm ( T x , T y , T Mod ) {T tmp = 1;while ( y ) {if ( y % 2 == 1 ) tmp = ( tmp * x % Mod );x = ( x * x ) % Mod;y >>= 1;}return tmp;}

/**********************************************************************************************************************************************************************************************************************************************************************/

const int N = 10005;

int n , a1 , a2 , k1 , k2 , idx;
int num[N];

inline bool cmp1 ( int x , int y ) {
return x > y;
}
inline bool cmp2 ( int x , int y ) {
return x < y;
}

int main ( void ) {

read ( a1 , a2 , k1 , k2 , n );

for ( int i = 1 ; i <= a1 ; i++ )
num[++idx] = k1;
for ( int i = 1 ; i <= a2 ; i++ )
num[++idx] = k2;
std :: sort ( num + 1 , num + 1 + idx , cmp1 );
int ans = 0;
int tmp = n;
for ( int i = 1 ; i <= idx ; i++ )
if ( tmp < num[i] ) {
tmp = 0;
break;
}
else
tmp -= num[i] - 1;

if ( tmp == 0 )
printf ( "%d " , ans );
else
printf ( "%d " , tmp );
std :: sort ( num + 1 , num + 1 + idx , cmp2 );
ans = 0 , tmp = n;
for ( int i = 1 ; i <= idx ; i++ )
if ( tmp < num[i] )
break;
else {
ans ++;
tmp -= num[i];
}
printf ( "%d\n" , ans );
return 0;
}
// Main Code

B.

分从后往前现在的数的正负性讨论即可,负负得正.

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
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
#include <map>
#include <set>
#include <cmath>
#include <cctype>
#include <ctime>
#include <vector>
#include <cstdlib>
#include <stack>
#define ll long long
#define pll std::pair<int,int>
#define MP std::make_pair
#define fi first
#define se second
#define oo 2147483647
#define PI 3.141592653590
#define rint register int
#define F(i,num,b) for(rint i=num;i<=b;i++)
#define D(i,num,b) for(rint i=num;i>=b;i--)
#define G(i,num,b,c) for(rint num=head[b];num;num=c[num].next)

inline int _read () {int s = 0 , w = 1;char ch = getchar ();while ( ch > '9' || ch < '0' ) { if ( ch == '-' ) w = -1; ch = getchar ();}while ( ch >= '0' && ch <= '9' ) { s = s * 10 + ch - '0'; ch = getchar ();}return s * w;}
template < class T > inline void read ( T &x ) {T s = 0 , w = 1;char ch = getchar ();while ( ch > '9' || ch < '0' ) { if ( ch == '-' ) w = -1; ch = getchar ();}while ( ch >= '0' && ch <= '9' ) { s = s * 10 + ch - '0'; ch = getchar ();}x = s * w;return;}
template < class T , typename ...Argc > inline void read ( T &x , Argc &...Args ) {read ( x );read ( Args... );return;}
template < class T > inline T max ( T x , T y ) {return x > y ? x : y;}
template < class T > inline T min ( T x , T y ) {return x < y ? x : y;}
template < class T > inline void abs ( T x ) {return x > 0 ? x : -x;}
template < typename T > void write ( T x ) {if ( x < 0 ) x = -x , putchar ( '-' );if ( x > 9 ) write ( x / 10 );putchar ( x % 10 + 48 );return;}
template < typename T > void writeln ( T x ) {write ( x ); printf ("\n"); }
template < class T > inline T gcd ( T x , T y ) {if ( x < y ) swap ( x , y );if ( !y ) return x;return gcd ( y , x % y );}
template < class T > inline T ksm ( T x , T y , T Mod ) {T tmp = 1;while ( y ) {if ( y % 2 == 1 ) tmp = ( tmp * x % Mod );x = ( x * x ) % Mod;y >>= 1;}return tmp;}

/**********************************************************************************************************************************************************************************************************************************************************************/

const int N = 4e5 + 10;

int n;
ll num[N] , s[N];
ll tai,fro;
ll odd,uodd;

int main ( void ) {
read ( n );
F ( i , 1 , n ) {
num[i] = _read ();
s[i] = s[i - 1] ^ ( num[i] < 0 );
if ( s[i] == 1 ) {
tai += odd;
fro += uodd;
odd++;
fro++;
}
else {
tai += uodd;
fro += odd;
tai++;
uodd++;
}
}
std :: cout << fro << " " << tai << std :: endl;
return 0;
}

C.

发现只有$A$和$B$,两种字符,很容易发现规律.

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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <queue>
#include <map>
#include <set>
#include <cmath>
#include <cctype>
#include <ctime>
#include <vector>
#include <cstdlib>
#include <stack>
#define ll long long
#define pll std::pair<int,int>
#define MP std::make_pair
#define fi first
#define se second
#define oo 2147483647
#define PI 3.141592653590
#define rint register int
#define F(i,num,b) for(rint i=num;i<=b;i++)
#define D(i,num,b) for(rint i=num;i>=b;i--)
#define G(i,num,b,c) for(rint num=head[b];num;num=c[num].next)

inline int _read () {int s = 0 , w = 1;char ch = getchar ();while ( ch > '9' || ch < '0' ) { if ( ch == '-' ) w = -1; ch = getchar ();}while ( ch >= '0' && ch <= '9' ) { s = s * 10 + ch - '0'; ch = getchar ();}return s * w;}
template < class T > inline void read ( T &x ) {T s = 0 , w = 1;char ch = getchar ();while ( ch > '9' || ch < '0' ) { if ( ch == '-' ) w = -1; ch = getchar ();}while ( ch >= '0' && ch <= '9' ) { s = s * 10 + ch - '0'; ch = getchar ();}x = s * w;return;}
template < class T , typename ...Argc > inline void read ( T &x , Argc &...Args ) {read ( x );read ( Args... );return;}
template < class T > inline T max ( T x , T y ) {return x > y ? x : y;}
template < class T > inline T min ( T x , T y ) {return x < y ? x : y;}
template < class T > inline void abs ( T x ) {return x > 0 ? x : -x;}
template < typename T > void write ( T x ) {if ( x < 0 ) x = -x , putchar ( '-' );if ( x > 9 ) write ( x / 10 );putchar ( x % 10 + 48 );return;}
template < typename T > void writeln ( T x ) {write ( x ); printf ("\n"); }
template < class T > inline T gcd ( T x , T y ) {if ( x < y ) swap ( x , y );if ( !y ) return x;return gcd ( y , x % y );}
template < class T > inline T ksm ( T x , T y , T Mod ) {T tmp = 1;while ( y ) {if ( y % 2 == 1 ) tmp = ( tmp * x % Mod );x = ( x * x ) % Mod;y >>= 1;}return tmp;}

/**********************************************************************************************************************************************************************************************************************************************************************/

char s[3][200005];
int n , sum;
int can1,can2,bc;
int cnt1[200005],cnt2[200005];

int main(){

read ( n );
scanf ( "%s%s" , s[1] , s[2] );
for(int i=0;i<n;i++){
if(s[1][i]!=s[2][i]){
if(s[1][i]=='a'){
can1++;
cnt1[can1]=i+1;
}
else{
can2++;
cnt2[can2]=i+1;
}
}
}
if(n%2==1){
puts ( "-1" );
return 0;
}
if(can1%2==1){
sum+=2;
sum+=(n-2)/2;

writeln ( sum );

printf ( "%d %d\n" , cnt1[1] , cnt1[1] );
printf ( "%d %d\n" , cnt1[1] , cnt2[1] );
for(int i=2;i<=can1;i+=2)
printf ( "%d %d\n" , cnt1[i] , cnt1[i + 1] );
for(int i=2;i<=can2;i+=2)
printf ( "%d %d\n" , cnt2[i] , cnt2[i + 1] );
return 0;
}
sum=(can1+can2)/2;
writeln ( sum );
for(int i=1;i<=can1;i+=2)
printf ( "%d %d\n" , cnt1[i] , cnt1[i + 1] );
for(int i=1;i<=can2;i+=2)
printf ( "%d %d\n" , cnt2[i] , cnt2[i + 1] );
return 0;
}
因为知道了自己是多么的菜,所以才要更加努力去追求那个永远也不可能实现的梦想

本文标题:CodeForces round585题解

文章作者:KRrrrrrrrr

发布时间:2019年09月15日 - 18:09

最后更新:2019年10月21日 - 11:10

原始链接:http://krrrr.xyz/2019/09/15/round585题解/

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