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 题解 解题思路 横向位置关系分析
初始横向距离 : 首先计算Alice和Bob棋子在横向上的初始距离$d = |y_a - y_b|$。
横向移动可能性 :
在每一次移动中,玩家可以选择横向不动或者横向移动(左或右一格)。
这意味着,如果两个棋子的横向距离是$d$,那么在下一次移动后,横向距离可能变为$d-1$,$d$或$d+1$。
考虑棋盘边界 :
需要注意的是,棋子的横向移动不能超出棋盘的边界。
如果棋子已经在最左侧或最右侧列,则它不能继续向该方向移动。
如何利用横向位置关系预测游戏结果
奇偶性分析 :
观察两个棋子的行间距$H = x_b - x_a$。如果$H$是奇数,Alice不败,反之Bob不败
如果$H$是奇数 :
分析横向移动后,他们是否可能在同一列相遇。
如果在Alice的某次移动后,两个棋子的横向距离可以变为0,则Alice获胜。
如果$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 ; }