Codeforces Round 920 (Div. 3)
Codeforces Round 920 (Div. 3)
A. Square
题意：随机给出正方形在平面坐标系上的四个顶点的坐标，求正方形的面积，正方形边与xy轴平行。
思路：因为正方形与坐标轴平行，所以找出相同的两x或y坐标即可找到一条边的长度，平方就是面积，注意结果返回整型。
AC code：文章来源地址https://www.toymoban.com/news/detail-796795.html
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 m_i mi时刻发送，开机一个单位损失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获得胜利。当轮到一方移动时，当前棋子无法移动游戏宣布平局游戏结束。 双方都以最佳状态进行下棋，请判断比赛结果。
思路：多情况讨论：文章来源：https://www.toymoban.com/news/detail-796795.html
- 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)的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
