Codeforces Round 675 (Div. 2)

十月 22, 2020 10706

做题情况

十分钟写完 A 题，B 题撞边界调了 1h 没调出来心态爆炸直接放弃整场 VP，赛后去看了题解一块补完。

A. Fence

题意简述

给定一个四边形的三条边长，输出任意一个合法的第四条边长。

解题思路

考场上花了五分钟才勉强猜出结论，一共写了十分钟 QAQ

分两种情况考虑：

  • 如果给定的三条边足够组成一个三角形的话，那么一定可以通过改变角的大小，来让两个端点之间的距离为 1，此时直接输出 1 即可
  • 如果给定的三条边不足以组成一个三角形的话，那么就先把缺的长度补上，然后再加个 1 即可

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
inline int read() {
    int s = 0, x = 1; char ch = getchar();
    while (!isdigit(ch)) { if (ch == '-') x = -x; ch = getchar(); }
    while (isdigit(ch)) { s = s * 10 + ch - '0'; ch = getchar(); }
    return s * x;
}

int t, aa[3];

int main() {
    t = read();
    while (t --> 0) {
        aa[0] = read(); aa[1] = read(); aa[2] = read();
        std::sort(aa, aa + 3);
        if (aa[0] + aa[1] >= aa[2]) puts("1");
        else printf("%d\n", aa[2] - aa[1] - aa[0] + 1);
    }
    return 0;
}

B. Nice Matrix

题意简述

给你一个 n \times m 的矩形，每次操作可以让矩形里的某一个数加一或减一，现要求这个矩形的行、列都变成回文的，求最小操作次数

解题思路

手玩一下可以发现，将行列变成回文的，等价于让一些以中心为轴对称的矩形的四个角数字相等。

画个图理解一下
BP0khF.png

这里画了一部分，其中相同颜色的格子数字要相同

代码实现

卡了好久如何处理奇数行列的情况，最后发现就一个判断的事

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
inline int read() {
    int s = 0, x = 1; char ch = getchar();
    while (!isdigit(ch)) { if (ch == '-') x = -x; ch = getchar(); }
    while (isdigit(ch)) { s = s * 10 + ch - '0'; ch = getchar(); }
    return s * x;
}

int t; long long int ans;
int n, m, mat[100 + 10][100 + 10];

long long int calc(std::vector<int>& vec) { 
    long long int ans = 0;
    std::sort(vec.begin(), vec.end());
    for (auto v : vec) {
        ans += std::abs(v - vec[vec.size() / 2]);
    }
    return ans;
}

int main() {
    t = read();
    while (t --> 0) {
        ans = 0;
        n = read(); m = read();
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                mat[i][j] = read();
            }
        }
        for (int lx = 1; lx <= (n + 1) / 2; ++lx) {
            for (int ly = 1; ly <= (m + 1) / 2; ++ly) {
                int rx = n - lx + 1, ry = m - ly + 1;
                std::vector<int> ff;
                ff.push_back(mat[lx][ly]);
                if (lx != rx) ff.push_back(mat[rx][ly]);
                if (ly != ry) ff.push_back(mat[lx][ry]);
                if (lx != rx && ly != ry) ff.push_back(mat[rx][ry]);
                ans += calc(ff);
            }
        }
        printf("%lld\n", ans);
    }
    return 0;
}

C. Bargain

题意简述

给一个长度为 n 的数字，现在允许删去至多一段连续的数位来得到一个新数，全删了就是 0，求所有可以得到的数字之和。

解题思路

发现按顺序考虑不大好搞，于是开始考虑算每一位的贡献。

假设从左到右枚举到了第 k 位，数位是 a_k ：

  • 删的这一段在第 k 位前面：
    此时删哪里对 k 的贡献并没有影响，贡献是 a_k \times 10^{n - k} ，由于前面可删的区间一共 C_k^2 个，所以总的贡献就是 C_k^2 \times a_k \times 10^{n - k}
  • 删的这一段在第 k 位后面：
    此时 k 的贡献与删的位数有关，假设删了 x 位，这样有 n - k + 1 - x 个能删的地方，那么贡献就是 a_k \times 10^{n - k - x}\times (n - k + 1 - x) ，总贡献就是 \sum_{x = 1}^{n - k}a_k \times 10^{n - k - x}\times (n - k + 1 - x)

所以这个答案柿子是：

\sum_{k = 1}^{n}\left[C_k^2 \times a_k \times 10^{n - k}+\sum_{x = 1}^{n - k}a_k \times 10^{n - k - x}\times (n - k + 1 - x)\right]

这个柿子是 O(n^2) 的，但是可以发现这个东西就是一个等差数列乘等比数列，推一推柿子就可以优化成线性的。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const int ha = 1e9 + 7;

std::string s; int n;

int main() {
    cin >> s; n = (int) s.size();
    long long int ans = 0, sum = 0, p = 1;
    for (long long int i = n - 1; i >= 0; --i) {
        long long int k = (i * (i + 1) / 2 % ha * p % ha + sum) % ha;
        sum = (sum + p * (n - i) % ha) % ha;
        p = p * 10 % ha;
        ans = (ans + (s[i] - '0') * k % ha) % ha;
    }
    printf("%lld\n", ans);
    return 0;
}

D. Returning Home

题目简述

给定一个 n\times n 的网格，初始你在 (x, y) ，每一分钟可以往上下左右走一格。现在上面有 m 个特殊点，与特殊点同行同列的点可以不需要时间就瞬移到特殊点，求走到 (a, b) 的最小时间。

解题思路

对 n 建边肯定是不现实的，考虑对 m 建边，但是这样需要建 O(m^2) 级别的边，仍然存不下。

注意到一个优化，就是，如果存在三个特殊点 (x_1, y_1), (x_2, y_2), (x_3, y_3) 满足 x_1 < x_2 < x_3 ，那么只需要建 (x_1, y_1), (x_2, y_2) 之间的和 (x_2, y_2), (x_3, y_3) 之间的边， (x_1, y_1), (x_3, y_3) 实际上可以通过上述两条边间接到达，而且答案相同，所以就不必要建。

通过这个优化，我们成功把边数优化到了 O(m) 级别，只需要对 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
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
80
81
82
83
84
#define mp std::make_pair

inline int read() {
    int s = 0, x = 1; char ch = getchar();
    while (!isdigit(ch)) { if (ch == '-') x = -x; ch = getchar(); }
    while (isdigit(ch)) { s = s * 10 + ch - '0'; ch = getchar(); }
    return s * x;
}

const int MAXM = 2e5 + 10;

std::map<coo, int> idx; int cnt;
int id(coo x) { if (idx[x]) return idx[x]; return idx[x] = ++cnt; }

int n, m; long long int sx, sy, tx, ty;
int s, t; coo coors[MAXM];

struct Edge { 
    int v; long long int w; Edge(int _v = 0, long long int _w = 0) : v(_v), w(_w) {} 
    bool operator < (const Edge &th) const {
        return w > th.w;
    }
}; typedef Edge Node;

std::vector<Edge> G[MAXM];

bool sortcmp1(coo x, coo y) {
    return x.first < y.first;
}
bool sortcmp2(coo x, coo y) {
    return x.second < y.second;
}

long long int dijk() {
    std::priority_queue<Node> q;
    static long long int dist[MAXM]; memset(dist, 0x3f, sizeof dist);
    static bool vis[MAXM]; memset(vis, 0, sizeof vis);
    q.push(Node(s, 0)); dist[s] = 0;
    while (!q.empty()) {
        Node nwnd = q.top(); q.pop();
        int u = nwnd.v; if (vis[u]) continue;
        vis[u] = true;
        for (int i = 0, siz = (int) G[u].size(); i < siz; ++i) {
            int v = G[u][i].v; long long int w = G[u][i].w;
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                q.push(Edge(v, dist[v]));
            }
        }
    }
    return dist[t];
}

int main() {
    n = read(); m = read();
    sx = read(); sy = read(); tx = read(); ty = read();
    s = id(mp(sx, sy)); t = id(mp(tx, ty));
    for (int i = 1; i <= m; ++i) {
        long long int xx = read(); long long int yy = read();
        coors[i] = mp(xx, yy);
    }
    G[s].push_back(Edge(t, std::abs(sx - tx) + std::abs(sy - ty)));
    std::sort(coors + 1, coors + 1 + m, sortcmp1);
    for (int i = 1; i <= m; ++i) {
        int nwid = id(coors[i]); 
        long long int sw = std::min(std::abs(coors[i].first - sx), 
                        std::abs(coors[i].second - sy));
        long long int tw = std::abs(coors[i].first - tx) + std::abs(coors[i].second - ty);
        G[s].push_back(Edge(nwid, sw));
        G[nwid].push_back(Edge(t, tw));
        if (i > 1) {
            G[nwid].push_back(Edge(id(coors[i - 1]),std::abs(coors[i].first - coors[i - 1].first)));
            G[id(coors[i - 1])].push_back(Edge(nwid, std::abs(coors[i].first - coors[i - 1].first)));
        }
    }
    std::sort(coors + 1, coors + 1 + m, sortcmp2);
    for (int i = 2; i <= m; ++i) {
        int nwid = id(coors[i]); 
        G[nwid].push_back(Edge(id(coors[i - 1]),std::abs(coors[i].second - coors[i - 1].second)));
        G[id(coors[i - 1])].push_back(Edge(nwid, std::abs(coors[i].second - coors[i - 1].second)));
    }
    printf("%lld\n", dijk());
    return 0;
}

E. Minlexes

题意简述

给定一个长为 n 的字符串，允许删除一些连续相同字母对（一些不重叠的、仅含有一种字符的长度为 2 的子串）。对于这个字符串的每一个后缀，输出通过删除操作能得到字典序最小的字符串。

解题思路

倒着做，从空串开始考虑每个字符加入对答案的影响。

令 f[i] (1 <= i <= n) 表示以下标 i 开头的后缀的答案。

边界：f[n + 1] = ""（空串）

假设当前枚举到了一个 i，求出了 f[i + 1], f[i + 2] 的答案，字符串为 s ，那么对于新加入的 s[i] 有以下两种处理方式：

  • 如果 s[i] 等于 s[i + 1] ，那么 f[i] = min(f[i + 2], s[i] + s[i] + f[i + 2]) ，也就是选与不选取最小的
  • 如果 s[i] 不等于 s[i + 1]，那么 f[i] = s[i] + f[i + 1] ，也就是只能乖乖选加入

第二种情况比较好处理，第一种情况直接做容易退化成 O(n^2) 的复杂度，那么该怎么办？

仍然分情况讨论：

  • 如果 f[i + 2][1] （f[i + 2] 这个字符串的第 1 个字符）字典序大于 s[i] ，自然是选上更优；
  • 如果 f[i + 2][1] 字典序小于 s[i]，自然是不选更优；
  • 如果 f[i + 2][1] 字典序等于 s[i] 而且f[i + 2] 前两个不等的字符字典序递增，就选上更优，否则不选更优。
    例如字符串 dddef，f[i + 2] = "def"，s[i] = s[i + 1] = 'd'，f[i + 2] 前两个不等的字符是 de 递增，自然是往后拖一拖比较优，所以就选上比较好
    而字符串 dddab 相反，后面有字典序更小的应该往前提，所以就不选比较好

代码实现

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
inline int read() {
    int s = 0, x = 1; char ch = getchar();
    while (!isdigit(ch)) { if (ch == '-') x = -x; ch = getchar(); }
    while (isdigit(ch)) { s = s * 10 + ch - '0'; ch = getchar(); }
    return s * x;
}

const int MAXN = 1e5 + 10;

struct Answer {
    std::string lp, rp;
    int len;
    bool inc; // 前两个相同的字符是否递增

    Answer() { len = 0; inc = false; lp.clear(); rp.clear(); }
    void insert(char ch) {
        if (lp.size() && lp[0] != ch) inc = (ch < lp[0]);
        ++len;
        lp = ch + lp;
        if (len > 10) {
            while (lp.size() > 5) {
                if (rp.size() < 2) rp = lp[lp.size() - 1] + rp;
                lp.pop_back();
            }
        }
    }
    void print() {
        printf("%d ", len);
        if (rp.size()) printf("%s...%s", lp.c_str(), rp.c_str());
        else printf("%s", lp.c_str());
        puts("");
    }
} f[MAXN];

int n;
char ss[MAXN];

int main() {
    scanf("%s", ss + 1); n = strlen(ss + 1);
    for (int i = n; i >= 1; --i) {
        if (ss[i] == ss[i + 1]) {
            f[i] = f[i + 2];
            if (f[i].len != 0 && ((f[i].inc && ss[i] == f[i].lp[0]) || ss[i] < f[i].lp[0])) {
                f[i].insert(ss[i]); f[i].insert(ss[i]);
            }
        } else {
            f[i] = f[i + 1]; f[i].insert(ss[i]);
        }
    }
    for (int i = 1; i <= n; ++i) f[i].print();
    return 0;
}