AtCoder Beginner Contest 373 A~D

· · 题解

A - September

洛谷链接

AtCoder链接

题目

有 12 个由小写英文字母组成的字符串 S_1,S_2, \ldots ,S_{12}。

求有多少个整数 i(1 \le i \le 12) 满足 S_i 的长度为 i 的整数。

代码

#include <bits/stdc++.h>

using namespace std;

string s;
int cnt;

int main()
{
    for (int i = 0; i < 12; i ++ )
    {
        cin >> s;
        if (s.length() == i + 1)
            cnt ++;
    }
    cout << cnt << '\n';
    return 0;
}

B - 1D Keyboard

洛谷链接

AtCoder链接

题目

有一个键盘，上面的 26 键排列在一条数轴上。

键盘的排列用字符串 S 表示，它是由 ABCDEFGHIJKLMNOPQRSTUVWXYZ 组成的排列。字符 S_x 对应的按键位于坐标 x(1 \le x \le 26) 处。(1 \le x \le 26)。这里的 S_x 表示 S 的第 x 个字符。

您将使用此键盘按此顺序输入 ABCDEFGHIJKLMNOPQRSTUVWXYZ，准确输入每个字母一次。要输入一个字符，您需要将手指移到与该字符对应的按键坐标处并按下该键。

起初，您的手指位于字母 A 对应键的坐标处。请找出从按下 A 键到按下 Z 键之间手指可能移动的最小总距离。在这里，按键并不影响距离。

思路

先找到 A 的位置，标记为 now，然后按顺序依次找到对应按键的位置，标记为 sit，更新距离，将 now 赋值为 sit。

代码

#include <bits/stdc++.h>

using namespace std;

string s;
int now, cnt, sit;

int main ()
{
    cin >> s;
    for (int i = 0; i < 26; i ++ )
    {
        if (s[i] == 'A')
            now = i + 1;
    }
    for (int i = 1; i < 26; i ++ )
    {
        for (int j = 0; j < 26; j ++ )
        {
            if (s[j] == 65 + i)
            {
                sit = j + 1;
                break;
            }
        }
        cnt += abs(sit - now);
        now = sit;
    }
    cout << cnt << '\n';
    return 0 ;
}

C - Max Ai+Bj

洛谷链接

AtCoder链接

题目

给你两个整数序列 A 和 B，每个长度为 N。请选择整数 i,j(1 \le i,j \le N) 使 A_i+B_j 的值最大。

思路

很明显，要得到 \max_{A_i+B_j} 只需要分别取两个序列的最大值相加。

代码

#include <bits/stdc++.h>

using namespace std;

int n, a[500010], b[500010];

int main ()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ )
        scanf("%d", &a[i]);
    for (int i = 0; i < n; i ++ )
        scanf("%d", &b[i]);
    sort(a, a + n);
    sort(b, b + n);
    cout << a[n - 1] + b[n - 1] << '\n';
    return 0 ;
}

D - Hidden Weights

洛谷链接

AtCoder链接

题目

给你一个有向图，图中有 N 个顶点和 M 条边。第 j 条有向边从顶点 u_j 到顶点 v_j，权值为 w_j。

请找出一种方法，在每个顶点写入一个介于 -10^{18} 和 10^{18} 之间的整数，从而满足下面的条件。

可以保证在给定的输入中至少存在一个这样的赋值。

思路

如果确定了一个顶点的值，相邻顶点的值确定。由于该图的连通性，只要任意一点上的值确定，所有的值都会根据该点得知而确定。

因此，可以给初始的顶点赋值为 0，BFS 确定其连通的值。

代码

#include <bits/stdc++.h>

using namespace std;

struct node
{
    long long v, w;
};

queue<long long> q;
vector<node> vc[200010];
bool vis[200010];
long long n, m, u, v, w, ans[200010];

int main()
{
    scanf("%lld %lld", &n, &m);
    while (m -- )
    {
        scanf("%lld %lld %lld", &u, &v, &w);
        vc[u].push_back({v, w});
        vc[v].push_back({u, -w});
    }
    for (long long i = 1; i <= n; i ++ )
    {
        if (vis[i])
            continue;
        q.push(i);
        vis[i] = 1;
        while (!q.empty())
        {
            u = q.front();
            for (auto i : vc[u])
            {
                if (!vis[i.v])
                {
                    vis[i.v] = 1;
                    ans[i.v] = ans[u] + i.w;
                    q.push(i.v);
                }
            }
            q.pop();
        }
    }
    for (long long i = 1; i <= n; i ++ )
        cout << ans[i] << ' ';
    return 0;
}