GoodCoder666的个人博客

AtCoder Beginner Contest 194 A~E 题解

2021-03-17 · 12 min read
C++ 算法竞赛

A - I Scream

题目大意

在日本，有如下四种冰淇淋产品：

  • 至少有15%15\%的milk solids和8%8\%的milk fat的产品称为“冰淇淋”；
  • 至少有10%10\%的milk solids和3%3\%的milk fat且不是冰淇淋的产品称为“冰奶”；
  • 至少有3%3\%的milk solids且不是冰淇淋或冰奶**的产品称为“乳冰”；
  • 不是以上三种的产品称为“调味冰”。

在这里，milk solids由milk fat和milk solids-not-fat组成。
有一种冰淇淋产品，它由A%A\%的milk solids-not-fat和B%B\%的milk fat组成。
这种产品是上述的哪一类？

0≤A,B≤1000\le A,B\le 100
0≤A+B≤1000\le A+B\le 100

输入格式

A BA~B

输出格式

请按如下格式输出类别：

  • 如果这是冰淇淋，输出11；
  • 如果这是冰奶，输出22；
  • 如果这是乳冰，输出33；
  • 如果这是调味冰，输出44。

样例

AA BB 输出
1010 88 11
11 22 33
00 00 44

分析

只需将AA加上BB（变为milk solids的占比），再按题目所说的判断即可。

代码

#include <cstdio>
using namespace std;

int main()
{
	int a, b;
	scanf("%d%d", &a, &b);
	a += b;
	if(a >= 15 && b >= 8) puts("1");
	else if(a >= 10 && b >= 3) puts("2");
	else if(a >= 3) puts("3");
	else puts("4");
	return 0;
}

B - Job Assignment

题目大意

你的公司有NN位员工，他们叫员工11，员工22，……，员工NN。
你有两份重要工作要完成——工作A和工作B。
员工ii可以在AiA_i分钟内完成工作A并在BiB_i分钟内完成工作B。
你要将两个工作分别分给某一位员工。
假设工作A分给了员工ii，工作B分给了员工jj，将要花的分钟数设为tt，则：

t={Ai+Bi(i=j)max⁡{Ai,Bj}(i≠j)t= \begin{cases} A_i+B_i & (i=j) \\ \max\{A_i,B_j\} & (i\ne j) \\ \end{cases}

求最小的tt。

2≤N≤10002\le N\le 1000
1≤Ai,Bi≤1051\le A_i,B_i\le 10^5

输入格式

NN
A1 B1A_1~B_1
A2 B2A_2~B_2
⋮\vdots
AN BNA_N~B_N

输出格式

输出答案。

样例

略，请自行前往AtCoder查看

分析

这题由于NN最大只有10310^3，所以枚举是完全可行的，只要枚举所有的(i,j)(i,j)，再根据题目里的公式求出答案取最小值即可，这样做总时间复杂度为O(n2)\mathcal O(n^2)。
另外，本题也有贪心的O(n)\mathcal O(n)的算法，但是情况太多，代码太麻烦，所以这里不写。

代码

#include <cstdio>
#define maxn 1005
#define INF 2147483647
using namespace std;

int a[maxn], b[maxn];

inline void setmin(int& x, int y) { if(y < x) x = y; }
inline int max(int x, int y) { return x > y ? x : y; }

int main()
{
	int n;
	scanf("%d", &n);
	for(int i=0; i<n; i++)
		scanf("%d%d", a + i, b + i);
	int ans = INF;
	for(int i=0; i<n; i++)
	{
		setmin(ans, a[i] + b[i]); // i == j
		for(int j=i+1; j<n; j++)
		{
			setmin(ans, max(a[i], b[j]));
			setmin(ans, max(a[j], b[i]));
		}
	}
	printf("%d\n", ans);
	return 0;
}

C - Squared Error

题目大意

给你一个长度为NN的序列AA。
输出∑i=2N∑j=1i−1(Ai−Aj)2\displaystyle \sum_{i = 2}^{N} \sum_{j = 1}^{i - 1} (A_i - A_j)^2。

2≤N≤3×1052 \le N \le 3 \times 10^5
∣Ai∣≤200|A_i| \le 200

输入格式

NN
A1 A2 A3 … ANA_1~A_2~A_3~\dots~A_N

输出格式

输出一行，即∑i=2N∑j=1i−1(Ai−Aj)2\displaystyle \sum_{i = 2}^{N} \sum_{j = 1}^{i - 1} (A_i - A_j)^2。

样例

样例输入1

3
2 8 4

样例输出1

56

通过计算，我们得到∑i=2N∑j=1i−1(Ai−Aj)2=(8−2)2+(4−2)2+(4−8)2=56\displaystyle \sum_{i = 2}^{N} \sum_{j = 1}^{i - 1} (A_i - A_j)^2 = (8 - 2)^2 + (4 - 2) ^ 2 + (4 - 8) ^ 2 = 56。

样例输入2

5
-5 8 9 -4 -3

样例输出2

950

分析

根据公式(a−b)2=a2+b2−2ab(a-b)^2=a^2+b^2-2ab，我们可以使用如下推理：

∑i=2N∑j=1i−1(Ai−Aj)2\sum_{i = 2}^{N} \sum_{j = 1}^{i - 1} (A_i - A_j)^2

∑i=2N∑j=1i−1Ai2+Aj2−2AiAj\sum_{i = 2}^{N} \sum_{j = 1}^{i - 1} {A_i}^2+{A_j}^2-2A_iA_j

(∑i=2N∑j=1i−1Ai2)+(∑i=2N∑j=1i−1Aj2)−(∑i=2N∑j=1i−12AiAj)(\sum_{i = 2}^{N} \sum_{j = 1}^{i - 1} {A_i}^2)+(\sum_{i = 2}^{N} \sum_{j = 1}^{i - 1} {A_j}^2)-(\sum_{i = 2}^{N} \sum_{j = 1}^{i - 1} 2A_iA_j)

这时，我们设Si=∑j=1i−1AiS_i=\sum\limits_{j=1}^{i-1} A_i，则：

(n−1)(∑i=1NAi2)−2(∑i=1NSiAi)(n-1)(\sum_{i = 1}^{N} {A_i}^2)-2(\sum_{i = 1}^{N} S_iA_i)

这时，计算所有SiS_i的时间复杂度为O(n)\mathcal O(n)，求最终结果的时间复杂度也是O(n)\mathcal O(n)，所以总时间复杂度为O(n)\mathcal O(n)。

代码

#include <cstdio>
#define maxn 300005
using namespace std;

using LL = long long;

int main()
{
	int n, s1 = 0;
	scanf("%d", &n);
	LL s2 = 0, m = 0LL;
	for(int i=0; i<n; i++)
	{
		LL x;
		scanf("%lld", &x);
		m += x * s1;
		s1 += x, s2 += x * x;
	}
	m <<= 1LL, s2 *= n - 1LL;
	printf("%lld\n", s2 - m);
	return 0;
}

D - Journey

题目大意

我们有一个NN个顶点（称为顶点11、顶点22、……、顶点NN）。
目前，这个图没有任何边。
Takahashi会重复执行以下操作，直到这个图变为连通图：

  • 从这NN个顶点中随机选一个顶点。每个顶点被抽中的概率相等，即1N\frac 1 N。
  • 在现在站着的点和选中的顶点之间添加一条边，并走到这个点上。

求Takahashi执行操作次数的期望值。

输入格式

NN

输出格式

输出答案，最大允许浮点数误差10−610^{-6}。

样例

NN 输出
22 22
33 4.54.5

分析

通过dp分析，我们可以得到∑i=1n−1Ni\sum\limits_{i=1}^{n-1}\frac Ni这个公式。这时，就可以写代码了。

代码

#include <cstdio>
using namespace std;

int main()
{
	int n;
	scanf("%d", &n);
	double res = 0;
	for(int i=1; i<n; i++)
		res += double(n) / i;
	printf("%.8lf\n", res);
	return 0;
}

E - Mex Min

题目大意

我们定义mex(x1,x2,x3,…,xk)\mathrm{mex}(x_1, x_2, x_3, \dots, x_k)为最小的不出现在x1,x2,x3,…,xkx_1, x_2, x_3, \dots, x_k中的自然数。
给你一个长度为NN的序列AA：(A1,A2,A3,…,AN)(A_1, A_2, A_3, \dots, A_N)。
对于每个0≤i≤N−M0\le i\le N-M的整数ii，我们计算mex(Ai+1,Ai+2,Ai+3,…,Ai+M)\mathrm{mex}(A_{i + 1}, A_{i + 2}, A_{i + 3}, \dots, A_{i + M})。输出这些N−M+1N-M+1个结果中的最小值。

样例

略，请自行前往AtCoder查看

分析

先用最基本的方法想一下这道题，要求mex(x1,x2,x3,…,xk)\mathrm{mex}(x_1, x_2, x_3, \dots, x_k)，只需记录每个xix_i的出现次数，放进数组cnt\text{cnt}里（cnti=i\text{cnt}_i=i在xx中出现的次数）。这时，只要找到cnt\text{cnt}中第一个00即可，这样计算mex\mathrm{mex}的时间复杂度为O(k)\mathcal O(k)。我们还可以想到一种优化方法，就是每一次计算mex(Ai+1,Ai+2,Ai+3,…,Ai+M)\mathrm{mex}(A_{i + 1}, A_{i + 2}, A_{i + 3}, \dots, A_{i + M})（1≤i≤N−M1\le i\le N-M）时，将cntAi\text{cnt}_{A_i}减少11，并且将cntAi+M\text{cnt}_{A_{i+M}}增加11，这样就达到了O(1)\mathcal O(1)计算cnt\text{cnt}的效果。但是，即使这样还会TLE。所以，我们可以用一个set维护cnt\text{cnt}中所有00的位置，这样总时间复杂度就能降至O(Nlog⁡M)\mathcal O(N\log M)。

代码

这里注意，set中一定要添加NN！

#include <cstdio>
#include <set>
#define maxn 1500005
using namespace std;

int cnt[maxn], a[maxn];

set<int> s;

inline void setmin(int& x, int y)
{
	if(y < x) x = y;
}

int main()
{
	int n, m;
	scanf("%d%d", &n, &m);
	for(int i=0; i<n; i++)
		scanf("%d", a + i);
	for(int i=0; i<m; i++)
		cnt[a[i]] ++;
	for(int i=0; i<n; i++)
		if(cnt[i] == 0)
			s.insert(i);
	s.insert(n);
	int ans = *s.begin();
	n -= m;
	for(int i=0; i<n; i++)
	{
		if(cnt[a[i + m]]++ == 0) s.erase(a[i + m]);
		if(--cnt[a[i]] == 0) s.insert(a[i]);
		setmin(ans, *s.begin());
	}
	printf("%d\n", ans);
	return 0;
}