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

AtCoder Beginner Contest 190 A~D 题解

时间:2024-09-08 21:07:21浏览次数:8  
标签:输出 le 15 AtCoder int 题解 样例 190 编号

A - Very Very Primitive Game

题目大意

Takahashi和Aoki在玩一个游戏。
游戏规则是这样的:

  • 最开始,Takahashi和Aoki分别有\(A\)和\(B\)颗糖。
  • 他们将轮流吃一颗糖,第一个无法吃糖的人算输。如果\(C=0\),那么Takahashi先吃;如果\(C=1\),那么Aoki先吃。

请输出最终胜者的名字。

\(0\le A,B\le 100\)
\(C \in \{0,1\}\)

输入格式

\(A~B~C\)

输出格式

输出答案。

样例

A B C 输出
2 1 0 Takahashi
2 2 0 Aoki
2 2 1 Takahashi

分析

可以看出,如果是Aoki先吃(\(C=1\)),那么当\(B>A\)时,Aoki会赢。那么如果Takahashi先吃(\(C=1\)),我们可以先将\(B\)加上\(1\),这时就变成了前一种情况,再判断\(B>A\)是否成立即可。

代码

#include <cstdio>
using namespace std;

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

B - Magic 3

题目大意

一位魔术师要与怪兽战斗。
他可以使用\(N\)种咒语。
第\(i\)个咒语的冷却时间是\(X_i\)秒、伤害是\(Y_i\)。
但是,这个怪兽可以免疫冷却时间不少于\(S\)或伤害不超过\(D\)的任何咒语的伤害。
这位魔术师能伤害到怪兽吗?

\(1\le N\le 100\)
\(1\le X_i, Y_i\le 10^9\)
\(1\le S, D\le 10^9\)

输入格式

\(N~S~D\)
\(X_1~Y_1\)
\(X_2~Y_2\)
\(\vdots\)
\(X_N~Y_N\)

输出格式

如果魔术师能伤害到怪物,输出Yes;否则,输出No

样例

样例输入1

4 9 9
5 5
15 5
5 15
15 15

样例输出1

Yes

\(S=D=9\),则:

咒语编号 冷却时间 伤害 能否伤害到怪物
\(1\) \(5\)秒\(~~~\checkmark\) \(5~~~\bm\times\) \(\bm\times\)
\(2\) \(15\)秒\(~~~\bm\times\) \(5~~~\bm\times\) \(\bm\times\)
\(3\) \(5\)秒\(~~~\checkmark\) \(15~~~\checkmark\) \(\checkmark\)
\(4\) \(15\)秒\(~~~\bm\times\) \(15~~~\checkmark\) \(\bm\times\)

样例输入2

3 691 273
691 997
593 273
691 273

样例输出2

No

样例输入3

7 100 100
10 11
12 67
192 79
154 197
142 158
20 25
17 108

样例输出3

Yes

只有第七个咒语能伤害怪兽。

分析

这题可以遍历每一个\(i\),并判断如果\(X_i<S\)和\(Y_i>D\)同时成立,输出Yes;当所有\(i\)都不符合条件时,输出No

代码

我写的这个代码是在输入时处理的,当然也可以输入之后再处理。

#include <cstdio>
using namespace std;

int main()
{
	int n, s, d;
	scanf("%d%d%d", &n, &s, &d);
	while(n--)
	{
		int x, y;
		scanf("%d%d", &x, &y);
		if(x < s && y > d)
		{
			puts("Yes");
			return 0;
		}
	}
	puts("No");
	return 0;
}

C - Bowls and Dishes

题目大意

有\(N\)个编号为\(1,2,\dots,N\)的盘子和\(M\)个编号为\(1,2,\dots,M\)的条件。
当编号为\(A_i\)和\(B_i\)的盘子中都有(至少一个)球时,第\(i\)个条件就被满足了。
有\(K\)个编号为\(1,2,\dots,K\)的人。第\(i\)个人会将一个球放入编号为\(C_i\)\(D_i\)的盘子中。
最多能有多少个条件被满足?

\(2\le N\le 100\)
\(1\le M\le 100\)
\(1\le A_i<B_i\le N\)
\(1\le K\le 16\)
\(1\le C_i<D_i\le N\)

输入格式

\(N~M\)
\(A_1~B_1\)
\(\vdots\)
\(A_M~B_M\)
\(K\)
\(C_1~D_1\)
\(\vdots\)
\(C_K~D_K\)

输出格式

输出答案。

样例

样例输入1

4 4
1 2
1 3
2 4
3 4
3
1 2
1 3
2 3

样例输出1

2

如果编号为\(1,2,3\)的人将他们的球分别放入编号为\(1,3,2\)的盘子中,则条件\(1\)和\(2\)将被满足。

样例输入2

4 4
1 2
1 3
2 4
3 4
4
3 4
1 2
2 4
2 4

样例输出2

4

如果编号为\(1,2,3,4\)的人将他们的球分别放入编号为\(3,1,2,4\)的盘子中,则所有条件将被满足。

样例输入3

6 12
2 3
4 6
1 2
4 5
2 6
1 5
4 5
1 3
1 2
2 6
2 3
2 5
5
3 5
1 4
2 6
4 6
5 6

样例输出3

9

分析

这个题数据范围很小,所以我们考虑枚举。
我们可以按人枚举,枚举第\(i\)个人是将自己的球放入编号为\(C_i\)还是\(D_i\)的盘子。
每个人有选\(C_i\)和\(D_i\)两种情况,所以枚举次数为\(2^K\),而题目保证\(1\le K\le16\),所以不会超时。
我们可以使用二进制法来枚举:

  • 有\(K\)个二进制位。
  • 第\(i\)个二进制位如果是\(1\),则第\(i\)个人将球放入编号为\(C_i\)的盘子;否则,他会把球放入编号为\(D_i\)的盘子。

总时间复杂度为\(\mathcal O(M2^K)\)。

代码

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

int a[105], b[105], c[20], d[20];

int main()
{
	int n, m, k;
	scanf("%d%d", &n, &m);
	for(int i=0; i<m; i++)
	{
		scanf("%d%d", a + i, b + i);
		a[i] --, b[i] --;
	}
	scanf("%d", &k);
	for(int i=0; i<k; i++)
	{
		scanf("%d%d", c + i, d + i);
		c[i] --, d[i] --;
	}
	int limit = 1 << k, ans = 0;
	for(int st=0; st<limit; st++)
	{
		bool hasdish[105] = {false};
		for(int i=0; i<k; i++)
			if(st & (1 << i))
				hasdish[c[i]] = true;
			else hasdish[d[i]] = true;
		int cnt = 0;
		for(int i=0; i<m; i++)
			cnt += hasdish[a[i]] && hasdish[b[i]];
		if(cnt > ans) ans = cnt;
	}
	printf("%d\n", ans);
	return 0;
}

D - Staircase Sequences

题目大意

有多少个和为\(N\)、公差为\(1\)的等差数列?
\(1\le N\le 10^{12}\)

输入格式

\(N\)

输出格式

输出答案。

样例

N 输出
\(12\) \(4\)
\(1\) \(2\)
\(63761198400\) \(1920\)

分析

我们设和为\(N\)、公差为\(1\)的等差数列为\([a,b]\),则

\[\frac {(a+b)(b-a+1)} 2=N \]

\[{(a+b)(b-a+1)}=2N \]

所以,我们求\(2N\)的奇偶性不同的因子对数即可。这里注意,题目里的等差数列是可以有负数的,所以最终结果一定要乘\(2\)!
代码总时间复杂度为\(\mathcal O(\sqrt n)\)。

代码

请注意一定要使用long long

#include <cstdio>
using namespace std;

typedef long long LL;

int main()
{
	LL n;
	scanf("%lld", &n);
	n <<= 1LL;
	int cnt = 0;
	for(LL i=1; i*i<=n; i++)
		if(n % i == 0 && i % 2 != n / i % 2)
			cnt ++;
	printf("%d\n", cnt << 1);
	return 0;
}

标签:输出,le,15,AtCoder,int,题解,样例,190,编号
From: https://www.cnblogs.com/stanleys/p/18403454/abc190

相关文章

  • AtCoder Beginner Contest 194 A~E 题解
    A-IScream题目大意在日本,有如下四种冰淇淋产品:至少有\(15\%\)的milksolids和\(8\%\)的milkfat的产品称为“冰淇淋”;至少有\(10\%\)的milksolids和\(3\%\)的milkfat且不是冰淇淋的产品称为“冰奶”;至少有\(3\%\)的milksolids且不是冰淇淋或冰奶的产品称为“乳冰**”;......
  • AtCoder Beginner Contest 198 A~E 题解
    A-Div题目大意两个男孩要分\(N\)颗糖。问一共有几种分法(每个男孩都必须分到糖)?\(1\leN\le15\)输入格式\(N\)输出格式将答案输出为一个整数。样例\(N\)输出\(2\)\(1\)\(1\)\(0\)\(3\)\(2\)分析这题说白了就是将\(N\)分成\(A\)和\(B\)两个正整数......
  • AtCoder Beginner Contest 196 A~E 题解
    A-DifferenceMax题目大意给定四个整数\(a,b,c\)和\(d\)。我们要选择两个整数\(x\)和\(y\)(\(a\lex\leb\);\(c\ley\led\))。输出最大的\(x-y\)。\(-100\lea\leb\le100\)\(-100\lec\led\le100\)输入格式\(a~~b\)\(c~~d\)输出格式输出最大的\(x-y\)。样例\(......
  • Mynavi Programming Contest 2021 (AtCoder Beginner Contest 201) A~E 题解
    A-TinyArithmeticSequence题目大意给定序列\(A=(A_1,A_2,A_3)\)。能否将\(A\)重新排列,使得\(A_3-A_2=A_2-A_1\)?\(1\leA_i\le100\)输入格式\(A_1~A_2~A_3\)输出格式如果能将\(A\)重新排列使得\(A_3-A_2=A_2-A_1\),输出Yes;如果不能,输出No。样例\(A\)输出\((5......
  • AtCoder Beginner Contest 204 A~E 题解
    A-Rock-paper-scissors三个人玩石头剪刀布平局,其中两个出的分别是\(x,y\),求另一个人出的。\(0\lex,y\le2\)(\(0,1,2\)分别表示石头,剪刀,布)输入格式\(x,y\)输出格式用整数格式输出答案。样例\(x\)\(y\)输出\(0\)\(1\)\(2\)\(0\)\(0\)\(0\)分析石头......
  • AISing Programming Contest 2021 (AtCoder Beginner Contest 202) A~E 题解
    A-ThreeDice一个人抛了三个骰子,它们的顶面分别是\(a,b,c\)。求它们的底面之和。这里用的骰子是标准骰子,即两个相对的面之和为\(7\)。\(1\lea,b,c\le6\)输入格式\(a~b~c\)输出格式输出答案。样例\(a\)\(b\)\(c\)答案\(1\)\(4\)\(3\)\(13\)\(5\)\(6......
  • AtCoder Beginner Contest 203 (Sponsored by Panasonic) A~E 题解
    A-Chinchirorin题目大意给定三个整数\(a,b,c\),如果它们中有两个相等,输出另一个;否则,输出\(0\)。\(1\lea,b,c\le6\)输入格式\(a~b~c\)输出格式如果\(a,b,c\)中有两个相等,输出另一个;否则,输出\(0\)。样例\(a\)\(b\)\(c\)输出\(2\)\(5\)\(2\)\(5\)\(4\)......
  • AtCoder Beginner Contest 199 (Sponsored by Panasonic) A~E 题解
    A-SquareInequality题目大意给定三个整数\(A,B,C\)。判断\(A^2+B^2<C^2\)是否成立。\(0\leA,B,C\le1000\)输入格式\(A~B~C\)输出格式如果\(A^2+B^2<C^2\),输出Yes;否则,输出No。样例\(A\)\(B\)\(C\)输出\(2\)\(2\)\(4\)Yes\(10\)\(10\)\(10\)N......
  • KYOCERA Programming Contest 2021 (AtCoder Beginner Contest 200) A~E 题解
    A-Century题目大意公元\(N\)年在第几个世纪中?一个世纪是由\(100\)个年份组成的一个区间。如,\(1\)世纪为\([1,100]\)年,\(2\)世纪为\([101,200]\)年,……\(1\leN\le3000\)输入格式\(N\)输出格式将答案输出为一个整数。样例\(N\)输出\(2021\)\(21\)\(200......
  • AtCoder Beginner Contest 205 A~E 题解
    A-kcal题目大意我们有一种每\(100\)毫升含有\(A\)千卡热量的饮料。\(B\)毫升的这种饮料含有多少千卡热量?\(0\leA,B\le1000\)输入格式\(A~B\)输出格式输出\(B\)毫升这种饮料包含的的千卡数。最大允许浮点数精度误差\(10^{-6}\)。样例\(A\)\(B\)输出\(45\)......