shyyhs

分类

DP专题(52) 图论(4) 多校补题(2) 数据结构(27) 数论(4) 日记(14) 未归档(38) 题解(330)

/ 注册

TA的专栏 440篇文章 0人订阅

415篇文章 3901人学习

AtCoder思维大提升

6篇文章 753人学习

kuangbin专题记录

0篇文章 0人学习

牛客每日一题推介(裙子计划~)

19篇文章 848人学习

全部文章（共469篇）

#2815. [ZJOI2012]灾难

因为是一个有向无环图,一个生物灭绝的条件是它的食物都灭绝. 那么我们考虑按topotopotopo序重构这张图,因为一定是一个森林/树,我们考虑增加一个超级源点uuu.然后且当它的祖先节点灭绝它就会灭绝,考虑把它**到它所有食物的lcalcalca下面,然后灭绝它的毁灭值就是子树大小−1子树大小-1...

倍增重构

2022-04-14

0 460

主席树来自专栏

前言以前学的算法等于白学(点分治除外)>>,今天ac500后将系统学习以及记录主席树. 主席树它是一个类似前缀的数据结构,通过每次在原有的树上更新需要更新的区间信息,从而达到区间查询的目的,可以把它看成一个差分效果?它一般把权值当成下标可以查询区间第k大,以及区间不同种类数等功能...

主席树

2022-04-12

0 366

中位数来自专栏

关于带权中位数自己的理解. 不妨把权值全部变成数,那么就转化成了中位数问题,显然只有包含中位数才能达到最优,所以可以进行二分,考虑假如前面的和不超过后面的,显然这个值不含有中位数,一定不是最优解,那么就是大于等于它的第一个位子是最优解.

中位数

2022-04-11

0 404

牛牛的方格图来自专栏

感觉自己在降智... 一开始写c想二分,二分半天也没二分出什么...最后是枚举. 想e的时候一直想偏序,我不知道正解是啥,最后写完我的想法刚好没时间了..当然还没调qwq 介绍下自己的想法,将方格的横坐标看成是时间,然后在维护时间的一个优先队列,假如现在的时间要大于优先队列对头的时间,那么对头就要去...

排序

2022-04-08

0 514

异度之刃

首先考虑贡献如何算? 比如1 2 3 4 5 2 3 4,很显然的一个算就是把2 3 4去掉,然后只求1 2 3 4 5的贡献. 考虑i以及相邻的一段的贡献,很显然i的贡献就是相邻一段的长度,比如说1 2 3,1的贡献是1,2的贡献是2,3的贡献是3. 知道贡献怎么算了,下面就分为几步解决这个问题....

线段树

2022-04-07

4 430

题解 | #割韭菜# 来自专栏

首先讲ai排序(从小到大)后,后缀一定是不减的. 证明:在没有割草之前这个一定是成立的,假设我有割草,割的高度是b,那么前面的一定小于b,后面=b,然后后面还是比前面长的更快. 由此就产生了一个线段树二分的做法. 上一次被割草的时间day+1,区间内草的增加速度之和spd,区间内左端点的速度nmsp...

线段树

2022-04-05

0 589

题解 | gk的爬山之旅

单调栈一般就是栈内的更新细节...无数次折磨了首先发现这个图是个dag(有向无环图),假如对值比它大的最近的左右两个点连边的话,然后对dag做个简单的线性dp就好了. 细节就是一段相同的时候,因为数据保证递增,在前面的时候肯定选取最前面的最优,在后面的时候肯定选最后面最优,然后一定要在栈内更新,比...

单调栈

2022-04-05

2 474

进来DP 来自专栏

大部分代码贪心解法是错误的,原题是CF1442D,可以在cf上测试一下. 首先不考虑贪心,这是个分组背包O(N2K)O(N^2K)O(N2K),考虑贪心暴力仍然是O(N2K)O(N^2K)O(N2K). 贪心题解讲的很清楚了,那么我们如何能够做到更优的时间复杂度解决这个问题呢. 可以是分治,在每次递...

dp

2022-04-04

0 459

蹦蹦炸弹来自专栏

应该又是一个模拟...模拟此生之敌. 首先考虑一个方向和不同速度的情况叭? 很容易想到,假如方向从右到左,那么我们按从左到右输入,考虑相邻两个,假如我右边那个速度小于左边那个,肯定是追不上的啦(这辈子都不可能追上). 从此我们可以得出,它们前面那些炸弹共存的条件就是速度递减,那么我假如突然来了一个速...

set

2022-04-04

0 957

迷宫来自专栏

根号分治. 对于队列里面没有满sqrt(n∗m∗h){sqrt(n*m*h)}sqrt(n∗m∗h)的直接对于每个查询进行暴力. 对于满了的,对队列所有的元素做一次bfs{bfs}bfs,bfs{bfs}bfs复杂度是n∗m∗h{n*m*h}n∗m∗h. 然后清空队列即可. 总复杂度为nsqrt(n...

C++

2022-04-03

0 472