AtCoder Beginner Contest 384 A~D

· · 题解

A - aaaadaa

洛谷链接

AtCoder链接

题目

给你一个长度为 N 的字符串 S，和两个小写英文字母 c_1 和 c_2。

请找出并用 c_2 替换 S 中每个不是 c_1 的字符后得到的字符串。

代码

#include <bits/stdc++.h>

using namespace std;

int n;
char c1, c2;
string s;

int main()
{
    scanf("%d", &n);
    cin >> c1 >> c2 >> s;
    for (int i = 0; i < s.length(); i ++ )
    {
        if (s[i] == c1)
            cout << s[i];
        else
            cout << c2;
    }
    return 0;
}

B - ARC Division

洛谷链接

AtCoder链接

题目

AtCoder 常规赛（ARC）分为两个组别。

高桥决定参加 N 场 ARC。

他的初始评分为 R。

第 i \ (1 \le i \le N) 次 ARC 是 ARC Div.D_i，他在比赛中的表现用整数 A_i 表示。

如果他在第 i 场 ARC 中评分更新了，那么 T 就是他在比赛开始时的评分。那么在比赛结束后，他的评分就变成了 T+A_i。

如果他没有更新评分，那么他的评分就不会改变。

ARC 的评分更新是在比赛结束后立即进行的，他在下一场比赛中是否要更新评分取决于他上一场更新后的评分。

求在完成 N 场 ARC 之后他的评分。

除了这 N 场 ARC 之外，他没有参加任何比赛。他的评分也没有其他方面的变化。

代码

#include <bits/stdc++.h>

using namespace std;

int n, r, d, a;

int main()
{
    scanf("%d %d", &n, &r);
    for (int i = 0; i < n; i ++ )
    {
        scanf("%d %d", &d, &a);
        if (d == 1)
        {
            if (1600 <= r && r <= 2799)
                r += a;
        }
        else
        {
            if (1200 <= r && r <= 2399)
                r += a;
        }
    }
    cout << r << '\n';
    return 0;
}

C - Perfect Standings

洛谷链接

AtCoder链接

题目

Takahashi 决定举办一次编程竞赛。

竞赛包含五道题目：A、B、C、D、E，得分分别为 a、b、c、d、e。

共有 31 名参赛者，每人都至少解答了一道题目。

更具体地说，对于字符串 ABCDE 的每个非空子序列(不一定连续)，都有一个以该子序列命名的参赛者，他解答了与其名字中字母对应的题目，而没有解答其他题目。

例如，参赛者 A 只解答了题目 A，参赛者 BCE 解答了题目 B、C 和 E。

按得分从大到小的顺序打印参赛者的姓名。参与者获得的分数是他们所解决问题的分数的总和。

如果两个参与者获得的分数相同，则首先打印名字在字典中较小的参与者。

思路

其实题目说的很清楚了，且五个题目的分数是逐渐递增（可能相等）的。

由于排名中人的名字和数量是不变的，所以我们可以借助结构体打表，存储所有人的名字，以及这个人对应的分数。

这时，如何对数据进行排序呢？

我们先考虑根据分数排序，如果分数相同，则根据字典序排序。排序完成后，按排序顺序直接输出名字即可。

代码

// LUOGU_RID: 206168283
#include <bits/stdc++.h>

using namespace std;
int a, b, c, d, e;
string names[] = {"ABCDE", "BCDE", "ACDE", "ABDE", "ABCE", "ABCD", "CDE", "BDE", "ADE", "BCE", "ACE", "BCD", "ABE", "ACD", "ABD", "ABC", "DE", "CE", "BE", "CD", "AE", "BD", "AD", "BC", "AC", "AB", "E", "D", "C", "B", "A"}; // 打表存储名字

// 结构体存储信息
struct node
{
    string name;
    int val;
} p[110];

bool cmp(node a, node b) // cmp()：告诉 sort() 排序方法
{
    if (a.val != b.val) // 先根据分数排序
        return a.val > b.val;
    if (a.val == b.val) // 后根据字典序排序
        return a.name < b.name;
}

int main()
{
    scanf("%d %d %d %d %d", &a, &b, &c, &d, &e); // 输入
    for (int i = 0; i <= 30; i ++ ) // 将数据计算并存入结构体
    {
        p[i + 1].name = names[i];
        for (int j = 0; j < names[i].size(); j ++ )
        {
            if (names[i][j] == 'A')
                p[i + 1].val += a;
            else if (names[i][j] == 'B')
                p[i + 1].val += b;
            else if (names[i][j] == 'C')
                p[i + 1].val += c;
            else if (names[i][j] == 'D')
                p[i + 1].val += d;
            else if (names[i][j] == 'E')
                p[i + 1].val += e;
        }
    }
    sort(p + 1, p + 32, cmp); // 排序 
    for (int i = 1; i <= 31; i ++ ) // 输出
        cout << p[i].name << '\n';
    return 0;
}

D - Repeated Sequence

洛谷链接

AtCoder链接

题目

给你一个周期为 N 的无穷序列 A=(A_1,A_2,A_3, \ldots) 的前 N 项 A_1,A_2, \ldots ,A_N。

请判断该无穷序列是否存在和为 S 的非空连续子序列。

这里，当每个整数 i>N 的周期为 A_i=A_{i-N} 时，无穷序列 A 的周期为 N。

思路

为了模拟题目中无限的这个定义。我们可以让数量 n 变成 2 \times n。

此时我们我们只需开一个队列，维护当前的区间和，设为 val。

如果 val 与 s 相等，就直接输出。

否则调节左右端点就行。如果小，右端点右移，否则左端点右移就行了。

代码

#include <bits/stdc++.h>

using namespace std;

long long n, s, a[400010], sum, val;
queue<long long> stk;

int main()
{
    scanf("%lld %lld", &n, &s);
    for (long long i = 1; i <= n; i ++ )
    {
        scanf("%d", &a[i]);
        sum += a[i];
        a[i + n] = a[i];
    }
    s %= sum;
    for (long long i = 1; i <= n * 2; i ++ )
    {
        while (val > s)
        {
            val -= stk.front();
            stk.pop();
        }
        if (val == s)
        {
            puts("Yes");
            return 0;
        }
        val += a[i];
        stk.push(a[i]);
    }
    puts("No");
    return 0;
}