lijyya's Blog
0%

发表于 更新于 分类于 ， ， ，

题目描述

一种叫 0123 的纸牌游戏，桌面上有 c_0 张 0 ， c_1 张 1 ， c_2 张 2 ， c_3 张 3 ，Rabbit 和 Horse 先后取牌（Rabbit 先手），每次选择两张牌，要求数字之和 \leq3 ，然后将这两张牌替换成数值为两张之和的一张牌，最后无法取牌的玩家输，求赢家。

题解：找规律，SG打表

首先发现，能选的组合有： 0+0，0+1，0+2，0+3，1+1，1+2

因此，在刚开始数量足够的时候，无论先手怎么选，后手都能使两人操作后 c_0-2 或 c_1-3 ，因此如果 c_0 为二的倍数且 c_1 为三的倍数，先手必败。

因此，只需考虑剩下（数量不够时）的每种情况，当某种情况能转移到必败态，则该情况为必胜态，反之为必败态。经过分析，一共有五种情况。可以用 dfs 实现。

代码

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
#include <bits/stdc++.h>
using namespace std;

bool dfs(int c0, int c1, int c2, int c3) {
    if (c0 == 0 && c1 == 0) return false;
    if (c0 == 0 && c1 == 1 && c2 == 0) return false;
    if (c0 > 0 && !dfs(c0 - 1, c1, c2, c3)) return true;
    if (c1 >= 2 && !dfs(c0, c1 - 2, c2 + 1, c3)) return true;
    if (c1 > 0 && c2 > 0 && !dfs(c0, c1 - 1, c2 - 1, c3 + 1))
        return true;
    return false;
}

int main() {
    int T;
    scanf("%d", &T);
    for (int t = 1; t <= T; ++t) {
        int c0, c1, c2, c3;
        scanf("%d %d %d %d", &c0, &c1, &c2, &c3);
        bool f;
        if (c0 + c1 + c2 + c3 == 0) f = false;
        else if (c1 + c2 + c3 == 0 && c0 % 2 == 1) f = false;
        else if (c1 + c2 + c3 == 0 && c0 % 2 == 0) f = true;
        else f = dfs(c0 % 2, c1 % 3, c2, c3);
        printf("Case #%d: ", t);
        f ? puts("Rabbit") : puts("Horse");
    }
}

发表于 分类于

1. 字符串相关操作

1.1 字符串输入输出

  • 输入：
1
s = input()
  • 输出：
1
print(s)

在输出时，可通过 + 和 * 运算符同时输出多个字符串（字符串之间无空格），也可通过 , （字符串之间以一个空格间隔）

例如：

1
2
3
4
5
6
7
s1 = "qwq"

s2 = "qq"

print(s1 + s2)
print(s1, s2)
print(s1 * 3)

运行结果：

1
2
3
qwqqq
qwq qq
qwqqwqqwq

占位符的使用方法：

1
2
3
4
5
6
7
s = 3.1415
print("%d" % s)
print("%.3lf" % s)
print("%.3f" % s)
# 四舍五入
print("%s" % str(s))
print("%s+%d" % (str(s),(s))

运行结果：

1
2
3
4
5
3
3.142
3.142
3.1415
3.1415+3

改变结尾方式：使用 end 改变

具体用法：

1
2
3
4
5
a = 2
print(a)
# 默认为换行
print(a, end = " ")
print(a)

运行结果：

1
2
2
2 2

1.2 字符串的拼接及长度获取

  • 拼接可使用 + 和 * 运算符将多个字符串合为一个字符串

  • 长度获取：

1
l = len(s)

1.3 字符串的转化

  • 大小写转化

upper() 可以将字符串中的小写字母转化为大写字母， lower() 可以将字符串中的大写字母转化为小写字母， title() 可以将字符串所有单词的首字母变成大写，而其他字母依然小写。

upper() 具体用法：

1
2
3
4
5
6
s = "aBcD"
print(s)
s.upper()
print(s)
s1 = s.upper()
print(s1)

运行结果：

1
2
3
aBcD
aBcD
ABCD

可以注意到， s.upper() 对 s 本身并不会造成任何影响，需要赋值给字符串变量才能体现出来。 lower() 和 title() 同理。

  • 去除首尾空格

strip() 可以去除字符串两侧（不包含内部）全部的空格。使用该方法，也可以通过指定参数，去除两侧指定的特定字符。（不加任何参数就是默认删除空格）

注意：

在指定参数时，如果参数是多个字符，则该方法会将多个字符逐个去比对，进行删除（区分大小写），直到首尾两侧没有匹配的字符为止。该方法t同样对字符串中间的字符没有影响。

这东西同样得记得赋值！

具体用法：

1
2
3
4
5
6
s1 = " qqwqq "
s2 = s1.strip()
s3 = s2.strip("q")
print(s1)
print(s2)
print(s3)

运行结果：

1
2
3
qqwqq 
qqwqq
w

1.4 字符串替换

  • 前置知识：字符串查找

利用 find() 可以在一个较长的字符串中查找子字符串。如果该字符串中有一个或者多个子字符串，则该方法返回第一个子串所在位置的最左端索引（注意：索引从 0 开始），若没有找到符合条件的子串，则返回 -1 。

具体用法：

1
2
3
4
s1 = "qwqaqwq"
print(s1.find("qaq"))
print(s1.find("qwq"))
print(s1.find("QwQ"))

运行结果：

1
2
3
2
0
-1
  • 字符串替换

replace() 函数括号中包括两个参数，第一个参数是代替换串，第二个参数是替换串。

具体语法：

1
2
3
4
5
6
7
8
9
s = "qwqaqwq"
olds = "qaq"
news = "QwQ"
print(s)
s1 = s.replace(olds, news)
# olds: 将被替换
# news: 用来替换
print(s)
print(s1)

运行结果：

1
2
3
qwqaqwq
qwqaqwq
qwQwQwq

1.5 字符串分割

split() 可以将字符串分割成字符列表，括号里共一个参数，表示以什么作为分隔符（不传入参数默认以 " " 或 "\n" 或 "\t"作为分隔符），若字符串中未出现该分隔符则不分割，即列表中只包含它本身。

具体用法：

1
2
3
4
s = "a+b c+d\ne+f"
print(s.split())
print(s.split("+"))
print(s.split("&"))

运行结果：

1
2
3
['a+b', 'c+d', 'e+f']
['a', 'b c', 'd\ne', 'f']
['a+b c+d\ne+f']']

1.6 字符串与其他类型相互转换

具体用法：

1
2
3
4
5
6
7
8
9
10
11
s1 = "123456"
s2 = "2.3"
print(int(s1))
print(eval(s1))
print(bool(s1))
print(float(s2))
print(eval(s2))
l1 = list(s1)
print(l1)
l2 = [ord(x) - ord("0") for x in l1]
print(l2)s2))

运行结果：

1
2
3
4
5
6
7
123456
123456
True
2.3
2.3
['1', '2', '3', '4', '5', '6']
[1, 2, 3, 4, 5, 6]

2. 变量与表达式

2.1 各种运算符

操作符 描述
+ 加
- 减
* 乘
/ 除
// 整除
% 取余
** 幂

2.2 math 库函数

  • 两种调用方式
1
2
import math
math.<函数名>()
1
2
from math import *
<函数名>()
  • 常用函数
函数名 描述
pi 圆周率数值（注意不是弧度）
e 自然常数
abs(x) 整数型绝对值
fabs(x) 浮点数型绝对值
exp(x) e^x
log2(x)
log10(x)
log(x) ln(x)
pow(x, y) x^y
sqrt(x) x 的平方根
cos(x)（sin tan 等同理） 三角函数
degrees(x) 弧度转角度
radians(x) 角度转弧度

3. 各种结构

注意缩进！！！！！！！！！！

3.0 条件表达式

<, <=, >, >=, ==, !=

and, or, not

优先级 not>and>or

3.1 分支结构

1
2
3
4
5
6
7
if <条件1>:
    <语句1>
elif <条件2>:
    <语句2>
...
else:
    <语句>

elif 和 else 部分可按需取舍

分支结构可嵌套

题型相关知识补充：闰年指的是能被 4 整除但不能被 100 整除或者能被 400 整除。

3.2 循环结构

  • while 语句
1
2
while <条件>:
    <语句>

执行顺序：

  1. 判断条件语句为真还是假

  2. 如果为真，执行语句块；如果为假，跳出循环

  3. 重复上述过程 ...

（直到跳出循环）

（若陷入死循环，就一直执行下去）

  • for 语句
1
2
for <循环变量> in <遍历结构(可以是列表，字符串等，例如range(n)就是一个列表)>:
    <语句>

  • range(n) 生成一个包含 0 到 n-1 的列表

  • range(start, stop) 生成一个包含 start 到 stop-1 的列表

  • range(start, stop, step) 生成一个包含 start 到 stop-1 步长为 step 的列表

  • continue 与 break

continue ：结束当前循环，进入下一次循环（对于当前所在的循环结构）

break ：直接结束循环（对于当前所在的循环结构）

4. 元组

元组的元素不可修改，列表的元素可修改，这是他们俩的典型区别。

元组内部有序。

4.1 创建

1
2
3
4
tuple1 = ("a", "b", 1, 2)
tuple2 = (1, 2, 3)
tuple3 = 1, 2, "a"
tuple_none = () # 创建空元组

4.2 访问

1
2
3
4
5
6
7
t = (1, 2, 3, 4, 5)
print(t[1])
print(t[-1])
print(t[0: 3])
print(t[0: 4: 2])
print(t[4: 1: -1])
print(t[-1: :-1])

运行结果：

1
2
3
4
5
6
2
5
(1, 2, 3)
(1, 3)
(5, 4, 3)
(5, 4, 3, 2, 1)

4.3 连接

元组元素无法修改，只能通过 + 运算符连接两个元组：

1
t3 = t1 + t2

4.4 删除

元组元素无法删除，只能通过 del 语句删除整个元组：

1
2
t = (1, 2, 3)
del t

删除完毕后再次调用已删除的元组程序会报错：

1
NameError: name 't' is not defined

4.5 函数

函数 描述
len(t) 计算元素个数
cmp(t1, t2) 比较两个元组
max(t) 找最大值
min(t) 找最小值
tuple(list) 将列表转换为元组

注意：元组中数字小于其他类型

5. 列表

5.1 创建

1
2
3
list1 = ["a", "b", 1, 2]
list2 = [1, 2, 3]
list_none = [] # 创建空列表

5.2 访问

1
2
3
4
5
6
7
l = [1, 2, 3, 4, 5]
print(l[1])
print(l[-1])
print(l[0: 3])
print(l[0: 4: 2])
print(l[4: 1: -1])
print(l[-1: :-1])

运行结果：

1
2
3
4
5
6
2
5
[1, 2, 3]
[1, 3]
[5, 4, 3]
[5, 4, 3, 2, 1]

5.3 更新

1
2
3
4
5
6
7
8
9
10
l = []
l.append(7)
l.append(3)
print(l)
l.insert(1, 5) # insert(索引(正), 元素) 表示在该索引处插入元素
print(l)
l.insert(-1, 9) # insert(索引(负), 元素) 表示在该索引前插入元素
print(l)
l[0] = 2
print(l)nt(l)

运行结果：

1
2
3
4
[7, 3]
[7, 5, 3]
[7, 5, 9, 3]
[2, 5, 9, 3]]

5.4 删除

1
2
3
4
5
6
7
l = [1, 3, 5, 7, 3]
del l[3]
print(l)
l.remove(3) # 删除第一个为 3 的元素
print(l)
l.pop(0)
print(l)

运行结果：

1
2
3
[1, 3, 5, 3]
[1, 5, 3]
[5, 3]

5.5 函数

函数 描述
len(l) 计算元素个数
cmp(l1, l2) 比较两个列表
max(l) 找最大值
min(l) 找最小值
list(tuple) 将元组转换为列表
list.append(x) 末尾添加元素
list.insert(index, x) 插入元素
list.pop(index) 末尾删除元素（index 默认 -1）
list.remove(x) 删除指定元素
list.count(x) 统计某元素出现次数
list.extend(seq) 末尾追加另一个序列的所有元素
list.index(x) 找出某个值第一个匹配项的索引位置
list.reverse() 反向列表中的元素
list.sort() 升序排序
list.sort(reverse = True) 降序排序

6. 字典

字典无序，不允许同一个键出现多次，键不可变。

6.1 创建

1
2
3
dict1 = {"a": 1, "b": 2}
dict2 = {"a": 1, 3: 4}
dict_none = {} # 创建空字典

6.2 访问

1
2
d = {"a": 1, "b": 2, "c": 3}
print(d["a"]))

运行结果：

1
1

6.3 更新

1
2
3
d = {"a": 1, "b": 2, "c": 3}
d["a"] = 4
print(d["a"])

运行结果：

1
4

6.4 删除

1
2
3
4
d = {"a": 1, "b": 2, "c": 3}
del d["a"] # 删除键是"a"的条目
d.clear()  # 清空
del d      # 删除字典

6.5 函数

函数 描述
len(d) 计算键个数
cmp(d1, d2) 比较两个字典
str(d) 输出字典可打印的字符串表示
type(v) 返回输入的变量类型，如果变量是字典就返回字典类型
d.clear() 清空
d.copy() 浅复制
d.fromkeys(seq[, val]) 创建一个新字典，以序列 seq 中元素做字典的键，val 为字典所有键对应的初始值
d.get(key, default=None) 返回指定键的值，如果值不在字典中返回default值
d.has_key(key) 如果键在字典dict里返回true，否则返回false
d.items() 返回可遍历的(键, 值) 元组的列表
d.keys() 返回一个字典所有键的列表
d.values() 返回一个字典所有值的列表
d.update(d2) 把字典d2的键/值对更新到d里
pop(key[,default]) 删除字典给定键 key 所对应的值，返回值为被删除的值。key值必须给出。 否则，返回default值。
popitem() 返回并删除字典中的最后一对键和值。