首页 > 其他分享 >AtCoder Beginner Contest 205 A~E 题解

AtCoder Beginner Contest 205 A~E 题解

时间:2024-09-08 21:02:24浏览次数:10  
标签:dots 输出 le 205 AtCoder int 题解 样例 10

A - kcal

题目大意

我们有一种每\(100\)毫升含有\(A\)千卡热量的饮料。\(B\)毫升的这种饮料含有多少千卡热量?

\(0\le A, B\le 1000\)

输入格式

\(A~B\)

输出格式

输出\(B\)毫升这种饮料包含的的千卡数。最大允许浮点数精度误差\(10^{-6}\)。

样例

\(A\) \(B\) 输出
\(45\) \(200\) \(90\)
\(37\) \(450\) \(166.5\)
\(0\) \(1000\) \(0\)
\(50\) \(0\) \(0\)

分析

废话不多说,答案就是\(\frac{AB}{100}\)~

代码

#include <cstdio>
using namespace std;

int main()
{
	int a, b;
	scanf("%d%d", &a, &b);
	a *= b;
	printf("%d.%d\n", a / 100, a % 100);
	return 0;
}

B - Permutation Check

题目大意

给定长度为\(N\)的序列\(A=(A_1,A_2,\dots,A_N)\)。
判断\(A\)是否为\((1,2,\dots,N)\)的一种排列。

\(1\le A_i\le N\le 10^3\)

输入格式

\(N\)
\(A_1~A_2~\dots~A_N\)

输出格式

如果\(A\)是\((1,2,\dots,N)\)的一种排列,输出Yes;否则,输出No

样例

样例输入1

5
3 1 2 4 5

样例输出1

Yes

\((3,1,2,4,5)\)是\((1,2,3,4,5)\)的一种排列,所以我们输出Yes

样例输入2

6
3 1 4 1 5 2

样例输出2

No

\((3,1,4,1,5,2)\)不是\((1,2,3,4,5,6)\)的一种排列,所以我们输出No

样例输入3

3
1 2 3

样例输出3

Yes

样例输入4

1
1

样例输出4

Yes

分析

由于题目保证\(1\le A_i\le N\),所以\((1,2,\dots,N)\)的一种排列\(A\)定义如下:

  • \(A\)中\(1\)到\(N\)每个数字不重复出现。

因此,我们可以用数组记录每个数字是否出现,所以总时间复杂度为\(\mathcal O(n)\)。

代码

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

bool used[maxn];

int main()
{
	int n;
	scanf("%d", &n);
	for(int i=0; i<n; i++)
	{
		int a;
		scanf("%d", &a);
		if(used[a])
		{
			puts("No");
			return 0;
		}
		used[a] = true;
	}
	puts("Yes");
	return 0;
}

C - POW

题目大意

给定三个整数\(A,B,C\),判断\(A^C\)和\(B^C\)哪个更大。

\(-10^9\le A,B\le 10^9\)
\(1\le C\le 10^9\)

输入格式

\(A~B~C\)

输出格式

本题分如下三种情况输出:

  • 如果\(A^C<B^C\),输出<
  • 如果\(A^C>B^C\),输出>
  • 如果\(A^C=B^C\),输出=

样例

\(A\) \(B\) \(C\) 输出
\(3\) \(2\) \(4\) >
\(-7\) \(7\) \(2\) =
\(-8\) \(6\) \(3\) <

分析

首先,由于负负得正,\((-a)^2=a^2\)。
这样,我们可以根据奇偶性得出,如果\(n\)为偶数,\((-a)^n=a^n\);但如果\(n\)为奇数,则\((-a)^n=-(a^n)\)。
因此,我们只需判断如果\(C\)为偶数,将\(A\)替换为\(|A|\),再将\(B\)替换为\(|B|\)。
最后,\(A\)和\(B\)的大小关系就是\(A^C\)和\(B^C\)的大小关系。

代码

#include <cstdio>
using namespace std;

int main()
{
	int a, b, c;
	scanf("%d%d%d", &a, &b, &c);
	if(!(c & 1))
	{
		if(a < 0) a = -a;
		if(b < 0) b = -b;
	}
	puts(a < b? "<": a > b? ">": "=");
	return 0;
}

D - Kth Excluded

题目大意

给定长度为\(N\)的正整数序列\(A=(A_1,A_2,\dots,A_N)\)和\(Q\)次查询。
在第\(i\)次查询中,给定正整数\(K_i\),求第\(K_i\)小的不在\(A\)中的正整数。

\(1\le N,Q\le 10^5\)
\(1\le A_1<A_2<\dots<A_N\le10^{18}\)
\(1\le K_i\le 10^{18}\)

输入格式

\(N~Q\)
\(A_1~A_2~\dots~A_N\)
\(K_1\)
\(K_2\)
\(\hspace{5pt}\vdots\)
\(K_N\)

输出格式

输出\(Q\)行。第\(i\)行应该包含第\(K_i\)小的不在\(A\)中的正整数。

样例

样例输入1

4 3
3 5 6 7
2
5
3

样例输出1

2
9
4

不在\(A\)中的正整数有\(1,2,4,8,9,10,11,\dots\),其中有:

  • 第\(2\)小的\(2\);
  • 第\(5\)小的\(9\);
  • 第\(3\)小的\(4\)。

因此,我们应该依次输出294

样例输入2

5 2
1 2 3 4 5
1
10

样例输出2

6
15

分析

本题我们可以先预处理出\(A\)中每个元素比它小的元素的数量,再二分查找即可。

代码

#include <cstdio>
#include <algorithm>
#define maxn 100005
using namespace std;

using LL = long long;
LL a[maxn];

int main()
{
	int n, q;
	scanf("%d%d", &n, &q);
	for(int i=0; i<n; i++)
	{
		scanf("%lld", a + i);
		a[i] -= i;
	}
	while(q--)
	{
		LL k;
		scanf("%lld", &k);
		printf("%lld\n", k + (upper_bound(a, a + n, k) - a));
	}
	return 0;
}

E - White and Black Balls

题目大意

有多少种排列\(N\)个白球和\(M\)个黑球的方法使得下列条件成立?

  • 对于每个\(i\) (\(1\le i\le N+M\)),设\(w_i\)和\(b_i\)分别是最左边\(i\)个球中白球和黑球的数量,\(w_i\le b_i+K\)成立。

答案对\((10^9+7)\)取模。

\(0\le N,M\le10^6\)
\(1\le N+M\)
\(0\le K\le N\)

输入格式

\(N~M~K\)

输出格式

输出答案,对\((10^9+7)\)取模。

样例

\(N\) \(M\) \(K\) 输出
\(2\) \(3\) \(1\) \(9\)
\(1\) \(0\) \(0\) \(0\)
\(1000000\) \(1000000\) \(1000000\) \(192151600\)

分析

首先,本题中合法排列数就是如下符合任意\(y\le x+K\)的\((0,0)\to(M,N)\)的最短路径的数量:
路径解释图

由此可见,如果\(N>M+K\)(即终点超出限制),答案一定为\(0\)。
我们还可以发现,如果没有\(y\le x+K\)这个限制,答案为\(\binom{N + M}{N}\)。
我们再考虑不合法的路径数,数量为\(\binom{N + M}{M + K + 1}\)。
因此,答案为\(\binom{N + M}{N}-\binom{N + M}{M + K + 1}\)。

代码

这里用AtCoder Library好像比较方便唉~

#include <iostream>
#include <atcoder/modint>
using namespace std;

using modint = atcoder::modint1000000007;

modint f(int n, int m)
{
	if(n < 0 || m < 0)
		return 0;
	modint ret = 1;
	for(int i=1; i<=m; i++)
		ret = ret * (n + i) / i;
	return ret;
}

int main()
{
	int n, m, k;
	scanf("%d%d%d", &n, &m, &k);
	if(n > m + k) puts("0");
	else printf("%d\n", (f(n, m) - f(n - k - 1, m + k + 1)).val());
	return 0;
}

标签:dots,输出,le,205,AtCoder,int,题解,样例,10
From: https://www.cnblogs.com/stanleys/p/18403477/abc205

相关文章

  • AtCoder Beginner Contest 168 C~D 题解
    这次比赛的题名很特殊,是由符号+(+英文+)组成的......
  • AtCoder Beginner Contest 171 A~D 题解
    A-αlphabet题目大意输入一个英文字母\(a\),判断它是大写还是小写。输入格式\(a\)输出格式如果\(a\)为小写,输出a;如果\(a\)为大写,输出A。样例输入1B样例输出1AB为大写,所以输出A。样例输入2a样例输出2aa为小写,所以输出a。代码#include<cstdio>usingnames......
  • AtCoder Beginner Contest 187 A~D 题解
    A-LargeDigits题目大意给定两个三位整数\(A\)和\(B\),求它们数位和的最大值。数位和:例如,\(123\)的数位和是\(1+2+3=6\)。\(100\leA,B\le999\)输入格式\(A~~B\)输出格式一行,即\(A\)和\(B\)数位和的最大值。样例输入输出12323495939531710099927......
  • AtCoder Beginner Contest 173 A~D 题解
    A-Payment题目大意如果使用价值\(1000\)元的纸币(假设有)支付\(N\)元,服务员会找多少钱?\(1\leN\le10000\)输入格式\(N\)输出格式一行,即服务员找的钱数。样例输入输出190010030000分析特判:如果\(N\)除以\(1000\)能整除,那么不需要找钱,输出\(0\);如果......
  • Panasonic Programming Contest 2020 C (Sqrt Inequality) 题解
    题目大意输入三个整数\(a\),\(b\),\(c\),如果\(\sqrta+\sqrtb<\sqrtc\)成立,输出Yes,否则输出No。样例输入#1239输出#1No\(\sqrt2+\sqrt3<\sqrt9\)不成立。输入#22310输出#2Yes\(\sqrt2+\sqrt3<\sqrt10\)成立。分析错误思路首先,由......
  • AtCoder Beginner Contest 188 A~D 题解
    A-Three-PointShot题目大意有两个球队,分别得到\(X\)分和\(Y\)分,问得分较少的球队能否在获得三分后超越对方。\(0\leX,Y\le100\)\(X\neY\)\(X\)和\(Y\)都是整数。输入格式\(X~Y\)输出格式如果能,输出Yes;否则,输出No。样例XY输出35Yes分析这个不用......
  • 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}\)为......