一般情形
一般情形下的必胜策略与两堆的情形基本一致：若物品堆的尼姆和为0，则后手方有必胜策略，否则先手方有必胜策略。必胜策略的构造基于下面的定理：
在尼姆和为0时，无论如何拿取物品，拿取之后物品堆的尼姆和一定不为0；
在尼姆和不为0时，总存在一种拿取物品的方式，使得拿取之后物品堆的尼姆和为0。
我们先说明必胜策略的构造方式
若物品堆的尼姆和为0，则无论先手方如何拿取，操作之后物品堆的尼姆和一定不为0，先手方总是不能将物品拿完。后手方总是可以选择拿取方式使得物品堆的尼姆和再次为0，同时物品的数量严格减小，这样操作下去，有限多轮之后即可使得后手方拿取物品后所有物品均被拿取，即后手方有必胜策略。
若物品堆的尼姆和不为0，则先手方总可以选择拿取方式使得拿取之后物品堆的尼姆和为0，且处于后手方的位置。由上述讨论可知，先手方有必胜策略。
''' https://www.lanqiao.cn/problems/1218/learning/ 难度: 简单 标签: nim博弈 ''' import os import sys t = int(input()) for _ in range(t): n = int(input()) ans = 0 a = list(map(int, input().split())) for i in range(n): ans ^= a[i] if ans!=0: print('NO') else: print('YES')
变体 反nim博弈
如果将规则改为拿到最后一个物品者败，可得到尼姆博弈的一种变体。此时我们有下面的结论：
若尼姆和为0且所有堆中仅有1个物品，则先手方有必胜策略；
若尼姆和不为0且至少有一堆物品数量大于1，则先手方有必胜策略；
否则后手方有必胜策略。
具体策略分析如下：
A. 假定尼姆和为0且所有堆中仅有1个物品，那么一定有偶数堆物品，否则尼姆和不为0。实际上此时双方均没有选择，只能每次拿走一堆物品，最终先手方拿走倒数第二堆物品，迫使后手方拿走最后一堆物品，输掉博弈。故先手方必胜。
经过相似的分析我们可以得出，若所有堆中仅有1个物品，且共有奇数堆物品，那么后手方必胜。
B. 假定尼姆和不为0且至少有一堆物品数量大于1，此时分为两种情况讨论：
B.1 只有一堆物品的数量大于1：
B.1.1此时若共有偶数个物品堆，则先手方只需要将物品数量大于1的这一堆全部拿走，就将情况转换为A中所有堆中仅有1个物品，且共有奇数堆物品并处于后手方；
B.1.2此时若共有奇数个物品堆，则先手方只需要使得物品数量大于1的这一堆物品拿取之后只剩1个物品，就将情况转换为A中所有堆中仅有1个物品，且共有奇数堆物品并处于后手方；
综合以上两点，此时先手方必胜。
B.2 至少有2堆物品的数量大于1：
此时先手方只需要将尼姆和变为0即可，由上面的讨论我们知道这样的拿取方式一定是存在的。并且拿完之后一定还至少有2堆物品的数量大于1，这是因为假设拿完之后只有第i堆物品数量大于1，不妨设其二进制表示的中最左侧的1在2d这一位上，那么物品堆的尼姆和中2d这一位上一定是1，因为只有的二进制表示中这一位是1，其他物品堆数量的二进制表示这一位上都是0，而
，从而尼姆和不为0，但这与尼姆和为0矛盾。故拿完之后一定还至少有2堆物品的数量大于1。由于物品数量严格减少，如此操作下去，在有限轮之后一定会遇到B.1中的情形，从而先手方必胜。
所以就是两种情况先手必胜，除此之外都是后手必胜
石子个数全部为1 & s u m = = 0
至少有一堆石子个数大于1 & s u m ≠ 0
""" https://www.lanqiao.cn/problems/1219/learning/ 难度: 简单 标签: 反nim博弈 """ t = int(input()) for _ in range(t): n = int(input()) a = list(map(int,input().split())) flag = True ans = 0 cnt = 0 for x in a: if x > 1: flag = False ans = ans^x if flag: if ans == 0: print('NO') # ans = 0,nim和为0，也就说明是偶数，这时候先手必胜 else: print('YES') else: if ans != 0: # 至少有一堆>1,并且nim不为0，先手胜 print('NO') else: print('YES')
快速幂
''' https://www.lanqiao.cn/problems/1181/learning/ 难度: 简单 标签: 快速幂 ''' import os import sys # 请在此输入您的代码 def quickpow(n,m,p): res = 1 while m: if m & 1: res = (res * n)%p n = (n*n)%p m = m>>1 return res t = int(input()) for i in range(t): n, m, p = map(int,input().split()) print(quickpow(n,m,p))
矩阵快速幂
''' https://www.lanqiao.cn/problems/1180/learning/ 难度: 简单 标签: 矩阵快速幂 ''' # 请在此输入您的代码 def multi(X,Y): n,m,k = len(X),len(X[0]),len(Y[0]) res =[[0]*k for _ in range(n)] for i in range(n): for j in range(k): ans = 0 for x in range(m): ans += X[i][x]*Y[x][j] res[i][j] = ans return res def fastpow(X,m): res = [[1, 0], [0, 1]] while m: if m&1: res = multi(res,X) X = multi(X,X) m = m>>1 return res t = int(input()) q = [[1,1],[1,0]] for _ in range(t): n = int(input()) res = fastpow(q,n-1) res = res[0][0] print(res)
最短路径问题
Floyd算法
''' https://www.lanqiao.cn/problems/1121/learning/ 难度: 简单 标签: Floyd ''' n,m,q = map(int,input().split()) MAP = [[float('inf')]*(n+1) for _ in range(n+1)] for i in range(m): u,v,w = map(int,input().split()) MAP[u][v] = w def floyd(MAP): for k in range(1,n+1): for i in range(1,n+1): for j in range(1,n+1): if MAP[i][j] > MAP[i][k] + MAP[k][j]: MAP[i][j] = MAP[i][k] + MAP[k][j] floyd(MAP) for _ in range(q): st,ed = map(int,input().split()) res = MAP[st][ed] if res != float('inf'): print(res) else: print(-1)
''' https://www.lanqiao.cn/problems/1122/learning/ 难度: 简单 标签: Dijkstra ''' # floyd算法 n,m = map(int,input().split()) p = [[float('inf')]*(n+1) for _ in range(n+1)] for _ in range(m): u,v,w = map(int,input().split()) p[u][v] = w def floyd(): for k in range(1,n+1): for i in range(1,n+1): for j in range(1,n+1): if p[i][j] > p[i][k] + p[k][j]: p[i][j] = p[i][k] + p[k][j] print('0',end = ' ') for i in range(2,n+1): if p[1][i] != float('inf'): print(p[1][i],end = ' ') else: print(-1,end = ' ')
Dijkstra算法
''' https://www.lanqiao.cn/problems/1122/learning/ 难度: 简单 标签: Dijkstra ''' import os import sys import functools n,m = map(int,input().split()) INF = float('inf') graph = [[INF] * (n) for _ in range(n)] for _ in range(m): u,v,w = map(int,input().split()) graph[u-1][v-1] = w def djs(start): visited = [0]*n dist = [INF]*n dist[start - 1] = 0 for i in range(n): # 找到未标记最近的点 x = -1 for y,u in enumerate(visited): if not u and (x == -1 or dist[x] > dist[y]): x = y visited[x] = 1 for y,w in enumerate(graph[x]): dist[y] = min(dist[y],dist[x] + w) print(" ".join(map(str,dist))) djs(1)
差分
# https://www.lanqiao.cn/problems/1276/learning/ # 难度: 简单 标签: 差分 n,q = map(int,input().split()) a = [0]+list(map(int,input().split())) b = [0]*(n+2) for i in range(1,n+1): b[i] = a[i] - a[i-1] for i in range(q): l,r,x = map(int,input().split()) b[l] += x b[r+1] -= x for i in range(1,n+1): a[i] = b[i] + a[i-1] if a[i] <= 0: print(0,end =' ') else: print(a[i],end = ' ')
计算几何基础
两线段相交
''' https://www.lanqiao.cn/problems/1287/learning/ 难度: 简单 标签: 计算几何基础 ''' import os import sys # 请在此输入您的代码 #Python3.6 class point(): #定义类 def __init__(self,x,y): self.x=x self.y=y def cross(p1,p2,p3):#跨立实验 x1=p2.x-p1.x y1=p2.y-p1.y x2=p3.x-p1.x y2=p3.y-p1.y return x1*y2-x2*y1 def IsIntersec(p1,p2,p3,p4): #判断两线段是否相交 #快速排斥，以l1、l2为对角线的矩形必相交，否则两线段不相交 if(max(p1.x,p2.x)>=min(p3.x,p4.x) #矩形1最右端大于矩形2最左端 and max(p3.x,p4.x)>=min(p1.x,p2.x) #矩形2最右端大于矩形最左端 and max(p1.y,p2.y)>=min(p3.y,p4.y) #矩形1最高端大于矩形最低端 and max(p3.y,p4.y)>=min(p1.y,p2.y)): #矩形2最高端大于矩形最低端 #若通过快速排斥则进行跨立实验 if(cross(p1,p2,p3)*cross(p1,p2,p4)<0 and cross(p3,p4,p1)*cross(p3,p4,p2)<0): D=2 elif (cross(p1,p2,p3)*cross(p1,p2,p4)==0 and cross(p3,p4,p1)*cross(p3,p4,p2)==0): D=1 else: D=0 else: D=0 return D t=int(input()) for i in range(t): p1,p2,p3,p4=point(0,0),point(0,0),point(0,0),point(0,0) x=list(map(float,input().split())) y=list(map(float,input().split())) p1.x,p1.y=x[0],x[1] p2.x,p2.y=x[2],x[3] p3.x,p3.y=y[0],y[1] p4.x,p4.y=y[2],y[3] print(IsIntersec(p1,p2,p3,p4))
并查集
一般并查集
朋友的朋友是朋友
''' https://www.lanqiao.cn/problems/1135/learning/ 难度: 简单 标签: 并查集 ''' N,M = map(int,input().split()) f = [i for i in range(N+1)] def find(x): if f[x] != x: f[x] = find(f[x]) return f[x] def union(x,y): fx = find(x) fy = find(y) if fx != fy: f[fy] = fx for i in range(M): op,x,y = map(int,input().split()) if op == 2: if find(f[x]) == find(f[y]): print('YES') else: print('NO') elif op == 1: union(x,y)
种类并查集
一般的并查集是亲戚的亲戚是亲戚
一般的并查集，维护的是具有连通性、传递性的关系，例如亲戚的亲戚是亲戚。但是，有时候，我们要维护另一种关系：敌人的敌人是朋友。种类并查集就是为了解决这个问题而诞生的。
我们开一个两倍大小的并查集。例如，假如我们要维护4个元素的并查集，我们改为开8个单位的空间：
我们用14维护**朋友**关系（就这道题而言，是指关在同一个监狱的狱友），用58维护敌人关系（这道题里是指关在不同监狱的仇人）。现在假如我们得到信息：1和2是敌人，应该怎么办？
我们merge(1, 2+n), merge(1+n, 2);。这里n就等于4，但我写成n这样更清晰。对于1个编号为i的元素，i+n是它的敌人。所以这里的意思就是：1是2的敌人，2是1的敌人。
现在假如我们又知道2和4是敌人，我们merge(2, 4+n), merge(2+n, 4);：
发现了吗，敌人的敌人就是朋友，2和4是敌人，2和1也是敌人，所以这里，1和4通过2+n这个元素间接地连接起来了。这就是种类并查集工作的原理。
''' https://www.lanqiao.cn/problems/1136/learning/ 难度: 简单 标签: 种类并查集 ''' import os import sys # 请在此输入您的代码 n,m = map(int,input().split()) # 用一半来维护朋友关系，另一半用来维护敌人关系 # 对于1个编号为i的元素，i+n是它的敌人。 f = [i for i in range(2*n+1)] # 种类并查集 def find(x): if f[x] != x: f[x] = find(f[x]) return f[x] def union(x,y): fx = find(x) fy = find(y) if fx != fy: f[fy] = fx for _ in range(m): x,y = map(int,input().split()) # 判断是否是朋友，或者相互是敌人，这样就说明有问题 if find(x) == find(y) or find(x+n) == find(y+n): print(x) break union(x,y+n) # 维护敌人关系 union(x+n,y) # 维护敌人关系
最小生成树
Kruskal算法，选择边，类似于并查集的写法
''' https://www.lanqiao.cn/problems/1124/learning/ 难度: 简单 标签: Kruskal, Prim ''' n,m = map(int,input().split()) # graph = [[0]*(n+1) for _ in range(n+1)] edge = [] for _ in range(m): u,v,w = map(int,input().split()) edge.append((u,v,w)) f = [i for i in range(n+1)] def find(x): if f[x] != x: f[x] = find(f[x]) return f[x] def union(x,y): fx,fy = find(x),find(y) if fx != fy: f[fy] = fx ans = 0 cnt = 0 edge.sort(key=lambda x:x[2]) for i in edge: u,v,w = i if find(u) != find(v) and cnt <= n - 1: ans += w union(u,v) cnt += 1 if cnt < n - 1: print(-1) else: print(ans)
树状数组
def lowbit(x): return x & -x def upate(x, d): while x <= n: tree[x] += d x += lowbit(x) def getsum(x): ans = 0 while x: ans += tree[x] x -= lowbit(x) return ans
树状数组求逆序对
import os import sys # 请在此输入您的代码 def lowbit(x): return x&-x def update(x,d): while x <= n: tree[x] += d x += lowbit(x) def getsum(x): res = 0 while x: res += tree[x] x -= lowbit(x) return res n = int(input()) tree = [0]*(n+1) a = list(map(int,input().split())) a = [0] + a ans = 0 tree = [0 for _ in range(n+1)] for i in range(1,n+1): update(a[i],1) ans += (i-getsum(a[i])) print(ans)
威尔逊定理
十八世纪中叶，一位英国法官约翰·威尔逊爵士，发现了数论中一种极为罕见的关系：取从1到某个质数所有连续正整数的乘积，例如从1乘到11，即11的阶乘11！。显然，11！能被从1到11的所有整数整除，除去11这个数，得10！。无疑10！不能被11整除。
然而，如果给10！加上1的话，1×2×3×4×5×6×7×8×9×10＋1＝3628801，怎么也不会想到，3628801却能被11整除（3628801÷11＝329891）。类似地，从1到质数7的阶乘7！中略去7，再加上1，得1×2×3×4×5×6＋1＝721，721也能被7整除（721÷7＝103）
11 和 7 都是质数，研究发现，此种整除性对一切质数都成立，但对合数却不成立。下面的表格展示了这一规律：
威尔逊定理：
当p为质数时，(p－1)!＋1能被p整除。
威尔逊定理逆定理：
若一个数(p－1)!＋1能被p整除，那么p为质数
""" https://www.lanqiao.cn/problems/1244/learning/ 难度: 简单 标签: 威尔逊定理 题目写错了，求的是(n-1)%n的结果 """ n = int(input()) flag = False for i in range(2,int(n**0.5)+1): if n%i == 0: flag = True break if not flag: print(n-1) else: if n == 4: print(2) else: print(0)
