IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓ 		图片批量下载器
↓批量下载图片,美女图库↓ 		图片自动播放器
↓图片自动播放器↓ 		一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 蓝桥杯之算法模板题 Python版 -> 正文阅读

[数据结构与算法]蓝桥杯之算法模板题 Python版

蓝桥杯之算法模板题 Python版

文章目录


记录一下算法模板题，这样方便查阅和学习，希望好好加油

线段树

import os
import sys

N,Q = map(int,input().split())
arr = [0]
arr.extend(list(map(int,input().split())))
def ls(p):return p<<1 # p//2
def rs(p):return p<<1|1 # p//2 + 1
tree = [0 for _ in range(N<<2)] # 一共有2n个节点
tag = [0 for _ in range(N<<2)] # lazy_tag标记

def pushdown(p,pl,pr):
  if tag[p]!=0:
    mid = pl + pr >> 1
    addtag(ls(p),pl,mid,tag[p])
    addtag(rs(p),mid+1,pr,tag[p])
    tag[p] = 0
    # tree[p] = tree[lr(p)] + tree[rs(p)]
    
def push_up(p):
  tree[p] = tree[ls(p)] + tree[rs(p)]
# 搭建线段树 节点的值是求和
def bulid(p,pl,pr):
  if pl == pr:
    # tree[p] = float('-inf')
    tree[p] = arr[pl]
    return 
  mid = pl + pr>>1
  bulid(ls(p),pl,mid)
  bulid(rs(p),mid+1,pr)
  # tree[p] = tree[pl] + tree[pr]
  push_up(p)

# 增加lazy_tag标记
def addtag(p,pl,pr,d):
  tag[p] += d
  tree[p] += d*(pr-pl+1)

def query(p,pl,pr,L,R): # L,R是查询区间
  # 当前节点在查询区间内
  if L <= pl and pr <= R: return tree[p]
  pushdown(p,pl,pr) # 标记向下传递
  res = 0
  mid = pl + pr >>1
  if L <= mid:
    res+=query(ls(p),pl,mid,L,R) 
  if R > mid:
    res+=query(rs(p),mid+1,pr,L,R)
  return res

# 更新线段树，也就是加上k L,R是更新区间
def update(p,pl,pr,L,R,d):
  if L<=pl and pr<=R:
    addtag(p,pl,pr,d)
    return
  pushdown(p,pl,pr) # 标记向下传递
  mid = pl + pr >> 1
  if L <= mid: update(ls(p),pl,mid,L,R,d)
  if R > mid: update(rs(p),mid+1,pr,L,R,d)
  push_up(p)

bulid(1,1,N)
for _ in range(Q):
  q = list(map(int,input().split()))
  if q[0] == 1:
    update(1,1,N,q[1],q[2],q[3])
  elif q[0] == 2:
    print(query(1,1,N,q[1],q[2]))


import os
import sys
def ls(p):return p<<1
def rs(p):return p<<1|1
def push_up(p):tree[p]=tree[rs(p)]+tree[ls(p)]
def build(p,pl,pr):
  if pl==pr:
    tree[p]=1
    return
  mid=(pl+pr)>>1
  build(ls(p),pl,mid)
  build(rs(p),mid+1,pr)
  push_up(p)
def addtag(p,pl,pr,d):
  tag[p]=d
  tree[p]=d*(pr-pl+1)
def push_down(p,pl,pr):
  if ~tag[p]!=0:
    mid=(pl+pr)>>1
    addtag(ls(p),pl,mid,tag[p])
    addtag(rs(p),mid+1,pr,tag[p])
    tag[p]=-1
# 把1变成0
def update0(p,pl,pr,cnt):
  if cnt==0:return
  if tree[p]==cnt:
    addtag(p,pl,pr,0)
    return
  mid=(pl+pr)>>1
  push_down(p,pl,pr)
  if tree[ls(p)]>cnt:update0(ls(p),pl,mid,cnt)
  else:
    cnt-=tree[ls(p)]
    addtag(ls(p),pl,mid,0)
    update0(rs(p),mid+1,pr,cnt)
  push_up(p)
# 把0变成1
def update1(p,pl,pr,cnt):
  if cnt==0:return
  if pr-pl+1-tree[p]==cnt:
    addtag(p,pl,pr,1)
    return
  mid=(pl+pr)>>1
  push_down(p,pl,pr)
  if mid-pl+1-tree[ls(p)]>cnt:update1(ls(p),pl,mid,cnt)
  else:
    cnt-=(mid-pl+1-tree[ls(p)])
    addtag(ls(p),pl,mid,1)
    update1(rs(p),mid+1,pr,cnt)
  push_up(p)
def query(p,pl,pr,L,R):
  if L<=pl and pr<=R:return tree[p]
  push_down(p,pl,pr)
  mid=(pl+pr)>>1
  res=0
  if L<=mid:res+=query(ls(p),pl,mid,L,R)
  if R>mid:res+=query(rs(p),mid+1,pr,L,R)
  return res
n,m=map(int,input().split())
tree=[0 for _ in range(n<<2)]
tag=[-1 for _ in range(n<<2)]
build(1,1,n)
for _ in range(m):
  op,num=map(int,input().split())
  if op==0:
    pos=n-tree[1]
    cnt=max(0,num-pos)
    update0(1,1,n,cnt)
  elif op==1:
    pos=tree[1]
    cnt=max(0,n-num+1-pos)
    update1(1,1,n,cnt)
ans1,ans2=[],[]
for i in range(1,n+1):
  if query(1,1,n,i,i)==0:ans1.append(i)
  else:ans2.append(i)
for x in ans1[::-1]+ans2:
  print(x,end=' ')

DP 动态规划

dp, LIS **

'''
https://www.lanqiao.cn/problems/1188/learning/
难度: 中等   标签: dp, LIS
'''

import os
import sys
import bisect
# 请在此输入您的代码

n = int(input())
a = list(map(int,input().split()))

dp = [float('inf')]*(n+1)
dp[0] = a[0]
for i in range(1,n):
    t = bisect.bisect_left(dp,a[i])
    dp[t] = a[i]

print(bisect.bisect_left(dp,float('inf')))

01背包

动态转移方程
f [ i ] [ j ] = m a x ( f [ i ? 1 ] [ j ] , f [ i ? 1 ] [ j ? v ] + w ) ( j > v ) f[i][j] = max(f[i-1][j], f[i-1][j-v] + w)(j>v) f[i][j]=max(f[i?1][j],f[i?1][j?v]+w)(j>v)

# https://www.lanqiao.cn/problems/1174/learning/
# 难度: 简单   标签: dp, 背包, 01背包
import os
import sys


# 请在此输入您的代码
N,V = map(int,input().split())
# f[N][V]
# f[i][j] 代表 i 件物品 ， 容量为 j 的时候，得到最大的价值
f = [[0]*(V+1) for _ in range(N+1)]

for i in range(1,N+1):
    # v为体积， w为价值
    v, w = map(int, input().split())
    for j in range(1,V+1):
        # 第i件物品有两种选择，
        # 第1种是选第i件物品，f[i-1][j]
        # 第2种是不选第i件物品，f[i-1][j]
        if j < v: 
            f[i][j] = f[i-1][j]
        else:
            f[i][j] = max(f[i-1][j], f[i-1][j-v] + w)

print(f[N][V])

完全背包

一般就是
f [ i ] [ j ] = m a x ( f [ i ? 1 ] [ j ? k ? v ] + w ? k ) ( 0 < = k < j / / v ) f[i][j] = max(f[i-1][j-k*v] + w*k)(0<=k<j//v) f[i][j]=max(f[i?1][j?k?v]+w?k)(0<=k<j//v)
不过可以转化为动态转移方程
f [ i ] [ j ] = m a x ( f [ i ? 1 ] [ j ] , f [ i ] [ j ? v ] + w ) f[i][j] = max(f[i-1][j],f[i][j-v] + w) f[i][j]=max(f[i?1][j],f[i][j?v]+w)

'''
https://www.lanqiao.cn/problems/1175/learning/
难度: 简单   标签: DP, 背包, 完全背包
'''

import os
import sys

# 请在此输入您的代码
N,V = map(int,input().split())

# f[i][j]表示前i种，总体积不超过j，最大的总价值
f = [[0]*(V+1) for _ in range(N+1)]


# 完全背包问题，可以买多个
for i in range(1,N+1):
    v,w = map(int,input().split())
    for j in range(1,V+1): # 这里是体积的范围
        # t = j//v
        # f[i][j] = f[i-1][j]
        # for x in range(1,t+1): # x是第i件物品的数量
        #     f[i][j] = max(f[i][j],f[i-1][j-x*v]+w*x)
        # 优化后写法，已经把所有的也考虑进去了
        if j < v:
            f[i][j] = f[i-1][j] # 相当于不买第 i 件物品
        else:
            f[i][j] = max(f[i-1][j],f[i][j-v] + w) # 这里是比较买i件物品和不买i件物品
print(f[N][V])


# 压缩成一维
# dp = [0]*(V+1)
# v,w = [],[]
# for i in range(N):
#     v,w = map(int,input().split())
#     for j in range(1,V+1):
#         if j >= v:
#             dp[j] = max(dp[j-v] + w, dp[j])
# print(dp[V])

多重背包

对于多重背包来说，实际上与一般是一样的情形的构造，就是数量受限制了而已

不过多重背包也有一种二进制的压缩写法，复杂度就会更低一点

'''
https://www.lanqiao.cn/problems/1176/learning/
难度: 简单   标签: dp, 背包, 多重背包
'''
import os
import sys

# 请在此输入您的代码

N,V = map(int,input().split())

# 多重背包和完全背包是一样的构造方式
f = [[0]*(V+1) for _ in range(N+1)] 

for i in range(1,N+1):
    v,w,s = map(int,input().split())
    for j in range(1,V+1):
        # 多重背包的区别就是，不可以直接简化，因为数量已经有了限制，所以说独立一个循环进行判断和更新
        for k in range(s+1):
            if k*v <= j:
                # 这一部分判断，是否买k个
                f[i][j] = max(f[i][j],f[i-1][j-k*v] + k*w)
            else:
                break
print(f[N][V])

二进制写法

多重背包二进制还可以进行优化，要不然上一部分的复杂度有 On的三次方

会把多重背包转化为01背包，对于01背包就稍微简单一点

比如200个数量的物体，可以转为为1,2,4,8,…,64,74这么多组

因为1127的数可以由164构成，然后200-127 = 73

（1~127 都可以表示出来，选出任意一种与 73 组合就可以表示出 74 ~ 200 ，所以合起来就可以表示 1~200）。

相当于每个数量的为一组

# 多重背包二进制还可以进行优化，要不然上一部分的复杂度有 On的三次方
# 会把多重背包转化为01背包，对于01背包就稍微简单一点
# 比如200个数量的物体，可以转为为1,2,4,8,....,64,74这么多组
# 因为1~127的数可以由1~64构成，然后200-127 = 73 
# （1~127 都可以表示出来，选出任意一种与 73 组合就可以表示出 74 ~ 200 ，所以合起来就可以表示 1~200）。
# 相当于每个数量的为一组

N,V = map(int,input().split())
v = [0]*12010
w = [0]*12010

cnt = 0
for i in range(N):
    a,b,s = map(int,input().split())
    k = 1
    # 按照二进制的形式分组
    while k <= s:
        cnt += 1
        v[cnt] = k*a
        w[cnt] = k*b
        s = s - k
        k = k*2
    # 不能按照二进制分组的物体数量单独划分为一组。
    if k > 0:
        cnt += 1
        v[cnt] = a*s
        w[cnt] = b*s
f = [0]*(cnt+1)
# 分组后就等同于0 1 背包
for i in range(1,cnt + 1):
    for j in range(V,0,-1):
        if j >= v[i]:
            f[j] = max(f[j],f[j-v[i]] + w[i])
        else:
            break

print(f[V])

混合背包

其中又有混合背包问题，混合背包问题就是，我们的数量变成无限了，对于无限来说，我们就不可以直接利用二进制进行计算。

不过我思考了一下，除非说以我们的体积作为我们的上界，还是可以进行的

首先就是先根据一个无限的情况进行一个判断，这里是改完全背包的，因为这些都是变体

'''
https://www.lanqiao.cn/problems/1177/learning/
难度: 简单   标签: dp, 背包, 混合背包
'''

N,V = map(int,input().split())

# f[i][j]表示前i种，总体积不超过j，最大的总价值
f = [[0]*(V+1) for _ in range(N+1)]


for i in range(1,N+1):
    v,w,s = map(int,input().split())
    for j in range(1,V+1):
        # 多重背包的区别就是，不可以直接简化，因为数量已经有了限制，所以说独立一个循环进行判断和更新
        if s != 0:
            for k in range(s+1):
                if k*v <= j:
                    # 这一部分判断，是否买k个
                    f[i][j] = max(f[i][j],f[i-1][j-k*v] + k*w)
                else:
                    break
        else:
            k = 0
            while k*v <= j:
                f[i][j] = max(f[i][j],f[i-1][j-k*v] + k*w)
                k += 1
print(f[N][V])

如果s=0表示该商品有无限个，但实际背包不可能放入无限多个，在此假设最大个数为能够全部放入背包的数量

所以这个也可以通过调整一个上界进行，因为我们的体积是有限的，所以也可以调整多重背包的二进制进行修改

'''
https://www.lanqiao.cn/problems/1177/learning/
难度: 简单   标签: dp, 背包, 混合背包
'''

N,V = map(int,input().split())
v = [0]*12010
w = [0]*12010

cnt = 0
for i in range(N):
    a,b,s = map(int,input().split())
    if s == 0:
        s = V//a # 设置上界即可
    k = 1
    # 按照二进制的形式分组
    while k <= s:
        cnt += 1
        v[cnt] = k*a
        w[cnt] = k*b
        s = s - k
        k = k*2
    # 不能按照二进制分组的物体数量单独划分为一组。
    if k > 0:
        cnt += 1
        v[cnt] = a*s
        w[cnt] = b*s
f = [0]*(cnt+1)
# 分组后就等同于0 1 背包
for i in range(1,cnt + 1):
    for j in range(V,0,-1):
        if j >= v[i]:
            f[j] = max(f[j],f[j-v[i]] + w[i])
        else:
            break

print(f[V])

分组背包

其实就类似于01背包，对于一个物品有两种决策选或不选，但是分组背包是在01背包的基础上对物品进行了分组，并且每一组只能最多选择一个物品，所以我们不妨用01背包的思想去思考分组背包.

分析：我们设f[i][j]为当前考虑到了第i组物品，剩余容里为j的背包能装物品的最大价值，那么很容易想到我们需要去枚举第i组物品，考虑选哪一个物品时最优的(或者不选)，状态转移方程就是
i f ( j > = v [ i ] [ k ] ) f [ i ] [ j ] = m a x ( f [ i ] [ j ] , f [ i ? 1 ] [ j ? v [ i ] [ k ] ] + w [ i ] [ k ] ) i f ( j > = v [ i ] [ k ] ) f [ i ] [ j ] = m a x ( f [ i ] [ j ] , f [ i ? 1 ] [ j ? v [ i ] [ k ] ] + w [ i ] [ k ] ) if(j>=v[i][k])f[i][j]=max(f[i][j],f[i?1][j?v[i][k]]+w[i][k])
v[i][k]和w[i][k]分别表示第i组物品中第k个物品的体积和价值

for(int i=1;i<=n;i++)
	 for(int j=0;j<=m;j++)
	  for(int k=1;k<=s[i];k++)//s[i]表示第i组物品的个数
	   if(j>=v[i][k])//剩余的背包容量j大于第i组的第k个物品的体积 
	   {
	   	  f[i][j] = max(f[i][j],f[i-1][j-v[i][k]]+w[i][k]);
	   }


'''
https://www.lanqiao.cn/problems/1178/learning/
难度: 简单   标签: dp, 背包, 分组背包
'''

N,V = map(int,input().split())

f = [0]*(V+1)
v = [[0]]
w = [[0]]
s = [0]
for i in range(1,N+1):
    s.append(int(input()))
    # 一组物品只能买一件
    vi = [0]
    wi = [0]
    for _ in range(s[i]):
        a,b = map(int,input().split())
        vi.append(a)
        wi.append(b)
    v.append(vi)
    w.append(wi)

# f[i][j] 代表在选择i组中， 体积不超过j的最大价值
f = [[0]*(V+1) for _ in range(N+1)]
for i in range(1,N+1): # 1~N 组数
    for j in range(V,-1,-1): # V~0 体积数
        for k in range(1,s[i]+1): # 1~i 分组的物品数
            if j >= v[i][k]:
                f[i][j] = max(f[i][j],f[i-1][j - v[i][k]] + w[i][k])

print(f[N][V])

还可以进行压缩成一维的，减少空间

for 所有的组k
	for v=V..0
		for 所有的i属于组k
			f[v]=max{f[v],f[v-c[i]]+w[i]}

# 压缩成一维
N,V = map(int,input().split())

f = [0]*(V+1)
v = [[0]]
w = [[0]]
s = [0]
for i in range(1,N+1):
    s.append(int(input()))
    # 一组物品只能买一件
    vi = [0]
    wi = [0]
    for _ in range(s[i]):
        a,b = map(int,input().split())
        vi.append(a)
        wi.append(b)
    v.append(vi)
    w.append(wi)
    
# f[i][j] 代表在选择i组中， 体积不超过j的最大价值
f = [0]*(V+1)
for i in range(1,N+1): # 1~N 组数
    for j in range(V,-1,-1): # V~0 体积数
        for k in range(1,s[i]+1): # 1~i 分组的物品数
            if j >= v[i][k]:
                f[j] = max(f[j],f[j - v[i][k]] + w[i][k])

print(f[V])

区间DP

一.什么是区间dp?

? 顾名思义：区间dp就是在区间上进行动态规划，求解一段区间上的最优解。主要是通过合并小区间的 最优解进而得出整个大区间上最优解的dp算法。

二.核心思路

? 既然让我求解在一个区间上的最优解，那么我把这个区间分割成一个个小区间，求解每个小区间的最优解，再合并小区间得到大区间即可。所以在代码实现上，我可以枚举区间长度len为每次分割成的小区间长度（由短到长不断合并），内层枚举该长度下可以的起点，自然终点也就明了了。然后在这个起点终点之间枚举分割点，求解这段小区间在某个分割点下的最优解。板子如下：

for(int len = 1;len<=n;len++){//枚举长度
        for(int j = 1;j+len<=n+1;j++){//枚举起点，ends<=n
            int ends = j+len - 1;
            for(int i = j;i<ends;i++){//枚举分割点，更新小区间最优解
                dp[j][ends] = min(dp[j][ends],dp[j][i]+dp[i+1][ends]+something);
            }
        }
    }

三.朴素区间dp（n^3)

转移方程

dp[j][ends] = min(dp[j][ends],dp[j][i]+dp[i+1][ends]+weigth[i][ends]);

j~ends堆合并 = 较小的（原来， 分割点i坐部分重量 + 分割点i右边部分重量 + 合并后两堆总重量）

注：可以用sum[j] - sum[i - 1]表示i~j堆的重量！

博弈论

nim博弈

这实际上是一个尼姆博弈的问题，尼姆博弈就是一个两人博弈，2名玩家轮流从数堆物品中拿取一定数量的物品，每次拿取时先选择某一堆，再从中拿取任意数量个物品，至少拿1个，至多将这一堆物品全部拿走，不能不拿。拿到最后一个物品的玩家获胜。

尼姆博弈是一个两人博弈，2名玩家轮流从数堆物品中拿取一定数量的物品，每次拿取时先选择某一堆，再从中拿取任意数量个物品，至少拿1个，至多将这一堆物品全部拿走，不能不拿。拿到最后一个物品的玩家获胜。

两堆的情形

我们从最简单的两堆物品的情形开始分析，并使用二元组（n，m）来表示这两堆物品当前的数量。当（n，m）情形下先手方\后手方有必胜策略时，我们称（n，m）为制胜位置。

我们将说明：当n=m时，后手有必胜策略，否则先手有必胜策略。

  • 当n=m=1时，先手方仅能够将其中一堆完全取走，故后手方只需要将另一堆的1个物品取走即可获胜。即（1，1）是后手方的制胜位置。
  • 当n=m=k>1时，无论先手方选择哪一堆，取走多少数量的物品，后手方只需要选择另一堆，并取走相同数量的物品，就可以将物品堆的状态从（k，k）转换到（j，j），其中j<k。如此操作下去，由于两堆物品的数量保持相等且严格递减，故后手方玩家总能将物品堆的数量转换为（1，1）或（0，0）。由上面的讨论与游戏规则知，后手方必胜。即（n，m），n=m是后手方的制胜位置。
  • 当时，先手方只需要从较多的一堆物品中拿取适量的物品，使得两物品堆物品数量一致，就将情形转换为了上述两种情况之一，且自身处于后手方。由上面的讨论知，先手方必胜。即（n，m），是先手方的制胜位置。

定义：物品堆的尼姆和是一个二进制数，它是由所有物品堆中物品的数量转换为二进制后，进行异或运算得到的。设有k个物品堆，分别有
在这里插入图片描述

一般情形

一般情形下的必胜策略与两堆的情形基本一致：若物品堆的尼姆和为0，则后手方有必胜策略，否则先手方有必胜策略。必胜策略的构造基于下面的定理：

  1. 在尼姆和为0时，无论如何拿取物品，拿取之后物品堆的尼姆和一定不为0；
  2. 在尼姆和不为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博弈

如果将规则改为拿到最后一个物品者败，可得到尼姆博弈的一种变体。此时我们有下面的结论：

  1. 若尼姆和为0且所有堆中仅有1个物品，则先手方有必胜策略；
  2. 若尼姆和不为0且至少有一堆物品数量大于1，则先手方有必胜策略；
  3. 否则后手方有必胜策略。

具体策略分析如下：

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. 石子个数全部为 1 1 1 && s u m = = 0 sum == 0 sum==0

  2. 至少有一堆石子个数大于 1 1 1 && s u m ≠ 0 sum \neq 0 sum?=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个单位的空间：

img

我们用14维护**朋友**关系（就这道题而言，是指关在同一个监狱的狱友），用58维护敌人关系（这道题里是指关在不同监狱的仇人）。现在假如我们得到信息：1和2是敌人，应该怎么办？

我们merge(1, 2+n), merge(1+n, 2);。这里n就等于4，但我写成n这样更清晰。对于1个编号为i的元素，i+n是它的敌人。所以这里的意思就是：1是2的敌人，2是1的敌人。

img

现在假如我们又知道2和4是敌人，我们merge(2, 4+n), merge(2+n, 4);：

img

发现了吗，敌人的敌人就是朋友，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 都是质数，研究发现，此种整除性对一切质数都成立，但对合数却不成立。下面的表格展示了这一规律：

n

(n-1)!

(n-1)!+1

[(n-1)!+1] mod n

数性

2

1

2

0

质数

3

2

3

0

质数

4

6

7

3

合数

5

24

25

0

质数

6

120

121

1

合数

7

720

721

0

质数

8

5040

5041

1

合数

9

40320

40321

1

合数

10

362880

362881

1

合数

11

3628800

3628801

0

质数

12

39916800

39916801

1

合数

13

479001600

479001601

0

质数

14

6227020800

6227020801

1

合数

15

87178291200

87178291201

1

合数

威尔逊定理：

当 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)
  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用：海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题＜有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2022-04-09 18:42:57  更:2022-04-09 18:43:35 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年11日历 -2024/11/26 9:35:39-

图片自动播放器
↓图片自动播放器↓ 		TxT小说阅读器
↓语音阅读,小说下载,古典文学↓ 		一键清除垃圾
↓轻轻一点,清除系统垃圾↓ 		图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码