年前集训总结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 binations(a, r))  9.滑动窗口

滑动窗口的两种类型

固定大小的滑动窗口：

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

动态大小的滑动窗口：

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

                第一次排位赛问题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)