Asuka158

新知识

题解(3)

/ 注册

全部文章 / 新知识（共5篇）

01bfs

01 bfs UVA11573 Ocean Currents 分析：题中给了两种移动方式，一种是沿着洋流的方向移动，不需要消耗能量，不沿着洋流走需要消耗1能量，此类按照普通的bfs不能保证队列前面的一定是当前消耗能量最少的情况。正确做法是利用双端队列，不消耗能量就从队首入队，消耗能量就从队尾入...

deque 01bfs c++ 搜索 ACM

2021-03-18

0 989

整理整理

并查集有关食物链分析：存在A吃B，B吃C，C吃A这三种关系，即存在三种生物，三个集合，而这三种生物又是等价的，对于每一个生物x，他都可以是A，也可以是B，也可以是C，假定fa[x],fa[n + x], fa[2 * n + x]分别是生物x是A,B,C的情况下的父节点。对于每次的两个生物都要把...

c++ 二分二分图图论并查集 ACM

2021-03-15

0 753

最短路模板（Dijkstra + spfa）

dijkstral算法 (复杂度O(nlongn + m))——不能有负权边spfa算法 (复杂度O(km))——不能有负权环如何存图用的是伪邻接表（链式前向星）插入用的是头插法 int tot; struct node { int to, l, next;//to代表这条边指向谁，l...

c++ 最短路图论 Dijkstral ACM spfa

2021-03-06

1 869

几天前所学？（单调队列 + 堆）

单调队列单调队列这个东东之前学过一遍了~但似乎忘得一干二净惹，或者当时就妹学会 NC50528 滑动窗口模板（找最小的数） l = 0;//左闭右开的区间 r = 1; p[0] = 1;//数组p存的原数组的下标 if(k == 1) printf(&qu...

c++ 对顶堆堆单调队列 ACM 优先队列

2021-02-28

1 619

二分 + 01分数规划

一.STL的二分函数 1.binary_search(ar, ar + n, x); 三个参数，第一个是数组首地址，第二个是数组名+数组大小，第三个数要找的数。存在这个数则返回true，否则返回false； 2.lower_bound(ar, ar + n, x); 参数和上面那个一样，返回的是第一...

2021-02-24

0 707