上海哪个网站最好用,宽屏企业网站源码,智慧软文发稿平台,一个平台网站开发文章目录 题目求和棋盘挖矿 前缀和有利于快速求解 区间的和、异或值 、乘积等情况差分是前缀和的反操作 前缀和 一维前缀和#xff1a;
# 原始的数组num,下标从1到n
n len(num)
pre [0]*(n1)
for i in range(n):pre[i1] pre[i] num[i]
# 如果需要求解num[l] 到num[r] 的区… 文章目录 题目求和棋盘挖矿 前缀和有利于快速求解 区间的和、异或值 、乘积等情况差分是前缀和的反操作 前缀和 一维前缀和
# 原始的数组num,下标从1到n
n len(num)
pre [0]*(n1)
for i in range(n):pre[i1] pre[i] num[i]
# 如果需要求解num[l] 到num[r] 的区间和
ans pre[r] - pre[l-1]二维前缀和
# 原本的数组是n*m形状的pre [[0]*(m1) for _ in range(n1)]for i in range(n):for j in range(m):pre[i1][j1] pre[i][j1] pre[i1][j] - pre[i][j] num[i][j]前缀和的应用 当你想在一个区间进行统一的加上一个数或者减去一个数的时候一个个操作会很慢并且涉及多次操作的时候更新很麻烦但是我们可以结合这个差分和前缀和进行快速求解 一维
# 在区间l到r之间同时都加上a,那么我们只需在num[l] a,在num[r1] -a
# 然后求解前缀和即可就可以得到每个位置的最后的值二维
# 1x1x2y1y2n
# 在x1,y1 到 x2,y2 之间都加上一个数
num[x1][y1] a
num[x21]y21] a
num[x1][y21] -a
num[x21][y1] -a 差分 一维差分
# 1lrn 那么区间l到r之间的和值为
ans pre[r] - pre[l-1]二维查分
#
ans pre[x2][y2] - pre[x2][y1] - pre[x1][y2] pre[x1][y1]题目
求和
求和 思路分析 首先直接暴力是肯定不行的所以得考虑转换发现可以提取相同的元素然后使用这个前缀和进行优化即可
import os
import sys# 请在此输入您的代码# 提取公因式你会发现 ans a1*(a2···an) a2*(a3···an) an-1*(an)n int(input())
num list(map(int,input().split()))pre [0]*(n1)
for i in range(n):pre[i1] pre[i] num[i]ans 0
for i in range(n-1):ans num[i]*(pre[n]-pre[i1])
print(ans)
棋盘
棋盘 思路分析 这个题目得使用到这个二维的前缀和与查分进行优化
import os
import sys# 请在此输入您的代码# 其实和这个异或操作是类似的
# 0表示白色1表示黑色n,m map(int,input().split())num [[0]*(n1) for _ in range(n1)]for _ in range(m):x1,y1,x2,y2 map(int,input().split())x1,y1,x2,y2 x1-1,y1-1,x2-1,y2-1num[x1][y1] 1num[x21][y21] 1num[x1][y21] -1num[x21][y1] -1# 求解二维前缀和
dp [[0]*(n1) for _ in range(n1)]for i in range(n):for j in range(n):dp[i1][j1] (dp[i1][j] dp[i][j1] - dp[i][j] num[i][j])%2for i in range(1, n 1):row .join(str(dp[i][j]) for j in range(1, n 1))print(row)
挖矿
挖矿 思路分析 首先明确一个问题在坐标轴上移动最多只能转向一次证明设你转向多次之后到达左端点是 l,到达右端点的坐标是 r,如果你直接一开始不转向直接到达左端点l,然后再直接向后转向右边,那么到达的距离是肯定比r大的
import os
import sys# 请在此输入您的代码
n,m map(int,input().split())
num list(map(int,input().split()))
# 开的空间
l ,r [0]*(m 1),[0]*(m 1)iszero 0for i in num:if i 0 and i m:r[i] 1if i 0 and abs(i) m:l[abs(i)] 1if i 0:iszero 1# 计算出其中的左和右可以到达的位置所能得到的矿
for i in range(1,m1):r[i] r[i-1]l[i] l[i-1]
ans 0# 枚举可以到达的端点注意左边和右边
for j in range(1,m//2 1):ans max(ans,r[j] l[m-2*j],l[j] r[m-2*j])print(ansiszero)
