pubgoso_2024

acm

atcoder(1) bfs(3) cf(14) clion(2) dfs(15) dp(33) KMP(3) segement tree beats(1) wannafly(7) 主席树(2) 二分(10) 匹配(2) 单调栈(2) 大数(2) 字典树(1) 字符串(3) 思维(6) 数学(50) 暴力(2) 最小生成树(7) 最短路(8) 未归档(45) 构造(1) 树(4) 树状数组(11) 树链剖分(1) 模拟(3) 矩阵(2) 离散化(5) 线段树(16) 莫队(4) 记录(3) 贪心(20)

/ 注册

全部文章 / acm （共131篇）

hdu6705

题目链接大意：给你一张有向加权图，让你求出第k小的路径思路：显然我们从大到小处理到最大的询问就可以了。先对所有点的出边按权值从小到大排序，然后塞到优先队列中，每次取出队头最小的元素更新答案，但是如果直接遍历点所有出边的话是会tle的，我们需要一个multiset来记录优先队列中的答案，如果mu...

2020-05-06

0 469

hdu6686 Rikka with Travels(树的直径)

题目链接大意：给你一棵树，让你求出多少对 ( l , r ...

2020-05-06

0 438

hdu6655 Just Repeat(贪心)

题目链接大意：两个人玩游戏，每回合一方可以放另一方没有放过的卡，谁最后没卡放谁输思路：每回合，出卡的人肯定要出场上最多的卡，这样可以使自己尽量多或者别人尽量少细节见代码： #include<bits/stdc++.h> #define LL unsigned long long...

2020-05-06

0 410

hdu6701 Make Rounddog Happy(分治)

题目链接大意:让你求满足题意的区间个数思路：先跑一遍rmq，记录区间最大值下标，预处理每个点最左到左边哪个点，最右到右边哪个点，使得这段区间没有重复。然后就直接分治，每次分治的区间先求出最大值下标，然后对小的一边for扫一遍求出符合的区间然后更新答案即可。细节见代码 #include<...

2020-05-06

0 441

2019牛客暑期多校训练营（第三场）F Planting Trees(单调队列)

题目链接大意：给你一个n*n的矩阵，让你求出面积最大的矩形，使得矩形内极差小于等于k 思路：我们枚举矩形上下界，然后遍历右边界，维护每列的最大最小值，同时维护两个个下标递增，值分别递增和递减的单调队列，每次弹出不合法的队头元素，然后更新答案即可。细节见代码： #include<bits...

2020-05-06

0 522

2019牛客暑期多校训练营（第三场）G Removing Stones

题目链接大意：给你一个数组，让你求出有多少个合法的区间。合法区间定义为：每次选择两个元素同时减1，若能都减为0即为合法，特别的，如果区间和为奇数时，可以选择一个值最小的使他减1. 思路：转换一下问题就是，让你求多少个区间，使得区间的最大值不大于区间和的1/2，（向下取整）。那么我们可以分治做，...

2020-05-06

0 541

Manthan, Codefest 19 (open for everyone, rated, Div. 1 + Div. 2) E.Let them slide(单调队列)

题目链接大意：给你一个n*m的空间，每行都有一些元素，你可以整体滑动这些元素，让你求出每列和的最大值思路：如果行的元素不能充满m列的话，我们在前后补上0，防止负数。然后扫一遍记录每个元素可能出现的列号，然后维护一个单调不增的单调队列，每次弹出元素就在差分数组中更新答案，然后把这个值存到队列中，要...

2020-05-06

0 414

2019 计蒜之道初赛第五场浪潮面试题之数组（单调栈）

题目链接题目大意：思路：用单调栈维护最优决策的集合。我们倒着遍历数组，每次遍历到的相当于 i i i, 每次新建一个决策 ...

2020-05-06

0 775

2019南京网络赛A 树状数组+思维

官方题解：代码如下： #include<bits/stdc++.h> #define fi first #define se second #define mp make_pair #define pb push_back #define LL long long #define...

2020-05-06

0 416

2019南京网络赛F 树状数组+主席树

题目链接大意：输出每个i为开头情况下的满足字典序最大的长度。思路：每个i的答案显然是在[pos-k,pos+k]中取一个最大的且不超过i的答案+1，那么，我们可以用树状数组预处理出每个i在区间内小于他的个数，然后用主席树直接差区间第x小即可。树状数组的操作细节为，把区间拆成左右两部分，然后...

2020-05-06

0 467