Codeforces Round 922 (Div. 2)

Codeforces Round 922 (Div. 2)

Codeforces Round 922 (Div. 2)

A. Brick Wall

题意：在n*m的墙内填1Xk的砖，k最小为2，墙得填满不留边，墙的稳定性为水平砖-垂直砖，最大化稳定性。

思路：最大化稳定性即水平砖尽量多的用，垂直砖少用，那就k取最小，若m为奇数说明得竖着单独来一排。

AC code：

void solve() {
    cin >> n >> m;
    if (m % 2) m -= 1;
    int ans = n * m;
    cout << ans / 2 << endl;
}

B. Minimize Inversions

题意：给出两个长度为n的正整数排列，可以随意交换ab中索引相同的两数，即交换是同时作用于两序列同下标的四个数的，最小化两序列的逆序对之和。

思路：最小化其中一个序列，也就是排序其中一个序列，即可。

AC code：

void solve() {
    cin >> n;
    for (int i = 1; i <= n; i ++) {
        cin >> p[i].first;
    }
    for (int i = 1; i <= n; i ++) {
        cin >> p[i].second;
    }
    sort(p + 1, p + n + 1);
    for (int i = 1; i <= n; i ++)
        cout << p[i].first << " ";
    cout << endl;
    for (int i = 1; i <= n; i ++) 
        cout << p[i].second << " ";
    cout << endl;
}

C. XOR-distance

题意：给出整数a,b,x，求所有[0,x]中，|(a㊉i)-(b㊉i)|的最小值。

思路：按位枚举：

• 对于a,b的每一位中，相同的不需要去操作，因为一减就没了
• 而对于ab中不同的位，1 0即+2^i, 0 1即-2^i，枚举是否可以操作，因为最多操作数为x
  • 若可以操作，看当前答案的正负，若为正，当前位为1 0，则需要一步操作变为0 1减去当前位来减少绝对值，以此类推；
  • 若不能操作，直接根据当前位情况加减答案
• 需要额外注意两点：
  • 若当前答案为0，则均不需要进行操作，不必累加操作数，根据当前位进行操作即可；
  • 使用(1 << i)的操作在C++中因为数据会爆int，需要(1LL << i)才行

AC code：

void solve() {
    int a, b, x; 
    cin >> a >> b >> x;
    int now = 0, ans = 0;
    bool flag = true;
    for (int i = 60; i >= 0; i --) {
        if ((a >> i & 1LL) == (b >> i & 1LL)) continue;
        if (ans == 0) {
            if ((a >> i & 1)) ans += 1LL << i;
            else ans -= 1LL << i;
            flag = false;
            continue;
        }
        if (now + (1LL << i) <= x) {
            if (ans > 0) {
                ans -= 1LL << i;
                if (a >> i & 1LL) now += 1LL << i;
            } else {
                ans += 1LL << i;
                if (b >> i & 1LL) now += 1LL << i;
            }
        } else {
            if ((a >> i & 1LL)) ans += 1LL << i;
            else ans -= 1LL << i;
        }
    } cout << abs(ans) << endl;
}