AtCoder Beginner Contest 048

A - AtCoder *** Contest

先输出首字母，然后遍历字符串，遇到空格就输出后面的第一个字符。

#include <bits/stdc++.h>

using namespace std;
using i64 = long long;

int main() {
	ios::sync_with_stdio(false), cin.tie(nullptr);
	string s;
	getline(cin, s);
	cout << s[0];
	for (int i = 0; i < s.size(); i++) {
		if (s[i] == ' ') cout << s[i + 1];
	}
	return 0;
}

B - Between a and b ...

如果暴力来做的话肯定会超时。问 \([a,b]\) 之间有多少数可以整除 \(x\)，考虑计算 \(x\) 的倍数 \(k\)。分别用 \(a\) 除以 \(x\) 上取整、\(b\) 除以 \(x\)（自然下取整）分别得到 \(k_1\)、\(k_2\)，则 \(k_1x\)、\(k_2x\) 是 \([a,b]\) 之间的两个数且能整除 \(x\)。答案即为 \(k_2-k_1+1\).

#include <bits/stdc++.h>

using namespace std;
using i64 = long long;

int main() {
	ios::sync_with_stdio(false), cin.tie(nullptr);
	i64 a, b, x;
	cin >> a >> b >> x;
	i64 k1 = (a + x - 1) / x, k2 = b / x;
	cout << k2 - k1 + 1;
	return 0;
}

C - Boxes and Candies

简单贪心。对于相邻的两个箱子，肯定优先吃右边箱子的糖果，因为其可以兼顾左边和右边。

首先需要注意的是 \(a[i]+a[i-1]\) 有可能爆 \(\rm int\)，需要开 \(\rm long\) \(\rm long\)。

一开始的做法：WA 了最后四个点。

#include <bits/stdc++.h>

using namespace std;
using i64 = long long;

int main() {
	ios::sync_with_stdio(false), cin.tie(nullptr);
	int N, x;
	cin >> N >> x;
	vector<int> a(N);
	for (int i = 0; i < N; i++) cin >> a[i];
	i64 ans = 0;
	for (int i = 1; i < N; i++) {
		i64 sum = a[i] + a[i - 1];
		if (sum > x) {
			i64 t = sum - x;
			a[i] -= t;
			ans += t;
		}
	}
	cout << ans;
	return 0;
}

这里犯的错误在于，\(a[i]+a[i-1]\) 比 \(x\) 多出的那一块，\(a[i]\) 不一定够减的，这时就需要将 \(a[i-1]\) 也减去。

代码：

#include <bits/stdc++.h>

using namespace std;
using i64 = long long;

int main() {
	ios::sync_with_stdio(false), cin.tie(nullptr);
	int N, x;
	cin >> N >> x;
	vector<int> a(N);
	for (int i = 0; i < N; i++) cin >> a[i];
	i64 ans = 0;
	for (int i = 1; i < N; i++) {
		i64 sum = a[i] + a[i - 1];
		if (sum > x) {
			i64 t = sum - x;
			if (a[i] >= t) {
				a[i] -= t;
				ans += t;
			} else {
				a[i] = 0;
				a[i - 1] -= (t - a[i]);
				ans += t;
			} 
		}
	}
	cout << ans;
	return 0;
}

D - An Ordinary Game

思维题。

我们发现：当删除到无法删除时，字符串一定是这样的：\(abababab...abab\)，即字符串中出现且只出现两种不同的字符，且所有奇数下标位置上的字符相同，所有偶数下标位置上的字符相同,即奇偶交替出现（或只剩两个，但也可以看作这种情况）

哪方操作后率先出现这样的死局，哪方先获胜。当字符串长度为奇数时，首尾字符下标均为奇数，若首尾字符不同则最后一定无法在己方形成死局，己方获胜。反之，当字符串长度为偶数且首尾字符不同时，我做了一步操作之后对方进入必胜态。

当首尾字符相同时，如果字符串长度为奇数我方必败（形成死局），反之则胜。

#include <bits/stdc++.h>

using namespace std;
using i64 = long long;

int main() {
	ios::sync_with_stdio(false), cin.tie(nullptr);
	string s;
	cin >> s;
	int n = s.size();
	if ((n % 2 == 1 && s[0] != s[n - 1]) || (n % 2 == 0 && s[0] == s[n - 1])) cout << "First";
	else cout << "Second";
	return 0;
}