Z_L_G - 个人主页动态

07-13 12:03

已编辑

题意  n个数，确定了m对关系(a>b) 求还需要多少对关系就能确定任意两个数之间的大小  思路  把大小关系视为一条有向边 这个题就变成了任意两个点是否联通 考虑使用FLoyd，但是n是1000量级的，刚好爆炸 使用bitset优化  足够 floyd算法可以传递闭包关系 bitset错误赋值，1是int超过32位就无效了   cin >> n >> m ; for(int i=1;i<=m;i++){ int x,y; cin >> x >> y; f[x]|=(1<<(y-1)); }  代码 #include&lt...

0 点赞评论收藏

07-13 11:40

北京航空航天大学算法工程师

算法入门-HDUOJ5521Meeting

题意  n个点，m个集合，在i-th集合内相互移动的代价为t-th 两个人从1和n开始移动，求碰面最短时间和碰面的点  思路  强行给每个集合之间的点互相连边复杂度会到  不可以 对于这种集合/平台类的问题，我们通常选择给每个集合/平台单开一个点，集合中所有点到这个单开点建双向边，过去的代价为t，回来的代价为0,这样就建完了图 建完图后，从1和n跑两遍dijkstra 最终答案遍历每一个点，取   代码 #include<bits/stdc++.h> using namespace std; struct ty{ int t,l,nxt; }edge[2020220]; int h...

0 点赞评论收藏

07-13 10:23

北京航空航天大学算法工程师

算法入门-[SCOI2012]滑雪与时间胶囊

题意  给定n个点，每个点有自己的高度，给定m条边，边总是由高的点指向低的点 特别的，两个点一样高，就认为是双向边 求出最多能到达的点的个数，以及到达这些点需要的最小距离  思路  先dfs一遍，确定哪些点能到 类似于最小生成树，但是最小生成树需要保证边都是无向边，因为最小生成树加入一条边本质上是两个点之间能联通 到这个题，由任意点都只能向下访问各个点，所以，Prim的排序就不再只按照长度排序，而是先按照高度(保证尽可能访问更多点)，再按照长度 而如果使用Kruskal，给边排序的时候也是按照边中较低的点进行排序，使得终点最高，然后再按长度排序，拿到一条边的时候从高的地方走向矮的地方，那就要保...

0 点赞评论收藏

07-11 23:10

北京航空航天大学算法工程师

算法入门-[HNOI2015]菜肴制作

#反向建边 #拓扑排序 题意  有n个菜，m个条件约束条件(a,b)，表a必须在b之前 除了约束条件外，要保证序号小的的尽可能先做 在满足所有限制的前提下，1 号菜肴”尽量“优先制作； 在满足所有限制，1号菜肴”尽量“优先制作的前提下，2号菜肴”尽量“优先制作； 以此类推。 例：共4 道菜肴，两条限制<3,1>、<4,1>，那么制作顺序是 3,4,1,2。  思路  正向描述这个拓扑序不好描述，因为每做一个菜都可能影响当前的“最优先做的菜” 考虑反向描述 先做序号最小的->最后做序号最大的 通过反向建边，变为在拓扑序中寻找字典序最大的  代码 #include&l...

0 点赞评论收藏

07-11 22:58

北京航空航天大学算法工程师

算法入门-胖胖的牛牛

题意  n*n的正方形地图，从起点走到终点，图中有一些障碍物不能走 求最小转弯次数  思路  图不大，迷宫问题，考虑搜索，不再记录步长，而是在走每一步的时候考虑和走过来的方向是否相同，如果不同就给转弯次数+1 用一个优先队列避免重复走 不开vis，否则部分优势可能掩盖全局劣势 也可以最短路做，每个点转化成四个点，和其它点建边  代码 #include<bits/stdc++.h> using namespace std; //太痛了，01bfs用vis可能会劣势路抢占优势路 char mp[120][120]; int dis[120][120][4]; int mv[4][2] ...

0 点赞评论收藏

07-11 22:35

北京航空航天大学算法工程师

图论-最短路

特殊最短路  树：直接起点dfs搜索到终点即可 有向无环图：拓扑排序，删掉每一个点时更新后继的最短距离 边权全部为相等：bfs  单源最短路  从一个点出发到其它顶点的最短路径长度 基本操作：松弛  这样的(u,v)称为紧的，可以对它进行松弛  dijkstra  不能存在负边，每个边会被访问一次，每个边都有可能进一次优先队列   dis数组初值赋为极大 起点dis为0 计算与s相邻的所有点的dis—— 取还没算出最短路的点中dis最小的点u，它的最短路就是 对于u相连的所有点v如果能松弛，更新 重复4,5直到所有点求完  #include<bits/stdc++.h> using...

0 点赞评论收藏

07-11 22:34

北京航空航天大学算法工程师

图论-最小生成树

Prim  从单一顶点开始 不断加入最小的边，且边的一个顶点在树中一个顶点不在  #include<bits/stdc++.h> using namespace std; typedef struct{ int t,l,nxt; }E; E edge[1010110]; int head[101010]; int cnt; int n,m; void insert(int a,int b,int v){ edge[++cnt].t=b; edge[cnt].l=v; edge[cnt].nxt=head[a]; head[a]=cnt; } struct ty{ int x,len...

0 点赞评论收藏

07-11 22:33

北京航空航天大学算法工程师

图论-AOE与关键路径

关键路径  AOE网(Activity On Edge network)，即边表示活动的网络，与AOV网相对应，它通常表示一个工程的计划或进度。 AOE网是一个带权的有向无环图，图中的：  边：表示活动(子工程)， 边上的权：表示该活动的持续时间，即完成该活动所需要的时间； 顶点：表示事件，每个事件是活动之间的转接点，即表示它的所有入边活动到此完成，所有出边活动从此开始。   其中有两个特殊的顶点(事件)  一个称做源点，它表示整个工程的开始，亦即最早活动的起点，显然它只有出边，没有入边； 另一个称做汇点，它表示整个工程的结束，亦即最后活动的终点，显然它只有入边，没有出边。除这两个顶点外，其余...

0 点赞评论收藏

07-11 22:33

北京航空航天大学算法工程师

图论-AOV与拓扑排序

引入  一个工程有许多子工程，称为活动，在有向图中用顶点表示活动，有向边表示活动的先后顺序，这样的图称为AOV网，在AOV网中为了更好的完成工程，需要满序先后关系，将各活动排一个先后次序，就称为拓扑排序  问题  对一个AOV图，判断能否排序，并进行排序  解决方法  从有向图中选一个没有前驱的结点，输出 从图中删除这个点以及所有出边 重复上述两步直至图为空，或者无法删除 注意，拓扑排序存在多解，可能同时存在两个没有前驱的结点  实现  开一个队列，把入度为0的点弹入，弹出队首，给邻接点入读减一，如果减成0,入队 对于每个点每个边都访问一次，O(nm)  #include<bits/st...

0 点赞评论收藏

07-11 22:31

北京航空航天大学算法工程师

图论-图存储总结

1.邻接矩阵  二维数组，如果有重边就按题意考虑是否可以合并成一条边，或者只取一条边  2.邻接表  链表结构，头插法  3.vector  开一个vector数组来简化邻接表，但有时不够块  4.链式前向星  开一个结构体存边信息，开一个数组存每一条边，开一个head记录连接着这个点的下一个点是谁,head初值赋值成-1  typedef struct{ int t,val,nxt; }E; E edge[N]; int head[N]; int cnt; void insert(int x,int y,int l){ edge[++cnt].t=y; edge[cnt].val=l; ed...

0 点赞评论收藏

07-11 22:30

北京航空航天大学算法工程师

图论-欧拉图判断

什么是欧拉图  图G中存在一个路径，包含每个边恰好一次，该路径是欧拉路径 如果一个回路是欧拉路径，就称为欧拉回路 有欧拉回路的图是欧拉图，有欧拉路径没有欧拉回路的图称为半欧拉图  怎么判  图联通 无向图所有顶点的度是偶数 有向图所有顶点的入度等于出度

0 点赞评论收藏

07-09 23:33

北京航空航天大学算法工程师

算法入门-[NOIP2003]加分二叉树

题意  一个1-base二叉树，n个结点，中序遍历为(1,2,3,...,n),每个点有一个val，选择一个子树的加分规则如下： 如果某个子树为空，就视为val=1，叶子节点分数为本身的分数 求符合中序遍历的加分最高的二叉树，输出加分和前序遍历  思路  对于一段中序遍历序号，总需要选择一个根，切分出左右子树计算价值 对于切分出的区间不断重复上述过程，得出整个树的最优解 那么大概就是一个区间dp，表示区间(i,j)最高分, 注意k如果是左右边界的时候需要强制置为1 对于还原根这个事，其实就是要在dp过程中保留每次取最优解的时候选择的根，所以再开一个path数组即可 最终还原前序遍历的时候dfs...

0 点赞评论收藏

07-09 23:22

已编辑

北京航空航天大学算法工程师

算法入门-树学

题意  一个树，n个结点，每个结点的深度是到根的距离，整棵树的价值是所有点的深度和 求选择哪个点为根时可以使深度和最小  思路  让每一个点为根跑一遍dfs就可以维护出每个点的深度和整个树的深度和 但是让每一个点跑一遍复杂度会爆炸 能不能只跑一遍？如果只跑一遍，根变换怎么办 对于一个选定根的树，如果把根的一个子节点提升为根，则除了这个子节点所在子树以外的结点都下降了一层，子节点所在子树上升了一层 则总和的变换就可以推出 任选一个点为根，维护每个点深度和子树，然后再跑一遍dfs表示换根，跑出每一个点为根的时候的sum 最后遍历每一个sum维护出答案即可  代码 #include<bits/...

0 点赞评论收藏

07-08 21:29

北京航空航天大学算法工程师

算法入门-[NOIP2018]货币系统

#动态规划 #完全背包 题意  给定一个n种面值组成的货币系统，如果其中某一个面值可以由系统中的其它货币表示就认为这个面值是冗余的 求出这个货币系统去除冗余后最少有几种面值  思路  按照题意完全背包即可 注意判断一个货币是否冗余，是在使用它之前判断是否已经被表示  代码 #include<bits/stdc++.h> using namespace std; /** * 对于一个货币系统尝试简化它，其实就是从已知的种类中尝试删掉几个 * 可以转化为一个完全背包，背包的容积为最大的面值 * 尝试用小的货币去表示大的货币，如果可以表示，就删除 */ int f[25500]; int...

0 点赞评论收藏

07-08 20:33

北京航空航天大学算法工程师

算法入门-[SCOI2009]粉刷匠

#动态规划 #多次dp 题意  有n块木板，每块木板有m格，你可以粉刷t次，每次可以粉刷连续的若干格，不能覆盖 给定正确的粉刷方案，请问最多可以刷对多少格 0<=n,m<=50,t<=2500  思路  如果只有一块木板，可以线性dp解决 表示刷i次，刷到j  对于若干块板子，如果能在O(1)的时间知道对于任意一块板子刷到某一个程度的正确格数就可以dp 预处理每一块木板的价值 再dp任意块的价值 注意考虑每个循环的意义确定范围  代码 #include<bits/stdc++.h> #define int long long using namespace std...

0 点赞评论收藏

创作者周榜

关注他的用户也关注了：