Codeforces Round 913 (Div. 3) A~E(F,G更新中)

A.Rook（循环）

题意：

给出一个$8\times 8$的棋盘和一个棋子（可以任选上下左右四方向移动任意步数），问一次移动可以到达哪些格子。

分析：

使用for循环对棋子所在的行列进行遍历并输出。

代码：

#include <bits/stdc++.h>

typedef long long LL;
using namespace std;
const int N = 3e5 + 5;

void solve() {
    string s;
    cin >> s;
    for (int i = 1; i <= 8; i++) {
        if (s[1] - '0' != i) {
            cout << s[0] << i << endl;
        }
    }
    for (int i = 0; i < 8; i++) {
        if (s[0] - 'a' != i) {
            cout << (char)(i + 'a') << s[1] << endl;
        }
    }
}

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

B.YetnotherrokenKeoard(模拟)

题意：

给出一个仅包含字母的字符串，其中'B'字符为删去当前字符前的第一个大写字母，'b'字符为删去当前字符前的第一个小写字母。

问：最后剩下的字符串是什么？

分析：

使用结构体存储每个字符，同时记录字符和字符原本所在的下标，并开两个vector分别存储大小写字母，遇到大小写的b且当前对应的vector非空，就删除对应vector最后一个元素。

遍历完字符串后将两个vector中的元素放在一起排序输出即可。

hint：大小写'b'的功能仅为删除元素，不会出现在结果字符串中

代码：

#include <bits/stdc++.h>

typedef long long LL;
using namespace std;
const int N = 3e5 + 5;

struct Node{
    char c;
    int pos;
    bool operator < (const Node &o) const {
        return pos < o.pos;
    }
};

vector<Node> up, low, ans;

void solve() {
    string s;
    cin >> s;
    up.clear();
    low.clear();
    ans.clear();
    for (int i = 0; i < s.size(); i++) {
        if (s[i] >= 'a' && s[i] <= 'z') {
            if (s[i] == 'b') {
                if (!low.empty()) low.pop_back();
            } else {
                low.push_back(Node{s[i], i});
            }
        } else {
            if (s[i] == 'B') {
                if (!up.empty()) up.pop_back();
            } else {
                up.push_back(Node{s[i], i});
            }
        }
    }
    for (int i = 0; i < up.size(); i++) {
        ans.push_back(up[i]);
    }
    for (int i = 0; i < low.size(); i++) {
        ans.push_back(low[i]);
    }
    sort(ans.begin(), ans.end());
    for (int i = 0; i < ans.size(); i++) {
        cout << ans[i].c;
    }
    cout << endl;
}

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

C.Removal of Unattractive Pairs(思维)

题意：

给出一个仅包含小写字母的字符串，每次可以选择两个相邻且不同的字符删除，问经过若干次删除后，剩下的字符串的最短长度是多少？

分析：

只需要考虑出现次数最多的字符，如果其他字符加起来的数量还没有该字符的出现次数多，那么一定无法消除所有字符。

共分为以下几种情况：

• 出现次数最多的字符的数量不大于其他所有字符的数量

  • n为奇数，由于每次只能消除2个字符，那么必然有1个字符会被剩下
  • n为偶数，可以全部删除

• 出现次数最多的字符的数量大于其他所有字符的数量

  • 此时消耗掉所有其他字符都无法将出现次数最多的字符消除，计算剩余多少个字符即可。

代码：

#include <bits/stdc++.h>

typedef long long LL;
using namespace std;
const int N = 3e5 + 5;

int cnt[30];

void solve() {
    int n;
    string s;
    cin >> n >> s;
    memset(cnt, 0, sizeof (cnt));
    int maxn = -1;
    for (int i = 0; i < n; i++) {
        cnt[s[i] - 'a']++;
        maxn = max(maxn, cnt[s[i] - 'a']);
    }
    if (maxn * 2 <= n) {
        if (n % 2 == 1) cout << 1 << endl;
        else cout << 0 << endl;
    }
    else cout << n - 2 * (n - maxn) << endl;
}

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

D.Jumping Through Segments(二分)

题意：

在数轴上有$n$条线，第$i$条线段覆盖$l_i\sim r_i$的区域，开始时站在$0$点上，每次可以选择一个$0\sim k$之间的数字$x$，可以向前或向后跳跃$x$距离。

要求：第$i$次跳跃的落点需要在第$i$条线段中。

问：$k$最少是多少才能保证完成所有跳跃？

分析：

可以对$k$进行二分，每次检查时维护可以跳到的区间的最左端和最右端，然后检查能否落在下一条线段中。如果不能，那么当前$k$不合法，否则，继续检查，并将区间约束在当前线段中。

代码：

#include <bits/stdc++.h>

typedef long long LL;
using namespace std;
const int N = 3e5 + 5;

int n, l[N], r[N];

bool check(int k) {
    int L = 0, R = 0;
    for (int i = 1; i <= n; i++) {
        int jump_l = L - k, jump_r = R + k;
        if (jump_l > r[i] || jump_r < l[i]) return false;
        L = max(jump_l, l[i]), R = min(jump_r, r[i]);
    }
    return true;
}

void solve() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> l[i] >> r[i];
    }
    int L = 0, R = 1e9, ans = -1;
    while (L <= R) {
        int mid = (L + R) / 2;
        if (check(mid)) {
            ans = mid;
            R = mid - 1;
        } else {
            L = mid + 1;
        }
    }
    cout << ans << endl;
}

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

E.Good Triples(思维)

题意：

给出一个非负整数$n$，问有多少三元组$(a,b,c)$满足$a+b+c=n$且$digsum(a)+digsum(b)+digsum(c)=digsum(n)$。

• $digsum(i)$表示将数字$i$十进制位上的每一个数字加在一起的结果。

分析：

当$a+b+c$出现进位时，必有$digsum(a)+digsum(b)+digsum(c)\ne digsum(n)$，因此，将$n$十进制位上每个数字拆出来，单独考虑每个数字的方案，最后根据乘法原理统计答案即可。

hint：需预处理$i=a+b+c(0\le i\le 9)$的方案数。

代码：

#include <bits/stdc++.h>

typedef long long LL;
using namespace std;
const int N = 3e5 + 5;

LL cnt[15];

void solve() {
    string s;
    cin >> s;
    LL ans = 1;
    for (int i = 0; i < s.size(); i++) {
        ans *= cnt[s[i] - '0'];
    }
    cout << ans << endl;
}

int main() {
    for (int i = 0; i <= 9; i++) {
        for (int j = 0; i + j <= 9; j++) {
            for (int k = 0; i + j + k <= 9; k++) {
                cnt[i + j + k]++;
            }
        }
    }
    int Case;
    cin >> Case;
    while (Case--) {
        solve();
    }
    return 0;
}

F,G

更新中…

学习交流

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