Codeforces Round 920 (Div. 3) D、E题解

D. Very Different Array

E. Eat the Chip

D. Very Different Array 题解

解题思路

在这个问题中,我们使用了贪心算法来最大化Vasya数组和Petya数组之间的总差异$D$。

1. 排序

首先对Petya的数组$a_i$和Vasya可选的数字集合$b_i$进行排序,为双指针操作做准备。

2. 双指针策略

使用两个指针,分别指向$a_i$的两端和 $b_i$ 的两端。

3. 贪心选择

  • 在每一步中,计算$a_i$两端与$b_i$两端的差的绝对值。
  • 选择四种可能差值中的最大值,并累加到结果变量$D$中。
  • 相应地移动指针。

4. 重复以上步骤

直到$a_i$中的所有元素都被处理完毕。

通过这个过程,我们每步都选择当前最大的差异,确保了$D$的值尽可能大。最后输出最大总差异$D$。

代码实现

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
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;

const int N = 2e5 + 10;
int a[N];
int b[N];

int main()
{
int _;
cin >> _;
while (_--)
{
int n, m;
cin >> n >> m;
for (int i = 0; i < n; i++)
{
cin >> a[i];
}
sort(a, a + n);
for (int i = 0; i < m; i++)
{
cin >> b[i];
}
sort(b, b + m);
int l = 0, r = m - 1;
int L = 0, R = n - 1;
ll D = 0;
while (L <= R)
{
int l1, l2;
int r1, r2;
l1 = abs(a[L] - b[l]);
l2 = abs(a[L] - b[r]);
r1 = abs(a[R] - b[l]);
r2 = abs(a[R] - b[r]);
if (max(l1, l2) > max(r1, r2))
{
if (l1 > l2)
{
D += l1;
l++;
}
else
{
D += l2;
r--;
}
L++;
}
else
{
if (r1 > r2)
{
D += r1;
l++;
}
else
{
D += r2;
r--;
}
R--;
}
}
cout << D << endl;
}
return 0;
}

E. Eat the Chip

E. Eat the Chip 题解

解题思路

横向位置关系分析

  1. 初始横向距离: 首先计算Alice和Bob棋子在横向上的初始距离$d = |y_a - y_b|$。

  2. 横向移动可能性:

    • 在每一次移动中,玩家可以选择横向不动或者横向移动(左或右一格)。
    • 这意味着,如果两个棋子的横向距离是$d$,那么在下一次移动后,横向距离可能变为$d-1$,$d$或$d+1$。
  3. 考虑棋盘边界:

    • 需要注意的是,棋子的横向移动不能超出棋盘的边界。
    • 如果棋子已经在最左侧或最右侧列,则它不能继续向该方向移动。

如何利用横向位置关系预测游戏结果

  1. 奇偶性分析:

    • 观察两个棋子的行间距$H = x_b - x_a$。如果$H$是奇数,Alice不败,反之Bob不败
  2. 如果$H$是奇数:

    • 分析横向移动后,他们是否可能在同一列相遇。
    • 如果在Alice的某次移动后,两个棋子的横向距离可以变为0,则Alice获胜。
  3. 如果$H$是偶数:

    • 需要分析在这一行相遇时,横向距离是否可以为1。
    • 如果可以,那么Bob有可能获胜,因为他可以在下一个回合将棋子移动到Alice棋子的位置。

代码实现

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
#include <iostream>
#include <cmath>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;

const int N = 2e5 + 10;

int main()
{
int _;
cin >> _;
while (_--)
{
int h, w;
int x1, y1;
int x2, y2;
cin >> h >> w >> x1 >> y1 >> x2 >> y2;
int H = x2 - x1;
bool isDraw = false;
int isAliceWin = false;
if (x2 <= x1 || x1 == h || x2 == 1)
{
isDraw = true;
}
if (H % 2 == 1) //奇数
{
int d1 = H / 2 + 1;
if ((y1 + 1 < y2 && y1 + d1 < w) || (y1 - 1 > y2 && y1 - d1 > 1))
{
isDraw = true;
}
else
{
isAliceWin = true;
}
}
else
{
int d1 = H / 2;
int d2 = H / 2;
if ((y1 < y2 && y2 - d2 > 1) || (y1 > y2) && y2 + d2 < w)
{
isDraw = true;
}
else
{
isAliceWin = false;
}
}
if (isDraw)
{
cout << "Draw" << endl;
}
else if (isAliceWin)
{
cout << "Alice" << endl;
}
else
{
cout << "Bob" << endl;
}
}
return 0;
}