AtCoder Beginner Contest 245 A~E 题解

A - Good morning

题目大意

在同一天里，Takahashi在$A$时$B$分起床，Aoki在$C$时$D$分$1$秒起床，请问谁起床更早？

$0\le A,C < 24$
$0\le B,D < 60$

输入格式

$A~B~C~D$

输出格式

输出起得更早的人的名字（Takahashi或Aoki）。

样例

$A$ $B$ $C$ $D$ 输出
$7$ $0$ $6$ $30$ Aoki
$7$ $30$ $7$ $30$ Takahashi
$0$ $0$ $23$ $59$ Takahashi

分析

思路很明显，直接判断$(A,B)\le(C,D)$是否成立即可。

代码 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

#include <cstdio>
using namespace std;

int main()
{
	int a, b, c, d;
	scanf("%d%d%d%d", &a, &b, &c, &d);
	puts((a == c? b <= d: a < c)? "Takahashi": "Aoki");
	return 0;
}

B - Mex

题目大意

给定整数序列$A=(A_1,\dots,A_N)$。求最小的不在$A$中的自然数。

$1\le N\le 2000$
$0\le A_i\le 2000$

输入格式

$N$
$A_1~\dots~A_N$

输出格式

输出一行，即最小的不在$A$中的自然数。

样例

略，请自行前往AtCoder查看

分析

由于题面中有限制$0\le A_i\le 2000$，所以我们直接开一个数组记录$[0,2001]$中每个数是否出现过即可。
本题方法很多，这里介绍的是最快的算法，时间复杂度$\mathcal O(N)$。

代码 

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

#include <cstdio>
using namespace std;

bool used[2005];

int main()
{
	int n;
	scanf("%d", &n);
	while(n--)
	{
		int a;
		scanf("%d", &a);
		used[a] = true;
	}
	int i = -1;
	while(used[++i]);
	printf("%d\n", i);
	return 0;
}

C - Choose Elements

题目大意

给定两个长度为$N$的整数序列$A=(A_1,\dots,A_N)$和$B=(B_1,\dots,B_N)$。
问是否存在序列$X=(X_1,\dots,X_N)$，满足如下条件：

  • $X_i=A_i$或$X_i=B_i$
  • $|X_i-X_{i+1}|\le K$，其中$1\le i < N$

$1\le N\le 2\times 10^5$
$1\le K\le 10^9$
$1\le A_i,B_i\le 10^9$

输入格式

$N~K$
$A_1~\dots~A_N$
$B_1~\dots~B_N$

输出格式

如果存在符合全部条件的$X$，输出Yes；否则，输出No。

样例

略，请自行前往AtCoder查看

分析

好家伙，C题都要用dp……
本题普通的方法貌似不太好做，因此我们考虑$\text{DP}$。
令$f(i)=X_i$选择能否等于$A_i$，$g(i)=X_i$能否等于$B_i$。
然后状态转移方程就简单了，详见代码。

代码 

 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 200005
using namespace std;

int a[maxn], b[maxn];
bool f[maxn], g[maxn];

int main()
{
	int n, k;
	scanf("%d%d", &n, &k);
	for(int i=0; i<n; i++)
		scanf("%d", a + i);
	for(int i=0; i<n; i++)
		scanf("%d", b + i);
	f[0] = g[0] = true;
#define set(x, y, z) x |= y - z <= k && z - y <= k
	for(int i=1; i<n; i++)
	{
		if(f[i - 1])
			set(f[i], a[i - 1], a[i]),
			set(g[i], a[i - 1], b[i]);
		if(g[i - 1])
			set(f[i], b[i - 1], a[i]),
			set(g[i], b[i - 1], b[i]);
	}
	puts(f[n - 1] || g[n - 1]? "Yes": "No");
	return 0;
}

==注：本题还有一种很奇怪的解法，就是直接判断相邻的四种连接方式是否有至少一种能连通，比如#30453703，如果有大佬能证明这种方法的正确性，欢迎在评论区留言告诉我，谢谢！==

D - Polynomial division

题目大意

$$ A(x)=\sum_{i=0}^N A_iX^i\\ B(x)=\sum_{i=0}^M B_iX^i\\ C(x)=\sum_{i=0}^{N+M} B_iX^i $$


已知$A_0,\dots,A_N$和$C_0,\dots,C_N$且$A(x)\times B(x)=C(x)$（$x\in R$），求$B_0,\dots,B_M$。
换句话说，给定多项式$A$和$C$每一项的系数，求多项式$B=\frac C A$。

$1\le N,M < 100$
$|A_i|\le 100$
$|C_i|\le 10^6$
$A_N\ne0,C_{N+M}\ne0$
题目保证存在合法的$(B_0,\dots,B_M)$。

输入格式

$N~M$
$A_0~\dots~A_N$
$C_0~\dots~C_{N+M}$

输出格式

输出$B_0,\dots,B_M$，用空格分隔。

样例

略，请自行前往AtCoder查看

分析

本题可以直接模拟多项式的大除法运算，运算时只需记录系数即可。

代码 

 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 105
using namespace std;

int a[maxn], b[maxn], c[maxn << 1];

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<=n+m; i++) scanf("%d", c + i);
	for(int i=m; i>=0; i--) // NOTE: 必须倒推！
	{
		b[i] = c[n + i] / a[n];
		for(int j=0; j<=n; j++)
			c[i + j] -= a[j] * b[i];
	}
	for(int i=0; i<=m; i++)
		printf("%d ", b[i]);
	return 0;
}

E - Wrapping Chocolate

题目大意

我们有$N$块巧克力和$M$个盒子。第$i$块巧克力长$A_i$厘米，宽$B_i$厘米；第$i$个盒子长$C_i$厘米，宽$D_i$厘米。
问是否能把巧克力分别装在盒子里，使其满足如下条件：

  • 每个盒子里只能有一块巧克力。
  • 当我们将第$i$块巧克力放入第$j$个盒子里时，$A_i\le C_j$和$B_i\le D_j$必须都成立。

$1\le N\le M\le 2\times10^5$
$1\le A_i,B_i,C_i,D_i\le 10^9$

输入格式

$N~M$
$A_1~\dots~A_N$
$B_1~\dots~B_N$
$C_1~\dots~C_N$
$D_1~\dots~D_N$

输出格式

如果有合法的方法，输出Yes；否则，输出No。

分析

本题可以考虑如下贪心算法：

  1. 将所有的巧克力和盒子放入一个数组，按长度（$A_i$或$C_i$）的降序排序，长度相等的把盒子排在前面。
  2. 准备好一个空序列$S=()$，按如下规则遍历每个元素：
    • 如果当前遍历的是一个盒子$(C_i,D_i)$：
      将$D_i$加入$S$。
    • 如果当前遍历的是一块巧克力$(A_i,B_i)$：
      从$S$中删除不超过$B_i$的最小元素，如果没有元素可删除，输出No。
  3. 如果顺利地遍历了所有元素，输出Yes；否则，输出No。

本算法的时间复杂度是$\mathcal O(MN)$，但经过multiset优化后可降为$\mathcal O((M+N)\log(M+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
38
39
40
41
42
43
44
45
46
47
48
49

#include <cstdio>
#include <set>
#include <algorithm>
using namespace std;

struct Item {
	int w, h;
	bool type;
	inline bool operator <(const Item& i2) const {
		return w == i2.w? type > i2.type: w > i2.w;
		//                ^^^^^^^^^^^^^^
		// 注意sort必须有严格顺序，一开始我这里写成了type==1导致RE，详见：
		// https://atcoder.jp/contests/abc245/submissions/30526563
	}
} v[400005];

int main()
{
	int n, m;
	scanf("%d%d", &n, &m);
	// Chocolate
	for(int i=0; i<n; i++) scanf("%d", &v[i].w);
	for(int i=0; i<n; i++) scanf("%d", &v[i].h);
	// Box
	m += n;
	for(int i=n; i<m; i++) scanf("%d", &v[i].w);
	for(int i=n; i<m; i++) scanf("%d", &v[i].h);
	for(int i=n; i<m; i++) v[i].type = 1;
	// Algorithm
	sort(v, v + m);
	multiset<int> s;
	for(int i=0; i<m; i++)
	{
		const Item& it = v[i];
		if(it.type) s.insert(it.h); // Box
		else
		{
			auto itr = s.lower_bound(it.h);
			if(itr == s.end())
			{
				puts("No");
				return 0;
			}
			s.erase(itr);
		}
	}
	puts("Yes");
	return 0;
}
© 2020 - 2025 GoodCoder's Blog
使用 Hugo 构建
主题 Stack 由 Jimmy 设计