AtCoder Beginner Contest 398 A~D 题解

A - Doors in the Center

签到题。

• 若 \(N\) 为奇数，则输出 \(\frac{N-1}{2}\) 个 -、\(1\) 个 =、\(\frac{N-1}{2}\) 个 -。
• 若 \(N\) 为偶数，则输出 \(\frac{N}{2}-1\) 个 -、\(2\) 个 =、\(\frac{N}{2}-1\) 个 -。

这里有个偷懒的小技巧，在 C++ 里，由于 / 2（相当于 >> 1）是整除\(2\)，
所以N - 1 >> 1 在 \(N\) 为奇数时等同于 \(\frac{N-1}{2}\)（显而易见），在 \(N\) 为偶数时也等同于 \(\frac{N}{2}-1\)。

#include <iostream>
signed main(void) {
 int n;
 std::cin >> n;
 for (int i = 1; i <= n - 1 >> 1; i++)
 std::cout << '-';
 if (!(n % 2))
 std::cout << '=';
 std::cout << '=';
 for (int i = 1; i <= n - 1 >> 1; i++)
 std::cout << '-';
 std::cout << std::endl;
 return 0;
}

B - Full House 3

签到题。

用桶统计每个数值出现的次数。由于正整数 \(A_i \in [1,13]\)，故直接用一维数组即可，无需 map 或离散化。

想要偷懒就把这个桶降序 sort 一下，若 \(A_1 \ge 3\) 且 \(A_2 \ge 2\) 则输出 Yes，否则输出 No。

#include <iostream>
#include <algorithm>
int a[15];
signed main(void) {
 for (int i = 1, x; i <= 7; i++) {
 std::cin >> x;
 a[x]++;
 }
 std::sort(a + 1, a + 14, std::greater<int>());
 if (a[1] >= 3 && a[2] >= 2)
 std::cout << "Yes\n";
 else
 std::cout << "No\n";
 return 0;
}

C - Uniqueness

签到题。

直接用 map 之类作桶。
统计所有持有人数为 \(1\) 的 \(A_i\)，输出其中最大者对应的 \(i\) 即可。

用 unordered_map 方便些。

#include <iostream>
#include <unordered_map>
std::unordered_map<int, int> map;
int n, a[300005];
int x, ans = -1;
signed main(void) {
	std::cin >> n;
	for (int i = 1; i <= n; i++) {
	std::cin >> a[i];
	map[a[i]]++;
	}
	for (int i = 1; i <= n; i++)
	if (map[a[i]] == 1 && a[i] >= x) {
	x = a[i];
	ans = i;
	}
	std::cout << ans << '\n';
	return 0;
}

D - Bonfire

不很好想，不过有了思路之后其实也是签到题。

关键思路：物体的运动是相对的。（参见粤沪版物理八年级下册）
举个例子，我们以烟为参照物，风把烟向北吹，相当于人和篝火同时向南走，并且篝火在原来的位置留下一坨烟。
这样就好处理多了。

遍历每一次风吹，用 set 记下篝火到过的每一个位置。
若某次操作后人到了篝火到过的位置，也就是说那个位置有一坨烟，输出 1，否则输出 0。

#include <iostream>
#include <set>
#include <string>
int n, r, c;
int rf, cf;
std::string str;
std::set<std::pair<int, int>> path;
signed main(void) {
	std::cin >> n >> r >> c;
	std::cin >> str;
	path.insert({ 0, 0 });
	for (char i : str) {
	if (i == 'N') 
	rf++, r++;
	else if (i == 'S')
	rf--, r--;
	else if (i == 'E')
	cf--, c--;
	else
	cf++, c++;
	path.insert({ rf, cf });
	std::cout << path.count({ r, c });
	}
	std::cout << std::endl;
	return 0;
}