Codeforces Round #1078(Div.2)

最trivial的一集，都是比较简单的题目，但是代码编写很烦人。

B

题目大意：有 $n$ 家银行，每次转出只能转出 $x$ 元，同时转入到对方银行 $y$ 元，最后将所有钱汇聚到某家银行，它的最大值是多少？

数据范围： $2 \leq n \leq 2 \cdot 10^5, 1 \leq y \leq x \leq 10^9$ 。

思路：手玩样例可知，最后其他银行把钱全部转到某家银行即可，那么可流动资金是知道的，因此可以直接扣掉转入银行的流动资金，遍历 $O(n)$ 取最大值。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


void solve() {
    int n, x, y;
    cin >> n >> x >> y;
    vi a(n);
    rep(i, 0, n - 1) cin >> a[i];
    ll ans = 0;
    rep(i, 0, n - 1) ans += 1LL * (a[i] / x) * y;
    ll res = LLONG_MIN;
    rep(i, 0, n - 1) { res = max(res, a[i] + ans - 1LL * (a[i] / x) * y); }
    cout << res << endl;
    return;
}

C

题目大意：给定 $k$ 个纸条，每个长度为 $n$ ，要求构造一个新的字符串 $s$ ，且 $s_j \in {ma[i][j],0 \leq i \leq k-1,0 \leq j \leq n-1 }$ ，使得 $s$ 的最小正周期最小。

数据范围： $2 \leq n,k \leq 50000,4 \leq n \cdot k \leq 10^5$

思路：看到最小正周期，很trivial的一个思路就是枚举它的最小正周期，时间复杂度为 $O(\sqrt{n})$ 。

然后再跑一遍 $O(n)$ 的遍历，由于状态只有 $26$ ，因此可以考虑使用状压求集合交，类似一个分组循环的形式，时间复杂度为 $O(n \sqrt{n})$ 。

 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
50
51
52
53
54
55
56
57


void solve() {
    int n, k;
    cin >> n >> k;
    vector<string> ma(k);
    rep(i, 0, k - 1) cin >> ma[i];
    vi ma2(n);
    rep(i, 0, k - 1) { rep(j, 0, n - 1) ma2[j] |= (1 << (ma[i][j] - 'a')); }
    string ans = "";
    vector<int> d;
    auto init = [&](int x) -> void {
        for (int i = 1; i * i <= x; i++) {
            if (x % i == 0) {
                d.push_back(i);
                d.push_back(n / i);
            }
        }
        return;
    };
    init(n);
    ranges::sort(d);
    int m = sz(d);
    int res = 0;
    rep(i, 0, m - 1) {
        int val = d[i];
        bool flag = true;
        for (int j = 0; j <= val - 1; j++) {
            int tem = INT_MAX;
            for (int v = j; v <= n - 1; v += val) {
                tem &= ma2[v];
            }
            if (tem == 0) {
                flag = false;
                break;
            }
        }
        if (flag) {
            for (int j = 0; j <= val - 1; j++) {
                int tem = INT_MAX;
                for (int v = j; v <= n - 1; v += val) {
                    tem &= ma2[v];
                }
                rep(v, 0, 25) {
                    if ((tem >> v) & 1) {
                        ans += (char)('a' + v);
                        break;
                    }
                }
            }
            int res = n / d[i];
            string tem2 = ans;
            rep(i, 1, res - 1) ans += tem2;
            break;
        }
    }
    cout << ans << endl;
    return;
}

D

题目大意：在一个 $n \times m$ 的0-1网格上，请从左上到右下划一刀，刀口只能向右或者向下，请使得切割后两部分的1数量乘积最大，并输出刀口。

数据范围： $1 \leq n,m \leq 3 \cdot 10^5,2 \leq n \cdot m \leq 3 \cdot 10^5$ 。

思路：首先第一反应肯定是两部分都切到总数的 $\frac{1}{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


void solve() {
    int n, m;
    cin >> n >> m;
    vvi ma(n, vi(m));
    int tot = 0;
    rep(i, 0, n - 1) {
        rep(j, 0, m - 1) {
            cin >> ma[i][j];
            if (ma[i][j] == 1) tot++;
        }
    }
    cout << 1LL * (tot / 2) * (tot - tot / 2) << endl;
    vi dp(m);
    int tem = 0;
    int idx = 0;
    rep(j, 0, m - 1) {
        if (tem == tot / 2) {
            dp[j] = n;
            continue;
        }
        frep(i, n - 1, 0) {
            tem += ma[i][j];
            dp[j] = i;
            if (tem == tot / 2) break;
        }
    }
    string ans = "";
    rep(i, 0, m - 1) {
        if (i > 0) {
            rep(j, 1, dp[i] - dp[i - 1]) { ans += 'D'; }
        } else {
            rep(j, 1, dp[i]) { ans += 'D'; }
        }
        ans += 'R';
    }
    rep(i, 1, n - dp[m - 1]) { ans += 'D'; }
    cout << ans << endl;
    return;
}

E

题目大意：在一个 $n \times m$ 的网格上，Bob可以将某个格子的数取相反数，问Alice从左上角到右下角的路径，至少的路径总和是多少，其中Alice会在Bob操作后按照最优情况行动。

数据范围： $1 \leq n,m \leq 10^6,1 \leq n \cdot m \leq 10^6, -10^9 \leq a_{i,j} \leq 10^9$

思路：肯定是网格图DP，再往下看，不难发现Bob如果要反转一个格子，那么肯定是翻转最优路径上的格子。

于是出现两种情况，一种是直接按照原来路径踩着翻转的格子过去，一种是绕过去。

前者的计算不难，绕过去怎么计算？假设翻转的格子是 $(x,y)$ ，则绕过去的格子必然经过 $(a,b),$ 其中 $a>x,b<y$ 或者 $a<x,b>y$ ，然后就变为前后缀分解问题了，可以使用二维前缀最大值将查询复杂度降为 $O(1)$ ，总时间复杂度为 $O(n \cdot m)$ 。

同时，由上文的讲解，这道题还需要还原路径，因为需要从被翻转的点上做文章。

 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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79


void solve() {
    int n, m;
    cin >> n >> m;
    vvl ma(n, vl(m));
    rep(i, 0, n - 1) { rep(j, 0, m - 1) cin >> ma[i][j]; }
    vvl dp(n, vl(m, LLONG_MIN / 2));
    dp[0][0] = ma[0][0];
    rep(i, 0, n - 1) {
        rep(j, 0, m - 1) {
            if (i == 0 && j == 0) continue;
            int ax = i - 1, ay = j;
            int bx = i, by = j - 1;
            if (ax >= 0 && ax <= n - 1 && ay >= 0 && ay <= m - 1) {
                dp[i][j] = max(dp[i][j], dp[ax][ay] + 1LL * ma[i][j]);
            }
            if (bx >= 0 && bx <= n - 1 && by >= 0 && by <= m - 1) {
                dp[i][j] = max(dp[i][j], dp[bx][by] + 1LL * ma[i][j]);
            }
        }
    }
    ll ans = dp[n - 1][m - 1];
    vvl fdp(n, vl(m, LLONG_MIN / 2));
    fdp[n - 1][m - 1] = ma[n - 1][m - 1];
    frep(i, n - 1, 0) {
        frep(j, m - 1, 0) {
            if (i == n - 1 && j == m - 1) continue;
            int ax = i + 1, ay = j;
            int bx = i, by = j + 1;
            if (ax >= 0 && ax <= n - 1 && ay >= 0 && ay <= m - 1) {
                fdp[i][j] = max(fdp[i][j], fdp[ax][ay] + ma[i][j]);
            }
            if (bx >= 0 && bx <= n - 1 && by >= 0 && by <= m - 1) {
                fdp[i][j] = max(fdp[i][j], fdp[bx][by] + ma[i][j]);
            }
        }
    }
    vvl pre1(n, vl(m, LLONG_MIN / 2));
    vvl pre2(n, vl(m, LLONG_MIN / 2));
    frep(i, n - 1, 0) {
        rep(j, 0, m - 1) {
            if (i != n - 1) pre1[i][j] = max(pre1[i][j], pre1[i + 1][j]);
            if (j != 0) pre1[i][j] = max(pre1[i][j], pre1[i][j - 1]);
            pre1[i][j] = max(pre1[i][j], dp[i][j] + fdp[i][j] - ma[i][j]);
        }
    }
    rep(i, 0, n - 1) {
        frep(j, m - 1, 0) {
            if (i != 0) pre2[i][j] = max(pre2[i][j], pre2[i - 1][j]);
            if (j != m - 1) pre2[i][j] = max(pre2[i][j], pre2[i][j + 1]);
            pre2[i][j] = max(pre2[i][j], dp[i][j] + fdp[i][j] - ma[i][j]);
        }
    }
    int x = n - 1, y = m - 1;
    vector<pii> path;
    path.emplace_back(x, y);
    while (!(x == 0 && y == 0)) {
        if (x == 0 && y != 0)
            y--;
        else if (x != 0 && y == 0)
            x--;
        else {
            if (dp[x - 1][y] > dp[x][y - 1])
                x--;
            else
                y--;
        }
        path.emplace_back(x, y);
    }
    rep(i, 0, sz(path) - 1) {
        auto& [x, y] = path[i];
        ll res = LLONG_MIN;
        res = max(res, dp[n - 1][m - 1] - 2 * ma[x][y]);
        if (x != n - 1 && y != 0) res = max(res, pre1[x + 1][y - 1]);
        if (x != 0 && y != m - 1) res = max(res, pre2[x - 1][y + 1]);
        ans = min(ans, res);
    }
    cout << ans << endl;
    return;
}