AtCoder Beginner Contest 281 (A-D)

A

题意：输入一个整数，输出(n + 1)行，从n一直输出到0.

解法/思路：一个循环完事儿。

代码：

#include <iostream>
using namespace std;
int main() {
	int n;
	cin >> n;
	for (int i = n; i >= 0; --i) {
		cout << i << endl;
	}
	return 0;
}

B

题意：判断字符串s是否满足以下条件：

·总长度为8

·第1个和第8个字符均为大写字母

·第2-7个字符的组合为一个不含前导0的六位整数

解法/思路：简单的if判断即可。

代码：

#include <iostream>
#include <string>
using namespace std;
int main() {
	string s;
	cin >> s;
	int len = s.length();
	if (len == 8 && 65 <= s[0] && s[0] <= 90 && 65 <= s[7] && s[7] <= 90 && 49 <= s[1] && s[1] <= 57) {
		for (int i = 2; i <= 6; ++i) {
			if (s[i] <= 47 || s[i] >= 58) {
				cout << "No";
				return 0;
			}
		}
		cout << "Yes";
	} else {
		cout << "No";
	}
	return 0;
}

C

题意：歌单总共包含n首歌，每首歌的播放时间为a_i列表循环播放，问经过时间t后播放到第几首歌的什么时间点。

解法/思路：先统计出播放整个歌单所需时间sum，t模等于sum，就可以消去循环歌单的时间，最后从第一首个开始逐个减去每首歌的时长，终止条件为t <= a_i，即结束时播放到第i首歌。

代码：

#include <iostream>
using namespace std;
#define ll long long
ll a[100005];
int main() {
	ll n, t;
	ll sum = 0;
	cin >> n >> t;
	for (ll k = 1; k <= n; ++k) {
		cin >> a[k];
		sum += a[k];
	}
	t %= sum;
	ll p = 1;
	while (t > a[p]) {
		t -= a[p];
		++p;
	}
	cout << p << ' ' << t;
	return 0;
}

D

题意：在有n个数的数组中取出k个数，求出当这k个数的和s为d的倍数时最大的s。

解法/思路：暴力枚举显然会超时，所以考虑动态规划。用dp[x][y][z]表示在前x个数中取y个数，其和s模d等于z时的最大的s，答案为dp[n][k][0]。对于每个a[x]，都有取或不取两种情况。若不取，则dp[x][y][z] = dp[x - 1][y][z]。若取，则dp[x][y][z] = dp[x - 1][y - 1][prev] + a[x]。其中prev = ((z - a[x]) % d + d) % d，这样就能保证prev一定在[0, d - 1]范围内。需要注意的是，若dp[x - 1][y - 1][prev] = -1，则该"状态"是不可达的，令dp[x][y][z] = dp[x - 1][y - 1][prev] + a[x]显然不符合逻辑。

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
ll a[105];
ll dp[105][105][105];
int main() {
	ll n, k, d;
	scanf("%lld %lld %lld", &n, &k, &d);
	for (ll i = 1; i <= n; ++i) {
		scanf("%lld", &a[i]);
	}
	memset(dp, -1, sizeof(dp));
	dp[0][0][0] = 0;
	for (ll x = 1; x <= n; ++x) {
		for (ll y = 0; y <= min(x, k); ++y) {
			for (ll z = 0; z <= d - 1; ++z) {
				dp[x][y][z] = dp[x - 1][y][z];
				ll prev = ((z - a[x]) % d + d) % d;
				if (dp[x - 1][y - 1][prev] != -1 && y > 0) {                    // 注意这里的判断条件
					dp[x][y][z] = max(dp[x][y][z], dp[x - 1][y - 1][prev] + a[x]);
				}
			}
		}
	}
	printf("%lld", dp[n][k][0]);
	return 0;
}