Atcoder ABC388个人游记（A~E）

比赛链接

A. ?UPC

题面

给你一个字符串 $S$ 。在这里， $S$ 的第一个字符是大写英文字母，第二个和后面的字符是小写英文字母。
打印由 $S$ 的第一个字符和 UPC 按此顺序连接而成的字符串。

思路

a题难度稳定依旧炒鸡简单，按题意模拟即可。

代码

1
2
3
4
5
6
7
8
9
#include<bits/stdc++.h>
using namespace std;
int main()
{
	char s;
	cin >> s;
	cout << s << "UPC";
	return 0;
}

B.Heavy Snake

题面

有 $N$ 条蛇。

最初， $i$ (条)蛇的厚度是 $T_i$ ，长度是 $L_i$ 。

蛇的重量定义为其厚度和长度的乘积。

对于满足 $1 \leq k \leq D$ 的每个整数 $k$ ，求每条蛇的长度增加 $k$ 时最重的蛇的重量。

$1 \leq N, D \leq 100$
$1 \leq T_i, L_i \leq 100$

思路

还是一道签到题，$N$的范围小的可怜，直接模拟即可，不再过多赘述

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
using namespace std;
int n, d;
struct node {
	int x, y;
} a[114514];
int main()
{
	cin >> n >> d;
	for (int i = 1; i <= n; i++) {
		cin >> a[i].x >> a[i].y;
	}
	for (int i = 1; i <= d; i++) {
		for (int i = 1; i <= n; i++) {
			a[i].y++;
		}
		int maxx = 0;
		for (int i = 1; i <= n; i++) {
			maxx = max(maxx, a[i].x * a[i].y);
		}
		cout << maxx << '\n';
	}
	return 0;
}

C.Various Kagamimochi

题面

有 $N$ 个麻糬（年糕），按大小升序排列。第 $i$ 个麻糬 $(1 \leq i \leq N)$ 的大小是 $A_i$ 。

给定大小分别为 $a$ 和 $b$ 的两个麻糬 $A$ 和 $B$ ，当且仅当 $a$ 至多是 $b$ 的一半时，将麻糬 $A$ 放在麻糬 $B$ 的上面，就可以做出一个叠年糕。

你从 $N$ 个年糕中选择两个年糕，并将一个放在另一个上面，组成一个叠年糕。

求可以做出多少种不同的叠年糕。

如果至少有一个麻糬是不同的，即使麻糬的大小相同，也能区分出两种不同的麻糬。

$2 \leq N \leq 5 \times 10^5$
$1 \leq A_i \leq 10^9 \ (1 \leq i \leq N)$
$A_i \leq A_{i+1} \ (1 \leq i \leq N)$

思路

终于是来一道需要大概想一想的题了…

这个数据范围明显可以二分，我们先把数组给从小到大排序，然后从前到后遍历，在还没有遍历到的数组部分内lower_bound查找当前数的两倍，算一下离末尾的距离就行了。

但是！Atcoder怎么可能这么轻松就让你过呢？

重要的事情说三遍:

不开long long见祖宗！

代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	sort(a.begin(), a.end());
	long long ans = 0;
	for (int i = 0; i < n; i++) {
		int aa = a[i];
		auto it = lower_bound(a.begin() + i + 1, a.end(), 2 * aa);
		ans += a.end() - it;
	}
	cout << ans;
	return 0;
}

D.Coming Of Age Celebration

题面

在某个星球上，有 $N$ 名外星人，他们都是未成年人。

其中 $i$ 个外星人目前拥有 $A_i$ 颗宝石，并将在 $i$ 年后成为成年人。

当这个星球上有人成年时，每个至少拥有一块宝石的成年人都会向刚刚成年的外星人赠送一块宝石作为贺礼。

求 $N$ 年后每个外星人将拥有多少块石头。

假设未来不会有新的外星人诞生。

思路

由题意可知：每个人最多可以给出min( $A_i$ , $n-i$ )块宝石，因为一个人只能在自己成年后的那 $n-i$ 年给出宝石

对于每个人 $j$ ，他们给出宝石的范围是 $(j+1)$ ~ $(j+c_j)$

我们使用差分数组在这些范围内加 $1$ ，然后通过前缀和得到每个人收到的宝石总数。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	vector<ll> a(n);
	for (auto &x : a) cin >> x;
	vector<ll> c(n, 0);
	for (int i = 0; i < n; i++) c[i] = min(a[i], (ll)(n - i - 1));
	int max_iters = 10;
	while (max_iters--) {
		vector<ll> add(n + 2, 0LL);
		for (int j = 0; j < n; j++) {
			if (c[j] == 0) continue;
			ll l = j + 1;
			ll r = j + c[j];
			if (l >= n) continue;
			r = min(r, (ll)(n - 1));
			add[l] += 1;
			if (r + 1 < n) add[r + 1] -= 1;
		}
		vector<ll> received(n, 0);
		received[0] = add[0];
		for (int i = 1; i < n; i++) received[i] = received[i - 1] + add[i];
		bool changed = false;
		for (int i = 0; i < n; i++) {
			ll new_c = min(a[i] + received[i], (ll)(n - i - 1));
			if (new_c != c[i]) {
				c[i] = new_c;
				changed = true;
			}
		}
		if (!changed) break;
	}
	vector<ll> add_final(n + 2, 0LL);
	for (int j = 0; j < n; j++) {
		if (c[j] == 0) continue;
		ll l = j + 1;
		ll r = j + c[j];
		if (l >= n) continue;
		r = min(r, (ll)(n - 1));
		add_final[l] += 1;
		if (r + 1 < n) add_final[r + 1] -= 1;
	}
	vector<ll> received_final(n, 0);
	received_final[0] = add_final[0];
	for (int i = 1; i < n; i++) received_final[i] = received_final[i - 1] + add_final[i];
	vector<ll> final_gems(n, 0);
	for (int i = 0; i < n; i++) {
		ll given = c[i];
		ll received = received_final[i];
		final_gems[i] = a[i] - given + received;
	}
	for (int i = 0; i < n; i++) {
      cout << final_gems[i] << ' ';
    }
}

E.Simultaneous Kagamimochi

题面

有 $N$ 个麻糬（年糕），按大小升序排列。其中 $i$ 个年糕的大小是 $A_i$ 。

给定大小分别为 $a$ 和 $b$ 的两个年糕 $A$ 和 $B$ ，当且仅当 $a$ 至多是 $b$ 的一半时，将年糕 $A$ 放在年糕 $B$ 的上面，就可以做出一个叠年糕。

求可以同时制作多少个叠年糕。

更精确地讲，求能同时制作出下面这些麻糬的最大非负整数 $K$ ：

从 $N$ 个麻糬中选择 $2K$ 个组成 $K$ 对。在每对年糕中，将一个放在另一个的上面，做成 $K$ 个叠年糕。

思路

匹配问题，用双指针就OK了

初始化两个指针，left指向序列的起始位置，right指向序列的中点。

遍历序列，移动right指针，找到最小的 $b_j$ 使得 $a_i <= b_j / 2$ 。

每当找到一个满足条件的配对时，增加计数并移动两个指针。

一直重复直到任一指针超出序列范围。

代码

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int n;
	cin >> n;
	vector<ll> a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	int left = 0, right = n / 2;
	int count = 0;
	while (left < n / 2 && right < n) {
		if (a[left] <= a[right] / 2) {
			count++;
			left++;
			right++;
		} else {
			right++;
		}
	}
	cout << count;
	return 0;
}

总结

最近的atcoder题目排版非常贴心…测试点还有hack…真是做的一天比一天难受了:(

不过这次算幸运的，5题还不错，继续加油吧！

当然你能看到这里，也算尊重我的成果，谢谢！祝好运！

GOODBYE