Codeforces Round #583 (Div. 1 + Div. 2, based on Olympiad of Metropolises)

A - Optimal Currency Exchange

跑一个完全背包暴力一下答案。

#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
bool dp[100000005];
int main()
{
	ll n, d, e;
	sc("%lld%lld%lld", &n, &d, &e);
	e *= 5;
	dp[0] = true;
	for (int i = d; i <= n; i++)
	{
		if (dp[i - d])
			dp[i] = true;
	}
	for (int i = e; i <= n; i++)
	{
		if (dp[i - e])
			dp[i] = true;
	}
	ll ans = 1e9;
	for (int i = n; i >= 0; i--)
	{
		if (dp[i])
		{
			pr("%lld\n", n - i);
			return 0;
		}
	}
}

B - Badges

因为保证a+b>n，所以不会有重复，直接减就可以

#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
bool dp[100000005];
int main()
{
	int a, b, n;
	sc("%d%d%d", &a, &b, &n);
	int ans = n + 1;
	if (a < n)
	{
		ans -= n - a;
	}
	if (b < n)
	{
		ans -= n - b;
	}
	pr("%d", ans);
}

C - Bad Sequence

#include <bits/stdc++.h>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
char s[200005];
int main()
{
	int n;
	sc("%d", &n);
	sc("%s", s);
	if (n & 1)
	{
		puts("No");
		return 0;
	}
	int l = 0, minn = 0;
	for (int i = 0; i < n; i++)
	{
		if (s[i] == '(')
			l++;
		else
		{
			l--;
			minn = min(minn, l);
		}
	}
	if (l == 0 && minn >= -1)
		puts("Yes");
	else
		puts("No");
}

D - Treasure Island

首先答案最大是2，因为我们可以通过[1,2],[2,1]来使他不能到达终点，考虑两次BFS，第一次求尽量向右走的路径，第二次求尽量向下走的路径，如果走不到终点，输出0，否则，如果两条路径有重合输出1，否则输出2。

#include<bits/stdc++.h>
#define Pair pair<int,int>
#define sc scanf
#define pr printf
using namespace std;
int main()
{
	int n, m;
	scanf("%d%d", &n, &m);
	char s[n + 1][m + 1];
	for (int i = 1; i <= n; ++i)
		scanf("%s", s[i] + 1);
	int sum[n + 1][m + 1];
	bool vis[n + 1][m + 1];
	memset(sum, 0, sizeof(sum));
	Pair fa[n + 1][m + 1];
	vector<Pair>v;
	//bfs1
	queue<Pair>q1;
	int dir1[2][2] = { 0,1,1,0 };
	q1.push(Pair{ 1,1 });
	memset(vis, false, sizeof(vis));
	vis[1][1] = true;
	while (!q1.empty())
	{
		Pair t = q1.front();
		q1.pop();
		for (int k = 0; k < 2; k++)
		{
			int tx = t.first + dir1[k][0];
			int ty = t.second + dir1[k][1];
			if (tx<1 || tx>n || ty<1 || ty>m)continue;
			if (vis[tx][ty] == false && s[tx][ty] == '.')
			{
				vis[tx][ty] = true;
				q1.push(Pair{ tx,ty });
				fa[tx][ty] = t;
			}
			if (tx == n && ty == m)
			{
				t = Pair{ tx,ty };
				t = fa[t.first][t.second];
				while (t.first != 1 || t.second != 1)
				{
					v.push_back(t);
					t = fa[t.first][t.second];
				}
				goto qwe1;
			}
		}
	}
	qwe1:;
	//bfs2
	queue<Pair>q2;
	int dir2[2][2] = { 1,0,0,1 };
	q2.push(Pair{ 1,1 });
	memset(vis, 0, sizeof(vis));
	vis[1][1] = true;
	while (!q2.empty())
	{
		Pair t = q2.front();
		q2.pop();
		for (int k = 0; k < 2; k++)
		{
			int tx = t.first + dir2[k][0];
			int ty = t.second + dir2[k][1];
			if (tx<1 || tx>n || ty<1 || ty>m)continue;
			if (vis[tx][ty] == false && s[tx][ty] == '.')
			{
				vis[tx][ty] = true;
				q2.push(Pair{ tx,ty });
				fa[tx][ty] = t;
			}
			if (tx == n && ty == m)
			{
				t = Pair{ tx,ty };
				t = fa[t.first][t.second];
				while (t.first != 1 || t.second != 1)
				{
					v.push_back(t);
					t = fa[t.first][t.second];
				}
				goto qwe2;
			}
		}
	}
	qwe2:;
	sort(v.begin(), v.end());
	if (v.size() == 0)
		pr("0\n");
	else if (unique(v.begin(), v.end()) != v.end())
		pr("1\n");
	else
		pr("2\n");
}
/*
3 4
....
.#.#
..#.
 
*/

E - Petya and Construction Set

给出n个长度，第i个长度点2*i-1与2*i的距离，求一颗满足上述条件的2*n个结点的数（保证答案一定存在

1、构造，考虑将两个点看成一条链，然后从大到小排序

2、我们以最长链作为主链，那么只要我们把主链填满了，剩下的所有链都可以加在主链上。

3、考虑如何填满主链，从左向右遍历找到一个主链没有放结点的位置，然后将当前最长的链的一头放在这个节点上，然后向后延伸，那么他的另一个结点有三种情况

        a、主链上放不下，那么他一定要放在主链的尾部的下一个结点，即将主链延长（因为长度是有序的

        b、主链上能放下，并且这个位置没有放结点，那么我们考虑将这个点放在主链上。

        c、主链上能放下，但这个位置有别的结点，那么我们考虑让这个点和这个位置的前一个位置的点连接。

4、主链构造满之后，剩下的所有链，第一个点连主链的第一个点，然后根据长度计算下一个点的位置就可以。

5、在 3c 构造的时候，注意 这个位置的前一个位置 不一定存在点，所以我们是让这个点和前一个位置直接连接，最后输出的时候，在根据位置来找输出的值。

#include <bits/stdc++.h>
#define Pair pair<int,int>
#define ll long long
#define sc scanf
#define pr printf
using namespace std;
const int MAXN = 1e6 + 10;
int n, len, path1[MAXN], path2[MAXN], pos[MAXN];
//path1表示主链上的点
//path2表示与主链上的某个点相接
//pos表示与非主链上的点相接
Pair in[MAXN];
int u = 2;
int main()
{
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i)
	{
		scanf("%d", &in[i].second);
		in[i].first = i;
	}
	sort(in + 1, in + 1 + n, [](Pair q, Pair w) {
		return q.second > w.second;
		});
	path1[1] = in[1].first * 2;
	len = in[1].second + 1;
	path1[len] = in[1].first * 2 - 1;
	//构造主链 
	for (int i = 2; i <= len; ++i)
	{
		if (path1[i] != 0)
			continue;
		path1[i] = in[u].first * 2;
		int second = in[u].second + i;
		if (second > len)
		{
			path1[len + 1] = in[u].first * 2 - 1;
			++len;
		}
		else
		{
			if (path1[second] != 0)
				pos[in[u].first * 2 - 1] = second - 1;
			else
				path1[second] = in[u].first * 2 - 1;
		}
		++u;
	}
	//加边 
	while (u <= n)
	{
		path2[in[u].first * 2] = path1[1];
		if (in[u].second == 1)
			path2[in[u].first * 2 - 1] = in[u].first * 2;
		else
			path2[in[u].first * 2 - 1] = path1[in[u].second - 1];
		++u;
	}
	//output
	for (int i = len; i >= 2; i--)
		printf("%d %d\n", path1[i], path1[i - 1]);
	for (int i = 1; i <= 2 * n; ++i)
	{
		if (path2[i])
			printf("%d %d\n", i, path2[i]);
		if (pos[i])
			printf("%d %d\n", i, path1[pos[i]]);
	}
}