首页 > 其他分享 >AtCoder Beginner Contest 188 A~D 题解

AtCoder Beginner Contest 188 A~D 题解

时间:2024-09-08 20:51:30浏览次数:9  
标签:AtCoder le 输出 int 题解 样例 188 include 10

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\)……

代码

#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

2
-3 6
4 2

样例输出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

2
4 5
-1 -3

样例输出2

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

3
1 3 5
3 -6 3

样例输出3

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

分析

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

代码

#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

2
1 4 2 5

样例输出1

2

\(4\)个玩家,排名分别为\(1,4,2,5\):

  1. 1,4,2,5
  2. 4,5(\(2\)号玩家在这里被淘汰了)

所以,我们输出\(2\)。

样例输入2

2
3 1 5 4

样例输出2

1

\(4\)个玩家,排名分别为\(3,1,5,4\):

  1. 3,1,5,4
  2. 3,5(\(1\)号玩家在这里被淘汰了)

所以,我们输出\(1\)。

样例输入3

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

样例输出3

2

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

分析

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

代码

写代码时要注意两点:

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

2 6
1 2 4
2 2 4

样例输出1

10
sample1_note

样例输入2

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

样例输出2

163089627821228

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

样例输入3

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

样例输出3

88206004785464

自制样例

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

输入:

2 7
1 3 5
2 6 4

输出:

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\)表示的是一天的开始,应该转换为前一天的结束)。
#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新特性,如果上面的代码无法通过本地编译,请使用下面的代码:

#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;
}

标签:AtCoder,le,输出,int,题解,样例,188,include,10
From: https://www.cnblogs.com/stanleys/p/18403448/abc188

相关文章

  • AtCoder Beginner Contest 161D 题解
    原题链接:洛谷链接;AtCoder链接思路每次根据上一位,计算下一位为TA-1/TA/TA+1,放入queue中,最后输出第\(K\)次弹出的整数。注意事项不用longlong会WA!上一位为\(0\)时下一位不能为\(-1\)!(要特判)上一位为\(9\)时下一位不能为\(10\)!(也要特判)代码#include<cstdio>#include<que......
  • CodeForces Round #621 ABC (1307A+1307B+1307C) 题解
    A.CowandHaybales题面TheUSAConstructionOperation(USACO)recentlyorderedFarmerJohntoarrangearowofnhaybalepilesonthefarm.The\(i\)-thpilecontains\(a_i\)haybales.However,FarmerJohnhasjustleftforvacation,leavingBessieal......
  • 2024CCPC网络赛题解
    前言开局掉线30min比较搞心态,不过比赛延迟了1个小时,但是后面也一直没过题,如果时间再少点可能排名还更好看。最后是8题前面,这里简单讲一下我有写的题,队友写的题就放一下队友的赛时代码,大家自己看看吧。B队友写的,签到,但是数据范围\(n\)给\(10^3\)给队友整不自信了,因为答案的......
  • AT_dwacon6th_prelims_c Cookie Distribution 题解
    组合意义保平安。思路发现\(\prod\)的贡献不好统计。我们可以考虑\(\prod\)的组合意义。容易发现:\[\prodc_i=\prod\sum_{j=1}^{c_i}1\]那么依照分配律,我们发现这个东西的组合意义是每个人从获得的饼干中选一个出来的方案。这样就会变好统计很多。设\(dp_{i,j}\)为......
  • CF1534F2 Falling Sand (Hard Version) 题解
    题目链接点击打开链接题目解法做法1一个沙子消失,会带走所有它所在列下面的沙子我们记每列从下往上第\(a_i\)个沙子为关键点,第\(i\)列至少消失\(a_i\)个沙子等价于所有关键点都消失一个显然的事情是:记一列最上面的沙子为起始点,则我们只会干扰起始点第一感觉是找到一......
  • LOJ4218 「IOI2024」尼罗河船运 题解
    题目描述有\(n\)件手工艺品,第\(i\)件重量为\(w_i\),有参数\(a_i\)和\(b_i\)。每艘船最多可以运输两件手工艺品:如果只运输第\(i\)件,重量没有要求,代价为\(a_i\)。如果同时运输第\(i\)和第\(j\)件,要求\(|w_i-w_j|\leD\),代价\(b_i+b_j\)。\(q\)次询问,给......
  • Leetcode第 414 场周赛题解
    Leetcode第414场周赛题解Q1.将日期转换为二进制表示给你一个字符串date,它的格式为yyyy-mm-dd,表示一个公历日期。date可以重写为二进制表示,只需要将年、月、日分别转换为对应的二进制表示(不带前导零)并遵循year-month-day的格式。返回date的二进制表示。解法:STL一......
  • 题解:P11020 「LAOI-6」Radiation
    我们发现一种最优策略,把石头按照斜线摆,即(1,1),......
  • P1419 寻找段落 题解
    其他学习笔记这题真是凝聚了很多精华,那么我们就介绍这题的四兄弟:大哥平均数这道题是其他兄弟的基础。二哥BestCow这位更是重量级,因为没特长只能强大哥的外貌,会大哥即识二哥。三哥PROSJEK这位哥看似有点创新却仍没逃过一家子的基因,只是变为了小数运算。四哥寻......
  • 【题解】CPS-S模拟2
    目录PreT1.不相邻集合题目描述部分分40pts10pts正解思路代码T2.线段树题目描述部分分20pts正解思路代码T3.部分分40pts正解思路代码T4.部分分10pts正解思路代码AndPre赛时没有第一时间找到签到题,遂四处游走,后来决定先打T1,约1h时切了,然后1h打后3题暴力,后面推了推T4一个特殊性质,......