Codeforces Round #552 (Div. 3)

A - Restoring Three Numbers

#include <bits/stdc++.h>
using namespace std;
int a[4];
int main()
{
	for (int i = 0; i < 4; i++)
		scanf("%d", &a[i]);
	sort(a, a + 4);
	printf("%d %d %d", a[3] - a[0], a[3] - a[1], a[3] - a[2]);
}

B - Make Them Equal

如果只有两种数字并且差为偶数，除2

#include <bits/stdc++.h>
using namespace std;
map<int, int>mp;
int flag = -1;
int main()
{
	int n, t;
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &t);
		mp[t]++;
	}
	vector<int>v;
	for (auto it = mp.begin(); it != mp.end(); it++)
		v.push_back(it->first);
	if (v[0] == v[v.size() - 1])
	{
		printf("0");
		return 0;
	}
	int f = 0, s = 0;
	int cnt = mp.size();
	for (int i = 1; i < v.size(); i++)
	{
		if (v[i - 1] != v[i])
		{
			f = v[i] - v[i - 1];
			s = v[i];
			break;
		}
	}
	for (int i = 0; i < v.size(); i++)
	{
		if (v[i] != s)
		{
			if (v[i] < s && v[i] + f == s)
				;
			else if (v[i] > s && v[i] - f == s)
				;
			else
			{
				printf("-1");
				return 0;
			}
		}
	}
	if (cnt == 2 && f % 2 == 0)
		f /= 2;
	printf("%d", f);
}

C - Gourmet Cat

先把一个循环搞出来，然后算出剩下的，然后暴力模拟从周一到周日开始，跑循环

#include <bits/stdc++.h>
using namespace std;
int a[3], tt[3];
int eat[7] = { 0,1,2,0,2,1,0 };
int main()
{
	scanf("%d%d%d", &a[0], &a[1], &a[2]);
	int flag = 1e9;
	flag = min(flag, a[0] / 3);
	flag = min(flag, a[1] / 2);
	flag = min(flag, a[2] / 2);
	a[0] -= flag * 3;
	a[1] -= flag * 2;
	a[2] -= flag * 2;
	int ans = flag * 7;
	int temp = 0;
	for (int j = 0; j < 7; j++)
	{
		tt[0] = a[0], tt[1] = a[1], tt[2] = a[2];
		int t = 0;
		for (int i = j; i < 49; i++)
		{
			i %= 7;
			if (tt[eat[i]] > 0)
				tt[eat[i]]--;
			else
				break;
			t++;
		}
		temp = max(temp, t);
	}
	printf("%d", temp + ans);
}

D - Walking Robot

如果蓄电池的电量满了，那么即使实在太阳下，我们也选择蓄电池

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

E - Two Teams

删除的时候，将删除了的区间的左端点想上设为右端点，右端点向下设为左端点，然后，暴力他旁边的人的时候，跳着访问，249ms

#include <bits/stdc++.h>
using namespace std;
bool book[200005];
map<int, int>mp;
int ans[200005];
int toup[200005], todown[200005];
struct node
{
	int num;
	int index;
}que[200005];
auto cmp = [](node q, node w) {
	return q.num < w.num;
};
priority_queue<node, vector<node> ,decltype(cmp)>q(cmp);
vector<int>v1, v2;
int main()
{
	int n, m, cnt = 0;
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++)
	{
		toup[i] = i + 1;
		todown[i] = i - 1;
		scanf("%d", &que[i].num);
		que[i].index = i;
		q.push(que[i]);
		mp[que[i].index] = que[i].num;
	}
	while (!q.empty())
	{
		qwe:;
		if (q.empty())
			break;
		node temp = q.top();
		q.pop();
		if (book[temp.num] == true)
			goto qwe;
		book[mp[temp.index]] = true;
		if (cnt % 2 == 0)
		{
			int up = temp.index;
			int down = temp.index;
			v1.push_back(temp.index);
			for (int i = 1; i <= m; i++)
			{
				while (down >= 1 && book[mp[down]] == true)
					down = todown[down];
				if (down >= 1 && book[mp[down]] == false)
				{
					v1.push_back(down);
					book[mp[down]] = true;
				}
				while (up <= n && book[mp[up]] == true)
					up = toup[up];
				if (up <= n && book[mp[up]] == false)
				{
					v1.push_back(up);
					book[mp[up]] = true;
				}
			}
			toup[down] = up;
			todown[up] = down;
		}
		else
		{
			int up = temp.index;
			int down = temp.index;
			v2.push_back(temp.index);
			for (int i = 1; i <= m; i++)
			{
				while (down >= 1 && book[mp[down]] == true)
					down = todown[down];
				if (down >= 1 && book[mp[down]] == false)
				{
					v2.push_back(down);
					book[mp[down]] = true;
				}
				while (up <= n && book[mp[up]] == true)
					up = toup[up];
				if (up <= n && book[mp[up]] == false)
				{
					v2.push_back(up);
					book[mp[up]] = true;
				}
			}
			toup[down] = up;
			todown[up] = down;
		}
		cnt++;
	}
	for (int i = 0; i < v1.size(); i++)
		ans[v1[i]] = 1;
	for (int i = 0; i < v2.size(); i++)
		ans[v2[i]] = 2;
	for (int i = 1; i <= n; i++)
		printf("%d", ans[i]);
}

F - Shovels Shop

简单DP，先将价格数组排序，枚举到选了K个的情况，如果此时有选了K个的优惠，将选K个的优惠和最前的优惠取最大转移就可以了，赛时没时间想了。被E搞了好久。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
map<int, int>mp;
int a[200005];
ll dp[2005], pre[200005];
int main()
{
	int n, m, k;
	scanf("%d%d%d", &n, &m, &k);
	for (int i = 1; i <= n; i++)
		scanf("%d", &a[i]);
	while (m--)
	{
		int a, b;
		scanf("%d%d", &a, &b);
		mp[a] = max(mp[a], b);
	}
	sort(a + 1, a + 1 + n);
	for (int i = 1; i <= n; i++)
		pre[i] = pre[i - 1] + a[i];
	for (int i = 1; i <= k; i++)
	{
		dp[i] = dp[i - 1] + a[i];
		for (auto it = mp.begin(); it != mp.end(); it++)
		{
			if (it->first > i)
				break;
			dp[i] = min(dp[i], dp[i - it->first] + pre[i] - pre[i - it->first + it->second]);
		}
	}
	printf("%lld", dp[k]);
}

G - Minimum Possible LCM

找有公因子的最小的两个数的lcm的最小值

1、首先枚举公因子  从1-1e7

2、枚举含有公因子的数  ，每次都加上 

3、复杂度，证明请百度调和级数。

#include <bits/stdc++.h>
#define ll long long
using namespace std;
vector<int>v[10000005];
int s[1000005];
int main()
{
	int n, l, r;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &s[i]);
		v[s[i]].push_back(i);
	}
	ll ans = 1e18;
	for (int i = 1; i <= 100000000; i++)
	{
		int a = 0, b = 0;
		for (int j = i; j <= 10000000; j += i)
		{
			for (int k = 0; k < v[j].size(); k++)
			{
				if (a == 0)
					a = v[j][k];
				else if (b == 0)
				{
					b = v[j][k];
					break;
				}
			}
			if (b != 0)
				break;
		}
		if (b != 0)
		{
			if (ans > 1LL * s[a] * s[b] / i)
			{
				ans = 1LL * s[a] * s[b] / i;
				l = a;
				r = b;
			}
		}
	}
	if (l > r)
		swap(l, r);
	printf("%d %d", l, r);
}