苟且的狮子

分类

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

/ 注册

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

kuangbin题单刷题详解(最短路篇)

9篇文章 696人学习

kuangbin题单刷题详解(网络流)

10篇文章 648人学习

kuangbin题单刷题详解(匹配问题)

14篇文章 724人学习

kuangbin刷题题单详解(后缀数组)

8篇文章 588人学习

kuangbin刷题题单详解(博弈论)

8篇文章 736人学习

kuangbin刷题题单详解(连通图)

9篇文章 814人学习

Kuangbin刷题详解(AC自动机)

4篇文章 613人学习

Kuangbin题单详解(kmpManacher)

20篇文章 950人学习

Kuangbin题单详解(区间dp)

6篇文章 791人学习

全部文章（共229篇）

L. Lottery

思维+二进制+递归分治首先一个重要的策略我们先对数据从小到大排序然后如果一个前缀和，比后面的阶数要小那么，我们此刻就可以将这个数组分开单独看这里就是分治了答案是两边结果的乘积然后对于一个没有被分开的数组，我们该如何求解他的答案呢？答案就是将他的每一阶数全都转化为当前区间的最小的那个阶数统...

思维分治二进制

2021-03-25

0 869

L. Two Buildings

决策的单调性和分治这一题有两步转化第一步是：将原式看作为矩形的面积其实，即使我们不做这个转化，我们也是能够看出来的我们可以知道，如果且那么作为右端点一定比优这样就维护了一个单调减的序列同样，方向反过来，我们也可以找到作为左端点的单调增的序列我赛时分析到这里，然后走不下去了。但，我们既然将...

决策的单调性递归分治

2021-03-25

0 733

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

数据结构上机作业实验报告一

C:\Program Files\Microsoft SQL Server\MSSQL.2\MSSQL\DATA school.mdf

2021-03-17

0 787

[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

A - Character Encoding

组合数学、容斥原理真的太毒了，今天的模拟什么都没有做出来这一题刚开始就到想了，最后也没有想出来首先如果没有那个n的限制的话，就是简单的隔板法，组合数学。但是有了n的限制就一下子麻烦了起来。其实当时隐隐约约的感觉到了，只不过没有方向坚定地走下去。我们在利用隔板法计算出来之后，在减去多余的。这是基...

容斥组合数学

2021-01-29

1 562