shyyhs

分类

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

/ 注册

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

415篇文章 3901人学习

AtCoder思维大提升

6篇文章 753人学习

kuangbin专题记录

0篇文章 0人学习

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

19篇文章 848人学习

全部文章（共469篇）

E. Qpwoeirut and Vertices

kruskal重构树模板题首先有三个等价的性质我不会证! 图上任意两点的所有路径最大权值的最小值=最小生成树上任意路径的最大值=kruskal树上的lca. 就像不会sam一样不过这个记着就行. 那么原问题就是按边的编号作为权值,查询两两之间的lca的val,最后用一个可以维护区间最值的数据结...

kruskal重构树

2022-07-29

0 632

D. Rain

千万不要把题目想复杂...一定要学会手推!!! 我们可以通过观察发现以下性质: 111.极值一定出现在端点. 222.对于出现的每个值我们可以进行差分. 然后可以进行手推发现另外一个性质: 考虑删除一个点对其他点的影响. 假如其他点id>posid>posid>pos,那么由公式可...

C++

2022-07-28

0 518

D - Deterministic Placing

一个很难的题目写个博客加深印象. 首先可以把树划分成许多链每个链可以分为0端和1端有三个结论(可证). 1.0端和0端不能在一起 2.1端和1端不能在一起 3.中间点不能和别的端点在一起除此之外其他都是合法的. so,把链划分dp转移可以得到答案. 定义dp状态: 0:表示为中间点端点两个...

树形dp

2022-07-19

0 575

线段树

区间+等差数列区间求和 #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=2e5+5; const int mod=998244353; const int iv=(m...

线段树

2022-07-11

0 539

Recovering BST 来自专栏

感觉很妙,所以来水题解了~ 问给你一个升序序列,问是不是可以还原一个bstbstbst,使得相邻的两个节点gcdgcdgcd不为111.n<=700n<=700n<=700. 因为是颗二叉树,很容易想到区间dpdpdp,然后假设区间[l,k][l,k][l,k]满足了,这个区间的父...

dp

2022-05-03

1 419

D. MEX Tree 来自专栏

一些我不会做的题,加上没有正常题解...就会变得very hard. 其实并没有多难. 这个先容斥一下,然后lca分三种情况讨论就好了. 贴个智商代码: using namespace std; typedef long long ll; typedef unsigned long long ull...

思维题

2022-04-25

0 562

E. Bored Bakry 来自专栏

陷入思维误区的一个题目. 首先肯定知道的是一定是最高位全为111,而且长度为偶数是最优,且前面的位异或和为000. 那么我在解这个题的时候,因为使用了局部最优,从而忽视了某些情况,导致一直wawawa而且无法理解别人的代码. 其实这个不能使用dpdpdp.而应该使用贪心. 怎么贪,记录当前位的1的数...

思维

2022-04-25

0 402

XOR Partitioning 来自专栏

这题也好难诶!!!好叭可能只是对于我.因为dp方程不是我写的,网上也没注释.. 首先满足子区间异或和相等且当形式为 A 0 A 0 A 0..这种形式的异或前缀和才行. so?这题就做完了,我们进行dp即可. 令dp为现在出现位子i值为A的区间的种数,很明显,当前出现假如为A,那么它可以和前面的一起...

dp

2022-04-22

0 413

Coloring 来自专栏

好难的题目啊！写个博客记录一下. 首先显然满足要求的一定是相邻行取反或者列取反的矩阵.画下图可推出来. 然后,分别考虑行列肯定是2^n,和2^m,可以看成确定一排后面的都确定了,也可以看成每一排都有两种选法. 然后考虑修改...和去重重复即是两种情况都满足的,其实只有两种取法,即是黑白染色,确定...

思维题

2022-04-21

0 506

题解 | #游戏# 来自专栏

本来一开始就写完了... 可惜读错题了,我读的题更复杂一点点... 所以越写到后面脑子越晕... 直接导致后面调傻了,在原代码上. 我读的题里面他是每一轮都可以出它集合里面的东西.而不是固定一种. 两者处理方法是一样的,但是前者更为复杂? 好了... 考虑第iii个人怎么才能赢,那么就是第iii个人...

C++

2022-04-16

0 440