AtCoder Beginner Contest 378 A~C

IronMen · 2024-12-06 22:19:31 · 题解

A - Pairing

洛谷链接

AtCoder链接

题目

有四个球，第 i 个球的颜色是 A_i。

选择两个颜色相同的球，然后把两个球都丢掉，求这样操作的最大次数。

代码

#include <bits/stdc++.h>

using namespace std;

int a, b, c, d, cnt[4], sum;

int main()
{
    scanf("%d %d %d %d", &a, &b, &c, &d);
    cnt[a - 1] ++;
    cnt[b - 1] ++;
    cnt[c - 1] ++;
    cnt[d - 1] ++;
    if (cnt[0] == 4)
        sum += 2;
    else if (cnt[0] >= 2)
        sum ++;
    if (cnt[1] == 4)
        sum += 2;
    else if (cnt[1] >= 2)
        sum ++;
    if (cnt[2] == 4)
        sum += 2;
    else if (cnt[2] >= 2)
        sum ++;
    if (cnt[3] == 4)
        sum += 2;
    else if (cnt[3] >= 2)
        sum ++;
    cout << sum << '\n';
    return 0;
}

B - Garbage Collection

洛谷链接

AtCoder链接

题目

在 AtCoder City，有 N 种垃圾会被定期收集。第 i 个类型的垃圾 (i=1,2, \ldots ,N) 在日期模 q_i 等于 r_i 的日子被收集。

有 Q 个问题。在 (j=1,2, \ldots ,Q) 的 j 次查询中，考虑到 t_j 次类型的垃圾是在 d_j 这一天投放的，请回答下一天将在哪一天收集垃圾。

在这里，如果第 i 个类型的垃圾是在收集该类型垃圾的当天投放的，那么垃圾将在同一天被收集。

思路

对于某个非负整数 a 来说，除以 q 的余数为 r 的日期表示为日 (aq+r)。因此，只要找出 d \le aq+r 的最小值 a 即可。

设 b 和 c 分别是 d 除以 q 的商和余数。那么，d=bq+c。现在比较 c 和 r。

如果是 c \le r，a 与 d \le aq+r 的最小值是 a=b，所以答案是 bq+r。

若 c>r，a 与 d \le aq+r 的最小值为 a=b+1，故答案为 (b+1)q+r。

代码

#include <bits/stdc++.h>

using namespace std;

int n, Q, t, d, a, b, c, ans, q[110], r[110];

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ )
        scanf("%d %d", &q[i], &r[i]);
    scanf("%d", &Q);
    while (Q -- )
    {
        scanf("%d %d", &t, &d);
        t --;
        b = d / q[t];
        c = d % q[t];
        a = c <= r[t] ? b : b + 1;
        ans = a * q[t] + r[t];
        cout << ans << '\n';
    }
    return 0;
}

C - Repeating

洛谷链接

AtCoder链接

题目

给你一个由 N 个正数 A=(A_1,A_2, \ldots ,A_N) 组成的数列。求长度为 N 的序列 B=(B_1,B_2, \ldots ,B_N) 的定义如下。

• 对于 i=1,2, \ldots, N，定义 B_i 如下：
  • 设 B_i 是在 i 之前出现元素 A_i 的最近位置。如果不存在这样的位置，则设为 B_i=-1。
    更确切地说，如果存在一个正整数 j，使得 A_i=A_j 和 j<i，那么就让 B_i 成为最大的 j。如果不存在这样的 j，则设 B_i=-1。

思路

考虑在数组 \mathrm{last} 中从头开始扫描序列 A，同时保留值 x 的最后出现位置，即最大值 j 与 A_j=x。那么我们可以采用以下算法：

• 用 -1 初始化数组 \mathrm{last} 中的元素。
• 对每个 i=1,2, \ldots ,N 进行如下操作：
  • 让 B_i \leftarrow \mathrm{last}[A_i]。
  • 让 \mathrm{last}[A_i] \leftarrow i。

这个问题的关键在于 A_i 的长度可以达到 10^9，这就需要保留长度为 10^9 的数组 \mathrm{last}，但这并不适合内存。

在这种情况下，使用关联数组是非常有用的。数组存储与特定索引相对应的值。不过，它可以接受任意的索引集，只记忆所需的部分。在我们的问题中，A_i 最多可以是 10^9，但实际的索引仅限于 A 中出现的值（最多有 N \le 2 \times 10^5 种），这样我们就可以减少所需的内存。

大多数语言都将关联数组作为标准功能。在 C++ 中，可以使用 map 或 unordered_map；在 Python 中，可以使用 dict。

代码

C++ 版本要高，否则 CE。

#include <bits/stdc++.h>

using namespace std;

int n;
map<int, int> last;

int main()
{
    scanf("%d", &n);
    vector<int> a(n), b(n, -1);
    for (auto& x : a)
        scanf("%d", &x);
    for (int i = 0; i < n; i ++ )
    {
        if (last.contains(a[i]))
            b[i] = last[a[i]];
        last[a[i]] = i + 1;
    }
    for (int i = 0; i < n; i ++ )
        cout << b[i] << (i < n - 1 ? ' ' : '\n');
    return 0;
}