Codeforces Round 931(Div.2) A~D2

本文主要是介绍Codeforces Round 931(Div.2) A~D2，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

A. Too Min Too Max （数学）

题意：

给定长度为$n$的数组$a$，求下列表达式的最大值，$(i,j,k,l)$为不同的索引
$|a_i-a_j|+|a_j-a_k|+|a_k-a_l|+|a_l-a_i|$

分析：

构造出最小-最大 + 最大-次小 + 次小-次大 + 次大-最小的形式。
去掉绝对值之后可以保证为 $2$个最大+$2$个次大-$2$个最小-$2$个次小

代码：

#include <bits/stdc++.h>using namespace std;
const int N = 2e5 + 5;
int a[N];int main() {int t;cin >> t;while (t--) {int n;cin >> n;for (int i = 1; i <= n; i++)cin >> a[i];sort(a + 1, a + 1 + n);cout << a[n] - a[1] + (a[n - 1] - a[1]) + (a[n - 1] - a[2]) + (a[n] - a[2]) << endl;}return 0;
}

B.Yet Another Coin Problem （枚举）

题意：

有$1,3,6,10,15$面额的硬币无数枚，组成$n$元的硬币至少需要多少枚硬币。

分析：

可以发现每种硬币最多出现次数有着限制：面额$1$，最多出现$2$次，面额$3$，最多出现$1$次，面额$6$，最多出现$2$次，面额$10$，最多出现$2$次，面额$15$，没有限制。
枚举每种硬币出现次数即可。

代码：

#include <bits/stdc++.h>using namespace std;int main() {int t;cin >> t;while (t--) {int n;cin >> n;int ans = 1e9;for (int i1 = 0; i1 <= 2; i1++)for (int i3 = 0; i3 <= 1; i3++)for (int i6 = 0; i6 <= 2; i6++)for (int i10 = 0; i10 <= 2; i10++) {int sum = i1 + i3 * 3 + i6 * 6 + i10 * 10;if (sum <= n && (n - sum) % 15 == 0)ans = min(ans, (n - sum) / 15 + i1 + i3 + i6 + i10);}cout << ans << endl;}return 0;
}

C.Find a Mine （交互）

题意：

给定$n\times m$的地图，地图上有两个位置有矿物。每次你需要输入一个坐标$(x,y)$，系统将返回曼哈顿距离最近的矿物的距离。你需要通过最多四次询问，找到其中一个矿物的位置。

分析：

我们首先询问$(1,1),(1,m)$，并假设他们离第一个矿物更近，那么我们就可以解除第一个矿物的坐标，第三次询问用于确认计算结果是否正确。否则询问$(1,n)$，再和$(1,1)$联立解出坐第一个矿物的坐标。

代码：

#include <bits/stdc++.h>using namespace std;
typedef long long LL;int ask(int x, int y) {cout << "? " << x << " " << y << endl;cout.flush();int tmp;cin >> tmp;return tmp;
}int main() {int t;cin >> t;while (t--) {int n, m;cin >> n >> m;int tmp1 = ask(1, 1), tmp2 = ask(1, m),tmp3 = ask(n, 1);if ((tmp1 + tmp3 + 3 - n) > 0 && (tmp1 + tmp3 + 3 - n) % 2 == 0) {int y1 = (tmp1 + tmp3 + 3 - n) / 2, x1 = tmp1 - y1 + 2;if (x1 >= 1 && x1 <= n && y1 >= 1 && y1 <= m) {int q = ask(x1, y1);if (q == 0) {cout << "! " << x1 << " " << y1 << endl;continue;}}}int x1 = (tmp1 + tmp2 + 3 - m) / 2, y1 = tmp1 + 2 - x1;cout << "! " << x1 << " " << y1 << endl;cout.flush();}return 0;
}

D1.XOR Break — Solo Version （位运算）

题意：

给定$x$，每次可选择满足以下条件的$y$：

• $0<y<x$且$x⨁y<x$

令$x$变成$y$或者$x⨁y$，询问是否能够通过最多$63$次操作令$x$变为$m$。请输出操作序列。

分析：

$2$的幂次是无解的，如果是这种情况，直接就是失败。如果两个数最高位相同，可以通过一步操作$x$到$y$。否则最高位一定不同，从最高位往下，如果$x$和$y$第一个不同的位中$y$是$1$是无解的，因为无论如何操作这位都不可能是$1$。否则就可以通过把从高位往下遇到的$x$中的第一个$1$变成从该位往下全是$1$，可以得到一个全是$1$的数字，再通过一步操作就可以变成$y$。

代码：

#include <bits/stdc++.h>using namespace std;
typedef long long LL;LL check(LL x, LL y) {if (y < x && (x ^ y) < x)return 1;LL t = (x ^ y);if (t < x && (x ^ t) < x)return 1;return 0;
}LL pow1(LL x) {return (x & (x - 1)) == 0;
}int main() {int t;cin >> t;while (t--) {LL n, m;cin >> n >> m;if ((n ^ m) < n) {cout << 1 << endl;cout << n << " " << m << " " << endl;continue;}if (pow1(n)) {cout << -1 << endl;continue;}int tmp1 = __lg(n ^ m);int tmp2 = -1;for (int i = tmp1 - 1; i >= 0; i--) {int bit1 = (n >> i & 1);int bit2 = (m >> i & 1);if (bit2 > bit1) {break;} else if (bit1) {tmp2 = i;break;}}if (tmp2 == -1) {cout << -1 << endl;continue;}vector<LL> ans;ans.push_back(n);LL tmp = n;tmp ^= 1LL << tmp1;tmp |= (1LL << (tmp2 + 1)) - 1;ans.push_back(tmp);if (tmp != m) {ans.push_back(m);}for (int i = 0; i + 1 < ans.size(); i++) {assert(check(ans[i], ans[i + 1]));}cout << ans.size() - 1 << endl;for (auto x: ans)cout << x << " ";cout << endl;}return 0;
}

D2.XOR Break — Solo Version （交互）

题意：

给一个数字$n$，两个人轮流操作，

• 当前人选择将$n$拆分成$n=p_1⨁p_2,p_1<n,p_2<n$。无法拆分认为失败

• 另一个人选择将$n$变成$p_1$或者$p_2$

两人各拆分一次算作一次，询问是先手必胜还是后手必胜。你可以选择先后手，并和测试机进行这个游戏，你需要在$63$轮之内获胜。

分析：

首先考虑$n$数位上$1$的个数，如果$1$的个数是偶数，那么选择先手，否则选择后手。如果$1$的个数是偶数，我们可以将其拆成两个奇数给后手，后手只能选择一个奇数拆成奇数加偶数还给先手。先手又从中选择偶数拆成两个奇数。最后无法操作的状态为$1$的个数为$1$。

代码：

#include <bits/stdc++.h>using namespace std;
typedef long long LL;LL get(LL x) {for (LL i = 60; i >= 0; i--) {if ((x >> i) & 1)return i;}
}int cal(LL n) {int res = 0;for (int i = 60; i >= 0; i--) {if ((n >> i) & 1)res++;}return res;
}int main() {int t;cin >> t;while (t--) {LL n, x, y;cin >> n;if (cal(n) & 1) {cout << "second" << endl;cout.flush();while (true) {cin >> x >> y;if (x == 0 && y == 0)break;if (cal(x) % 2 == 0) {LL x1 = (1ll << get(x));cout << x1 << " " << (x ^ x1) << endl;cout.flush();} else {LL y1 = (1ll << get(y));cout << y1 << " " << (y ^ y1) << endl;cout.flush();}}} else {cout << "first" << endl;cout.flush();LL n1 = (1ll << get(n));cout << n1 << " " << (n ^ n1) << endl;cout.flush();while (true) {cin >> x >> y;if (x == 0 && y == 0)break;if (cal(x) % 2 == 0) {LL x1 = (1ll << get(x));cout << x1 << " " << (x ^ x1) << endl;cout.flush();} else {LL y1 = (1ll << get(y));cout << y1 << " " << (y ^ y1) << endl;cout.flush();}}}}return 0;
}

赛后交流

在比赛结束后，会在交流群中给出比赛题解，同学们可以在赛后查看题解进行补题。

群号： 704572101，赛后大家可以一起交流做题思路，分享做题技巧，欢迎大家的加入。

这篇关于Codeforces Round 931(Div.2) A~D2的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---