AtCoder Beginner Contest 161

A - ABC Swap

题意：略。

分析：略。

#include <bits/stdc++.h>
#define rep(i, a, b) for (long long i = a; i <= b; ++i)
#define mp make_pair
#define ll long long
#define SIZE 1005
using namespace std;
void io() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); }
int n, m, k;

int main() {
	io(); cin >> n >> m >> k;
	swap(n, m); swap(n, k);
	cout << n << ' ' << m << ' ' << k;
}

B - Popular Vote

题意：略。

分析：略。

#include <bits/stdc++.h>
#define rep(i, a, b) for (long long i = a; i <= b; ++i)
#define mp make_pair
#define ll long long
#define SIZE 1005
using namespace std;
void io() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); }
int n, m, k;
int main() {
	io(); cin >> n >> m;
	vector<double> a(n);
	double sum = 0;
	for (auto& i : a) cin >> i, sum += i;
	sum /= (4.0 * m);
	sort(a.begin(), a.end());
	reverse(a.begin(), a.end());
	rep(i, 0, (m - 1)) {
		if (a[i] < sum) {
			cout << "No";
			return 0;
		}
	}
	cout << "Yes";
}

C - Replacing Integer

题意：给定两个正整数 (N,K) ，你能够进行以下操作无限次：将 (N) 替换为 (|N-K|) 。询问所有操作中 (N) 的最小值。

分析：随便推导一下不难发现最小值只能是 (min(K\%N,K-K\%N)) 。

#include <bits/stdc++.h>
#define rep(i, a, b) for (long long i = a; i <= b; ++i)
#define mp make_pair
#define ll long long
#define SIZE 1005
using namespace std;
void io() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); }
ll k, n;

int main() {
	io(); cin >> n >> k;
	cout << min(n % k, k - n % k);
}

D - Lunlun Number

题意：定义 (Lunlun Number) 是指相邻每两位数字之差不超过 (1) 的数字，求第 (k) 大的 (Lunlun Number) 。

分析：假设某个 (Lunlun Number) 的末尾是 (k) ，那么由它能够引出的下一个 (Lunlun Number) 只能是在末尾加上 (k-1,k,k+1) 这三种情况（注意特判 (k=0,9) 的情况）。然后用这个性质 (BFS) 即可。

#include <bits/stdc++.h>
#define rep(i, a, b) for (long long i = a; i <= b; ++i)
#define mp make_pair
#define ll long long
#define SIZE 1005
using namespace std;
void io() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); }
ll k;
set<string> st;

int main() {
	io(); cin >> k;
	queue<string> q;
	rep(i, 1, 9) q.push(to_string(i));
	vector<ll> vec;
	while (st.size() <= 2e5) {
		string top = q.front();
		q.pop();
		st.insert(top);
		if (top.back() != '9' && top.back() != '0') {
			char ch = top.back(); --ch;
			q.push(top + ch);
			q.push(top + top.back());
			ch += 2;
			q.push(top + ch);
		}
		else if (top.back() == '0') {
			char ch = top.back(); ++ch;
			q.push(top + top.back());
			q.push(top + ch);
		}
		else {
			char ch = top.back(); --ch;
			q.push(top + ch);
			q.push(top + top.back());
		}
	}
	for (auto i : st) vec.emplace_back((ll)stoll(i));
	sort(vec.begin(), vec.end());
	cout << vec[k - 1];
}

E - Yutori

题意：(Takahashi) 在总共 (N) 天里一共要选择 (K) 个工作日，但是他每工作一天就要休息 (C) 天。给定一个由 (x,o) 构成的字符串，若 (s_i=x) 就代表第 (i) 天不能工作，询问哪几天是 (Takahashi) 没得选择，必须工作的。

分析：先考虑 (Takahashi) 在什么情况下不存在无法选择的情况，显然是贪心时至少存在 (K+1) 个可选工作日。因此，我们只需要考虑在贪心的情况下只存在 (K) 个工作日时，这 (K) 个工作日的分布，极端地考虑，我们正反贪心两次如果两次都需要工作的日子就必定是 (Takahashi) 的工作日了。

#include <bits/stdc++.h>
#define rep(i, a, b) for (long long i = a; i <= b; ++i)
#define mp make_pair
#define ll long long
#define SIZE 1005
using namespace std;
void io() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); }
ll n, k, c;

int main() {
	io(); cin >> n >> k >> c;
	string s; cin >> s;
	int pos = -1, res = 0;
	set<int> st, st2;
	rep(i, 0, (s.length() - 1)) {
		if (pos >= i || s[i] == 'x') continue;
		if (st.size() == k) {
			++res;
			break;
		}
		pos = i + c;
		st.insert(i);
	}
	if (res) return 0;
	pos = s.length();
	for (int i = s.length() - 1; i >= 0; --i) {
		if (pos <= i || s[i] == 'x') continue;
		if (st2.size() == k) {
			++res;
			break;
		}
		pos = i - c;
		if (st.count(i)) st2.insert(i);
	}
	if (res) return 0;
	for (auto i : st2) cout << i + 1 << '
';
}

F - Division or Substraction

题意：给定一个正整数 (N) ，然后你可以选择一个正整数 (K) 并执行以下两种操作：

如果 (N\%K=0) 则可以将当前的 (N) 替换为 (frac{N}{K}) ；
将 (N) 替换为 (N-K) 。

询问能将 (N) 转化为 (1) 的正整数 (K) 的数量。

分析：分成两部分考虑：一是 (N) 直接减去 (N-1) ，这种情况下的 (K) 就是 (N-1) 的所有因子；二是除了情况一以外的所有情况（就是需要考虑操作 (1) 的情况，情况一我们只考虑了操作 (2) ），这些情况下的 (K) 不难发现必定是 (N) 的因子，因此我们取出所有 (N) 的因子模拟即可。

这两种情况不存在相同的因子，因为相邻自然数互质。

#include <bits/stdc++.h>
#define rep(i, a, b) for (long long i = a; i <= b; ++i)
#define mp make_pair
#define SIZE 2010
#define ll long long
using namespace std;
void io() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); }
ll n;

int main() {
	io(); cin >> n;
	int ans = 1;
	for (ll i = 2; i * i <= n; ++i) {
		if (n % i == 0) {
			ll tmp = n;
			while (tmp % i == 0) tmp /= i;
			if ((tmp - 1) % i == 0) ans++;
			tmp = n;
			if (i * i == n) continue;
			ll x = n / i;
			while (tmp % x == 0) tmp /= x;
			if ((tmp - 1) % x == 0) ans++;
		}
	}
	if (--n > 1) ++ans;
	for (ll i = 2; i * i <= n; ++i) {
		if (n % i == 0) {
			ans += 2;
			if (i * i == n) --ans;
		}
	}
	cout << ans;
}