年前集训总结python

1.用空格隔开输出列表list1

print(" ".jion(map(str,list1)))

2.转换函数

int()
将一个数字或字符串转换为整数。可以指定基数，支持从其他进制（如二进制、十六进制）转换为十进制。
int('101', 2)   # 二进制字符串转十进制 => 5
int('1F', 16)   # 十六进制字符串转十进制 => 31

float()
将一个数字或字符串转换为浮动点数。
float('3.14')   # 转换为浮动点数 => 3.14

complex()
将一个数字或字符串转换为复数。可以指定实部和虚部。
complex(1, 2)   # 生成复数 => (1+2j)
complex('1+2j') # 从字符串生成复数 => (1+2j)

str()
将对象转换为字符串。
str(123)    # 将整数转为字符串 => '123'
str(3.14)   # 将浮点数转为字符串 => '3.14'

repr()
返回对象的字符串表示，通常用于调试，目标是能够重建对象（即返回的字符串可以通过 eval() 恢复原对象）。
repr(123)   # 返回字符串 => '123'
repr('abc') # 返回字符串 => "'abc'"

进制转换函数

bin()
将一个整数转换为二进制字符串，返回值以 '0b' 为前缀。
bin(5)    # 转换为二进制 => '0b101'

oct()
将一个整数转换为八进制字符串，返回值以 '0o' 为前缀。
oct(8)    # 转换为八进制 => '0o10'

hex()
将一个整数转换为十六进制字符串，返回值以 '0x' 为前缀。
hex(255)  # 转换为十六进制 => '0xff'

序列类型转换函数

list()
将一个可迭代对象转换为列表。
list('abc')  # 转换为列表 => ['a', 'b', 'c']

tuple()
将一个可迭代对象转换为元组。
tuple('abc')  # 转换为元组 => ('a', 'b', 'c')

set()
将一个可迭代对象转换为集合。
set([1, 2, 2, 3])  # 转换为集合 => {1, 2, 3}

dict()
将一个序列转换为字典，通常传入的是一个包含键值对的可迭代对象。
dict([(1, 'a'), (2, 'b')])  # 转换为字典 => {1: 'a', 2: 'b'}

其他类型转换函数

bool()
将一个值转换为布尔类型，任何非零数字、非空序列、非空集合和字典都会转换为 True，否则转换为 False。
bool(0)      # 转换为布尔值 => False
bool(1)      # 转换为布尔值 => True
bool('abc')  # 转换为布尔值 => True

chr()
将一个整数转换为对应的字符（根据 Unicode 码点）。
chr(65)   # 转换为字符 => 'A'

ord()
将一个字符转换为对应的整数（根据 Unicode 码点）。
ord('A')  # 转换为对应的整数 => 65

id()
返回对象的唯一标识符。
id('abc')  # 返回对象的内存地址（标识符）

type()
返回对象的类型。
type(123)  # 返回对象的类型 => <class 'int'>

eval()
计算一个字符串表达式并返回结果。
eval('3 + 4')  # 计算表达式 => 7

exec()
执行存储在字符串中的 Python 代码。
exec('x = 5')  # 执行代码 => x = 5
 

3.处理无限输入

while True:
    try:
    
    except EOFError:
        break

 1.21问题I

inputdata=sys.stdin.read().splitlines()#读取所有输入数据并将其按行分割成一个列表，每一行的数据是一个字符串。
idx=0#用于追踪当前处理到哪一行。
while idx<len(inputdata):#按行数处理所有数据
    n=int(inputdata[idx])#读取当前组数据中的第一个数字，它表示接下来要处理的用户数量。
    idx+=1#将索引增加 1，移动到下一个输入数据。
    if n==0:#n=0的数据不管
        continue
    ...#处理这一组数据
    idx+=n#更新索引，跳过这些用户数据，准备读取下一组数据。
    ...

4.格式化输出

name = "Alice"
age = 30
print(f"My name is {name} and I am {age} years old.")

value = 1234567.8910
print(f"{value:,.2f}")  # 以千分位分隔符输出两位小数

number = 42
print(f"Number: {number:10}")  # 宽度为10，默认右对齐
print(f"Number: {number:<10}")  # 左对齐
print(f"Number: {number:^10}")  # 居中对齐

5.素数筛

def sieve_of_eratosthenes(limit):
    sieve = [True] * (limit + 1)  # 创建布尔数组
    sieve[0] = sieve[1] = False   # 0 和 1 不是素数
    for i in range(2, int(limit ** 0.5) + 1):  # 从2到sqrt(limit)
        if sieve[i]:
            for j in range(i * i, limit + 1, i):
                sieve[j] = False  # 标记倍数为合数
    return [x for x in range(2, limit + 1) if sieve[x]]  # 返回素数列表

6.字符串处理

字符串处理函数

1. 字符串基本操作

连接字符串：使用 + 连接两个或多个字符串。
s1 = "Hello"
s2 = "World"
result = s1 + " " + s2  # 结果是 "Hello World"

重复字符串：使用 * 将字符串重复多次。
s = "abc"
result = s * 3  # 结果是 "abcabcabc"

字符串长度：使用 len() 获取字符串的长度。
s = "Hello"
length = len(s)  # 结果是 5

转换为小写：lower() 返回字符串的小写版本。
s = "Hello"
result = s.lower()  # 结果是 "hello"

转换为大写：upper() 返回字符串的大写版本。
s = "Hello"
result = s.upper()  # 结果是 "HELLO"

大小写反转：swapcase()

去除两端空格：strip() 去除字符串两边的空白字符。
s = "  Hello  "
result = s.strip()  # 结果是 "Hello"

替换子字符串：replace() 用指定的字符串替换目标字符串中的部分内容。
s = "Hello World"
result = s.replace("World", "Python")  # 结果是 "Hello Python"

查找子字符串：find() 返回子字符串的第一个出现位置，如果没有找到则返回 -1。
s = "Hello World"
result = s.find("World")  # 结果是 6

检查字符串是否以某个子字符串开头/结尾：startswith() 和 endswith()
s = "Hello World"
result = s.startswith("Hello")  # 结果是 True
result = s.endswith("World")   # 结果是 True

按分隔符拆分字符串：split() 方法按指定的分隔符将字符串拆分为一个列表。
s = "Hello,World,Python"
result = s.split(",")  # 结果是 ['Hello', 'World', 'Python']

拼接字符串：join() 方法将一个可迭代对象中的字符串连接起来。
words = ["Hello", "World", "Python"]
result = " ".join(words)  # 结果是 "Hello World Python"

使用 format() 方法格式化字符串：
name = "Alice"
age = 25
result = "My name is {} and I am {} years old.".format(name, age)  # 结果是 "My name is Alice and I am 25 years old."

使用 f-string 格式化字符串（Python 3.6 及以上）：
name = "Alice"
age = 25
result = f"My name is {name} and I am {age} years old."  # 结果是 "My name is Alice and I am 25 years old."

检查字符串是否为数字：isdigit() 检查字符串是否由数字组成。
s = "12345"
result = s.isdigit()  # 结果是 True

检查字符串是否由字母组成：isalpha() 检查字符串是否只包含字母。
s = "Hello"
result = s.isalpha()  # 结果是 True

检查字符串是否为字母和数字的组合：isalnum() 检查字符串是否只包含字母和数字。
s = "Hello123"
result = s.isalnum()  # 结果是 True

检查字符串是否为空：isspace() 检查字符串是否仅包含空白字符。
s = "    "
result = s.isspace()  # 结果是 True

反转字符串：
s = "Hello"
result = s[::-1]  # 结果是 "olleH"

将字符串按指定宽度填充：rjust()、ljust()、center() 等方法。
s = "Hello"
result = s.rjust(10, "*")  # 结果是 "***Hello"
result = s.ljust(10, "*")  # 结果是 "Hello***"
result = s.center(10, "*") # 结果是 "**Hello**"

7.字典

1. 创建字典

# 创建一个空字典
my_dict = {}
# 创建一个包含初始键值对的字典
person = {"name": "Alice", "age": 25, "city": "New York"}

2. 访问字典的值

通过键来访问对应的值：
# 访问字典中的值
print(person["name"])  # 输出: Alice
print(person["age"])   # 输出: 25
如果访问一个不存在的键，会抛出 KeyError 错误。

3. 使用 .get() 方法访问字典值

使用 get() 方法访问字典的值，如果键不存在，则返回 None（或者指定的默认值）：
# 使用 .get() 方法，键不存在时不会抛出错误
print(person.get("name"))  # 输出: Alice
print(person.get("address"))  # 输出: None
print(person.get("address", "Unknown"))  # 输出: Unknown

4. 添加和修改键值对

添加：可以直接通过键来添加新的键值对。
修改：如果键已经存在，可以直接修改对应的值。
# 添加新的键值对
person["address"] = "123 Main St"
print(person)  # 输出: {'name': 'Alice', 'age': 25, 'city': 'New York', 'address': '123 Main St'}
# 修改已有的键值对
person["age"] = 26
print(person)  # 输出: {'name': 'Alice', 'age': 26, 'city': 'New York', 'address': '123 Main St'}

5. 删除键值对

可以使用 del 语句或 .pop() 方法删除字典中的键值对。
# 使用 del 删除键值对
del person["address"]
print(person)  # 输出: {'name': 'Alice', 'age': 26, 'city': 'New York'}
# 使用 .pop() 删除键值对并返回被删除的值
age = person.pop("age")
print(age)     # 输出: 26
print(person)  # 输出: {'name': 'Alice', 'city': 'New York'}

6. 遍历字典

你可以遍历字典的键、值或者键值对。
# 遍历字典的键
for key in person:
    print(key)
# 遍历字典的值
for value in person.values():
    print(value)
# 遍历字典的键值对
for key, value in person.items():
    print(f"{key}: {value}")

7. 字典常用方法

len(dict)：返回字典中键值对的数量。
dict.keys()：返回字典的所有键。
dict.values()：返回字典的所有值。
dict.items()：返回字典的所有键值对。
dict.clear()：清空字典中的所有键值对。

# 返回字典中的键
print(person.keys())   # 输出: dict_keys(['name', 'city'])

# 返回字典中的值
print(person.values())  # 输出: dict_values(['Alice', 'New York'])

# 返回字典中的键值对
print(person.items())   # 输出: dict_items([('name', 'Alice'), ('city', 'New York')])

# 清空字典
person.clear()
print(person)  # 输出: {}

8. 使用 defaultdict（来自 collections 模块）

defaultdict 是 dict 的一个子类，它提供了一个非常方便的功能：当访问字典中不存在的键时，会自动创建一个默认值。
from collections import defaultdict
# 创建一个默认值为 list 的 defaultdict
my_dict = defaultdict(list)
# 向字典中添加元素时，如果键不存在，会自动创建一个空的 list
my_dict["a"].append(1)
my_dict["a"].append(2)
my_dict["b"].append(3)
print(my_dict)  # 输出: defaultdict(<class 'list'>, {'a': [1, 2], 'b': [3]})
lambda name: (len(name), name)：这是一个匿名函数（lambda 函数），用于定义排序的规则。它接收每一个名字（name），并返回一个元组 (len(name), name)：
len(name) 计算名字的长度。
name 本身是用来在长度相同的情况下进行字典顺序比较。

8.从序列 a 中选取所有可能的 r 个元素的组合

第一次排位赛题D、H

import itertools
result = list(itertools.combinations(a, r))

 9.滑动窗口

滑动窗口的两种类型

1. 固定大小的滑动窗口：

   • 窗口的大小是固定的，通常用于解决某个连续子数组或子串的问题。
   • 在每次滑动时，窗口的大小保持不变，通常是右边界向右滑动一个单位，左边界保持不变，或者左边界右移，右边界也随之右移。

2. 动态大小的滑动窗口：

   • 窗口的大小是动态变化的，通常是基于某个条件，右边界不断扩展，左边界根据需要向右滑动，确保满足某个特定条件（如子数组和小于某个值，子串包含所有的字符等）。

                第一次排位赛问题N

典型问题：

最大/最小子数组和：找出一个数组中，连续的子数组具有最大或最小的和。

包含所有字符的最小子串：在给定的字符串中，找出包含目标子串所有字符的最小子串。

最长不重复的子串：找出一个字符串中最长的不含重复字符的子串。

10.排序

1.20问题G

返回一个新列表
sorted(iterable, key=None, reverse=False)

# 默认升序排序
numbers = [5, 2, 9, 1, 5, 6]
sorted_numbers = sorted(numbers)
print(sorted_numbers)  # [1, 2, 5, 5, 6, 9]

# 降序排序
sorted_numbers_desc = sorted(numbers, reverse=True)
print(sorted_numbers_desc)  # [9, 6, 5, 5, 2, 1]

# 按照绝对值排序
numbers = [-5, 3, -2, 7, -1]
sorted_numbers_by_abs = sorted(numbers, key=abs)
print(sorted_numbers_by_abs)  # [-1, -2, 3, -5, 7]


更改原列表
list.sort(key=None, reverse=False)

# 默认升序排序
numbers = [5, 2, 9, 1, 5, 6]
numbers.sort()
print(numbers)  # [1, 2, 5, 5, 6, 9]

# 降序排序
numbers.sort(reverse=True)
print(numbers)  # [9, 6, 5, 5, 2, 1]

# 按照绝对值排序
numbers = [-5, 3, -2, 7, -1]
numbers.sort(key=abs)
print(numbers)  # [-1, -2, 3, -5, 7]

#字典排序 返回一个按照键排序的列表，列表中的每个元素是一个元组，包含键和值。

11.计数

1.21题I

#Counter(users) 会对列表 users 中每个元素的出现次数进行统计，并返回一个 Counter 对象，它看起来像一个字典，键是列表中的元素，值是每个元素的出现次数。
from collections import Counter

users = ['alice', 'bob', 'alice', 'alice', 'bob']
counter = Counter(users)

print(counter)#输出Counter({'alice': 3, 'bob': 2})

12.动态规划

1.22题B

动态规划的基本步骤：
定义状态：明确我们需要解决的问题可以表示为某个状态的子问题。一般来说，动态规划问题的状态是一个数组或表格，表示从初始状态到目标状态的某个中间状态。
状态转移方程：明确从一个状态如何转移到另一个状态，即当前状态与前一个状态的关系。
初始化：设置初始状态，通常是边界条件或起点。
填表：按照状态转移方程逐步填充表格或数组。
返回结果：根据最终状态的结果，返回最优解。

13.快速幂

#a^b%p
a,b,p=map(int,input().split())
if p==1:
    print("0")
    exit()
 
if b==0:
    print("1")
    exit()
 
if a<0:
    a+=p
    
result=1
base=a%p
if base==0:
    print("0")
    exit()
while b>0:
    if b%2==1:
        result=(result*base)%p
    base=(base*base)%p
    b//=2
print(result)