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;
        }
    }
}