Codeforces Round 920 (Div. 3)

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

Codeforces Round 920 (Div. 3)

Codeforces Round 920 (Div. 3)

A. Square

题意：随机给出正方形在平面坐标系上的四个顶点的坐标，求正方形的面积，正方形边与xy轴平行。

思路：因为正方形与坐标轴平行，所以找出相同的两x或y坐标即可找到一条边的长度，平方就是面积，注意结果返回整型。

AC code：

void solve() {PII q[100];for (int i = 1; i <= 4; i ++) {int x, y; cin >> x >> y;q[i] = {x, y};}sort(q + 1, q + 4 + 1);cout << (q[1].second - q[2].second) * (q[1].second - q[2].second) << endl;}

B. Arranging Cats

题意：给出两个01字符串，可以对第一个字符串进行0变1,1变0,10交换这样的三种操作，最少多少次操作可以让两字符串相等。

思路：

• 找到两字符串中字符‘1’的数量，以及两字符串中不同字符的数量；
• 若1的数量相同，则只需要交换操作即可，最小操作数为不同字符的数量now/2；
• 若1的数量不相同，则需要先将两字符串的字符差值进行操作，再用不同字符数减去该差值除2；

AC code：

void solve() {cin >> n;string s, f; cin >> s >> f;if (s == f) {cout << 0 << endl;return;}int cnts = 0, cntf = 0;for (int i = 0; i < n; i ++) {cnts += (s[i] == '1');cntf += (f[i] == '1');}int now = 0;for (int i = 0; i < n; i ++) {if(s[i] != f[i]) now ++;}if (cnts == cntf) {cout << now / 2 << endl;return;}cout << abs(cnts - cntf) + (now - abs(cnts - cntf)) / 2 << endl;
}

C. Sending Messages

题意：现在需要用一部剩余f单位电的时间发n条信息，每条信息需在$m_i$时刻发送，开机一个单位损失a单位电量，关机稍后打开损失b单位电量，电量为0不能发信息，是否可以将所有信息发完。

思路：从前往后跑一遍，比较关机与待机的耗电量，最小化每次发信息间隔的耗电量。

AC code：

void solve() {cin >> n >> f >> a >> b;for (int i = 0; i < n; i ++)cin >> m[i];int now = 0;for (int i = 0; i < n; i ++) {int cnt = m[i] - now;if (cnt * a > b) f -= b;else f -= cnt * a;now = m[i];}if (f <= 0) {cout << "NO" << endl;} else {cout << "YES" << endl;}
}

D. Very Different Array

题意：给出长度为n的数组a，现在从长度为m的数组b中选择n个数字组成数组c，使得数组c与数组a对应位置的总差值最大。

思路：不是最大对最小就是最佳答案，差值取绝对值，正负均可，这里用的是对排序后的数组ab进行双指针判断。

AC code：

void solve() {cin >> n >> m;for (int i = 0; i < n; i ++) cin >> a[i];for (int i = 0; i < m; i ++) cin >> b[i];sort(a, a + n);sort(b, b + m, greater<int>());int ans = 0, pos = 0;int la = 0, ra = n - 1, lb = 0, rb = m - 1;while (pos < n) {int x = abs(a[la] - b[lb]), y = abs(a[ra] - b[rb]);if (x > y) {ans += x;la ++, lb ++;} else {ans += y;ra --, rb --;}pos ++;}cout << ans << endl;
}

E. Eat the Chip

题意：

A和B正在一个有h行w列的棋盘上下棋，保证两个棋子不会重合，现在双方轮流下棋，由A开始。

当轮到A下棋时，A，可以将棋子向下，向右或向左斜单元格移动一格。当轮到陛下期时必可以将其子向上向右或向左斜单元格移动一格，不允许移动超出棋盘边界。

当A将自己的棋子移动到B当前所占据的坐标上时，A获得胜利。当B将自己的妻子移动到a当前所占据的坐标时，B获得胜利。当轮到一方移动时，当前棋子无法移动游戏宣布平局游戏结束。 双方都以最佳状态进行下棋，请判断比赛结果。

思路：多情况讨论：

• A的行数只能增加，B只能减小，当xa >= xb时一定平局；
• AB每次移动一定会缩短相对行距，若列距大于行距，双方在相遇前就会错过，一定平局；
• 然后根据双方行距的奇偶性判断，当行距为奇数时：
  • 若列距<=1，A胜，一步制胜；
  • 只有当A的列坐标与边界的距离<=行距的一半时，A胜，该情况下，在AB行距减小时，A可以将B逼至边界，然后制胜；
  • 若A不能将B绝杀，则一定平局；
• 当行距为偶数时：
  • AB列距为0，无论A怎么移动，在第二步B均能制胜；
  • 只有当B的列坐标与边界的距离<=行距的一半时，B胜，该情况下，在AB行距减小时，B可以将A逼至边界，然后制胜；
  • 若B不能将A绝杀，则一定平局；

AC code：

void solve() {int h, w, xa, ya, xb, yb;cin >> h >> w >> xa >> ya >> xb >> yb;if (xa >= xb) {cout << "Draw" << endl;return;}int cnt = xb - xa;int now = abs(ya - yb);if (now > cnt) {cout << "Draw" << endl;return;}if(cnt % 2) {if (now <= 1) {cout << "Alice" << endl;} else if (ya > yb && ya - 1 <= cnt / 2 + 1) {cout << "Alice" << endl;} else if (ya < yb && w - ya <= cnt / 2 + 1) {cout << "Alice" << endl;} else {cout << "Draw" << endl;}} else {if (ya == yb) {cout << "Bob" << endl;} else if (ya < yb && yb - 1 <= cnt / 2) {cout << "Bob" << endl;} else if (ya > yb && w - yb <= cnt / 2) {cout << "Bob" << endl;} else {cout << "Draw" << endl;}}
}

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

---