Asuka158
Asuka158
全部文章
分类
新知识(5)
题解(3)
归档
标签
去牛客网
登录
/
注册
鬼頭 明里 の 博客
我把温柔和可爱都设置成了仅你可见
全部文章
(共7篇)
2021年广东工业大学第十五届文远知行杯程序设计竞赛 E 捡贝壳 (分块 | 思维)
E 捡贝壳 (分块 | 思维) 方法一:分块 1.块的大小时根号n,预处理分块数组2.求解时,对于两边的l,r所在的块不论是否是整块都单独求,先求l所在的,求完后判l,r是否在一个块内(对于是否在一个块内,数组下标从0开始,这样的话数组下标/根号n所得的数字即是第几个块),是则可直接return...
c++
二分查找
vector
分块
ACM
思维
2021-03-29
6
1062
01bfs
01 bfs UVA11573 Ocean Currents 分析:题中给了两种移动方式,一种是沿着洋流的方向移动,不需要消耗能量,不沿着洋流走需要消耗1能量,此类按照普通的bfs不能保证队列前面的一定是当前消耗能量最少的情况。正确做法是利用双端队列,不消耗能量就从队首入队,消耗能量就从队尾入...
deque
01bfs
c++
搜索
ACM
2021-03-18
0
977
整理整理
并查集有关 食物链 分析:存在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
744
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
664
最短路模板(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
872
NC20185 [JSOI2010]缓存交换
NC20185 [JSOI2010]缓存交换 这是一道堆的题,堆的题常与贪心有关,此题也是。借鉴别人的博客 + 别人的代码给整明白了,于是乎自己写篇博客再理理思路首先这个题肯定是要在下标上做文章,因为要判断当前数是否在缓存区内,我们可以用一个bool数组,而这个数组肯定存第i个数在不在缓存区内...
c++
堆
贪心
ACM
map
优先队列
2021-03-01
18
977
几天前所学?(单调队列 + 堆)
单调队列 单调队列这个东东之前学过一遍了~但似乎忘得一干二净惹,或者当时就妹学会 NC50528 滑动窗口 模板(找最小的数) l = 0;//左闭右开的区间 r = 1; p[0] = 1;//数组p存的原数组的下标 if(k == 1) printf(&qu...
c++
对顶堆
堆
单调队列
ACM
优先队列
2021-02-28
1
611