ACM中一些python3的使用方法

发表于 更新于 分类于 阅读次数：

这里收录一些OJ平台可能用到的Pyhton3使用技巧以及模板

输入方式

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
'''
def main():
    Do somthing
if __name__ == '__main__':
    t = int(input())
    for i in range(t):
        main()
'''
for T in range(0,int(input())): #T组数据
    N=int(input())
    n,m=map(int,input().split())
    s=input()
    s=[int(x) for x in input().split()] #一行输入的数组
    a[1:]=[int(x) for x in input().split()] #从下标1开始读入一行
    for i in range(0,len(s)):
        a,b=map(int,input().split())

while True: #未知多组数据
    try:
        #n,m=map(int,input().split())
        #print(n+m,end="\n")
    except EOFError: #捕获到异常
        break

一些基本数据结构

python中的栈和队列可以使用列表来模拟，或者import deque
匿名函数使用lambda关键字来定义lambda 参数: 表达式

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
#使用中括号[]定义一个列表
# l=[23,'wtf',3.14]
list.append(obj)#将obj添加到list末尾,O(1)
list.insert(index,obj)#将obj插入列表index位置,O(n)
list.pop([index=-1])#移除元素并返回该元素
list.sort(key=None,reverse=False)#默认升序排序,O(nlogn)
list.reverse()#反转列表元素
list.clear()
len(list)#列表元素个数,O(1)
max(list)#返回列表元素最大值,O(n)
del list[2]#删除list中第三个元素

#用小括号定义一个元组,可以当作不能修改的list
# t=(23,'wtf',3.14)

#用花括号{}定义一个字典
d={key1:value1,key2:value2}#通过key访问value
print(d[key1])#输出value1
if key in dict : #key不存在会报错,要先询问
    do somthing #或者使用
d.get(key)
for key in d: #遍历字典d
    print(key,':',d.get(key))
dMerge=dict(d1,**d2)#将d1和d2合并为dMerge

#调用set()方法创建集合
s=set([1,2,3])#定义
s.add(4)#添加
s.remove(4)#删除

math库

1
2
3
4
5
6
7
8
9
10
11
import math
math.e #常量e,2.718281828459045
math.pi #常量pi,3.141592653589793
math.factorial(x) #x的阶乘
math.gcd(x,y) #x,y的gcd
math.sqrt(x) #x的平方根
x=math.log(n,a) #以a为底n的对数x,a^x=n,默认底数为e
math.log(32,2) #5.0
math.degrees(math.pi/4) #将Π/4转为角度
math.radians(45) #将45度转为弧度
math.cos(math.pi/4) #参数都为弧度

一些封装的模板

快速幂

1
2
3
4
5
6
7
8
9
def qmod(a,b,mod):
    a=a%mod
    ans=1
    while b!=0:
        if b&1:
            ans=(ans*a)%mod
        b>>=1
        a=(a*a)%mod
    return ans

并查集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
N,m=map(int,input().split())
fa=[int(i) for i in range(N+1)]
siz=[1]*(N+1)
def findfa(x):
    if fa[x]!=x:
        fa[x]=findfa(fa[x])
    return fa[x]
def Merge(x,y):
    xx,yy=findfa(x),findfa(y)
    if xx == yy:
        return False
    if siz[xx] > siz[yy]: #按秩合并
        fa[yy]=xx
        siz[xx]+=siz[yy]
    else:
        fa[xx]=yy
        siz[yy]+=siz[xx]
    return True
for i in range(m):
    z,x,y=map(int,input().split())
    if z==1:
        Merge(x,y)
    else:
        print('Y' if findfa(x)==findfa(y)else 'N')

线段树区间加+区间和

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
class SegTreeNode(): #python3中所有类默认都是新式类
    def __init__(self): #类似构造函数,类方法必须包含参数self
        self.value=0
        self.lazytag=0

Data=[0 for i in range(0,100010)]

class SegTree():
    def __init__(self):
        self.SegTree=[SegTreeNode() for i in range(0,400010)]

    def Build_SegTree(self,Root,L,R):
        if L==R:
            self.SegTree[Root].value=Data[L]
            return
        mid=(L+R)>>1
        self.Build_SegTree(Root<<1,L,mid)
        self.Build_SegTree(Root<<1|1,mid+1,R)
        self.SegTree[Root].value=self.SegTree[Root<<1].value+self.SegTree[Root<<1|1].value
        return

    def Push_Down(self,Root,L,R):
        if self.SegTree[Root].lazytag==0:
            return
        Add=self.SegTree[Root].lazytag
        self.SegTree[Root].lazytag=0
        mid=(L+R)>>1
        self.SegTree[Root<<1].value+=(mid-L+1)*Add
        self.SegTree[Root<<1|1].value+=(R-mid)*Add
        self.SegTree[Root<<1].lazytag+=Add
        self.SegTree[Root<<1|1].lazytag+=Add
        return

    def Update(self,Root,L,R,QL,QR,Add):
        if R<QL or QR<L:
            return
        if QL<=L and R<=QR:
            self.SegTree[Root].value+=(R-L+1)*Add
            self.SegTree[Root].lazytag+=Add
            return
        mid=(L+R)>>1
        self.Push_Down(Root,L,R)
        self.Update(Root<<1,L,mid,QL,QR,Add)
        self.Update(Root<<1|1,mid+1,R,QL,QR,Add)
        self.SegTree[Root].value=self.SegTree[Root<<1].value+self.SegTree[Root<<1|1].value
        return

    def Query(self,Root,L,R,QL,QR):
        if R<QL or QR<L:
            return 0
        if QL<=L and R<=QR:
            return self.SegTree[Root].value
        mid=(L+R)>>1
        self.Push_Down(Root,L,R)
        return self.Query(Root<<1,L,mid,QL,QR)+self.Query(Root<<1|1,mid+1,R,QL,QR)

Tree=SegTree()
N,M=map(int,input().split())
a=input().split() #初始值

for i in range(1,N+1):
    Data[i]=int(a[i-1])

Tree.Build_SegTree(1,1,N)

while M:
    opt,L,R=map(int,input().split())
    if opt==1:
        Tree.Update(1,1,N,L,R,int(a[3]))
    else:
        print(str(Tree.Query(1,1,N,L,R)))
    M-=1