Codeforces Round 931 Div 2

发表于 更新于 分类于

A. Too Min Too Max

令\(a\leq b\leq c\leq d\)，手玩以下就能发现等式得出的最大的取值就是\(2\times (c+d-a-b)\)。sort一下取最大和最小的两个数就行了。

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
// Problem: A. Too Min Too Max
// Contest: Codeforces - Codeforces Round 931 (Div. 2)
// URL: https://codeforces.com/contest/1934/problem/0
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

//#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10;
const int inf = 1 << 30;
const long long llinf = 1ll << 60;
const double PI = acos(-1);

#define lowbit(x) (x&-x)
typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<db, db> pdd;
typedef pair<ll, int> pli;

int n, m, k, q;
int a[N];
void work()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
		cin >> a[i];
	sort(a + 1, a + n + 1);
	cout << (a[n] - a[1] + a[n - 1] - a[2]) * 2 << endl;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while (t --> 0)
	{
		work();
	}
}

B. Yet Another Coin Problem

如果n比较小，显然简单dp就能解决。

在n比较大的时候，可以发现，一定有一个数取了大部分。先预处理一定范围内的答案（比如1000），然后枚举这个数，用这个数把n减到1000以内，然后两部分答案相加即可。

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
// Problem: B. Yet Another Coin Problem
// Contest: Codeforces - Codeforces Round 931 (Div. 2)
// URL: https://codeforces.com/contest/1934/problem/B
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

//#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10;
const int inf = 1 << 30;
const long long llinf = 1ll << 60;
const double PI = acos(-1);

#define lowbit(x) (x&-x)
typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<db, db> pdd;
typedef pair<ll, int> pli;

int n, m, k, q;
int f[N];
int a[] = {0, 1, 3, 6, 10, 15};
void work()
{
	cin >> n;
	int ans = inf;
	for (int i = 1; i <= 5; i++)
	{
		int cnt = max(0, (n - 900) / a[i]);
		int now_n = n - cnt * a[i];
		int now = cnt + f[now_n];
		ans = min(ans, now);
	}
	cout << ans << '\n';
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	for (int i = 1; i <= 1000; i++)
	{
		f[i] = inf;
		for (int j = 1; j <= 5; j++)
			if (i >= a[j])
				f[i] = min(f[i], f[i - a[j]] + 1);
	}
	while (t --> 0)
	{
		work();
	}
}

C. Find a Mine

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
// Problem: C. Find a Mine
// Contest: Codeforces - Codeforces Round 931 (Div. 2)
// URL: https://codeforces.com/contest/1934/problem/C
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

//#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10;
const int inf = 1 << 30;
const long long llinf = 1ll << 60;
const double PI = acos(-1);

#define lowbit(x) (x&-x)
typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<db, db> pdd;
typedef pair<ll, int> pli;

#define int long long
int n, m, k, q;
void work()
{
	cin >> n >> m;
	auto query = [&](int x, int y)
	{
		cout << "? " << x << ' ' << y << endl;
	};
	auto answer = [&](int x, int y)
	{
		cout << "! " << x << ' ' << y << endl;
	};
	int dis1, dis2, dis3, dis4;
	query(1, 1);
	cin >> dis1;
	query(n, 1);
	cin >> dis2;
	query(1, m);
	cin >> dis3;
	auto cross = [&](int k1, int b1, int k2, int b2)
	{
		int x = (b2 - b1) / (k1 - k2);
		int y = k1 * x + b1;
		return make_pair(x, y);	
	};
	auto p1 = cross(-1, dis1 + 2, 1, dis2 - n + 1);
	auto p2 = cross(-1, dis1 + 2, 1, m - dis3 - 1);
	if (1 <= p1.first && p1.first <= n && 1 <= p1.second && p1.second <= m)
	{
		query(p1.first, p1.second);
		cin >> dis4;
		if (dis4 == 0)
			answer(p1.first, p1.second);
		else
			answer(p2.first, p2.second);
	}
	else
		answer(p2.first, p2.second);
	
}
main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while (t --> 0)
	{
		work();
	}
}

D1. XOR Break --- Solo Version

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
// Problem: C. Find a Mine
// Contest: Codeforces - Codeforces Round 931 (Div. 2)
// URL: https://codeforces.com/contest/1934/problem/C
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

//#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10;
const int inf = 1 << 30;
const long long llinf = 1ll << 60;
const double PI = acos(-1);

#define lowbit(x) (x&-x)
typedef long long ll;
typedef double db;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<db, db> pdd;
typedef pair<ll, int> pli;

#define int long long
int n, m, k, q;
void work()
{
	cin >> n >> m;
	auto query = [&](int x, int y)
	{
		cout << "? " << x << ' ' << y << endl;
	};
	auto answer = [&](int x, int y)
	{
		cout << "! " << x << ' ' << y << endl;
	};
	int dis1, dis2, dis3, dis4;
	query(1, 1);
	cin >> dis1;
	query(n, 1);
	cin >> dis2;
	query(1, m);
	cin >> dis3;
	auto cross = [&](int k1, int b1, int k2, int b2)
	{
		int x = (b2 - b1) / (k1 - k2);
		int y = k1 * x + b1;
		return make_pair(x, y);	
	};
	auto p1 = cross(-1, dis1 + 2, 1, dis2 - n + 1);
	auto p2 = cross(-1, dis1 + 2, 1, m - dis3 - 1);
	if (1 <= p1.first && p1.first <= n && 1 <= p1.second && p1.second <= m)
	{
		query(p1.first, p1.second);
		cin >> dis4;
		if (dis4 == 0)
			answer(p1.first, p1.second);
		else
			answer(p2.first, p2.second);
	}
	else
		answer(p2.first, p2.second);
	
}
main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin >> t;
	while (t --> 0)
	{
		work();
	}
}