Codeforces Round 920 (Div. 3) A~G-Toy模板网

这篇具有很好参考价值的文章主要介绍了Codeforces Round 920 (Div. 3) A~G。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

A.Square(思维)

题意：

给出正方形四个点的坐标，求出该正方形的面积。

分析：

统计行列坐标的最大最小值，然后计算得到边长，通过边长即可得到面积。

代码：

#include<bits/stdc++.h>

using namespace std;

void solve() {
    int maxx = -1001, minx = 1001;
    for (int i = 0; i < 4; i++) {
        int x, y;
        cin >> x >> y;
        maxx = max(maxx, x);
        minx = min(minx, x);
    }
    cout << (maxx - minx) * (maxx - minx) << endl;
}

int main() {
    int Case;
    cin >> Case;
    while (Case--) {
        solve();
    }
    return 0;
}

B.Arranging Cats(贪心)

题意：

有 $n$ 个盒子，每个盒子分为两种状态：

$b_i = 1$ ：第 $i$ 个盒子中有一只猫
$b_i = 0$ ：第 $i$ 个盒子中没有猫

你可以进行若干次操作，每次操作可以选择以下三种操作中的一种：

把一只猫放入空的盒子中
把一只猫从盒子里拿出来
从某个盒子里拿出一只猫，并把这只猫放到另一个盒子里

给出目前盒子的状态序列: $s_1, ..., s_n$ ，问将该序列修改为目标序列： $f_1, ..., f_n$ 至少需要几次操作。

分析：

首先思考应该优先选择哪个操作，不难发现操作3能同时改变两个盒子的状态，另外两种操作只能改变一个盒子的状态，因此，要优先选择操作3.

定义 $a dd$ 为序列中 $s_i = 0$ 但 $f_i = 1$ 的个数， $s u b$ 为序列中 $s_i = 1$ 但 $f_i = 0$ 的个数。

那么可以使用的操作3的次数即为 $min (a dd, s u b)$ ，同时不难发现，剩余所需的操作为 $∣ a dd - s u b ∣$ ，因此实际所需的总操作次数为 $ma x (a dd, s u b)$ ，统计完直接输出即可。

代码：

#include<bits/stdc++.h>

using namespace std;
const int N = 1e5 + 5e2;

int n;
string a, b;

void solve() {
    cin >> n >> a >> b;
    int add = 0, sub = 0;
    for (int i = 0; i < n; i++) {
        if (a[i] > b[i]) sub++;
        else if (a[i] < b[i]) add++;
    }
    cout << max(sub, add) << endl;
}

int main() {
    int Case;
    cin >> Case;
    while (Case--) {
        solve();
    }
    return 0;
}

C.Sending Messages(贪心)

题意：

有 $n$ 封邮件需要发送，这些邮件需要在 $m_1, m_2, ..., m_n$ 时间发送，而邮件均需使用手机发送，手机一开始（0时刻）拥有 $f$ 格电，且如果处于开机状态那么每单位时间会消耗 $a$ 格电，你也可以选择消耗 $b$ 格电将手机关机，而开机不需要消耗电量，同时开关机所需的时间忽略不计。

在0时刻时手机处于开机状态，能否发完这 $n$ 封邮件。

分析：

实际上只需要考虑发相邻两封邮件之间所需的时间，如果开机耗电更少就选择开机，开机耗电更大就选择关机，统计所需的总电量，再与开始时的电量比较，如果足够（开始电量大于消耗电量），那么就可以完成，否则就是不能完成。

坑点：

要注意计算耗电量时会超过int范围，需要使用long long类型存储数据。

代码：

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 2e5 + 5e2;

ll n, f, a, b, m[N];

void solve() {
    cin >> n >> f >> a >> b;
    for (int i = 1; i <= n; i++) {
        cin >> m[i];
        if (f <= 0) continue;
        if ((m[i] - m[i - 1]) * a > b) {
            f -= b;
        } else {
            f -= (m[i] - m[i - 1]) * a;
        }
    }
    if (f > 0) cout << "Yes" << endl;
    else cout << "No" << endl;
}

int main() {
    int Case;
    cin >> Case;
    while (Case--) {
        solve();
    }
    return 0;
}

D.Very Different Array(贪心)

题意：

给出一个包含 $n$ 个数字的序列 $A = a_1, a_2, ..., a_n$ 和一个包含 $\ge n)$ 个数字的序列 $B = b_1, b_2, ..., b_m$ ，你可以从序列 $B$ 中取出 $n$ 个数字并任意重排获得序列 $C = c_1, c_2, ..., c_n$ ，求最大的 $\sum\limits_{i = 1}^{n}|a_i - c_i|$ 。

分析：

先简化问题，思考从 $A$ 中取出一个数字 $x$ ， $B$ 中取出一个数字 $y$ ，该怎么得到最大的 $∣ x - y ∣$ ，不难想到，答案会是以下两种情况之一：

$x$ 为 $A$ 中最大的数字， $y$ 为 $B$ 中最小的数字。
$x$ 为 $A$ 中最小的数字， $y$ 为 $B$ 中最大的数字。

基于这个贪心的思路，先将输入的 $A, B$ 序列进行排序，并使用双指针维护这两个序列中最大最小的数字，并按以上思路进行取数，每次选择两个方案中较大的一个，序列 $A$ 中所有数字均被取完后就得到了最大的 $D$ 。

代码：

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 2e5 + 5e2;

ll n, m, a[N], b[N];

void solve() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int j = 1; j <= m; j++) cin >> b[j];
    sort(a + 1, a + n + 1); sort(b + 1, b + m + 1);
    ll ans = 0;
    int la = 1, ra = n, lb = 1, rb = m;
    while (la <= ra) {
        if (abs(a[la] - b[rb]) >= abs(a[ra] - b[lb])) {
            ans += abs(a[la++] - b[rb--]);
        } else {
            ans += abs(a[ra--] - b[lb++]);
        }
    }
    cout << ans << endl;
}

int main() {
    int Case;
    cin >> Case;
    while (Case--) {
        solve();
    }
    return 0;
}

E.Eat the Chip(思维)

题意：

有一个 $\times m$ 的棋盘，Alice和Bob各有一枚棋子，分别在棋盘上的 $x_a, y_a), (x_b, y_b)$ 坐标上。

Alice作为先手，Bob作为后手。

Alice每轮操作可以选择将棋子移动到 $x_a + 1, y_a), (x_a + 1, y_a + 1), (x_a + 1, y_a - 1)$ 三个位置中的一个。

Bob每轮操作可以选择将棋子移动到 $x_b - 1, y_b), (x_b - 1, y_b + 1), (x_b - 1, y_b - 1)$ 三个位置中的一个。

如果某个选手的棋子可以在移动后到达另一个棋子的位置上，那么另一个选手的棋子就被吃掉了，该选手就赢下了这场比赛。

问：谁可以赢下这场比赛？

分析：

首先在开始时就可以思考平局的情况，由于Alice的棋子只能向下移动，Bob的棋子只能向下移动，那么如果开始时Alice的棋子的位置已经在Bob的棋子同一层或是更低一层的位置上时，双方一定无法吃掉对方的棋子，此时必然平局。

然后考虑双方棋子之间差了多少行，如果差的行数是奇数，那么此时必然为Alice操作，那么只有Alice可能会胜利，反之，如果差的行数为偶数，那么只有Bob可能会获得胜利。

然后考虑当某一位选手可能胜利时，双方各自会选择什么策略，这里以Alice可能胜利的情况为例：

Alice想要胜利，那么必然会选择让棋子不断靠近 $B o b$ 的棋子所在的那一列
而Bob不想输掉比赛，那么必然会选择朝Alice棋子所在的列的另一个方向移动，即不断远离Alice的棋子，当到达边界后，选择不断向正下方移动。
记双方棋子之间的列差为 $l e n$ , 由于Alice想要追上Bob需要等Bob停留在边界上，那么实际上Alice需要的移动次数即为Alice距靠近Bob的棋子所在的边界的距离，这个距离记为 $s t e p$ ，而Alice是先手，那么此时Bob的移动次数是少一的，即移动次数为 $s t e p - 1$ ，那么此时双方的移动次数之和为 $\times step - 1$ ，只要 $\ge 2 \times step - 1$ ，那么之后无论Bob怎么移动，Alice都可以跟随Bob的操作追上Bob赢下比赛。
如果列差不够Alice追上Bob，那么就是平局。

对于Bob，如果想要获胜，条件为 $\ge 2 \times step$ 。

特殊情况：

当 $l e n$ 为正整数时，有以下两种特殊情况：

当len为奇数，且Alice和Bob的棋子在同一列或相邻两列时，此时Alice必胜。
当len为偶数，且且Alice和Bob的棋子在同一列时，此时Bob必胜。

代码：

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 2e5 + 5e2;

int n, m, ax, ay, bx, by;

void solve() {
    cin >> n >> m >> ax >> ay >> bx >> by;
    int len = bx - ax;
    if (len <= 0) {
        cout << "Draw" << endl;
        return;
    } 
    if (len & 1) {
        if (abs(ay - by) <= 1) {
            cout << "Alice" << endl;
            return;
        }
        int step = 0;
        if (ay > by) {
            step = ay - 1;
        } else {
            step = m - ay;
        }
        if (step * 2 - 1 <= len) {
            cout << "Alice" << endl;
        } else {
            cout << "Draw" << endl;
        }
    } else {
        if (abs(ay - by) == 0) {
            cout << "Bob" << endl;
            return;
        }
        int step = 0;
        if (ay > by) {
            step = m - by;
        } else {
            step = by - 1;
        }
        if (step * 2 <= len) {
            cout << "Bob" << endl;
        } else {
            cout << "Draw" << endl;
        }
    }
}

int main() {
    int Case;
    cin >> Case;
    while (Case--) {
        solve();
    }
    return 0;
}

F.Sum of Progression(根号分治，前缀和)

题意：

给出一个包含 $n$ 个数字的数组 $a$ ，有 $q$ 个询问，每个询问会给出三个数字 $s, d, k$ ，请你回答 $a_s + a_{s + d} \cdot 2 + ... + a_{s + d \cdot (k - 1)} \cdot k$ 是多少。

分析：

如果使用循环来进行计算，那么对于由于 $\times k \le n$ ，如果给出的 $d$ 比较大，那么要计算的总数 $k$ 就会很小，因此，可以选择接近 $\sqrt{n}$ 的一个数字作为分界点（这里选了333），当输入的 $d$ 大于等于分界点时，就使用循环来直接计算得到答案。

然后对于 $d$ 较小的情况，可以维护两种前缀和：

$p re [1] [d] [j]$ 表示 $a_{j - m \cdot d} + 2 \cdot a_{j - (m - 1) \cdot d} + ... + (m + 1) \cdot a_{j}$
$p re [0] [d] [j]$ 表示 $a_{j - m \cdot d} + a_{j - (m - 1) \cdot d} + ... + a_{j}$

其中， $m$ 表示的是从第 $j$ 个数字开始以 $d$ 为一步的距离，最多往前走 $m$ 次。

即预处理 $\sim 333$ 作为两个数之间的间隔，维护的前缀和。

然后通过前缀和就可以轻松计算得到要求的答案了。

例：

形如： $a_1, a_2, ..., a_n$ 为以某个数字为间隔取出的数字， $b_1, b_2, ... b_n$ 分别等于 $a_1, a_1 + a_2, ..., \sum\limits_{i = 1}^{n}a_i$ ， $c_1, c_2, ..., c_n$ 分别等于 $a_1, a_1 + 2 \cdot a_2, ..., \sum\limits_{i = 1}^{n} i \cdot a_i$

当想要知道此时 $\sum\limits_{i = l}^{r}(i - l + 1) \cdot a_i$ 时，可以通过前缀和先得到 $\cdot a_l + (p + 1) \cdot a_{l + 1} + ... + (p + k - 1) \cdot a_r$ ，然后通过另一个前缀和减去 $p - 1$ 个 $\sum\limits_{i = l}^{r}a_i$ 即可。

代码：

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 1e5 + 5e2;

int n, q, s, d, k;
ll a[N], pre[2][350][N];

void init() {
    for (int i = 1; i <= n && i <= 333; i++) {//枚举间隔
        for (int j = 1; j <= n; j++) {//计算间隔为i的前缀和
            pre[0][i][j] = a[j];
            pre[1][i][j] = ((j - 1) / i + 1) * a[j];
            if (j > i) {
                pre[0][i][j] += pre[0][i][j - i];
                pre[1][i][j] += pre[1][i][j - i];
            }
        }
    }
}

ll query_1() {//d <= 333
    //注意此时前缀和两个数之间的间隔为d
    ll ans = pre[1][d][s + (k - 1) * d] - pre[1][d][max(0, s - d)];
    ll sub = (s - 1) / d * (pre[0][d][s + (k - 1) * d] - pre[0][d][max(0, s - d)]);
    return ans - sub;
}

ll query_2() {// d > 333
    ll ans = 0;
    for (int i = 0; i < k; i++) {
        ans += (i + 1) * a[i * d + s];
    }
    return ans;
}

void solve() {
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];
    init();
    while (q--) {
        cin >> s >> d >> k;
        if (d <= 333) {
            cout << query_1();
        } else {
            cout << query_2();
        }
        if (q == 0) cout << endl;
        else cout << ' ';
    }
}

int main() {
    int Case;
    cin >> Case;
    while (Case--) {
        solve();
    }
    return 0;
}

G.Mischievous Shooter(分治，枚举)

题意：

Shel有一把特殊的武器，可以在击中一个目标点后同时击中四方向(右上，右下，左下，左上)中其中一个里的所有曼哈顿距离在 $k$ 以内的点。

给出一个 $\times m$ 的靶子，靶子上有若干个得分点，问使用这把武器最多可以击中多少个得分点。

分析：

题目关键信息： 由 $\times m \le 10^{5}$ 可知 $\le \sqrt{10^{5}}$

因此，可以枚举所有点作为被击中的目标点，对于目标点的四种方案的检查，可以根据 $n$ 和 $m$ 谁较小，就循环谁去检查。

假如循环检查的是行，为了避免再通过循环去检查列上存在多少个得分点，需要对于每一行均维护一个前缀和，同理，对于每一列也需要维护一个前缀和。

记录枚举过程中最大的答案即可。

代码：

#include<bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N = 1e5 + 5e2;

int n, m, k;

string s[N];

void solve() {
    cin >> n >> m >> k;
    //row[i][j]表示第i行的第1~j列的数字总和
    //col[i][j]表示第i列的第1~j行的数字总和
    vector<vector<int> > row(n + 1, vector<int>(m + 1, 0)),
                         col(m + 1, vector<int>(n + 1, 0));
    for (int i = 1; i <= n; i++) {
        cin >> s[i];
        for (int j = 1; j <= m; j++) {
            int a = (s[i][j - 1] == '#');
            row[i][j] = row[i][j - 1] + a;
        }
    }
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            int a = (s[j][i - 1] == '#');
            col[i][j] = col[i][j - 1] + a;
        }
    }
    int ans = 0;
    if (n < m) {//枚举行
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                int sum = 0;
                for (int h = i, len = k; h >= i - k && h >= 1; h--, len--) {
                    sum += row[h][min(m, j + len)] - row[h][j - 1];
                }
                ans = max(ans, sum);
                sum = 0;
                for (int h = i, len = k; h <= i + k && h <= n; h++, len--) {
                    sum += row[h][min(m, j + len)] - row[h][j - 1];
                }
                ans = max(ans, sum);
                sum = 0;
                for (int h = i, len = k + 1; h <= i + k && h <= n; h++, len--) {
                    sum += row[h][j] - row[h][max(0, j - len)];
                }
                ans = max(ans, sum);
                sum = 0;
                for (int h = i, len = k + 1; h >= i - k && h >= 1; h--, len--) {
                    sum += row[h][j] - row[h][max(0, j - len)];
                }
                ans = max(ans, sum);
            }
        }
    } else {//枚举列
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                int sum = 0;
                for (int w = j, len = k + 1; w <= j + k && w <= m; w++, len--) {
                    sum += col[w][i] - col[w][max(0, i - len)];
                }
                ans = max(ans, sum);
                sum = 0;
                for (int w = j, len = k; w <= j + k && w <= m; w++, len--) {
                    sum += col[w][min(n, i + len)] - col[w][i - 1];
                }
                ans = max(ans, sum);
                sum = 0;
                for (int w = j, len = k; w >= j - k && w >= 1; w--, len--) {
                    sum += col[w][min(n, i + len)] - col[w][i - 1];
                }
                ans = max(ans, sum);
                sum = 0;
                for (int w = j, len = k + 1; w >= j - k && w >= 1; w--, len--) {
                    sum += col[w][i] - col[w][max(0, i - len)];
                }
                ans = max(ans, sum);
            }
        }
    }
    cout << ans << endl;
}

int main() {
    int Case;
    cin >> Case;
    while (Case--) {
        solve();
    }
    return 0;
}

学习交流

以下为学习交流QQ群，群号： 546235402，每周题解完成后都会转发到群中，大家可以加群一起交流做题思路，分享做题技巧，欢迎大家的加入。

Codeforces Round 920 (Div. 3) A~G,codeforces题解,算法,OI,ACM-ICPC,信息学奥林匹克,Codeforces 文章来源地址https://www.toymoban.com/news/detail-798491.html

到了这里，关于Codeforces Round 920 (Div. 3) A~G的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

Codeforces Round 920 (Div. 3) A~G

A.Square(思维)

题意：

分析：

代码：

B.Arranging Cats(贪心)

题意：

分析：

代码：

C.Sending Messages(贪心)

题意：

分析：

坑点：

代码：

D.Very Different Array(贪心)

题意：

分析：

代码：

E.Eat the Chip(思维)

题意：

分析：

特殊情况：

代码：

F.Sum of Progression(根号分治，前缀和)

题意：

分析：

代码：

G.Mischievous Shooter(分治，枚举)

题意：

分析：

代码：

学习交流

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

支付宝扫一扫领取红包，优惠每天领

二维码1

二维码2