ProApe - 个人主页动态

2020-01-02 15:45

1 先用拓扑排序将多余的顶点去除，只剩下组成环的点，然后用DFS求出每个环的长度 #pragma GCC optimize(2) #include<bits/stdc++.h> using namespace std; #define pi acos(-1.0) #define e exp(1.0) typedef long long ll; const ll maxn=2e5+7;//用拓扑排序将不是环的点去掉  ll N,M,head[maxn],in[maxn],cnt,jie; bool vis[maxn]; queue<ll>Q; struct Edge { ...

0 点赞评论收藏

2020-01-02 15:45

已编辑

第一拖拉机制造厂拖拉机学院前端工程师

洛谷P1330 封锁阳光大学

按照题意，每个顶点要不放河蟹，要不不放河蟹，而且相连的顶点不能具有相同的状态。因此我们可以将其抽象成二分图，即两种相连的顶点不能染成相同的颜色，对于每一个连通图，我们使用两种颜色通过DFS将其染色，只要有一个连通图不能染色成功，就直接得到结果“NO”,因为题中可能含有多个连通图，对第i个连通图，我用2i和2i+1表示两种颜色，这个连通图放的河蟹数就是用这两种颜色染成的顶点数最小的那种颜色的数量，即min(用2i染的顶点数量，用2i+1染的顶点数量)，最后每一个连通图求和就是最后的答案 #pragma GCC optimize(2) #include<bits/stdc++.h> u...

0 点赞评论收藏

2020-01-02 15:44

第一拖拉机制造厂拖拉机学院前端工程师

HDU Wave

我们发现这道题的C很小，所以得从这方面下手，把这些数依据奇偶性划分成两个集合，并且把每一个数在序列中出现的位置记录下来，我们暴力尝试每一个奇数和偶数构成的Wave，最后取一个最大值就行了，每一次尝试过程是这样的的比如：N<mark>8 C</mark>2 2 1 1 2 2 1 2 1 1的位置：2 3 6 8 2的位置有：1 4 5 7 位置最小的是2中的1，然后在1中找第一个大于1的位置，此时是2，然后在2中找到第一个大于2的位置，此时是4，然后在1中找到一个大于4的位置……依次交替查找下去，直到查找失败  ```#pragma GCC optimize(2) #i...

0 点赞评论收藏

2020-01-02 15:44

已编辑

第一拖拉机制造厂拖拉机学院前端工程师

HDU Traffic

题意是这样的：在一个十字路口，有N辆车是东西通行的，有M辆车是南北通行的，并且给你每辆车通过的十字路口的时刻表，当东西通行的车和南北同行的车同时通过十字路口的话就会发生碰撞，现在要求东西通行的时刻表不变，南北通行的车辆要集体最少等待多少时间才能不发生碰撞一开始题读错了，忽略了集体等待，好吧，其实是我太菜 #pragma GCC optimize(2) #include<bits/stdc++.h> using namespace std; #define pi acos(-1.0) #define e exp(1.0) typedef long long ll; const ll ...

0 点赞评论收藏

2020-01-02 15:44

第一拖拉机制造厂拖拉机学院前端工程师

HDU Cotree(换根dp,树的重心)

我是看了这位大佬的博客，感谢大佬他的博客 题目描述：有两颗树，需要在这两棵树之间添加一条边，这样就变成了一棵树，求这棵树任意两点之间的最小距离和 即$$\sum ^{N}{i=1}\sum ^{N}{j=i+1}dis\left( i,j\right)$$ 解题思路：首先考虑，我们要在哪两个点之间添加一条边呢？这个点实际上就是树的重心，树的重心是这样定义的：树的重心也叫树的质心。找到一个点,其所有的子树中最大的子树节点数最少,那么这个点就是这棵树的重心,删去重心后，生成的多棵树尽可能平衡（引自百度百科）在这个问题中，也是找到一个点，使得这棵树上的其他点到这个点的距离和最小，这个点即这棵树的重心...

0 点赞评论收藏

2020-01-02 15:43

已编辑

第一拖拉机制造厂拖拉机学院前端工程师

Minimum Spanning Tree

题意：有一棵边带有权值的树，定义线图：将这颗树的每一条边缩成一个点，这个点的点权为原先的边权，当原先树中两条边有公用的节点时，则线图中缩成的两个点有边相连，且边的权值为这两个点的点权之和。求形成的线图的最小生成树。 解题思路：你会发现在原先的树中，父节点和他紧邻的所有子节点形成的线图是一个完全图，而这个完全图的最小生成树只需将其他点和点权最小的点连接起来就可以了。看懂下面这个图就好理解代码了  发下代码： #pragma GCC optimize(2) #include<bits/stdc++.h> using namespace std; #define pi acos(-1.0...

0 点赞评论收藏

2020-01-02 15:43

已编辑

第一拖拉机制造厂拖拉机学院前端工程师

Line-line Intersection

题意：给了N条线（注意这些线有可能重合），问两条直线有交点的对数，1 3和3 1 属于同一对，两条直线重合也算有交点 解题思路：这道题有些细节是很恶心的 因为怕卡精度，所以直接用了pair存，用map套一个pair存储斜率，但是只存储斜率是不行的，因为直线有重合的情况，所以还得用map套两个pair存储k和b。y=kx+b{k=(y1-y2)/(x1-x2),b=(x2y1-x1y2)/(x2-x1)}。因为第i条直线最多和前面的i-1条直线相交，加上i-1条，减去斜率相同的条数，再加上减多的条数（k和b值都相同的） 代码： #pragma GCC optimize(2) #include&l...

0 点赞评论收藏

2020-01-02 15:43

第一拖拉机制造厂拖拉机学院前端工程师

二叉树基本操作的实现

实验项目五：二叉树基本操作的实现 课程名称：数据结构 实验项目名称：二叉树基本操作的实现 实验目的： 1．掌握树的基本操作—遍历。 实验要求： 1、 分别用递归和非递归的方法实现一棵树的三种遍历。 实验过程： 1、 创建一棵二叉树（二叉树如下图所示）； 2、 用递归算法实现对该树的三种遍历； 3、 用非递归算法实现对该树的三种遍历； 4、 输入选项：0或1，0为递归遍历，1为非递归遍历。 5、 根据输入的选项，分别调用递归或非递归算法输出先序、中序、后序遍历序列。 实验报告中给出先序和后序遍历的非递归实现算法代码。 实验结果： 1、输入：ABD##E##CF#G###（创建二叉树） 2、输入：...

0 点赞评论收藏

2020-01-02 15:42

已编辑

第一拖拉机制造厂拖拉机学院前端工程师

串基本操作的实现

实验项目四：串基本操作的实现 课程名称：数据结构 实验项目名称：串基本操作的实现 实验目的： 1．掌握串的模式匹配操作。 实验要求： 1、 分别使用BF和KMP算法完成串的模式匹配。 实验过程： BF算法代码;; 1、 设计完成next值的计算函数； 2、 设计完成修正next值的函数； 3、 KMP算法代码； 4、 输入子串（aaac）和主串(aaabaaaaaac) 5、 输出子串在主串中开始的位置及不同算法比较的次数。 此部分实验报告中给出BF，next,修正next，KMP的代码。 实验结果： 输入： 子串：aaac； 主串：aaabaaaaaac 输出：BF,KMP,改进的KMP三种...

0 点赞评论收藏

2020-01-02 15:42

第一拖拉机制造厂拖拉机学院前端工程师

二叉树的线索化&&线索二叉树的遍历（中序）

二叉树的线索化：对于N个节点的二叉树，在二叉存储链表中有N+1个空链域，利用这些空链域存放某种遍历次序下的指向该节点的前驱和后继的指针，这些指针成为线索，被线索的二叉树成为线索二叉树。这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树(Threaded BinaryTree)。根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种。 中序线索二叉树：指在中序遍历的同时，对二叉树进行线索化，只需要在原先的中序遍历中添加相应的线索话语句即可,设置两个指针，P和Pre，P指向当前访问的节点，Pre指向上一个访问的节点，修改指针：如果P->Lch&l...

0 点赞评论收藏

2020-01-02 15:42

第一拖拉机制造厂拖拉机学院前端工程师

洛谷P2921

刚看到这道题的时候，没有在意复杂度，就直接暴力了，我也真是憨了，这可是提高省选组的题……后来看看算法标签说是记忆化搜索，再仔细看看题，这不就是每个顶点出度只有一的有向图嘛，包括自环，且是多个连通块，然后，每一个顶点停止遍历的时候一定是进入了一个环内或者自身是某个环的一部分，否则遍历是不会停止的，那么所有的数据应该类似这种情况    接下来咋搞呢？想半天也没有整明白，写了一个假算法，理论上是没问题的，结果RE了，我想应该是栈爆了，后来看了看洛谷的第一篇题解，也是看了很长一段时间才迷瞪过来，就感觉太妙了！！！ col[i]:该节点第一次被遍历到时是以那个顶点为起点的，上图我们是以顶点1开始遍历的，...

0 点赞评论收藏

创作者周榜

关注他的用户也关注了：