AtCoder Beginner Contest 188 A~D 题解

A - Three-Point Shot

题目大意

有两个球队，分别得到$X$分和$Y$分，问得分较少的球队能否在获得三分后超越对方。

$0\le X,Y\le 100$
$X \ne Y$
$X$和$Y$都是整数。

输入格式

$X~Y$

输出格式

如果能，输出Yes；否则，输出No。

样例

X Y 输出
3 5 Yes

分析

这个不用说了吧，就是求两个数的差是否小于$3$……

代码 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

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

int main(int argc, char** argv)
{
	int a, b;
	scanf("%d%d", &a, &b);
	puts((abs(a - b) < 3)? "Yes": "No");
	return 0;
}

B - Orthogonality

题目大意

给定两个长度为$N$的数组$A=\{A_1,A_2,A_3,...,A_N\}$和$B=\{B_1,B_2,B_3,...,B_N\}$。请判定$A$和$B$的内项积是否为$0$。换句话说，判断$\sum\limits_{i=1}^NA_iB_i$是否为$0$。

$1\le N\le 10^5$
$-100\le A_i,B_i\le 100$ 注意：可能会出现负数！

输入格式

$N$
$A_1~A_2~A_3~\dots~A_N$
$B_1~B_2~B_3~\dots~B_N$

输出格式

如果$A$和$B$的内项积为$0$，输出Yes；否则，输出No。

样例

样例输入1 

1
2
3

2
-3 6
4 2

样例输出1 

1

Yes

$N = 2$
$A = \{-3,6\}$
$B = \{4,2\}$
$A$和$B$的内项积为：$\sum\limits_{i=1}^NA_iB_i = (-3)\times4+6\times2=0$，所以输出Yes。

样例输入2 

1
2
3

2
4 5
-1 -3

样例输出2 

1

No

$N = 2$
$A = \{4,5\}$
$B = \{-1,-3\}$
$A$和$B$的内项积为：$\sum\limits_{i=1}^NA_iB_i = 4\times(-1)+5\times(-3)=19$，所以输出No。

样例输入3 

1
2
3

3
1 3 5
3 -6 3

样例输出3 

1

Yes

$N = 3$
$A = \{1,3,5\}$
$B = \{3,-6,3\}$
$A$和$B$的内项积为：$\sum\limits_{i=1}^NA_iB_i = 1\times3+3\times(-6)+5\times3=0$，所以输出Yes。

分析

只需按题目说的照做即可。

代码 

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

int a[maxn];

int main(int argc, char** argv)
{
	int n;
	scanf("%d", &n);
	for(int i=0; i<n; i++)
		scanf("%d", a + i);
	int res = 0;
	for(int i=0; i<n; i++)
	{
		int x;
		scanf("%d", &x);
		res += x * a[i];
	}
	puts(res == 0? "Yes": "No");
	return 0;
}

C - ABC Tournament

题目大意

有$2^N$个玩家，每个玩家的编号是$i$且有一个排名$A_i$，举行$N$场淘汰赛。
淘汰赛可以看作一棵二叉树，制度如下：
如，$N=3$，有$8$个玩家，排名分别为$1,6,7,10,5,13,8,9$：

  1. 1,6,7,10,5,13,8,9 两两比较，淘汰1,7,5,8；（排名越高的玩家越厉害）
  2. 6,10,13,9 两两比较，淘汰6,9；
  3. 10,13 $13$最大，胜利！

请输出比赛的第二名（即在最后一轮被淘汰的玩家，如上面的$13$）的编号。

$1\le N\le 16$
$1\le A_i \le 10^9$
$A_i$互不相同。

输入格式

$N$
$A_1~A_2~A_3~\dots~A_{2^N}$

输出格式

输出最终获得第二名的玩家的编号。

样例

样例输入1 

1
2

2
1 4 2 5

样例输出1 

1

2

$4$个玩家，排名分别为$1,4,2,5$：

  1. 1,4,2,5
  2. 4,5（$2$号玩家在这里被淘汰了）

所以，我们输出$2$。

样例输入2 

1
2

2
3 1 5 4

样例输出2 

1

1

$4$个玩家，排名分别为$3,1,5,4$：

  1. 3,1,5,4
  2. 3,5（$1$号玩家在这里被淘汰了）

所以，我们输出$1$。

样例输入3 

1
2

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

样例输出3 

1

2

博主提示：在这个样例上手算，就可以知道不能将输入排序后取第二大的值！！！

分析

首先，题目不允许偷懒（要求第二名的编号），不能将输入排序后取第二大的值。
我们考虑别的方法。
很容易想到，可以直接模拟。不过，模拟时不能直接删除元素，会TLE。可以采取利用循环队列的$\mathcal O(1)$进出，每次出队两个元素，再将其中较大的再放入队列即可。最后，当队列中只剩两个元素时，输出其中较小的编号即可。

代码

写代码时要注意两点：

  1. 一定要使用long long！
  2. 要在进行队列操作时记录编号，可以用pair实现。
 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

#include <cstdio>
#include <queue>
using namespace std;

using LL = long long;
using pli = pair<LL, int>;

int main(int argc, char** argv)
{
	queue<pli> q;
	int n;
	scanf("%d", &n);
	n = 1 << n;
	for(int i=1; i<=n; i++)
	{
		LL x;
		scanf("%lld", &x);
		q.emplace(x, i);
	}
	while(q.size() > 2)
	{
		pli x = q.front(); q.pop();
		pli y = q.front(); q.pop();
		if(x < y) q.push(y);
		else q.push(x);
	}
	pli x = q.front(); q.pop();
	pli y = q.front();
	printf("%d\n", x < y? x.second: y.second);
	return 0;
}

D - Snuke Prime

题目大意

Takahashi需要使用$N$种服务。
每种服务的价格是$c_i$元（原题中钱币单位是日元，翻译时使用人民币作单位），他需要从第$a_i$天的开始（0:00）用到第$b_i$天的结束（23:59）。有一种特殊的服务，它可以使你无限次使用任意其它服务，每天收费$C$元（需要从一天的开始订阅到一天的结束，订阅结束时失效，可以多次订阅）。
Takahashi使用这些服务至少需要多少元？

$1\le N\le 2\times 10^5$
$1\le C\le 10^9$
$1\le a_i\le b_i\le 10^9$
$1\le c_i\le 10^9$

输入格式

$N~C$
$a_1~b_1~c_1$
$a_2~b_2~c_2$
$...$
$a_N~b_N~c_N$

输出格式

输出一行，即最少需要的钱数。

样例

样例输入1 

1
2
3

2 6
1 2 4
2 2 4

样例输出1 

1

10

sample1_note

样例输入2 

1
2
3
4
5
6

5 1000000000
583563238 820642330 44577
136809000 653199778 90962
54601291 785892285 50554
5797762 453599267 65697
468677897 916692569 87409

样例输出2 

1

163089627821228

最优方案是不订阅特殊服务。

样例输入3 

1
2
3
4
5
6

5 100000
583563238 820642330 44577
136809000 653199778 90962
54601291 785892285 50554
5797762 453599267 65697
468677897 916692569 87409

样例输出3 

1

88206004785464

自制样例

博主在这里再提供一组样例，方便手算后面的代码以及理解题目的意思。

输入：

1
2
3

2 7
1 3 5
2 6 4

输出：

1

31

在这组数据中，我们在第$2$、$3$天订阅特殊服务。

分析

参考：AtCoder官方题解
我们可以把每一个服务的订阅拆分成两个事件$(a_i-1,c_i)$和$(b_i,-c_i)$。每个事件有两个参数，分别是时间（某一天的最后一刻）和每天增加的钱数（可以为负数，表示减少需要花的钱）。然后，再按时间排序这些事件。
我们可以用变量fee记录每天需要花的钱，用ans记录答案。循环遍历每个事件，当这个事件的事件与上一次不同时，将ans加上计算最划算的付钱方法（分开付，要花fee元或一起付，花$C$元）乘以与上一次差的天数，最后加上当前事件的增加钱数。
最后，输出ans即可。

代码

作为一个优先队列爱好者，排序当然是用priority_queue实现了~
以下代码要注意三点：

  • 必须使用long long；
  • 建议使用pair存储；
  • 拆分事件时第一个事件$(a_i-1,c_i)$中的$a_i$一定不能忘记$-1$（因为$a_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
30
31
32
33
34
35
36

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

typedef long long LL;
typedef pair<LL, LL> pll;

int main(int argc, char** argv)
{
	int n;
	LL c;
	scanf("%d%lld", &n, &c);
	priority_queue<pll, vector<pll>, greater<pll> > q;
	while(n--)
	{
		LL x, y, z;
		scanf("%lld%lld%lld", &x, &y, &z);
		q.emplace(--x, z);
		q.emplace(y, -z);
	}
	LL ans = 0LL, fee = 0LL, last = 0LL;
	while(!q.empty())
	{
		auto [day, cost] = q.top(); q.pop();
		if(last != day)
		{
			ans += min(c, fee) * (day - last);
			last = day;
		}
		fee += cost;
	}
	printf("%lld\n", ans);
	return 0;
}

上面的代码使用了C++17新特性，如果上面的代码无法通过本地编译，请使用下面的代码：

 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

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

typedef long long LL;
typedef pair<LL, LL> pll;

int main(int argc, char** argv)
{
	int n;
	LL c;
	scanf("%d%lld", &n, &c);
	priority_queue<pll, vector<pll>, greater<pll> > q;
	while(n--)
	{
		LL x, y, z;
		scanf("%lld%lld%lld", &x, &y, &z);
		q.push(pll(--x, z));
		q.push(pll(y, -z));
	}
	LL ans = 0LL, fee = 0LL, last = 0LL;
	while(!q.empty())
	{
		LL day = q.top().first, cost = q.top().second; q.pop();
		if(last != day)
		{
			ans += min(c, fee) * (day - last);
			last = day;
		}
		fee += cost;
	}
	printf("%lld\n", ans);
	return 0;
}
© 2020 - 2025 GoodCoder's Blog
使用 Hugo 构建
主题 Stack 由 Jimmy 设计