- 博客(193)
- 收藏
- 关注
RSS订阅原创 西电数据结构上机题第三次机考练习题部分题目题解
Problem318二叉树遍历题面给定一棵二叉树的先序遍历和中序遍历序列，求其后序遍历序列。解答用递归的方式进行求解。显而易见，任何一个子树的先序遍历序列的首字母一定是该子树的树根。而在中序遍历中，该树根左侧是左子树，右侧是右子树，那么我们只需要不断的递归分解左右子树，即可求出原树。需要注意的是，由于我们需要求后序遍历序列，因此对于每一棵子树，都需要在它左右子树分别递归分解完成之后再输出树根结点。codevoid getnxt (string pre, string mid, int len
2021-12-14 21:04:35
1267
原创 Python split()方法
split ()可以用split对字符串进行相应的分割，并生成一个字符串列表str.split(str="", num=string.count(str)).strstrstr代表分割的字符，numnumnum代表分割的次数。没有numnumnum默认分割所有出现strstrstr的地方，没有strstrstr默认为所有的空字符，包括空格、换行(\n)、制表符(\t)等。s = "wo#shi#da#shuai#bi"print (s.split ("#"))运行结果['wo', 'shi'
2021-05-28 09:08:18
636
原创 Python初学每日零散笔记
2021/5/27生成一个随机的整数使用random.randint(a,b)，此语句中aaa和bbb均可以生成import randoma = []for i in range (1000): a.append (random.randint (0, 100))sorted对列表进行部分排序reverse = True代表降序reverse = False代表升序（默认）sorted （a[x:y]）代表把列表aaa中左闭右开的区间[x,y)[x,y)[x,y)进行排序并返回
2021-05-27 09:32:31
207
原创 ccpc2018桂林 A. Array Merge
A. Array Merge题目大意给出长度为n的序列A和长度为m的序列B。现在要求将这两个序列在保持序列内顺序不变的情况下，合并成一个长度为n+m的大序列C。并且最小化cost，其中cost为：cost=∑i=1n+mi×C[i]cost=\sum_{i=1}^{n+m}i\times C[i]cost=i=1∑n+mi×C[i]求这个cost。声明该题解中的“子序列”，指的是“连续子序列”，可以理解为子段。类比问题如果我们有两个序列A和B，满足他们都是从大到小排好序的，现在要求合并
2020-12-18 17:55:13
861
2
原创 ccpc2018桂林 G. Greatest Common Divisor
G. Greatest Common Divisor题目大意给出n个数，每一次操作可以使所有数+1，问如果要使这些数的gcd>1，需要最少的操作次数。题解我们知道a>b的时候有gcd(a,b)=gcd(a,a−b)（公式1）\gcd(a,b)=\gcd(a, a-b)（公式1）gcd(a,b)=gcd(a,a−b)（公式1）所以c>b>a的时候有gcd(a+k,b+k,c+k)=gcd(b−a,c−b)\gcd(a+k,b+k,c+k)=\gcd(b-a,
2020-12-18 17:21:29
361
1
原创 单调栈 复习 POJ2559 Largest Rectangle in a Histogram
提交地址POJ2559洛谷提交地址code#include<bits/stdc++.h>using namespace std;int read () { int num = 0; char c = ' '; int flag = 1; for (;c > '9' || c < '0'; c = getchar ()) if (c == '-') flag = 0; for (;c >= '0' &am
2020-11-12 17:48:18
85
原创 对顶栈 复习 hdoj4699 editor
hdoj提交地址code#include<bits/stdc++.h>using namespace std;int read () { int num = 0; char c = ' '; int flag = 1; for (;c > '9' || c < '0'; c = getchar ()) if (c == '-') flag = 0; for (;c >= '0' && c &
2020-11-12 16:51:42
87
原创 NOIp2012D1T2 国王游戏 题解
国王游戏洛谷P1080国王游戏题解这道题有个重要的性质：如果交换相邻两个大臣，获得金钱变化的有且只有这两个大臣。其余大臣得到的金钱不变。我们考虑第iii个大臣和第i+1i+1i+1个大臣交换前后的变化。交换前，这两个大臣的奖励是1B[i]×∏j=0i−1A[j]与1B[i+1]×∏j=0iA[j]\frac {1}{B[i]}\times \prod_{j=0}^{i-1}A[j] 与 \frac {1}{B[i + 1]}\times \prod_{j=0}^{i}A[j]B[i]1×j=0
2020-11-12 13:01:54
710
原创 倍增 复习 P1816忠诚
提交地址洛谷P1816忠诚 提交地址RMQ问题倍增的两个状态转移方程：预处理方程a[i][j] = min (a[i][j - 1], a[i + (1 << j - 1)][j - 1]);查询方程=求[l,r]的最小值取k=log2(r−l+1)k = log_2(r - l + 1)k=log2(r−l+1)min (a[l][k], a[r - (1 << k) + 1][k]);code#include<bits/stdc++.h>u
2020-11-11 16:25:53
85
原创 归并排序复习 P1908 逆序对
提交地址洛谷提交地址错误点在xxx和yyy同时运行的whilewhilewhile循环中需要统计答案。在后面forforfor语句不需要统计答案。因为已经被统计过了。code#include<bits/stdc++.h>using namespace std;int read () { int num = 0; char c = ' '; int flag = 1; for (;c > '9' || c < '0'; c = getchar ())
2020-11-11 15:46:41
92
原创 离散化复习CF670C Cinema
提交地址洛谷提交地址分析把intintint范围内的语言，利用mapmapmap离散化映射到[1,2e5][1, 2e5][1,2e5]上即可。在线性时间内可以完成。#include <bits/stdc++.h>using namespace std;int read () { int num = 0; char c = ' '; int flag = 1; for (;c > '9' || c < '0'; c = getchar ())
2020-11-11 14:46:20
119
原创 三分法复习
题面假设有一个NNN次函数f(x)f(x)f(x)在xxx处取得极大值，现满足x∈[l,r]x∈[l,r]x∈[l,r]且是唯一地极值点。求x。输入格式第一行一次包含一个正整数 NNN和两个实数l,rl,rl,r含义如题目描述所示。第二行包含 N+1N+1N+1 个实数，从高到低依次表示该 NNN 次函数各项的系数。输出格式xxx。保留5位小数。#include<bits/stdc++.h>using namespace std;int read () { int nu
2020-11-10 22:13:55
82
原创 注意点
关于C++STLmapC++STLmapC++STLmap 如果一个元素没有在映射中出现过，那么它的初值是不确定的， 不能通过判断它的初值来判断它是否被赋值过。比如定义一个数到boolboolbool型的映射，如果没有出现过map[1]map[1]map[1]，那么我们不能通过判断map[1]==0map[1]==0map[1]==0来判断数字111是否过。...
2020-10-30 19:16:11
68
原创 Luogu P4552 IncDec Sequence 题解
题目描述给定一个长度为nnn的数列a1,a2,a3,…，ana_1, a_2, a_3,…，a_na1,a2,a3,…，an每次可以选择一个区间[L,R][L,R][L,R]，使这个区间内的所有数都+1+1+1或者−1-1−1。请问至少需要多少次操作才能使数列中所有数都一样，并求出在保证最少次数的前提下，最终得到的数列有多少种。提交地址洛谷提交地址Contest Hunter 提交地址分析这道题用差分做。对于原数列，求出它的差分数列bib_ibi。我们现在要做的事情就是：把差分数列b
2020-10-29 17:00:19
128
原创 回归刷题记录（停更）
看到之前发过的博客还是费用流和点双边双问题，感慨良多呀。10.15中午洛谷P1226 【模板】快速幂快速幂代码：int power (int a, int b, int p) { int ans = 1 % p; for (; b; b >>= 1) { if (b & 1) ans = (long long)ans * a % p; a = (long long)a * a % p; } return ans;}这里引用一下高中时代膜拜的大佬之一syq大佬的
2020-10-15 13:03:15
108
原创 分块算法坑点
分清楚iii代表的意义。solution：用k来枚举块不要iii在枚举块的时候还套p[i]p[i]p[i]， 不要iii在枚举数的时候不套p[i]p[i]p[i]。在维护累加和的时候，delta记号记得乘上数量。solution：特别检查一下吧…...
2018-09-05 21:18:51
216
原创 【haoi2009】毛毛虫
题面题目描述 对于一棵树，我们可以将某条链和与该链相连的边抽出来，看上去就象成一个毛毛虫，点数越多，毛毛虫就越大。例如下图左边的树，抽出一部分就变成了右边的一个毛毛虫了。 输入格式 第一行两个整数N，M，分别表示树中结点个数和树的边数。 接下来M行，每行两个整数a, b表示点a和点 b有边连接（a, b≤N）。你可以假定没有一对相同的(a, b)会出现一次以上。 输出格式 一个...
2018-08-31 10:39:06
311
原创 bzoj 1718: [Usaco2006 Jan] Redundant Paths 分离的路径
题面题目描述 In order to get from one of the F (1 <= F <= 5,000) grazing fields (which are numbered 1..F) to another field, Bessie and the rest of the herd are forced to cross near the Tree of Rott...
2018-08-23 08:56:22
257
原创 hdoj3394 railway
题面题目描述 有一个公园有n个景点，这n个景点由m条无向道路连接而成。 公园的管理员准备规划一一些形成回路的参观路线。如果一条道路被多条参观路线公用，那么这条路是冲突的；如果一条道路没在任何一个回路内，那么这条路是多余的道路。 问分别有多少条有冲突的路和多余的路 输入格式 包括多组数据 每组数据第一行2个整数n，m 接下来m行，每行2个整数x，y，表示从x到y有一条无向边。 输入...
2018-08-23 08:49:47
379
原创 Tarjan算法——边双和点双
边双连通分量边双连通图：如果一个无向连通图中，没有割边，那么这个无向连通图就是一个边双连通图。一个无向图的极大边双连通子图就是它的其中一个边双连通分量。 我们要解释下这里“极大”的概念：如果一个连通子图G1G1G1是边双，那么不存在一个原图的子图G2G2G2既满足G1∈G2G1∈G2G1\in G2又满足G2是边双G2是边双G2是边双。边双的“极大”不是指整个图范围内的最大，而是所有...
2018-08-23 08:37:56
6764
原创 poj 3694 network
题目大意给一张无向连通图，然后给q个操作，每个操作都会在某两个点xy之间连边，问每一个操作之后还有几座桥。题解先用tarjan求边双，缩点求新图。 先让ans=割边条数 然后对于每一个操作(x,y) 如果他们在同一个边双里，答案不变。 如果不在同一个边双，那么求出他们边双的lca=LCA(block[x],block[y])； x和y两个点分别向父亲跳，直到到lca。途径全部...
2018-08-17 20:23:40
287
原创 Tarjan算法——割点与割边
tarjan算法中的一些要素dfn[i]代表时间戳，是访问该节点的时间。low[i]代表追溯值。是该节点以及它的子树通过非搜索树边能追溯的dfn值最小的祖先的dfn值。割点割点的概念就是：在一张无向图中，去掉某一个点，这个图将会分裂成多个连通子图。我们知道一个点不是割点，当前仅当这个点在至少一个简单环上。 我们还可以知道，不在搜索树上的边一定是一个点连到它的祖先的。而不是连到...
2018-08-10 21:20:55
1439
原创 bzoj 2730 [HNOI2012]矿场搭建
题面Description 煤矿工地可以看成是由隧道连接挖煤点组成的无向图。为安全起见，希望在工地发生事故时所有挖煤点的工人都能有一条出路逃到救援出口处。于是矿主决定在某些挖煤点设立救援出口，使得无论哪一个挖煤点坍塌之后，其他挖煤点的工人都有一条道路通向救援出口。请写一个程序，用来计算至少需要设置几个救援出口，以及不同最少救援出口的设置方案总数。 Input 输入文件有若干组数据，每组数...
2018-08-02 11:27:13
178
原创 [网络流24题]负载平衡问题 （费用流）
题目描述G公司n个沿铁路运输线环形排列的仓库，每个仓库存储的货物数量不等。如何用最少搬运量可以使n 个仓库的库存数量相同。搬运货物时，只能在相邻的仓库之间搬运。 输入输出格式 输入格式： 文件的第1 行中有1 个正整数 n ，表示有 n 个仓库。第 2 行中有 n 个正整数，表示 n 个仓库的库存量。 输出格式： 输出最少搬运量。题解很明显，题目中要求运送的货物最少，我们...
2018-07-28 15:55:43
231
原创 poj3422 卡卡的矩阵旅行（费用流）
题意做过过河卒（一取方格数）、传纸条（二取方格数），我们这里来安利K取方格数。 也就是给出一个方阵，大小为n×nn×nn\times n 每一个格子都有一个权值。 我们需要从左上角到右下角取nnn条路径。每一条路径都会取掉当前方格内的数。多条路径通过同一个位置的话，这个位置的数只取一次。 要求最大化k条路径取到的数之和。题解由于每一个点的数只能被取一次，但是可以被走过多次。...
2018-07-21 18:42:42
258
原创 网络流小结
网络流建模建模的条件是根据限制性条件连边。 对于每条边的限制性条件用容量来限制； 对于每个点的限制性条件用拆点之后连自边来限制。网络流算法EK算法 Dinic算法 二分图的匈牙利算法 EK+SPFA费用流算法 ZKW费用流（等待填坑）写网络流的注意点数组大小问题邻接表从0开始，头结点数组填满-1.调不出来了就重敲。区分算法建模很重要！！！...
2018-07-21 14:38:47
152
原创 费用流模板——EK+SPFA实现的最小费用最大流
算法原理用两个字的高度概括——贪心~ 用一句话的概括：每一次通过spfa找到花费最小的可行流，然后进行增广，直到残量网络中，源点不能达到汇点。 其实还是通过代码理解比较好。code这里1是源点，n是汇点。 每次的读入四个数：有向边的两个结点+容量+费用#include<bits/stdc++.h>using namespace std;inline i...
2018-07-21 09:54:12
675
原创 bzoj1711 [Usaco2007 Open]Dingin吃饭 poj3281 Dining
题面Description 农夫JOHN为牛们做了很好的食品,但是牛吃饭很挑食. 每一头牛只喜欢吃一些食品和饮料而别的一概不吃.虽然他不一定能把所有牛喂饱,他还是想让尽可能多的牛吃到他们喜欢的食品和饮料. 农夫JOHN做了F(1<=F<=100)F(1<=F<=100)F (1 D(1<=D<=100)D(1<=D<=100)D (1 N(1&...
2018-07-14 13:59:32
215
原创 奶牛的聚会（最大流）
题面题目描述 N（3<=N<=200）头奶牛要办一个新年晚会。每头牛都会烧几道菜。一共有D(5<=D<=100)道不同的菜肴。每道菜都可以用一个1到D之间的数来表示。 晚会的主办者希望能尽量多的菜肴被带到晚会，但是每道菜的数目又给出了限制。每头奶牛可以带K(1<=K<=5)道菜，但是必须是各不相同的（例如，一头牛不能带三块馅饼，但是可以带上一块馅饼，一份面...
2018-07-14 09:38:18
1265
原创 bzoj1693 Asteroids（二分图最小顶点覆盖）
题目大意n * n矩阵有K个点，第i个点的坐标为(Xi，Yi)。每次可以把某行或者某列删掉。问至少需要多少次可以把K个点都删掉。 (n≤500n≤500n\leq 500)题解每一行每一列都建点，然后对于每一个坐标(Xi.Yi)(Xi.Yi)(X_i.Y_i)都建一条从Xi到YiXi到YiX_i到Y_i容量为1的边。 然后就是二分图的最小顶点覆盖了。 可以证明最小顶点覆盖=最小割...
2018-07-13 20:15:35
270
原创 POJ1149 养猪（最大流）
题面（来源于HLOJ）题目描述 尼克在一家养猪场工作，这家养猪场共有M间锁起来的猪舍，由于猪舍的钥匙都给了客户，所以尼克没有办法打开这些猪舍，客户们从早上开始一个接一个来购买生猪，他们到达后首先用手中的钥匙打开他所能打开的全部猪舍，然后从中选取他要买的生猪，尼克可以在此期间将打开的猪舍中的猪调整到其它开着的猪舍中，每个猪舍能存放的猪的数量是没有任何限制的。买完猪后客户会将他打开的猪舍关上。 ...
2018-07-13 16:02:36
614
原创 【网络流24题之一】飞行员配对问题+求方案（匈牙利算法求二分图最大匹配）
题面题目背景 第二次世界大战时期.. 题目描述 英国皇家空军从沦陷国征募了大量外籍飞行员。由皇家空军派出的每一架飞机都需要配备在航行技能和语言上能互相配合的2 名飞行员，其中1 名是英国飞行员，另1名是外籍飞行员。在众多的飞行员中，每一名外籍飞行员都可以与其他若干名英国飞行员很好地配合。如何选择配对飞行的飞行员才能使一次派出最多的飞机。对于给定的外籍飞行员与英国飞行员的配合情况，试设计一...
2018-07-10 21:18:34
281
原创 【网络流24题之一】飞行员配对问题+求方案（网络流dinic算法求二分图最大匹配）
题面题目背景 第二次世界大战时期.. 题目描述 英国皇家空军从沦陷国征募了大量外籍飞行员。由皇家空军派出的每一架飞机都需要配备在航行技能和语言上能互相配合的2 名飞行员，其中1 名是英国飞行员，另1名是外籍飞行员。在众多的飞行员中，每一名外籍飞行员都可以与其他若干名英国飞行员很好地配合。如何选择配对飞行的飞行员才能使一次派出最多的飞机。对于给定的外籍飞行员与英国飞行员的配合情况，试设计一...
2018-07-09 21:24:48
441
原创 二分图判定+noip2010关押罪犯
判定定理如果一个无向图中存在奇环，那么它不是二分图。判定方法所以我们采用染色法，对于一个点染色A，相邻的点染色B，再相邻的点染色A……一直下去，如果不存在奇环，那么一定不会发生冲突（比如你想对一个点染B，但是在你本次搜索之前已经搜索到它了，并且对这个点染了A）。伪代码这里给出深度优先搜索实现的染色，广度优先搜索的可以自行思考，原理一样，很简单。dfs(u,col...
2018-07-09 16:02:37
168
原创 最小割
定义网络的割：对于一个网络，存在一个边集，满足：删除这些边之后使得原网络不再连通。S-T割：首先是一个网络的割，然后满足源点和汇点在两个不同的连通块里面。最大流=最小割先证明任意割>=任意流 - 最小割中，源点s在的集合记作S，汇点t在的集合记作T，那么在原网络中存在这些边:从S出发指向T。 - 这些边一定不存在前驱后继的关系 - 那么这些边的流量之和<...
2018-07-08 18:39:01
3577
原创 最大流算法之三——Dinic算法的优化——当前弧优化
当前弧优化我们通过上一篇博客 传送门 知道，每一次bfs之后都跟着若干次dfs。每一次dfs都会发现一条可行流，而且这个可行流肯定是该路径的最大可行流。所以我们对于一条路径进行增广之后，肯定不用进行第二次增广。 所以我们这里加了一个优化，在同一个 bfs分层后跟着的dfs里面，加入要 遍历编号为1、3、5、7、9的五条边，我们默认cur[i]=1cur[i]=1cur[i]=1，然后...
2018-07-08 15:19:29
1575
原创 最大流算法之二——Dinic算法
Dinic是优化的EKDinic算法的流程是，每次寻找可行流路径的时候都先通过一次bfs给原网络分层（如果不能分层，那么已经是最大流网络了），再通过dfs给分层后的网络找可行流路径（这时候不是仅仅找一条，二十一次dfs可以找许多条可行流）。 （图片来源：https://www.cnblogs.com/LUO77/p/6115057.html）这里六张图是在若干次寻找增广路之后的中间形态。...
2018-07-08 14:59:56
398
原创 最大流算法之一——EK算法
EK算法流程EK算法的流程很简单：随意找一个可行流作为流量网络更新的基础（一般题目没有规定可以采用流量为0的可行流）利用bfsbfsbfs找一条从源点到汇点的可行流路径用新找到的可行流路径更新原有流量网络：先找到该可行流路径中流量最小边，然后将该路径上所有正向边都减去该最小边的流量，反向边都加上该最小边的流量（想想，为什么要设反向边）不断重复2和3两个步骤，直到在第2步的时候找不到...
2018-07-07 16:14:00
3269
原创 poj3263 Tallest Cow
题目大意一群奶牛排成一排。他们身高不同。 现在我们知道：有n头奶牛，第I头的身高最高，为h。 下面给出m组关系，每组关系包含两个数，表示这两个数代表的奶牛可以相互看到（两头奶牛之间的所有奶牛都比这两头奶牛矮才能相互看到） 题目要求我们给出所有n头奶牛的可能最大身高。题解我们这里采用差分。 差分数组先初始化0. 既然两头奶牛相互看到是因为他们之间的所有奶牛的身高都比他们矮，...
2018-07-07 10:42:29
305
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人