AtCoder Beginner Contest 144

October 27, 2019

前四道签到，至少这次没翻车

A. 9×9

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <functional>
#include <map>

#define M 2001

using namespace std;

int main()
{
	int x, y;
	cin >> x >> y;
	if (x >= 1 && x <= 9 && y >= 1 && y <= 9)
		cout << x*y << endl;
	else
		cout << -1 << endl;

	return 0;
}

B. 81

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <functional>
#include <map>

#define M 2001

using namespace std;

int main()
{
	int x;
	cin >> x;
	for (int i = 1; i <= 9; i++)
	{
		if (x%i != 0)
			continue;
		int y = x / i;
		if (y >= 1 && y <= 9)
		{
			cout << "Yes" << endl;
			return 0;
		}
	}

	cout << "No" << endl;

	return 0;
}

C. Walk on Multiplication Table

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <functional>
#include <map>

#define M 2001

using namespace std;

int main()
{
	long long x;
	cin >> x;
	int q = (int)sqrt(x);

	long long m, n;

	for (int i = q; i >= 1; i--)
	{
		if (x%i == 0)
		{
			m = i;
			n = x / i;
			break;
		}
	}

	cout << m + n - 2 << endl;

	return 0;
}

D. Water Bottle

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <functional>
#include <map>

#define M 2001

using namespace std;

int main()
{
	int a, b, x, v;
	cin >> a >> b >> x;
	v = a*a*b;

	double Rad_to_deg = 45.0 / atan(1.0);

	if (x <= v/2)
	{
		double tan = double(a)*b*b / (2 * x);
		printf("%0.7lf\n", atan(tan)*Rad_to_deg);
	}
	else
	{
		double tan = double(v-x)*2/(a*a*a);
		printf("%0.7lf\n", atan(tan)*Rad_to_deg);
	}

	return 0;
}

做这道题的时候还有50多分钟，看题目大概猜到了是二分答案，然而当时没有想出来。只能说是不熟练吧，很久没做题大脑像生锈了一样，前四道题就花了40多分钟。其实这道题很简单，只是当时一下子短路了没想到怎么验证解是否可行（可能是受了上周那道题的影响，总想着要建立一个和k有关的不等式）。突然想起当年noip滚粗也是因为d2t1的二分答案，大概我和这类题绝缘吧，所以还是要多做题，下次争取能A5道，至少再碰到二分答案不要放弃。

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <functional>
#include <map>

#define M (long long)2e5+10

long long a[M], f[M], m[M];

using namespace std;

bool cmp(const long long a, const long long b)
{
	return a > b;
}

int main()
{
	long long n, k;
	long long maxl = -1;
	cin >> n >> k;

	for (long long i = 1; i <= n; i++)
		cin >> a[i];

	for (long long i = 1; i <= n; i++)
		cin >> f[i];

	sort(a + 1, a + n + 1);
	sort(f + 1, f + n + 1, cmp);

	for (long long i = 1; i <= n; i++)
	{
		m[i] = a[i] * f[i];
		maxl = max(maxl, m[i]);
	}

	long long l = 0, r = maxl, mid;
	while (l <= r)
	{
		mid = (l + r) >> 1;
		long long tot = 0;
		for (long long i = 1; i <= n; i++)
			if (m[i] > mid)
				tot += a[i] - mid / f[i];

		if (tot > k)
			l = mid + 1;
		else
			r = mid - 1;
	}

	cout << l << endl;

	return 0;
}

F. Fork in the Road

典型的dp，考场上没时间想了，再加上本身也不熟，下次加油吧，感觉1500至少能进个700名。

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <functional>
#include <map>

#define M 605

using namespace std;

int n, m;
double f[M], a[M], ans;
vector<int>G[M];

double dfs(int u)
{
	if (u == n)
		return 0;
	if (f[u] != 0)
		return f[u];
	for (int v : G[u])
		f[u] += dfs(v);
	return f[u] = f[u] / G[u].size() + 1;
}

int main()
{
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		int x, y;
		cin >> x >> y;
		G[x].push_back(y);
	}
	dfs(1);
	a[1] = 1;
	for (int i = 1; i < n; i++)							//经过第i个点的概率
		for (int j : G[i])
			a[j] += a[i] / G[i].size();
	for (int i = 1; i < n; i++)
		if (G[i].size() > 1)
		{
			double tmp = 0;
			for (int j : G[i])
				tmp += f[j];
			for (int j : G[i])
				ans = max(ans, a[i] * (f[i] - ((tmp - f[j]) / (G[i].size() - 1) + 1)));
		}
	printf("%.10f\n", f[1] - ans);

	return 0;
}