shyyhs

题解

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

/ 注册

全部文章 / 题解（共329篇）

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

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

线段树

2022-04-05

0 592

题解 | gk的爬山之旅

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

单调栈

2022-04-05

2 480

进来DP 来自专栏

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

dp

2022-04-04

0 461

蹦蹦炸弹来自专栏

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

set

2022-04-04

0 965

迷宫来自专栏

根号分治. 对于队列里面没有满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 479

gk的树

求助...不知道dp状态设计错了还是贪心设计的有问题. fu,0/1f_{u,0/1}fu,0/1到了u这个节点删不删和它父亲相连的边使得度数都<=k 最少删除多少边. 然后抛出子节点状态更新父亲节点状态. 对于fu,0f_{u,0}fu,0来说它必须删除子节点个数−(k−1){-(k-...

2022-04-03

3 791

A.I 来自专栏

好菜做了一下午签了个到 A: 可以发现n/i值是一样的数成等差数列,所以对于大数据暴力分治就好了,小数据用rmq查询. https://ac.nowcoder.com/acm/contest/view-submission?submissionId=51451018 I: 同样也可以发现i,i+k...

C++

2022-03-26

5 520

灵力之泉来自专栏

换根dp{dp}dp. 首先我们假如知道子树相连点的答案,我们肯定优先选择最大的. dpdpdp方程为:fu=max(fu,fv+i/wu+1).f_u=max(f_u,f_v+i/w_u+1).fu=max(fu,fv+i/wu+1). iii表示第i大的fvf_vfv. 通过树形dpd...

C++

2022-01-10

0 421

「Nhk R1 D」Apocryphal Vir Pulcher

假如我知道这个值的第k小,那么它选择第k+1小是不是有n种选择. 所以就类似bfs,但是在bfs过程中会产生重复,什么重复呢,就是我现在是1搜3,搜出来是1+3,我现在是3搜1,搜出来是3+1,但是两者在题目中属于同一种含义. 所以我们简单的去重一下,就像定义两个for都从1开始循环,我们只要把两个...

2022-01-02

3 538

「Nhk R1 C」Zet'ubou Another

提供一个保证正确但是有点麻烦的写法. 因为障碍物就2500个,你假如矩阵大小n,m都大于2500,那么你只要没有把开头的2500∗2500{2500*2500}2500∗2500的矩阵围住且结尾的2500∗2500{2500*2500}2500∗2500的围住就是YES. 假如n,m都小于2500,...

2022-01-01

5 606