AtCoder ZONe Energy Programming Contest 题解_atcoder f - encounter and farewell

ZONe Energy Programming Contest

A - UFO Invasion

太简单了。

#include <cstdio>
char ch[10] = { 'Z', 'O', 'N', 'e' };
char s[20];

int main() {
	scanf( "%s", s );
	int tot = 0, idx = 0;
	for( int i = 0;i < 12;i ++ ) {
		if( s[i] == ch[idx] ) {
			idx ++;
			if( idx == 4 ) {
				tot ++;
				idx = 0;
			}else;
		} 
		else 
			idx = ( s[i] == ch[0] );
	}
	printf( "%d", tot );
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

B - Sign of Friendship

就是斜率问题。

#include <cstdio>
#include <iostream>
using namespace std;
#define maxn 105
double d[maxn], h[maxn];
int n;
double D, H;

int main() {
	scanf( "%d %lf %lf", &n, &D, &H );
	for( int i = 1;i <= n;i ++ )
		scanf( "%lf %lf", &d[i], &h[i] );
	double ans = 0;
	for( int i = 1;i <= n;i ++ )
		ans = max( ans, H - D * ( ( H - h[i] ) / ( D - d[i] ) ) );
	printf( "%f\n", ans );
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

C - MAD TEAM

二分最后的答案，利用二进制

如果第$i$个的第$j$个属性大于答案，设为$1$，否则为$0$

最后相当于找三个二进制串或起来填满了二进制五位$2^5-1=31$

#include <cstdio>
#include <set>
using namespace std;
#define maxn 3005
set < int > st;
int n;
int p[maxn][5];

bool check( int x ) {
	st.clear();
	for( int i = 1;i <= n;i ++ ) {
		int t = 0;
		for( int j = 0;j < 5;j ++ ) {
			t <<= 1;
			t += ( p[i][j] >= x );
		}
		st.insert( t );
	}
	for( set < int > :: iterator i = st.begin();i != st.end();i ++ )
		for( set < int > :: iterator j = st.begin();j != st.end();j ++ )
			for( set < int > :: iterator k = st.begin();k != st.end();k ++ )
				if( ( (*i) | (*j) | (*k) ) == 31 ) return 1;
	return 0;
}
 
int main() {
	scanf( "%d", &n );
	for( int i = 1;i <= n;i ++ )
		scanf( "%d %d %d %d %d", &p[i][0], &p[i][1], &p[i][2], &p[i][3], &p[i][4] );
	int l = 0, r = 1e9, ans;
	while( l <= r ) {
		int mid = ( l + r ) >> 1;
		if( check( mid ) ) ans = mid, l = mid + 1;
		else r = mid - 1;
	}
	printf( "%d\n", ans );
	return 0;
}
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

D - Message from Aliens

考虑以R作为分界点，不妨改写原串1R2R3R4...(1,2,3,4代表一个整字符串，可以为空)

定义$\overline{1}$ 表示翻转字符串1

手玩一下会发现，答案的长相只与R个数的奇偶性有关

• 个数为奇数，$\overline{3}\overline{1}24$

  奇数串翻转从大到小，偶数串从小到大

• 个数为偶数，$\overline{4}\overline{2}135$

  偶数串翻转从大到小，奇数串从小到大

定义一个整体翻转标记$flag$

既可以加在前面又可以加在后面的操作用deque实现

最后连续相同的字符需要删掉。就进行判断，如果即将要入队的字符与已加入的最后一个相同就都扔掉，再定义一个队列操作即可

#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
#define maxn 500005
deque < char > q, ans;
char s[maxn];

int main() {
	scanf( "%s", s );
	int len = strlen( s ); bool flag = 0;
	for( int i = 0;i < len;i ++ ) {
		if( s[i] == 'R' ) flag ^= 1;
		else
			if( flag ) q.push_front( s[i] );
			else q.push_back( s[i] );
	}
	if( flag ) reverse( q.begin(), q.end() );
	while( ! q.empty() ) {
		if( ! ans.empty() && ans.back() == q.front() ) q.pop_front(), ans.pop_back();
		else ans.push_back( q.front() ), q.pop_front();
	}
	while( ! ans.empty() ) printf( "%c", ans.front() ), ans.pop_front();
	return 0;
}
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

E - Sneaking

建图跑最短路

特殊情况是点可以无限往上飞，这导致边数过大，且$+1$非常不方便

建虚点$i^{\prime }$，$i-i^{\prime }\to 1,i^{\prime }-i\to 0,i^{\prime }-(i-1{)}^{\prime }\to 1$

#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
using namespace std;
#define maxn 505
struct node {
	int v, w;
	node(){}
	node( int V, int W ) {
		v = V, w = W;
	}
	bool operator < ( node t ) const {
		return w > t.w;
	}
};
priority_queue < node > q;
vector < node > G[maxn * maxn * 2];
int n, m;
int A[maxn][maxn], B[maxn][maxn];
int dp[maxn * maxn * 2];

void addedge( int u, int v, int w ) {
	G[u].push_back( node( v, w ) );
}

int id( int i, int j ) {
	return ( i - 1 ) * m + j;
}

int main() {
	scanf( "%d %d", &n, &m );
	for( int i = 1;i <= n;i ++ )
		for( int j = 1;j < m;j ++ )
			scanf( "%d", &A[i][j] );
	for( int i = 1;i < n;i ++ )
		for( int j = 1;j <= m;j ++ )
			scanf( "%d", &B[i][j] );
	for( int i = 1;i <= n;i ++ )
		for( int j = 1;j <= m;j ++ ) {
			addedge( id( i, j ), id( i, j ) + n * m, 1 );
			addedge( id( i, j ) + n * m, id( i, j ), 0 );
			if( i > 1 ) addedge( id( i, j ) + n * m, id( i - 1, j ) + n * m, 1 );
			if( i < n ) addedge( id( i, j ), id( i + 1, j ), B[i][j] );
			if( j > 1 ) addedge( id( i, j ), id( i, j - 1 ), A[i][j - 1] );
			if( j < m ) addedge( id( i, j ), id( i, j + 1 ), A[i][j] );
		}
	memset( dp, 0x7f, sizeof( dp ) );
	dp[1] = 0;
	q.push( node( id( 1, 1 ), 0 ) );
	while( ! q.empty() ) {
		node t = q.top(); q.pop();
		int u = t.v, w = t.w;
		if( u == n * m ) return ! printf( "%d\n", w );
		for( int i = 0;i < G[u].size();i ++ ) {
			int v = G[u][i].v, cost = G[u][i].w;
			if( dp[v] > w + cost ) {
				dp[v] = w + cost;
				q.push( node( v, dp[v] ) );
			}
		}
	}
	return 0;
}
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

F - Encounter and Farewell

$S$为被禁止边权集，其补集为$T$，$a\to b$相当于异或若干个$T$内元素，此乃线性基也

有解情况是$[1,N)$满秩

#include <cmath>
#include <cstdio>
using namespace std;
#define maxn 262200
int N, M, n;
int id[maxn], A[maxn], f[maxn];
bool flag[maxn];

int find( int x ) {
	return x == f[x] ? x : f[x] = find( f[x] );
}

void unionSet( int u, int v ) {
	int fu = find( u ), fv = find( v );
	f[fv] = fu;
}

int main() {
	scanf( "%d %d", &N, &M );
	while( ( 1 << n ) != N ) n ++;
	n --;
	for( int i = 1, x;i <= M;i ++ )
		scanf( "%d", &x ), flag[x] = 1;
	for( int i = 1;i < N;i ++ ) {
		if( flag[i] ) continue;
		int x = i;
		for( int j = n;~ j && x;j -- ) {
			if( x >> j & 1 ) {
				if( ! A[j] ) A[j] = x, id[j] = i;
				x ^= A[j];
			}		
		}
	}
	for( int i = 0;i <= n;i ++ )
		if( ! id[i] ) return ! printf( "-1\n" );
	for( int i = 0;i < N;i ++ ) f[i] = i;
	for( int i = 0;i < N;i ++ )
		for( int j = 0;j <= n;j ++ )
			if( find( i ) != find( i ^ id[j] ) ) {
				unionSet( i, i ^ id[j] );
				printf( "%d %d\n", i, i ^ id[j] );
			} else;
	return 0;
} 
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