生之、如舟 - 个人主页动态

2020-02-18 14:17

Is It A Tree? 题目 A tree is a well-known data structure that is either empty (null, void, nothing) or is a set of one or more nodes connected by directed edges between nodes satisfying the following properties. There is exactly one node, called the root, to which no directed edges point.Every node ex...

0 点赞评论收藏

2020-02-18 13:30

已编辑

河南理工大学 golang

HDU1272-小希的迷宫【并查集】

小希的迷宫 题目描述 上次Gardon的迷宫城堡小希玩了很久，现在她也想设计一个迷宫让Gardon来走。但是她设计迷宫的思路不一样，首先她认为所有的通道都应该是双向连通的，就是说如果有一个通道连通了房间A和B，那么既可以通过它从房间A走到房间B，也可以通过它从房间B走到房间A，为了提高难度，小希希望任意两个房间有且仅有一条路径可以相通（除非走了回头路）。小希现在把她的设计图给你，让你帮忙判断她的设计图是否符合她的设计思路。比如下面的例子，前两个是符合条件的，但是最后一个却有两种方法从5到达8。 分析 目的很简单，其实就是用并查集判断给定的图是否是无向边的一棵树，所以只需要判断是否用重边和环...

0 点赞评论收藏

2020-02-17 20:51

河南理工大学 golang

HDU3038 How Many Answers Are Wrong 【带权并查集】

How Many Answers Are Wrong 题意 给出一个区间的长度 N，及 M 个子区间和， 形如：x y z, 表示子区间 [x, y] 的和为 z如果一个“子区间和”与前面的“子区间和”冲突，即为错误（而且这个“子区间和”将在接下来的判断中被忽略）。求总错误个数。ps：这个题是多组数据 分析算法 这题考察点是带权并查集，对于每两个结点，既保存了他们的集合的关系，也会保存他们之间的权值。当我们join(a,b)时，他首先将a，b并入了同一个集合中，然后又保存了a，b分别到最顶端的距离，当我们要去查a，b的距离是多少的时候，就可以计算出来a到b的距离 = a到顶端的距离-b到顶端的...

0 点赞评论收藏

2020-02-16 18:28

河南理工大学 golang

HDU1213-How Many Tables 【并查集】

How Many Tables 题意 有N个朋友一起来吃饭，认识的人只跟认识的做一桌，认识的人是可以传递的，A认识B，B认识C，那么A就认识C，问最少需要多少张桌子？ 分析 使用并查集模板套一下，最后fa[i] == i的就是一桌，计数器+1即可 AC代码 #include <iostream> #include <stdio.h> using namespace std; typedef long long ll; const int maxn = 1e3+10; int T,N,M; int fa[maxn]; void init(){ for(int i...

0 点赞评论收藏

2020-02-16 18:07

河南理工大学 golang

POJ1611-The Suspects 【并查集】

The Suspects 题意 在一个学校，一共有N个学生，他们组建了M个小组，现在有一个人中了病毒，具有传染性，与感染者同组人员都会被传染，问最终会传染多少人？ 分析 使用并查集，把有联系的人都合并起来，最后压缩一边路径，看其id号为0的点有多少个就可以了 AC 代码 #include <iostream> #include <stdio.h> using namespace std; typedef long long ll; const int maxn = 3e4+10; int N,M; int fa[maxn]; int arr[maxn]; void i...

0 点赞评论收藏

2020-02-16 17:30

河南理工大学 golang

poj2236 Wireless Network 【并查集】

Wireless Network 题意 在一个网络中的共N台电脑都已经坏了，知道这些电脑的直角坐标，现在维修员对网络中的电脑一个一个维修，一边维修一边问某两台电脑是否可以通信了，通信双方电脑必须是已经修好了的，并且通信路线上每两台电脑的直接距离不能超过D。你需要回答维修员的问题。 分析 此题算是很典型的并查集算法，每次维修好一台电脑就把此台电脑和与其距离小于等于D的电脑合并在一起，也就是用并查集的join操作，然后师傅问两台电脑是否修好，就用find操作，就可以了。 AC 代码 #include <iostream> #include <algorithm> #incl...

0 点赞评论收藏

2020-02-16 15:13

已编辑

河南理工大学 golang

HDU4489 The King’s Ups and Downs 【组合DP】

The King’s Ups and Downs 题意：给你N个人的身高，他们身高各不相同，问排列是高低高低高低、或低高低高低高的方案数是多少？ 分析 此问题的阶段性很容易看出来，就是先求出N = 1的排列数，再求出N=2的排列书，然后再求N=3，再求N = i的排列数时，可能要用到N = 1，N = 2,N = 3...N = i-1的排列数。那如何去找前后阶段的关联性，试想一下，假如上一下阶段N = i-1的排列方案已经求了出来，现在要将第i个人插入到此排列中，假如插入到第j个位置，那么需要知道j位置之前j-1个人以高低结尾的方案数，还需要知道j位置之后i-1-j个人以低高开始的方案数，...

0 点赞评论收藏

2020-02-15 21:22

河南理工大学 golang

HDU2182 Frog 【基础dp】

HDU2182 Frog 首先，原谅我写这么简单的dp题解，其是是因为我dp基础非常差 题意 给定4个数N,A,B,K,在[0,N)上每个坐标上都有一些昆虫，现在一只在坐标0的青蛙可以原地不动或通过向右跳A至B步，总共可以跳K次，问最多能够吃到多少只昆虫？ 分析 首先考虑阶段性，跳i步的方案，不会影响跳i+1步的方案，所以阶段性就是先计算跳前i步，然后再计算跳前i+1步。状态表示dp[i][j]:跳跃前i步之后，落在位置j的方案数状态转移：dp[i][j] = max(dp[i][j],dp[i-1][j-k]) k是跳跃的步长然后看到状态转移dp[i][j]只会与上一轮有联系，所以可以使用动...

0 点赞评论收藏

2020-02-29 18:18

已编辑

河南理工大学 golang

Kuangbin专题

Kuangbin专题 并查集 poj2236 Wireless Network 并查集模板poj1611 The Suspects 并查集模板HDU1213-How Many Tables 并查集模板HDU3038 How Many Answers Are Wrong 带权并查集模板POJ2492-A Bug's Life 带权并查集(稍加思考)POJ1733-Parity game 带权并查集HDU1272-小希的迷宫 判断无向树POJ1308-Is It A Tree? 判断无向树POJ1456-Supermarket 贪心+并查集ZOJ3261-Connections in Galaxy...

0 点赞评论收藏

2020-02-15 20:13

已编辑

河南理工大学 golang

HDU2050 折线分割平面【递推】

HDU2050 折线分割平面 我们看到过很多直线分割平面的题目，今天的这个题目稍微有些变化，我们要求的是n条折线分割平面的最大数目。比如，一条折线可以将平面分成两部分，两条折线最多可以将平面分成7部分，具体如下所示。输入数据的第一行是一个整数C,表示测试实例的个数，然后是C 行数据，每行包含一个整数n(0<n<=10000),表示折线的数量。 Output对于每个测试实例，请输出平面的最大分割数，每个实例的输出占一行。 Sample Input212Sample Output27 分析 其实这是一个比较典型的图像方面的递推，其关键点就是观察，一条线最多可以通过多少条线，然后通过之后...

0 点赞评论收藏

2020-02-15 19:31

已编辑

河南理工大学 golang

HDU1024 Max Sum Plus Plus 【区间dp】【滚动数组】

HDU1024 Max Sum Plus Plus 题意：给你一个N个元素的数列，你需要从中选M个区间，区间之间不能有交叉，问选取的M个区间之和最大值是多少？ (N是1e6的数量级) 分析 我们考虑一个数一个数的放，过程是怎么样的。如果当前是选取第i个区间，现在要尝试放入a[j]，那么就会出现两种情况：1.a[j]直接跟在第i个区间的后面，最开始相当于跟在空区间的后面，后来就是a[j+1]跟在a[j]的后面组成区间2.找到j之前选择i-1个区间的最优值+新开一个区间[j,j]. 假如现在是第i轮区间选择: dp[j]: 当前轮第j个位置的两种选择情况的最大值mx:实时保存本轮在第j个位置选择后...

0 点赞评论收藏

2020-02-14 23:23

河南理工大学 golang

Hdu 1401 Solitaire 【双向BFS + Hash】

Hdu1401 Solitaire 题意 有一个8x8的棋盘，上面有4个棋子，棋子可以这样移动：1.移动到相邻空位置 2.跳过一个棋子到其前面，具体看图。然后给你两个棋盘到布局，问布局1是否可以在8步之内移动成布局2的样子？ 分析 可以想到这是一个最短路问题，每一个棋盘布局就是一种状态，从初始状态移动到目标状态就是一个求最短路的过程。这题由于给了初始状态和目标状态，所以很容易就想到是双向BFS算法写的话时间复杂度更低，保存的中间状态就更少，所以内存也会更少。 如何存储状态 显然我们可以使用string来存储棋盘，空的位置是0，有棋子的位置是1，然后串起来就可以hash了，但是此处可以看到是...

0 点赞评论收藏

2020-02-14 18:56

已编辑

河南理工大学 golang

hdu6171 Admiral 【双向BFS+Hash】

hdu6171 Admiral 题意：给你一个如图形状21个元素的排列，只能够通过0元素跟其上下相邻的元素进行交换，问是否可以在20步内转换成目标排列，如果可以输出最小步数，否则输出too difficult 这是目标排列，给定的初始排列可能不同 分析 首先可以看出这是一个求最短路的题，我们可以把元素的排列看成是一种状态，他可以经过若干次状态转移到达目标状态，这就是一个最短路问题了。 尝试使用普通BFS 0元素可以向四个方向移动，上左，上，下，下右，极端情况走到21步(也就是too difficult)，一共有4^21的复杂度，1e12的数量级了，普通bfs必定会超时。 尝试使用双向BFS ...

0 点赞评论收藏

2020-02-15 18:17

已编辑

河南理工大学 golang

题目导航

题目导航 图论 BFS 模板题 【easy】hdu1312Red and Blackbfs的基础模板题，会bfs就能做的 双向BFS 【medium】190. 字串变换 模板题 此题做法以及思想参考acwing题意：求字符串到目标字符串的最小变换次数。可以用双向BFS，让起点和终点同时搜索，然后判断是否有交点的状态，这样可以省去很大的搜索空间【hard】hdu6171 Admiral题意：把一个21元素的排列，通过规则移动，看是否能在20步之内移动到另一个状态。这题给定了初始状态和目标状态就可以想到是双向BFS算法做，当然也可以用A*算法，只不过双向BFS更好写一些，A*算法要退一个启发函数...

0 点赞评论收藏

2020-03-03 13:55

已编辑

河南理工大学 golang

1264. 动态求连续区间和【模板】【树状数组】

1264. 动态求连续区间和 给定 n 个数组成的一个数列，规定有两种操作，一是修改某个元素，二是求子数列 [a,b] 的连续和。 输入格式第一行包含两个整数 n 和 m，分别表示数的个数和操作次数。 第二行包含 n 个整数，表示完整数列。 接下来 m 行，每行包含三个整数 k,a,b （k=0，表示求子数列[a,b]的和；k=1，表示第 a 个数加 b）。 数列从 1 开始计数。 输出格式输出若干行数字，表示 k=0 时，对应的子数列 [a,b] 的连续和。 数据范围1≤n≤100000,1≤m≤100000，1≤a≤b≤n输入样例： 10 5 1 2 3 4 5 6 7 8 9 10 1 ...

0 点赞评论收藏

关注他的用户也关注了：