ICPC2022KunMingB

2022-04-24

题目大意

给定一个$W*H$的方格矩阵。和$n$的小方格阵，每个覆盖了左下角为$x_{i1},y_{i1}$，右上角为$x_{i2},y_{i2}$的方格。

每一步会等概率随机选择一个方格阵(包括被染色的)，把它全部涂黑，问把$W*H$的方格矩阵全部涂黑的期望步数是多少？ more >>

展开全文 >>

ICPC2022KunMingG

2022-04-23

题目大意

有$n$个豆子排成一排,每个豆子有$p_i$的概率被选中.每次随机选一个豆子,将其放到最前面,每次操作的代价是该豆子前面豆子的个数,问在操作无限次后再操作一次,操作代价的期望是多少？

more >>

展开全文 >>

ICPC2022KunMingF

2022-04-23

题目大意

给定一个$n$个节点的树，每个点有个权值$b_i$,任选一条路径，路径上的点至少为$2$个。求$max(\sum\frac{-x^2+b_kx}{v})$,其中$b_k$是路径上点的权值，$v$是路径上点的个数，$x$是任意一个自己选择的数。

more >>

展开全文 >>

ICPC 2022 KunMing K

2022-04-23

题目大意

G准备玩$n$场游戏，它心中有个胜率$x = \frac{a}{b}$,如果当前赢的局数 / 总局书小于等于$x$,那么他就会赢，否则它就会输。给定$a,b,n$，求他能赢多少局。 more >>

展开全文 >>

cf1665E

2022-04-18

题目大意

给定$n(1 \le n \le 10^5)$个数$a_i(0 \le a_i \le 2^{30})$。有$q(1 \le q \le 10^5)$次询问：求$l,r$内任选两个数，它们与运算后的最小值是多少。 more >>

展开全文 >>

Python 字符串，相关函数详解

2022-04-18

字符串编码

GBK2312 是我国制定的中文编码，用两个字节表示中文
Unicode 把所有语言同一到一套编码里，不会出现乱码,两个字节表示一个字符，偏僻字用四个
UTF-8对全世界需要用到的字符进行了编码，是“可变长编码”，用一个字节表示字母，三个字节表示中文，还有一些是两字节或四字节。

Python3.x版本默认使用UTF-8格式编码

转义字符

在字符串前面加上'r',或者'R',表示后面的字符串不进行任何转义。

1	path = r'C:\windows\python.exe'

字符串的格式化

% 进行格式化

格式

1	print('%d %s' % (a, b))

符号含义

'-' 指定左对齐 '+' 正数前面加+号 '.n' 指定精度

1 2	>>>'%.2f' % 0。33333 0.33

### 格式字符和C++基本相同， * %d 十进制整数 * %e 以e为底的指数 * %o 八进制整数

format()方法进行格式化

基本语法是通过'{}',':'替换之前的'%'

1 2	>>>'{:%}'.format(3.5) '350.0000%'

各类格式字符含义

指定位置参数

"{}{}".format('Hello', 'World') # 按默认位置
>>> "{0}{1}{0}".format('Hello', 'World'') # 指定位置
'World Hello World’
>>> print("my name is {name}, my age is {age}, and my QQ is
{qq}".format(name = "Dong Fuguo",age = 40,qq = "30646****")) # 变量命名
my name is Dong Fuguo, my age is 40, and my QQ is 30646****

字符串前加f

与format方法基本类似

>>> name = 'Dong'
>>> age = 39
>>> f'My name is {name}, and I am {age} years old.'
'My name is Dong, and I am 39 years old.'


>>> width = 10
>>> precision = 4
>>> value = 11/3
>>> f'result:{value:{width}.{precision}}'# 可以指定宽度和精度
'result: 3.667'

常用函数

find,rfind,count, index,rindex

find(str,beg=0,end=len(str))
rfind(str,beg=0,end=len(str)))
index(str,beg=0,end=len(str)))
rindex(str,beg=0,end=len(str)))
count()

find()和rfind方法分别用来查找一个字符串在另一个字符串指定范围（默认是整个字符串）中首次和最后一次出现的位置，如果不存在则返回-1
index()和rindex()方法用来返回一个字符串在另一个字符串指定范围中首次和最后一次出现的位置，如果不存在则抛出异常
count()方法用来返回一个字符串在当前字符串中出现的次数

split()、rsplit()、partition()、rpartition()

1	split(str="", num=string.count(str))、rsplit(str="",num=string.count(str))

split()和rsplit()方法分别用来以指定字符为分隔符，把当前字符串从左往右或从右往左分隔成多个字符串，并返回包含分隔结果的列表
partition()和rpartition()用来以指定字符串为分隔符将原字符串分隔为3部分，即分隔符前的字符串、分隔符字符串、分隔符后的字符串，如果指定的分隔符不在原字符串中，则返回原字符串和两个空字符串。把字符串 string 分成一个 3 元素的元组(string_pre_str,str,string_post_str)

join

返回通过指定字符连接序列中元素后生成的新字符串。

1
2
3

>>> li = ["apple","peach","banana","pear"]
>>> ','.join(li)
'apple,peach,banana,pear'

lower()、upper()、capitalize()、title()、swapcase()

>>> s =
"What is Your Name?"
>>> s.lower() #返回小写字符串
'what is your name?'
>>> s.upper() #返回大写字符串
'WHAT IS YOUR NAME?'
>>> s.capitalize() #字符串首字符大写'What is your name?'
>>> s.title() #每个单词的首字母大写'What Is Your Name?'
>>> s.swapcase() #大小写互换
'wHAT IS yOUR nAME?'

replace()、maketrans()、translate()

replace

查找替换replace(old, new[, max])，类似于Word中的“全部替换”功能 * old -- 将被替换的子字符串 * new -- 新字符串，用于替换old子字符串 * max -- 可选字符串, 替换不超过 max 次

注意：返回的是一个新字符串

>>> s ="中国，中国"
>>> print(s)
中国，中国
>>> s2 = s.replace("中国","中华人民共和国")
>>> print(s2)
中华人民共和国，中华人民共和国

maketrans()、translate()

字符串对象的maketrans()方法用来生成字符映射表，而translate()方法用来根据映射表中定义的对应关系转换字符串并替换其中的字符，使用这两个方法的组合可以同时处理多个字符。

#创建映射表，将字符"abcdef123"一一对应地转换为"uvwxyz@#$"
>>> table =
''.maketrans('abcdef123','uvwxyz@#$')
>>> s ="Python is a greate programming language. I like it!"
#按映射表进行替换
>>> s.translate(table)
'Python is u gryuty progrumming lunguugy. I liky it!'

一些常用的全体字母，并实现凯撒加密

lower = string.ascii_lowercase #小写字母
upper = string.ascii_uppercase #大写字母
before = string.ascii_letters
after = lower[k:] + lower[:k] + upper[k:] + upper[:k]
table =''.maketrans(before, after) #创建映射表 
return s.translate(table)

strip()、rstrip()、lstrip()

>>> s =" abc "
>>> s.strip() #删除空白字符
'abc'
>>> '\n\nhello world \n\n'.strip() #删除空白字符
'hello world'
>>> "aaaassddf".strip("a") #删除指定字符
'ssddf'
>>> "aaaassddf".strip("af")
'ssdd'
>>> "aaaassddfaaa".rstrip("a") #删除字符串右端指定字符
'aaaassddf'
>>> "aaaassddfaaa".lstrip("a") #删除字符串左端指定字符
'ssddfaaa'

注意，这三个函数的参数指定的字符串并不作为一个整体对待，而是在原字符串的两侧、右侧、左侧删除参数字符串中包含的所有字符

1 2	>>> 'aabbccddeeeffg'.strip('gbaefcd') ''

startswith()、endswith()

s.startswith(t, beg=0,end=len(string))、s.endswith(t,beg=0,end=len(string))，判断字符串是否以指定字符串开始或结束

>>> s = 'Beautiful is better than ugly.'
>>> s.startswith('Be') #检测整个字符串
True
>>> s.startswith('Be', 5) #指定检测范围起始位置
False
>>> s.startswith('Be', 0, 5) #指定检测范围起始和结束位置
True

isalnum()、isalpha()、isdigit()、isspace()、isupper()、islower()

isalnum()、isalpha()、isdigit()、isspace()、isupper()、islower()，用来测试字符串是否为数字或字母、是否为字母、是否为数字字符、是否为空白字符、是否为大写字母以及是否为小写字母。

>>> '1234abcd'.isalnum()
True
>>> '1234abcd'.isalpha() #全部为英文字母时返回True
False
>>> '1234abcd'.isdigit() #全部为数字时返回True
False
>>> 'abcd'.isalpha()
True
>>> '1234.0'.isdigit()
False

center()、ljust()、rjust()

center()、ljust()、rjust()，返回指定宽度的新字符串，原字符串居中、左对齐或右对齐出现在新字符串中，如果指定宽度大于字符串长度，则使用指定的字符（默认为空格）进行填充。

>>> 'Hello world!'.center(20) #居中对齐，以空格进行填充
' Hello world! '
>>> 'Hello world!'.center(20,'=') #居中对齐，以字符=进行填充
'====Hello world!===='
>>> 'Hello world!'.ljust(20,'=') #左对齐
'Hello world!========'
>>> 'Hello world!'.rjust(20,'=') #右对齐
'========Hello world!'

字符串支持的运算符

+

生成新的字符串

1 2	>>> 'hello ' + 'world' 'hello world'

in

成员判断，关键字in

>>> "a" in "abcde" #测试一个字符中是否存在于另一个字符串中
True
>>> 'ab' in 'abcde'
True
>>> 'ac' in 'abcde' #关键字in左边的字符串作为一个整体对待
False
>>> "j" in "abcde"
False

*

Python字符串支持与整数的乘法运算，表示序列重复，也就是字符串内容的重复，得到新字符串

1 2	>>> 'abcd' * 3 'abcdabcdabcd'

适用于字符串对象的内置函数

>>> x =
'Hello world.'
>>> len(x) #字符串长度
12
>>> max(x) #最大字符
'w'
>>> min(x)
' '
>>> list(zip(x,x)) #zip()也可以作用于字符串
[('H','H'), ('e','e'), ('l','l'), ('l','l'), ('o','o'), (' ','',('w','w'), ('o','o'), ('r','r'), ('l','l'), ('d','d'), ('.','.')]
>>> sorted(x)
[' ','.','H','d','e','l','l','l','o','o','r','w']
>>> list(reversed(x))
['.','d','l','r','o','w',' ','o','l','l','e','H']
>>> list(enumerate(x))
[(0,'H'), (1,'e'), (2,'l'), (3,'l'), (4,'o'), (5,' '), (6,'w'),(7,'o'), (8,'r'), (9,'l'), (10,'d'), (11,'.')]
>>> list(map(add, x, x))
['HH','ee','ll','ll','oo',' ','ww','oo','rr','ll','dd','..']