Fork me on GitHub

Educational Codeforces Round 73题解

qwq

A.2048 Game

我们发现,我们可以忽略掉$2048$以上的数,剩下的数开桶统计然后贪心即可.

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,a,b) for(rint i=a;i<=b;i++)
#define D(i,a,b) for(rint i=a;i>=b;i--)

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 = 105;

int n;
ll num[N];
int used[2050];

int main ( void ) {
int T = _read ();
while ( T-- ) {
memset ( used , 0 , sizeof ( used ) );
n = _read ();
F ( i , 1 , n ) {
num[i] = _read ();
if ( num[i] <= 2048 )
used[num[i]]++;
}
if ( used[2048] ) {
puts ( "YES" );
continue;
}
for ( int i = 1 ; i <= 1024 ; i *= 2 )
used[i * 2] += ( used[i] / 2 );
if ( used[2048] )
puts ( "YES" );
else
puts ( "NO" );
}
return 0;
}

B.Knights

我们贪心的考虑一下,如果我们现在这个位置的骑士,在它能移动的八个方向上,都会碰到其他的骑士,那么这个位置对答案的贡献一定是最优的.

结合样例,我们可以发现这样一种构造方法,我们从点$(1,1)$开始进行一次$bfs$,然后按照骑士的移动方法,每次更新一层,然后把这一层的骑士染色成和现在的骑士颜色不一样的颜色.

对于剩下的,那么可以证明没有任何点能跳到这个点,所以随便什么颜色都可以.

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
#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 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--)

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;}

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

int n;
char mp[105][105];

const int dx[] = { 0 , 1 , 1 , -1 , -1 , 2 , 2 , -2 , - 2 };
const int dy[] = { 0 , 2 , -2 , 2 , -2 , 1 , -1 , 1 , -1 };

void dfs ( int x , int y , char col ) {
mp[x][y] = col;
for ( int i = 1 ; i <= 8 ; i++ ) {
int xx = x + dx[i];
int yy = y + dy[i];
if ( xx >= 1 && xx <= n && yy >= 1 && yy <= n && mp[xx][yy] != 'W' && mp[xx][yy] != 'B' )
dfs ( xx , yy , col == 'W' ? 'B' : 'W' );
}
return;
}

int main ( void ) {
n = _read ();
dfs ( 1 , 1 , 'W' );
bool flag = 1;
for ( int i = 1 ; i <= n ; i++ ) {
for ( int j = 1 ; j <= n ; j++ ) {
if ( mp[i][j] == 'W' || mp[i][j] == 'B' )
printf ("%c",mp[i][j]);
else {
printf ("%c" , flag?'B':'W');
flag ^= 1;
}
}
puts("");
}
return 0;
}
// Main Code

C.Perfect Team

一个直观的感觉就是你从$c,m$中取一个$Min$,然后我们会发现可能人数凑不够$Min*3$,所以我们判断一下$min(Min,sum/3)$就是答案了.

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 <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--)

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;}

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

int n;
int c , m , x;

int main ( void ) {
int T = _read ();
while ( T-- ) {
read ( c , m , x );
int mins = min ( c , m );
int sums = c + m + x;
printf ( "%d\n" , min ( mins , sums / 3 ) );
}

return 0;
}
// Main Code

D.Make The Fence Great Again

毒瘤出题人一个DP数据范围开3e5

看到$3e5$的数据范围,第一反应就是贪心,但是发现貌似不怎么可做?
然后开始考虑$DP$,发现如果$i$这个点被升高了的话,貌似对后边的点是有影响的,有后效性,怎么办?
我们经过观察可知,如果一个点要升高,那么它最多升高两次,所以我们可以设$f_{i,j}$表示现在是第$i$个位置,其中$i$这个位置升高了$j$次.

转移的话很显然,我们枚举一个最小的$f_{i-1,k}$并且要保证$fence_{i-1}.high+k$不等于$fence_i.high+j$然后转移就好了.

时间复杂度的话是$O(n*16)$
硬核O(nlogn)

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
#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 int 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--)

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 = 3e5 + 10;

int n , idx;
struct Node {
int hi;
int vi;
}fence[N];
int f[N][5];

signed main ( void ) {
int T = _read ();
while ( T-- ) {
n = _read ();
for ( int i = 1 ; i <= n ; i++ ) {
read ( fence[i].hi , fence[i].vi );
for ( int j = 0 ; j <= 4 ; j++ )
f[i][j] = 1e17;
}
for ( int i = 1 ; i <= n ; i++ ) {
for ( int j = 0 ; j <= 4 ; j++ ) {
for ( int k = 0 ; k <= 4 ; k++ ) {
if ( fence[i].hi + j == fence[i - 1].hi + k )
continue;
f[i][j] = min ( f[i][j] , f[i - 1][k] );
}
if ( f[i][j] == 1e17 )
continue;
f[i][j] += 1ll * j * fence[i].vi;
}
}
int ans = 1e17;
for ( int i = 0 ; i <= 4 ; i++ )
ans = min ( ans , f[n][i] );
writeln ( ans );
}
return 0;
}
// Main Code
因为知道了自己是多么的菜,所以才要更加努力去追求那个永远也不可能实现的梦想

本文标题:Educational Codeforces Round 73题解

文章作者:KRrrrrrrrr

发布时间:2019年09月20日 - 17:09

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

原始链接:http://krrrr.xyz/2019/09/20/CF题解解/

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