苟且的狮子

题解

2020多校(6) CF(27) 作业(3) 区域赛真题题解(提升思维！！！)(8) 寒假模拟赛(1) 未归档(1) 苏州大学排位赛(7) 随笔(1)

/ 注册

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

H: Hot Springs

构造题我们从中间开始取元素，然后左右来回取最近的元素，一定可以保证范围不断地变大 #include<iostream> #include<algorithm> using namespace std; const int max_n = 1e5+100; int a[max...

2021-04-27

0 722

题解 | #分组#

D题因为细节错误，最后一分钟才A出来。。。。。。。首先，我们有一个很明显的贪心。就是，我们从左到右去枚举边的话，肯定是尽量囊括边到濒临阈值的情况下即，我们从最左端一直向右取边，取到极限，算作一组然后以当前位置为最左端，向右取边取到极限，算作一组以此类推。但是我们是无法这样做的，因为我们无法做...

二分思维 tarjan

2021-04-09

6 680

Beautiful Numbers

第一道数位dp 之前看了讲解视频，然后知道了数位dp的基本代码结构主要是求一个dp推导，然后再特判最终情况。这里的dp推导，不是直接循环将dp推导出来(我看的视频里是用循环推导的dp)这里面用循环的话，编码难度会很高因此这里选择的是dfs记忆化递归！然后，在特判最终情形就好了。数为dp最为困...

数位dp

2021-03-20

1 626

多彩的树

状压dp、容斥首先我们要知道树的一个重要的特性：对于树来说，他的路径总和为: 刚开始我想换根dp。。。。还以为自己想到了一个新的方法。。。。打算先以1为根处理以每个节点为起点，到其子树中找路径能找到的路径和然后再通过找子结点和父节点的关系从而换根但是，这里的路径，只是通过找子结点和父节点的关系...

树枚举状压dp

2021-03-17

0 802

[SCOI2005]互不侵犯KING

状压dp 思路很明显，但是实现起来对我来说真难。这里我就解读一下代码首先我们定义了一个dp数组dp[i][j][k]表示，第i个状态,再第j行，之后要放置k个国王从第一行开始遍历我们定义状态为，如果该位为1那么这一行中，我们在这里放置了一个国王否则我们不放置国王我们可以先跑一下，预先把所有满...

状压dp

2021-03-16

1 630

极差

线段树线段树是我的弱项我们来看这一题：要维护值得乘积对 abc如果a发生变化，那么我们要是知道b*c则只要加上a得增量就好了基于着中国想法，我们使用了线段树。我们一共开了7棵线段树！先开三棵a,b,c在我们的线段树所开的数组中记录的点seg[x]是，从点x到目前边界的极差线段树维护这个极差的...

单调栈线段树

2021-03-13

2 820

Neat Tree

单调栈单调栈接触挺久了，一直没有仔细研究。昨天模拟赛，一道单调栈没有看出来。现在认真学学！对于这道题，因为它是连续子序列所以我们可以统计每一个值的贡献即，(作为最大值的次数-作为最小值的次数)*高度如何求作为最大值的次数？我们可以求解，向左走第一个比他大的索引，向右走第一个比他大的索引那么，在...

单调栈

2021-03-13

0 637

Copy or Prefix Sum

本篇不适合当题解看水位线技术我们先利用推导dp公式，注意：这里因为dp公式的特殊性我们决定从前向后主动更新(类似dij)然后我们会注意到这个dp很是特殊，她似乎整体都上升一个相同的数。我们可以利用水位线思想：我们不要一个个地上升数，我们下降水位线不就好了吗？然后单独处理一些特殊的点。如此，复杂度...

2021-03-09

0 622

String painter HDU - 2476 来自专栏

待会儿更新

2020-12-26

0 533

You Are the One HDU - 4283 来自专栏

区间dp 这一题我没有做出来关键是我想不到，如何设置断点。因此我就无法写出状态转移方程。正确答案中的断点设置是dp[i][j] 枚举i是第k个出场的这真的十十分的巧妙换句话说，既然是区间dp那么就一定是可以设置断点的。 #include<iostream> #include<...

2020-12-26

0 791