Codeforces Round #560 (Div. 3)

补题记录

A. Remainder

#include <bits/stdc++.h>
using namespace std;
int n, m, k;
char s[200005];
int main()
{
	scanf("%d%d%d", &n, &m, &k);
	scanf("%s", s);
	int ans = 0;
	for (int i = 0; i < m; i++)
	{
		if (i == k)
		{
			if (s[n - 1 - i] == '0')
				ans++;
		}
		else
		{
			if (s[n - 1 - i] == '1')
				ans++;
		}
	}
	printf("%d", ans);
}

B. Polycarp Training

 #include <bits/stdc++.h>
using namespace std;
int a[200005];
int main()
{
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
		scanf("%d", &a[i]);
	sort(a, a + n);
	int j = 0, ans = 0;
	for (int i = 1; i <= n; i++)
	{
		while (a[j] < i && j < n)
			j++;
		if (j == n)
			break;
		ans++;
		j++;
	}
	printf("%d", ans);
}

C. Good String

暴力

#include <bits/stdc++.h>
using namespace std;
char s[200005];
vector<char>ans;
int main()
{
	int n;
	scanf("%d", &n);
	scanf("%s", s);
	for (int i = 0; i < n - 1;)
	{
		if (s[i] == s[i + 1])
			i++;
		else
		{
			ans.push_back(s[i]);
			ans.push_back(s[i + 1]);
			i += 2;
		}
	}
	printf("%d\n", n - ans.size());
	for (int i = 0; i < ans.size(); i++)
		printf("%c", ans[i]);
}

D. Almost All Divisors

如果存在答案，那么那个数一定是序列中最小的数和最大的数的乘积

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int a[305];
vector<int>v;
void calc(ll k)
{
	for (ll i = 2; i <= sqrt(k); i++)
	{
		if (k % i == 0)
		{
			v.push_back(i);
			if (i * i != k)
				v.push_back(k / i);
		}
	}
	sort(v.begin(), v.end());
}
int main()
{
	int T;
	scanf("%d", &T);
	while (T--)
	{
		v.clear();
		int n;
		scanf("%d", &n);
		for (int i = 0; i < n; i++)
			scanf("%d", &a[i]);
		sort(a, a + n);
		ll ans = 1LL * a[0] * a[n - 1];
		calc(ans);
		if (v.size() != n)
			printf("-1\n");
		else
		{
			for (int i = 0; i < n; i++)
			{
				if (a[i] != v[i])
				{
					printf("-1\n");
					goto qwe;
				}
			}
			printf("%lld\n", ans);
		}
		qwe:;
	}
}

E. Two Arrays and Sum of Functions

一个顺序，一个反序，这样相乘答案才会最小，注意要先算 a数组 的贡献，再排序相乘。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int n;
ll a[200005], b[200005];
const ll mod = 998244353;
int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)scanf("%lld", &a[i]);
	for (int i = 1; i <= n; i++)scanf("%lld", &b[i]);
	for (int i = 1; i <= n; i++)a[i] = (ll)(n - i + 1) * i * a[i];
	sort(a + 1, a + n + 1, [](ll q, ll w) {
		return q > w;
		});
	sort(b + 1, b + n + 1);
	ll ans = 0;
	for (int i = 1; i <= n; i++) {
		ans = (ans + ((a[i] % mod) * b[i] % mod) % mod) % mod;
	}
	printf("%lld", ans);
} 

F1. F2. Microtransactions (hard version)

二分天数，然后如果有打折，我们就在最后打折的那天买下需要的数量的物品，这样就可以做到能买到的打折的数量最多，（贪心），然后再从前往后判断，这一天是否有这么多钱，如果没有的话，就忽略掉这个打折，否则，买下这个打折的商品，然后我们统计有多少个还没有买的商品，在最后一天以每个2元的代价买下，最后如果剩下的钱非负，这个天数就合法，否则，不合法。

#include <bits/stdc++.h>
using namespace std;
int a[200005];
vector<int>v[200005];
bool vis[200005];
int buy[400005];
int cnt;
bool check(int mid)
{
	memset(buy, 0, sizeof(buy));
	memset(vis, false, sizeof(vis));
	for (int i = min(mid, 200000); i >= 1; i--)
	{
		for (int j = 0; j < v[i].size(); j++)
		{
			if (vis[v[i][j]] == false)
			{
				vis[v[i][j]] = true;
				buy[i] += a[v[i][j]];
			}
		}
	}
	int had = 0;
	int money = 0;
	for (int i = 1; i <= mid; i++)
	{
		money++;
		if (money >= buy[i])
		{
			money -= buy[i];
			had += buy[i];
		}
		else
		{
			had += money;
			money = 0;
		}
	}
	money -= (cnt - had) * 2;
	if (money >= 0)
		return true;
	else
		return false;
}
int main()
{
	int n, m;
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &a[i]);
		cnt += a[i];
	}
	for (int i = 0; i < m; i++)
	{
		int q, w;
		scanf("%d%d", &q, &w);
		v[q].push_back(w);
	}
	int l = cnt, r = cnt * 2;
	while (l + 1 < r)
	{
		int mid = (l + r) / 2;
		if (check(mid))
			r = mid;
		else
			l = mid;
	}
	if (!check(l))
		l = r;
	printf("%d", l);
}