Codeforces Round 1010 + Edu 176 题解

发表于 更新于 分类于 阅读次数： 本文字数： 7.7k
这就是thu场吗，毫无区分度，edu场双指针写反了有点招笑。

Codeforces Round 1010 (Div. 2, Unrated) 题解

A

题意

给一个 01 矩阵，一次操作可以改变一个位置的数，求让每一行和每一列的异或都是 0 的最少操作次数。

题解

一次操作可以贪心地同时改变一行和一列，行列较少的改变完之后单独改变行或列即可，答案就是最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve() {
    int n, m;
    cin >> n >> m;
    vector<string> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        a[i] = " " + a[i];
    }
    int rcnt = 0, ccnt = 0;
    for (int i = 1; i <= n; i++) {
        int v = 0;
        for (int j = 1; j <= m; j++) {
            v ^= a[i][j] - '0';
        }
        if (v == 1) {
            rcnt++;
        }
    }
    for (int i = 1; i <= m; i++) {
        int v = 0;
        for (int j = 1; j <= n; j++) {
            v ^= a[j][i] - '0';
        }
        if (v == 1) {
            ccnt++;
        }
    }
    cout << max(rcnt, ccnt) << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

B

题意

给定一个数，必须进行 \(n\) 次操作：除以 2 向下取整，和 \(m\) 次操作：除以 2 向上取整，求能获得的最大值和最小值。

题解

比较棘手的就是向上取整的情况，一个观察得出的结论是：一共 \(n + m\) 次操作中，我们设 \(x\) 的低 \(n + m\) 位为 \(k\)，其余位组成的数为 \(l\) ，前 \(n+m - 1\) 次操作会让 \(x\) 剩余 \(l\) 加上一位 0/1，如果最后一次操作是向上取整且产生了进位（即最后一位是1），那么答案就是 \(l+1\)，否则就是 \(l\) 。因此如果求最小值，不妨先把向上取整消耗掉，如果求最大值就先消耗向下取整。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve() {
    int x, n, m;
    cin >> x >> n >> m;
    m = min(m, 30ll);
    n = min(n, 30ll);
    auto getmin = [&](int x, int n, int m) {
        while (m--) {
            x = (x + 1) / 2;
        }
        while (n--) {
            x /= 2;
        }
        return x;
    };
    auto getmax = [&](int x, int n, int m) {
        while (n--) {
            x /= 2;
        }
        while (m--) {
            x = (x + 1) / 2;
        }
        return x;
    };
    cout << getmin(x, n, m) << " " << getmax(x, n, m) << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

C

题意

对于一个数 \(x\) ，每次操作都会除以2，有一半的概率向上取整和向下取整，求把这个数变成 1 的操作次数的期望。

题解

有了 B 题的基础，设 \(x\) 的二进制长度为 \(l\) ，我们知道操作次数要么是 \(l -1\) ，要么是 \(l\) （最后一次是向上取整且进位了），那么我们就需要知道最后一次是否是向上取整且进位了。

我们设 \(f_i\) 表示处理第 \(i\) 位时进位的概率，从低位向高位转移，如果当前位是 0 就必须前一位进位，同时这一次操作是向上取整，即 \(f_i = f_{i+1} * \frac{1}{2}\)，如果当前位是 1 ，需要前一位进位，当前操作任意，或者前一位不进位，当前操作为向上取整均可，\(f_i = f_{i+1} + (1-f_{i+1}) * \frac{1}{2} = (1+f_{i+1})*\frac{1}{2}\)。注意用逆元处理。

最终答案就是 \(l - 1 + f_{2}\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <bits/stdc++.h>
using namespace std;
#define int long long

const int mod = 1e9 + 7;
int qpow(int a, int b) {
    int res = 1;
    while (b) {
        if (b % 2 == 1) {
            res = res * a % mod;
        }
        a = a * a % mod;
        b /= 2;
    }
    return res;
}
int inv(int a) { return qpow(a, mod - 2); }
void solve() {
    int n;
    string x;
    cin >> n >> x;
    x = " " + x;
    int inv2 = inv(2);
    vector<int> dp(n + 2);
    for (int i = n; i > 1; i--) {
        if (x[i] == '0') {
            dp[i] = dp[i + 1] * inv2 % mod;
        } else {
            dp[i] = (1 + dp[i + 1]) * inv2;
            dp[i] %= mod;
        }
    }
    cout << (n - 1 + dp[2]) % mod << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

D（*2500）

题意

给定一个数组，可以进行操作：选择一个连续区间，改变这个区间内的任意数，但是不能改变相邻两个数的相对大小。求把原数组变为严格递增序列的最小操作次数。

题解

很抽象。我们统计出相邻逆序对的数量 \(s\)，注意一次操作最多可以改变两个逆序对（设 \([a_{i},a_{i+1}],[a_j,a_{j+1}]\) 是两个最远逆序对，那么 \([a_{i+1},a_j]\) 是正确顺序的，改变\([a_{i+1},a_{j+1}]\)），但是需要 \(a_j - a_i \ge j -i\)​，否则中间就不能严格递增，放不下这么多数。

那么如果逆序对数是奇数或不满足上述情况，答案应该是 \(\lceil \frac{s}{2}\rceil\)，否则就是 \(\lfloor\frac{s}{2}\rfloor\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    int cnt = 0;
    int lo = 0, hi = 0;
    for (int i = 1; i < n; i++) {
        if (a[i] > a[i + 1]) {
            cnt++;
            hi = i + 1;
            if (lo == 0) {
                lo = i;
            }
        }
    if (cnt % 2 == 1 || (lo != 0 && a[hi] - a[lo] < hi - lo)) {
        cout << cnt / 2 + 1 << "\n";
    } else {
        cout << cnt / 2 << "\n";
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

Educational Codeforces Round 176 (Rated for Div. 2) 题解

A

题意

给定两个数 \(n, k\)，\(k\) 是奇数，可以从 \(n\) 中减去 1～\(k\)，但是减去的数必须和 \(n\) 同奇同偶，求最小操作次数。

题解

贪心：\(n\) 是奇数的话就先减去一次 \(k\) 变成偶数，然后一直减去 \(k-1\) ,否则就直接减去 \(k-1\)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve() {
    int n, k;
    cin >> n >> k;
    if (n % 2 == 1) {
        n -= k;
        k--;
        cout << 1 + (n + k - 1) / k << "\n";
    } else {
        k--;
        cout << (n + k - 1) / k << "\n";
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

B

题意

从数组中选择 \(k\) 个数染色，然后继续染色，每次可以已经有颜色的位置的旁边一个未染色的位置，最后的答案为选择的 \(k\) 个数的值之和加上最后染色的一个数的值，求最大值。

题解

容易证明 \(k\ge2\) 时答案就是 前 \(k+1\) 个大数，\(k = 1\) 时至少需要选择一个最边上的数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    if (k == 1) {
        if (a[1] < a[n]) {
            int mx = 0;
            for (int i = 1; i < n; i++) {
                mx = max(mx, a[i]);
            }
            cout << a[n] + mx << "\n";
            return;
        } else {
            int mx = 0;
            for (int i = 2; i <= n; i++) {
                mx = max(mx, a[i]);
            }
            cout << mx + a[1] << "\n";
            return;
        }
    }
    sort(a.begin() + 1, a.end(), greater());
    int ans = 0;
    for (int i = 1; i <= k + 1; i++) {
        ans += a[i];
    }
    cout << ans << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

C

题意

有 \(m\) 种油漆，涂一个长度为 \(n\) 的栅栏，给出每种油漆能涂色的数量 \(a_i\)，每次涂色只能选择两种油漆，且这个栅栏必须恰好有两种颜色，每种颜色必须是连续的，求方案数。

题解

设两个不同的油漆分别有 \(a\)，\(b\) 个，那么 \(a\) 可以选择涂 \(1\)~\(a\) 块，答案就是 \(2\times(a+b-n+1)\)，我们排序后使用双指针维护第一个满足 \(a_i + a_j \ge n\) 的位置 \(j\) ，那么从 \(j\) 开始的所有数都可以与 \(i\) 组合， 答案就是 \(\sum_{j}^m2(a-n+1) + 2(suf_j)\)，维护后缀和即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> a(m + 1), pre(m + 1);
    for (int i = 1; i <= m; i++) {
        cin >> a[i];
        if (a[i] == n) {
            a[i] = n - 1;
        }
    }
    sort(a.begin() + 1, a.end());
    for (int i = 1; i <= m; i++) {
        pre[i] = pre[i - 1] + a[i];
    }
    int ans = 0, l = 1, r = 2;
    for (int l = 1, r = m; l <= m; l++) {
        r = max(l + 1, r);
        r = min(r, m);
        while (r > l && a[l] + a[r] >= n) {
            r--;
        }
        r++;
        ans += 2 * (a[l] + 1 - n) * (m - r + 1) + (pre[m] - pre[r - 1]) * 2;
    }
    cout << ans << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

D

题意

给定两个数 \(x,y\)，每次可以选择一个数右移 $i $ 位，消耗是 \(2^i\) ，但是不能选择相同的 \(i\) ，求让 \(x = y\) 的最小消耗。

题解

每种 \(i\) 只能取一次，想到 01 背包，设 \(dp_{i,j}\) 表示 \(x\) 右移 \(i\) 位，\(y\) 右移 \(j\) 位的最小消耗，那么取右移前 \(k\) 个数，\(dp_{i,j} = \min(dp_{i-k,j}, dp_{i,j-k})\)，初始状态 \(dp_{0,0} = 0\)。

然后 \(O(\log x\log y)\) 枚举 \(i,j\) ，\(x = y\) 时取最小值即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include <bits/stdc++.h>
using namespace std;
#define int long long

vector<vector<int>> dp;
void solve() {
    int x, y;
    cin >> x >> y;
    if (x == y) {
        cout << 0 << "\n";
        return;
    }
    int ans = 1e18;

    for (int i = 0; i <= 60; i++) {
        for (int j = 0; j <= 60; j++) {
            if ((x >> i) == (y >> j)) {
                ans = min(ans, dp[i][j]);
            }
        }
    }
    cout << ans << "\n";
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t = 1;
    cin >> t;
    dp.resize(61, vector<int>(61, 1e18));
    dp[0][0] = 0;
    for (int i = 1; i <= 60; i++) {
        for (int j = 60; j >= 0; j--) {
            for (int k = 60; k >= 0; k--) {
                if (j >= i) {
                    dp[j][k] = min(dp[j][k], dp[j - i][k] + (1ll << i));
                }
                if (k >= i) {
                    dp[j][k] = min(dp[j][k], dp[j][k - i] + (1ll << i));
                }
            }
        }
    }

    while (t--) {
        solve();
    }
    return 0;
}