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$是否成立即可。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


#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

样例输出1

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

样例输出2

1

No

样例输入3

样例输出3

1

Yes

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

分析

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

代码

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

 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;

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

样例输出1

1

2

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

样例输入2

样例输出2

1

4

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

样例输入3

样例输出3

1

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)$。

代码

 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


#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$

分析

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

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

代码

请注意一定要使用long long。

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


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