专栏文章

AtCoder Beginner Contest 378 A~C

IIronMen
题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miqv5svr
此快照首次捕获于
2025/12/04 11:15
3 个月前
此快照最后确认于
2025/12/04 11:15
3 个月前
查看原文

A - Pairing

洛谷链接
AtCoder链接

题目

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

代码

CPP
#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，有 NN 种垃圾会被定期收集。第 ii 个类型的垃圾 (i=1,2,…,N)(i=1,2, \ldots ,N) 在日期模 qiq_i 等于 rir_i 的日子被收集。
有 QQ 个问题。在 (j=1,2,…,Q)(j=1,2, \ldots ,Q) 的 jj 次查询中，考虑到 tjt_j 次类型的垃圾是在 djd_j 这一天投放的，请回答下一天将在哪一天收集垃圾。
在这里，如果第 ii 个类型的垃圾是在收集该类型垃圾的当天投放的，那么垃圾将在同一天被收集。

思路

对于某个非负整数 aa 来说，除以 qq 的余数为 rr 的日期表示为日 (aq+r)(aq+r)。因此，只要找出 d≤aq+rd \le aq+r 的最小值 aa 即可。
设 bb 和 cc 分别是 dd 除以 qq 的商和余数。那么，d=bq+cd=bq+c。现在比较 cc 和 rr。
如果是 c≤rc \le r，aa 与 d≤aq+rd \le aq+r 的最小值是 a=ba=b，所以答案是 bq+rbq+r。
若 c>rc>r，aa 与 d≤aq+rd \le aq+r 的最小值为 a=b+1a=b+1，故答案为 (b+1)q+r(b+1)q+r。

代码

CPP
#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链接

题目

给你一个由 NN 个正数 A=(A1,A2,…,AN)A=(A_1,A_2, \ldots ,A_N) 组成的数列。求长度为 NN 的序列 B=(B1,B2,…,BN)B=(B_1,B_2, \ldots ,B_N) 的定义如下。
  • 对于 i=1,2,…,Ni=1,2, \ldots, N，定义 BiB_i 如下：
    • 设 BiB_i 是在 ii 之前出现元素 AiA_i 的最近位置。如果不存在这样的位置，则设为 Bi=−1B_i=-1。
      更确切地说，如果存在一个正整数 jj，使得 Ai=AjA_i=A_j 和 j<ij<i，那么就让 BiB_i 成为最大的 jj。如果不存在这样的 jj，则设 Bi=−1B_i=-1。

思路

考虑在数组 last\mathrm{last} 中从头开始扫描序列 AA，同时保留值 xx 的最后出现位置，即最大值 jj 与 Aj=xA_j=x。那么我们可以采用以下算法：
  • 用 −1-1 初始化数组 last\mathrm{last} 中的元素。
  • 对每个 i=1,2,…,Ni=1,2, \ldots ,N 进行如下操作：
    • 让 Bi←last[Ai]B_i \leftarrow \mathrm{last}[A_i]。
    • 让 last[Ai]←i\mathrm{last}[A_i] \leftarrow i。
这个问题的关键在于 AiA_i 的长度可以达到 10910^9，这就需要保留长度为 10910^9 的数组 last\mathrm{last}，但这并不适合内存。
在这种情况下，使用关联数组是非常有用的。数组存储与特定索引相对应的值。不过，它可以接受任意的索引集，只记忆所需的部分。在我们的问题中，AiA_i 最多可以是 10910^9，但实际的索引仅限于 AA 中出现的值（最多有 N≤2×105N \le 2 \times 10^5 种），这样我们就可以减少所需的内存。
大多数语言都将关联数组作为标准功能。在 C++ 中，可以使用 map 或 unordered_map；在 Python 中，可以使用 dict。

代码

C++ 版本要高，否则 CE。
CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...