AtCoder Beginner Contest 280 (A-D)

本人第一次写博客，若有不足还望指出( •̀ ω •́ )✧

A

题意：输入一个H行W列的字符矩阵，统计'#'的个数。

解法/思路：挺简单的，直接贴代码吧。

代码：

#include <iostream>
#include <string>
using namespace std;
int main() {
	int n, m, ans = 0;
	cin >> n >> m;
	for (int i = 0; i < n; ++i) {
		string temp;
		cin >> temp;
		for (int j = 0; j < m; ++j) {
			if (temp[j] == '#') {
				++ans;
			}
		}
	}
	cout << ans;
	return 0;
}

B

题意：输入n个整数A₁, A₂ ... A_n，输出n个整数B₁, B₂ ... B_n，使得对于任意A_i，A_i = B₁ + B₂ + ... + B_i。

解法/思路：令A₀ = 0，显然B_i = A_i - A_i-1。

代码：

#include <iostream>
using namespace std;
int a[11];
int main() {
	int n;
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
	}
	for (int i = 1; i <= n; ++i) {
		cout << a[i] - a[i - 1] << ' ';
	}
	return 0;
}

C

题意：字符串t是由字符串s插入一个小写字母得到的，问这个字母是t的第几个字符，若有多种可能，输出任意一种

解法/思路：逐个字符对比，找到第一个不同的即可。

代码：

#include <iostream>
#include <string>
using namespace std;
string s, t;
int main() {
	cin >> s >> t;
	int len = t.length();
	for (int i = 0; i < len; ++i) {
		if (s[i] != t[i]) {
			cout << i + 1;
			return 0;
		}
	}
}

D

题意：输入整数k，找到最小的n使得n!是k的倍数。

解法/思路：显然需要对k进行分解质因数。虽然k的范围是[1, 1e12]，但实际上，大于√k的质因数至多只有一个。故只要在[1, 1e6]内查找k的质因数，再判断k分解到最后是否大于1即可。需要注意的是本题的答案不一定等于最大质因数，要考虑k的质因数分解的次数，例如，若k = 1120 = 2⁵∗5¹∗7¹，n = 8。确定x!包含k分解结果的方法：质因数p在x!中出现的次数等于[x/p¹] + [x/p²] + ... + [x/p^m] (p^m <= x)。拿9!举例，2的次数为[9/2] + [9/4] + [9/8] = 7。最后在[1, k]内找出n。

代码：

#include <iostream>
using namespace std;
typedef long long ll;
ll p[1000005];							// 记录k的质因数
ll cnt[1000005];						// 记录每个质因数的次数
ll num;									// 共有多少个质因数
bool check(ll mid);
int main() {
	ll k, k2, i;
	cin >> k;
	k2 = k;
	if (k % 2 == 0) {
		++num;
		p[1] = 2;
		while (k % 2 == 0) {
			k /= 2;
			++cnt[1];
		}
	}
	for (i = 3; i <= 1000000; i += 2) {
		if (k % i == 0) {
			p[++num] = i;
			while (k % i == 0) {
				k /= i;
				++cnt[num];
			}
		}
	}
	if (k > 1) {						// k > 1，此时的k一定是原来的k的大于1e6的质因数
		p[++num] = k;
		cnt[num] = 1;
	}
	// 数组p和cnt处理完毕
	ll l = 1, r = k2, mid;				// 用二分的思想，在[1, k]内寻找答案
	while (l < r) {
		mid = (l + r) >> 1;
		if (check(mid)) {				// 如果mid符合条件，在[l, mid]继续寻找
			r = mid;
		} else {						// 如果不符合，在[mid+1, r]继续寻找
			l = mid + 1;
		}
	}
	cout << l;
	return 0;
}
bool check(ll mid) {
	ll i, j, tot;						// 用tot记录质因数p[i]在mid!中的次数
	for (i = 1; i <= num; ++i) {
		tot = 0;
		for (j = p[i]; j <= mid; j *= p[i]) {
			tot += mid / j;
		}
		if (tot < cnt[i]) {
			return false;
		}
	}
	return true;
}