AtCoder Beginner Contest 194 A~E 题解

A - I Scream

题目大意

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

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

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

$0\le A,B\le 100$
$0\le A+B\le 100$

输入格式

$A~B$

输出格式

请按如下格式输出类别：

  • 如果这是冰淇淋，输出$1$；
  • 如果这是冰奶，输出$2$；
  • 如果这是乳冰，输出$3$；
  • 如果这是调味冰，输出$4$。

样例

$A$ $B$ 输出
$10$ $8$ $1$
$1$ $2$ $3$
$0$ $0$ $4$

分析

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

代码 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

#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

题目大意

$$t= \begin{cases} A_i+B_i & (i=j) \\ \max\{A_i,B_j\} & (i\ne j) \\ \end{cases}$$


求最小的$t$。

$2\le N\le 1000$
$1\le A_i,B_i\le 10^5$

输入格式

$N$
$A_1~B_1$
$A_2~B_2$
$\vdots$
$A_N~B_N$

输出格式

输出答案。

样例

略，请自行前往AtCoder查看

分析

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

代码 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

#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

题目大意

给你一个长度为$N$的序列$A$。
输出$\displaystyle \sum_{i = 2}^{N} \sum_{j = 1}^{i - 1} (A_i - A_j)^2$。

$2 \le N \le 3 \times 10^5$
$|A_i| \le 200$

输入格式

$N$
$A_1~A_2~A_3~\dots~A_N$

输出格式

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

样例

样例输入1 

1
2

3
2 8 4

样例输出1 

1

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 

1
2

5
-5 8 9 -4 -3

样例输出2 

1

950

分析

$$\sum_{i = 2}^{N} \sum_{j = 1}^{i - 1} (A_i - A_j)^2$$$$\sum_{i = 2}^{N} \sum_{j = 1}^{i - 1} {A_i}^2+{A_j}^2-2A_iA_j$$$$(\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)$$$$(n-1)(\sum_{i = 1}^{N} {A_i}^2)-2(\sum_{i = 1}^{N} S_iA_i)$$


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

代码 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

#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

题目大意

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

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

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

输入格式

$N$

输出格式

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

样例

$N$ 输出
$2$ $2$
$3$ $4.5$

分析

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

代码 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

#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

题目大意

我们定义$\mathrm{mex}(x_1, x_2, x_3, \dots, x_k)$为最小的不出现在$x_1, x_2, x_3, \dots, x_k$中的自然数。
给你一个长度为$N$的序列$A$：$(A_1, A_2, A_3, \dots, A_N)$。
对于每个$0\le i\le N-M$的整数$i$，我们计算$\mathrm{mex}(A_{i + 1}, A_{i + 2}, A_{i + 3}, \dots, A_{i + M})$。输出这些$N-M+1$个结果中的最小值。

样例

略，请自行前往AtCoder查看

分析

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

代码

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

#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;
}
© 2020 - 2025 GoodCoder's Blog
使用 Hugo 构建
主题 Stack 由 Jimmy 设计