shyyhs

分类

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

/ 注册

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

415篇文章 3901人学习

AtCoder思维大提升

6篇文章 753人学习

kuangbin专题记录

0篇文章 0人学习

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

19篇文章 848人学习

全部文章（共469篇）

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 787

动态开点线段树来自专栏

<发现自己写代码的能力好垃圾...也可能是饿的> 一下午在debug...跟昨天一样,自己写了份动态开点的代码,然后最后告诉自己清醒一点清楚每个变量要干什么终于解决了.QWQ code: #include <bits/stdc++.h> using namespace std...

动态开点

2022-03-29

0 537

Andrew and Taxi 来自专栏

问题是求一个有向图,可以修改边的方向,要求修改的最大值最小使得图无环问题是求一个有向图,可以修改边的方向,要求修改的最大值最小使得图无环问题是求一个有向图,可以修改边的方向,要求修改的最大值最小使得图无环首先对于最大值最小可以考虑二分,至于ckckck的话,我们对于边的权值小于二分值uuu的都可以...

拓扑排序

2022-03-29

0 422

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

ST表

#include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e6+5; const int M=25; const int mod=1e9+7; int fx[N][M],fi[N][...

st表

2022-02-24

1 467

灵力之泉来自专栏

换根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 417

「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 537

「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

题解 | #小葱的01串# 来自专栏

枚举枚举枚举:简单的来说就是枚举第一个1出现在哪个位子,其他位子的1就是在一个特定的区间,特定区间取min,然后用rmq维护查询.O(n2)O(n^2)O(n2)解决. code: https://ac.nowcoder.com/acm/contest/view-submission?submiss...

C++

2021-11-20

4 663

题解 | #WeChat Walk# 来自专栏

按每个点有没有超过条边分为重点和轻点.令超过的为重点,没超过的为轻点. 设数组表示这个点最后成为冠军的时间,初始值为表示还不是冠军. 令数组表示重点附近轻点的最大权值是多少. 令数组为答案数组,用于最后输出. 令数组为下标为多少的为第几个大点,用来缩小空间. 令该点包含的大点下标. 令为小点存在大点...

分块

2021-09-06

0 536