Asuka158

分类

新知识(5) 题解(3)

/ 注册

全部文章（共8篇）

2021年广东工业大学第十五届文远知行杯程序设计竞赛 E 捡贝壳（分块 | 思维）

E 捡贝壳（分块 | 思维）方法一：分块 1.块的大小时根号n，预处理分块数组2.求解时，对于两边的l，r所在的块不论是否是整块都单独求，先求l所在的，求完后判l，r是否在一个块内（对于是否在一个块内，数组下标从0开始，这样的话数组下标/根号n所得的数字即是第几个块），是则可直接return...

c++ 二分查找 vector 分块 ACM 思维

2021-03-29

6 1079

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

POJ3275 Ranking the Cows（floyd传递闭包）

POJ3275 Ranking the Cows 题意：有N个数字，已经比较了M对(x,y),其中x>y, 问至少再需要比较多少对数字，就能把N个数按大小有序的排列起来分析：如果x>y,就在x和y之间连一条单向边，然后用floyd算法（floyd传递闭包）， AC代码： #includ...

c++ 图论 Floyd STL ACM bitset

2021-03-08

1 673

最短路模板（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

NC20185 [JSOI2010]缓存交换

NC20185 [JSOI2010]缓存交换这是一道堆的题，堆的题常与贪心有关，此题也是。借鉴别人的博客 + 别人的代码给整明白了，于是乎自己写篇博客再理理思路首先这个题肯定是要在下标上做文章，因为要判断当前数是否在缓存区内，我们可以用一个bool数组，而这个数组肯定存第i个数在不在缓存区内...

c++ 堆贪心 ACM map 优先队列

2021-03-01

18 971

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

单调队列单调队列这个东东之前学过一遍了~但似乎忘得一干二净惹，或者当时就妹学会 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