网站建设 搜狐号,公司资质查询官方网站,如何建立网站后台,兰州网站制作要多少钱二分查找与二分答案 文章目录二分查找与二分答案应用总结例题木材加工题目背景题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1提示数据规模与约定思路代码递归与递推应用总结[NOIP2003 普及组] 栈题目背景题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1提示思…二分查找与二分答案 文章目录二分查找与二分答案应用总结例题木材加工题目背景题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1提示数据规模与约定思路代码递归与递推应用总结[NOIP2003 普及组] 栈题目背景题目描述输入格式输出格式样例 #1样例输入 #1样例输出 #1提示思路代码acwing3777. 砖块思路代码费解的开关思路代码约数之和思路代码并查集概述食物链思路代码银河英雄传说思路代码单调队列应用概述AcWing 135. 最大子序和思路代码AcWing 1089. 烽火传递思路代码应用总结
一般应用于求解最值或者具体某个数的并具有单调性的问题
例题
木材加工
题目背景
要保护环境
题目描述
木材厂有 nnn 根原木现在想把这些木头切割成 kkk 段长度均为 lll 的小段木头木头有可能有剩余。
当然我们希望得到的小段木头越长越好请求出 lll 的最大值。
木头长度的单位是 cm\text{cm}cm原木的长度都是正整数我们要求切割得到的小段木头的长度也是正整数。
例如有两根原木长度分别为 111111 和 212121要求切割成等长的 666 段很明显能切割出来的小段木头长度最长为 555。
输入格式
第一行是两个正整数 n,kn,kn,k分别表示原木的数量需要得到的小段的数量。
接下来 nnn 行每行一个正整数 LiL_iLi表示一根原木的长度。
输出格式
仅一行即 lll 的最大值。
如果连 1cm\text{1cm}1cm 长的小段都切不出来输出 0。
样例 #1
样例输入 #1
3 7
232
124
456样例输出 #1
114提示
数据规模与约定
对于 100%100\%100% 的数据有 1≤n≤1051\le n\le 10^51≤n≤1051≤k≤1081\le k\le 10^81≤k≤1081≤Li≤108(i∈[1,n])1\le L_i\le 10^8(i\in[1,n])1≤Li≤108(i∈[1,n])。
思路
对于一些求最值问题如果检验函数具有一定的单调性可以使用二分法来求解答案。 就本题具体来说检验函数用于检验分段长度n是否可以将所有原木切割成k段均为l的小木头。这是我们只需要检验n分割原木所切割的段数是否大于k即可。当n越大可以分割的段数越少所以具有一定的单调性。 二分即找到可行区间为左半段最值即右端点。
代码
def check(x) : # 用于检验划分长度为x时是否合法cnt 0for i in sticks :cnt i // xreturn cnt msticks []
n, m map(int, input().split())
for i in range(n) :sticks.append(int(input()))
# 左半段二分模板
l, r 0, sum(sticks)
while l r :mid (l r 1) 1if check(mid) : l midelse : r mid - 1
print(l)递归与递推
应用总结
递推 释义递是传递是不同问题规模之间的关系推是求解方向即由问题边界出发正向推出问题的解。每次向规模更大的方向推出时求解方法一致从而单向遍历了整个状态空间。 递推的关键是找到问题边界可能问题边界需要自己来计算比如费解的开关一题递归 释义递是向下传递的动作是将大数据规模的问题拆分成小数据规模的问题而归是对小问题规模的解进行整合从而获得大规模问题的解 递归的关键是缩小问题求解问题扩展问题
[NOIP2003 普及组] 栈
题目背景
栈是计算机中经典的数据结构简单的说栈就是限制在一端进行插入删除操作的线性表。
栈有两种最重要的操作即 pop从栈顶弹出一个元素和 push将一个元素进栈。
栈的重要性不言自明任何一门数据结构的课程都会介绍栈。宁宁同学在复习栈的基本概念时想到了一个书上没有讲过的问题而他自己无法给出答案所以需要你的帮忙。
题目描述 宁宁考虑的是这样一个问题一个操作数序列1,2,…,n1,2,\ldots ,n1,2,…,n图示为 1 到 3 的情况栈 A 的深度大于 nnn。
现在可以进行两种操作
将一个数从操作数序列的头端移到栈的头端对应数据结构栈的 push 操作将一个数从栈的头端移到输出序列的尾端对应数据结构栈的 pop 操作
使用这两种操作由一个操作数序列就可以得到一系列的输出序列下图所示为由 1 2 3 生成序列 2 3 1 的过程。 原始状态如上图所示
你的程序将对给定的 nnn计算并输出由操作数序列 1,2,…,n1,2,\ldots,n1,2,…,n 经过操作可能得到的输出序列的总数。
输入格式
输入文件只含一个整数 nnn1≤n≤181 \leq n \leq 181≤n≤18。
输出格式
输出文件只有一行即可能输出序列的总数目。
样例 #1
样例输入 #1
3样例输出 #1
5提示
【题目来源】
NOIP 2003 普及组第三题
思路
对于原问题大规模的回答较为困难但我们已知当操作数序列中元素个数为1时答案是1。我们试着能否直接推导出结果此时需要运用的是动态规划的思想。 边界是操作最终的状态 状态表示f[i, j] : 集合表示栈中包含i个元素操作序列中包含j个元素时输出序列的集合。 属性num 状态计算f[i, j] f[i - 1, j] f[i 1, j - 1] 也就是操作后状态可能是出栈的情况或者操作序列压入栈的情况 这类递推公式有加有减的情况最好的办法是记忆化搜索。 导向结果的边界不好确定或者是顺序不确定用递归否则用递推。 代码
N 20
f [[-1] * N for _ in range(N)]
# 记忆化搜索
def dfs(x, y) :if f[x][y] ! -1 : return f[x][y]f[x][y] 0if x - 1 0 :f[x][y] dfs(x - 1, y)if x 1 n and y - 1 0 :f[x][y] dfs(x 1, y - 1)return f[x][y]n int(input())
# 初始化边界
f[0][0] 0
for i in range(1, n 1) :f[i][0] 1
print(dfs(0, n))acwing3777. 砖块
n 个砖块排成一排从左到右编号依次为 1∼n 。
每个砖块要么是黑色的要么是白色的。
现在你可以进行以下操作若干次可以是 0 次
选择两个相邻的砖块反转它们的颜色。黑变白白变黑
你的目标是通过不超过 3n 次操作将所有砖块的颜色变得一致。
输入格式 第一行包含整数 T 表示共有 T 组测试数据。
每组数据第一行包含一个整数 n 。
第二行包含一个长度为 n 的字符串 s 。其中的每个字符都是 W 或 B如果第 i 个字符是 W则表示第 i 号砖块是白色的如果第 i 个字符是 B则表示第 i 个砖块是黑色的。
输出格式 每组数据如果无解则输出一行 −1 。
否则首先输出一行 k 表示需要的操作次数。
如果 k0 则还需再输出一行 k 个整数p1,p2,…,pk 。其中 pi 表示第 i 次操作选中的砖块为 pi 和 pi1 号砖块。
如果方案不唯一则输出任意合理方案即可。
数据范围 1≤T≤10 2≤n≤200 。
输入样例 4 8 BWWWWWWB 4 BWBB 5 WWWWW 3 BWB 输出样例 3 6 2 4 -1 0 2 2 1
思路
本题首先明确
每个位置只能操作0或1次操作顺序无影响默认从左到右最终状态要么全白要么全黑
那么这样只要确定了第一个位置的操作后序的操作便被确定这是一个递推的过程。
代码
T int(input())def check(s, target) :length len(s)res []for i in range(length - 1) :if s[i] target :continueelse :res.append(i)if s[i] W :s[i] Belse :s[i] Wif s[i 1] W :s[i 1] Belse :s[i 1] Wif s[-1] ! target : return Falseprint(len(res))if len(res) :for i in res :print(i 1, end )print()return True
for _ in range(T) :n int(input())s input()if not check(list(s), B) and not check(list(s), W) :print(-1)费解的开关
你玩过“拉灯”游戏吗
25 盏灯排成一个 5×5 的方形。
每一个灯都有一个开关游戏者可以改变它的状态。
每一步游戏者可以改变某一个灯的状态。
游戏者改变一个灯的状态会产生连锁反应和这个灯上下左右相邻的灯也要相应地改变其状态。
我们用数字 1 表示一盏开着的灯用数字 0 表示关着的灯。
下面这种状态
10111 01101 10111 10000 11011 在改变了最左上角的灯的状态后将变成
01111 11101 10111 10000 11011 再改变它正中间的灯后状态将变成
01111 11001 11001 10100 11011 给定一些游戏的初始状态编写程序判断游戏者是否可能在 6 步以内使所有的灯都变亮。
输入格式 第一行输入正整数 n 代表数据中共有 n 个待解决的游戏初始状态。
以下若干行数据分为 n 组每组数据有 5 行每行 5 个字符。
每组数据描述了一个游戏的初始状态。
各组数据间用一个空行分隔。
输出格式 一共输出 n 行数据每行有一个小于等于 6 的整数它表示对于输入数据中对应的游戏状态最少需要几步才能使所有灯变亮。
对于某一个游戏初始状态若 6 步以内无法使所有灯变亮则输出 −1 。
数据范围 0n≤500 输入样例 3 00111 01011 10001 11010 11100
11101 11101 11110 11111 11111
01111 11111 11111 11111 11111 输出样例
3 2 -1
思路
首先每个灯作为中心点最多只能操作一次顺序无所谓。 那么当前面一行操作后当前行所做的操作是必须将前面一行全部点亮。所以确定了一行就能确定后面所有行的状态。 我们通过枚举第一行所有可能的状态来确定最后所有可能的操作。
代码
import copy
DIRC [[-1, 0], [0, 1], [1, 0], [0, -1]]
def turn(x, y) : # 将以(x, y)为中心的五个灯按一下a[x][y] ^ 1for i in range(4) :x1, y1 x DIRC[i][0], y DIRC[i][1]if 0 x1 4 and 0 y1 4 :a[x1][y1] ^ 1
def work() :global atmp copy.deepcopy(a)res 10000010for i in range(1 5) : # 枚举第一行的操作cnt 0 # 记录操作数for j in range(5) :if i j 1 0 :cnt 1turn(0, j)for j in range(4) : # 递推后面几行for k in range(5) :if a[j][k] 0 :cnt 1turn(j 1, k)flag True # 判断操作是否成功for j in range(5) :if a[-1][j] 0 :flag Falsebreakif flag :res min(res, cnt)a copy.deepcopy(tmp)if res 6 :print(res)else :print(-1)T int(input())
a []
for t in range(T) :a []for i in range(5) :a.append(list(map(int, list(input()))))if t T - 1 :input()work()约数之和
假设现在有两个自然数 A 和 B S 是 AB 的所有约数之和。
请你求出 S mod 9901 的值是多少。
输入格式 在一行中输入用空格隔开的两个整数 A 和 B 。
输出格式 输出一个整数代表 S mod 9901 的值。
数据范围 0≤A,B≤5×107 输入样例 2 3 输出样例 15 注意: A 和 B 不会同时为 0。
思路
对于一个数可以写成质因数形式。即 则由约数个数定理可知的正约数有个 那么的个正约数的和为。 本题指数范围比较大需要我们使用到分治的思想。 对于p10p11p12...p1a1p_1^0 p_1^1p_1^2...p_1^{a_1}p10p11p12...p1a1来说 如果a1a_1a1为奇数则可表示为p10p11p12...p1a12p1a121...p1a1p_1^0 p_1^1p_1^2...p_1^{\cfrac{a_1}{2} } p_1^{\cfrac{a_1}{2} 1}...p_1^{a_1}p10p11p12...p12a1p12a11...p1a1 等价于(1p1a121)∗(p10p11p12...p1a12)(1p_1^{\cfrac{a_1}{2} 1})*(p_1^0 p_1^1p_1^2...p_1^{\cfrac{a_1}{2} })(1p12a11)∗(p10p11p12...p12a1) 如果a1a_1a1是偶数则可表示为(1p1a12)∗(p10p11p12...p1a12−1)p1a1(1 p_1^{\cfrac{a_1}{2}})*(p_1^0 p_1^1p_1^2...p_1^{\cfrac{a_1}{2} -1} ) p_1^{a_1}(1p12a1)∗(p10p11p12...p12a1−1)p1a1按照这种思路逐步递归。
代码
MOD 9901
# 快速幂
def q_mi(a, b) :if a 0 :return 0res 1while b :if b 1 :res (res * a) % MODb 1a (a * a) % MODreturn resdef figure(a, b) :if b 0 :return 1if b % 2 :return (1 q_mi(a, b // 2 1)) * figure(a, b // 2) % MODelse :return (1 q_mi(a, b // 2)) * figure(a, b // 2 - 1) q_mi(a, b) % MODn, m map(int, input().split())
ans 1
# 求质因子
i 2
while i n // i :s 0while n % i 0 :s 1n // iif s :ans (ans * figure(i, s * m)) % MODi 1
if n 1 :ans (ans * figure(n, m)) % MODif n 0 : print(0)
else :print(ans) 并查集
概述
一般的并查集主要记录节点之间的链接关系而没有其他的具体的信息仅仅代表某个节点与其父节点之间存在联系它多用来判断图的连通性。 带权并查集记录的是节点与代表元节点之间的一定权值关系节点与节点之前的权值关系通过相减可得。前缀和思想
食物链
动物王国中有三类动物 A,B,C 这三类动物的食物链构成了有趣的环形。
A 吃 B B 吃 C C 吃 A 。
现有 N 个动物以 1∼N 编号。
每个动物都是 A,B,C 中的一种但是我们并不知道它到底是哪一种。
有人用两种说法对这 N 个动物所构成的食物链关系进行描述
第一种说法是 1 X Y表示 X 和 Y 是同类。
第二种说法是 2 X Y表示 X 吃 Y 。
此人对 N 个动物用上述两种说法一句接一句地说出 K 句话这 K 句话有的是真的有的是假的。
当一句话满足下列三条之一时这句话就是假话否则就是真话。
当前的话与前面的某些真的话冲突就是假话 当前的话中 X 或 Y 比 N 大就是假话 当前的话表示 X 吃 X 就是假话。 你的任务是根据给定的 N 和 K 句话输出假话的总数。
输入格式 第一行是两个整数 N 和 K 以一个空格分隔。
以下 K 行每行是三个正整数 DXY 两数之间用一个空格隔开其中 D 表示说法的种类。
若 D1 则表示 X 和 Y 是同类。
若 D2 则表示 X 吃 Y 。
输出格式 只有一个整数表示假话的数目。
数据范围 1≤N≤50000 , 0≤K≤100000 输入样例 100 7 1 101 1 2 1 2 2 2 3 2 3 3 1 1 3 2 3 1 1 5 5 输出样例 3
思路
本题的带权并查集主要记录的是到根节点的路径上有多少个节点。
代码
N 50010
p [0] * N
d [0] * Ndef init() :for i in range(1, n 1) :p[i] idef find(x) :if p[x] ! x :t find(p[x])d[x] d[p[x]] # 更新到根节点路径上的节点数p[x] treturn p[x]n, m map(int, input().split())
init()cnt 0
for _ in range(m) :op, x, y map(int, input().split())if x n or y n : # 第一类错误cnt 1continuefx, fy find(x), find(y)if op 1:if fx fy and (d[x] - d[y]) % 3 : # 0表示同类判断过非同类cnt 1elif fx ! fy :p[fx] fyd[fx] d[y] - d[x] # 同类d[x] d[fx]与d[y]同模else :if fx fy and (d[x] - d[y] - 1) % 3 : cnt 1 # 判断过非x吃yelif fx ! fy :p[fx] fyd[fx] d[y] - d[x] 1
print(cnt)银河英雄传说
有一个划分为 N 列的星际战场各列依次编号为 1,2,…,N 。
有 N 艘战舰也依次编号为 1,2,…,N 其中第 i 号战舰处于第 i 列。
有 T 条指令每条指令格式为以下两种之一
M i j表示让第 i 号战舰所在列的全部战舰保持原有顺序接在第 j 号战舰所在列的尾部。 C i j表示询问第 i 号战舰与第 j 号战舰当前是否处于同一列中如果在同一列中它们之间间隔了多少艘战舰。 现在需要你编写一个程序处理一系列的指令。
输入格式 第一行包含整数 T 表示共有 T 条指令。
接下来 T 行每行一个指令指令有两种形式M i j 或 C i j。
其中 M 和 C 为大写字母表示指令类型i 和 j 为整数表示指令涉及的战舰编号。
输出格式 你的程序应当依次对输入的每一条指令进行分析和处理
如果是 M i j 形式则表示舰队排列发生了变化你的程序要注意到这一点但是不要输出任何信息
如果是 C i j 形式你的程序要输出一行仅包含一个整数表示在同一列上第 i 号战舰与第 j 号战舰之间布置的战舰数目如果第 i 号战舰与第 j 号战舰当前不在同一列上则输出 −1 。
数据范围 N≤30000,T≤500000 输入样例 4 M 2 3 C 1 2 M 2 4 C 4 2 输出样例 -1 1
思路
这道题的带权并查集的权值表示的是该元素合并时代表元集合内所有的元素个数也就是表示该元素在队列中所处位次。
代码
N 30010p [0] * N
d [0] * N
sz [1] * Ndef init() :for i in range(1, N) :p[i] i
def find(x) :if x ! p[x] :t find(p[x])d[x] d[p[x]]p[x] treturn p[x]T int(input())
init()
for _ in range(T) : cmd input().split()x, y int(cmd[1]), int(cmd[2])fx, fy find(x), find(y)if cmd[0] M :if fx ! fy :p[fx] fyd[fx] sz[fy] # x所处位次为y列最后sz[fy] sz[fx] # 更新y列的元素个数else :if fx ! fy :print(-1)else :print(max(abs(d[x] - d[y]) - 1, 0)) 单调队列
应用概述
维护一段窗口固定的按原数组顺序排序的单调序列用于查找一段固定长度的最大单调递增队列最小单调递减队列值常用于优化动态规划。
AcWing 135. 最大子序和
输入一个长度为 n 的整数序列从中找出一段长度不超过 m 的连续子序列使得子序列中所有数的和最大。
注意 子序列的长度至少是 1 。
输入格式 第一行输入两个整数 n,m 。
第二行输入 n 个数代表长度为 n 的整数序列。
同一行数之间用空格隔开。
输出格式 输出一个整数代表该序列的最大子序和。
数据范围 1≤n,m≤300000 输入样例 6 4 1 -3 5 1 -2 3 输出样例 7
思路
前缀和单调队列 求一段区间内的数的和当然就想到前缀和。但要求这个不超过m的段此时就想到当前位置i之前的前i个位置的一个情况。要求最大值这就要求我们维护包含i的一个大小为m的窗口但由于前缀和总是减去前面一个数所以窗口大小应该为m1。
代码
N 300010
a [0] * N
q [0] * Nn, m map(int, input().split())
a[1 : n 1] list(map(int, input().split()))# 前缀和
for i in range(1, n 1) :a[i] a[i - 1]
# 单调队列实现结合最大字段和
ans -1000010
hh, tt 0, 0 # 刚开始包含前缀0
for i in range(1, n 1) :while hh tt and i - q[hh] m : # 维护一个m 1的窗口hh 1ans max(ans, a[i] - a[q[hh]])while hh tt and a[q[tt]] a[i] :tt - 1tt 1q[tt] i
print(ans)AcWing 1089. 烽火传递
烽火台是重要的军事防御设施一般建在交通要道或险要处。
一旦有军情发生则白天用浓烟晚上有火光传递军情。
在某两个城市之间有 n 座烽火台每个烽火台发出信号都有一定的代价。
为了使情报准确传递在连续 m 个烽火台中至少要有一个发出信号。
现在输入 n,m 和每个烽火台的代价请计算在两城市之间准确传递情报所需花费的总代价最少为多少。
输入格式 第一行是两个整数 n,m 具体含义见题目描述
第二行 n 个整数表示每个烽火台的代价 ai 。
输出格式 输出仅一个整数表示最小代价。
数据范围 1≤m≤n≤2×105 , 0≤ai≤1000 输入样例 5 3 1 2 5 6 2 输出样例 4
思路
一道dp题不过需要用单调队列优化。 状态表示f[i] 集合表示前i座烽火台按要求点燃且第i座点燃的代价集合 属性min 状态计算 f[i]min(f[j])w[i],ji−m...i−1f[i] min(f[j]) w[i], j i - m ~... ~i - 1f[i]min(f[j])w[i],ji−m ... i−1
代码
N 200010
f [0] * N
a [0] * N
q [0] * Nn, m map(int, input().split())a[1 : n 1] list(map(int, input().split()))
hh, tt 0, 0
for i in range(1, n 1) :while hh tt and i - q[hh] m :hh 1f[i] f[q[hh]] a[i]while hh tt and f[q[tt]] f[i] :tt - 1tt 1q[tt] i
ans 1000010
for i in range(n - m 1, n 1) :ans min(ans, f[i])
print(ans)
