苟且的狮子

分类

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篇）

优秀的拆分

后缀数组、重复子串、回文子串题意：分析：刚拿到这题我是崩溃的，这可咋求啊？！AABB的，太吓人了！！然后我仔细看了看，其实问题的关键在于如何判断一个连续的AA串！！如果我们能够计算出哪里有AA串就好了。比如：a[i]记录了一索引i结尾的AA串有多少个b[i]记录了一索引i开始的AA串有多...

重复子串后缀数组

2020-09-03

3 746

[TJOI2017]DNA

后缀数组，枚举和暴力这是我的第一道真正意义上的后缀数组题！！！！！而且1A。祝贺！！！！！鸣炮！！！！！题意：分析：我的想法很简单，就是枚举。我想对s1从头到尾枚举每一个长度为s1.size()的子串。记s2得长度为m。枚举[0,m)、[1,m+1)、[2,m+2)......看枚举的字...

枚举后缀数组

2020-09-03

1 586

A Simple Problem

kmp、差分约束题意：分析第一个要突破的点在于：如何表示认错树木的现象。我们可以暴力地枚举记忆中的p字符串，然后再用kmp进行匹配但是很明显这会超时！所以我们需要采取其他的办法。进行分辨。这里我们使用的技巧叫做差分约束！通过记录当前p[i]出现的位置与其上一次出现位置的差值，来限制数目的...

差分约束 kmp

2020-08-31

2 565

Just A String

kmp 题意：分析：这一题，我最初很没思路。刚开始想会不会是kmp扩展，但是琢磨一番发现无法解决。然后，在进行手工推算时，发现这是个kmp问题。请看：题目让我们求的是：对于字符串s,判断他的每一个前缀和每一个后缀的B是否？从题目所给的数据量来看，我们很简单就能想到枚举。但是，即便枚举我们...

kmp

2020-08-31

12 617

点阵

最大流，建图题意：分析：难点就在建图。我们不难这样想：将每一条边视作一个点，将每一个格子视作一个点。格子点拆成两个。然后这样建造：但是，这很明显不能满足约束条件。对于相邻的两个格点，如果他们相邻的边被选中时，两个格点的s-s1或者s2-ed都要减一，并且该边所代表的点再也不能走了！很明显我...

最大流网络流建图

2020-08-30

1 558

[HNOI2012]矿场搭建

tarjan、割点、分类讨论题意：分析：这题很容易让我们想到割点。这并不难，但是细节上的处理于分类讨论才是这道题的难点。我们想想如果一个连通块，他有一个割点。那么，我们一定要在他被割点分开的两个连通块中放置救援出口。而放置的方案数就是两边的点数相乘，割点不算！如果，他有两个以上的割点...

tarjan 割点

2020-08-29

4 550

[JSOI2010]连通数

bfs,bitset 题意： ##分析：题目没给数据范围，n<=2000考录到数据范围，这题我们可以直接bfs，或者dfs。暴力搜索。细节处理好也能过。但是，显然有些勉强。这里面考的是，bitset容器。 bitset的或运算代替了搜索。看代码： bitset<max_n> a[...

bitset bfs

2020-08-29

1 637

字符串的问题

kmp 题意：分析：我们看着一题，我们仔细想想。首先如果没有要求中间子串的话，就很简单了。我们直接输出前后缀相等的就好了。无论是 kmp 还是暴力都是线性时间。但是麻烦就在于中间要有字串。那我们想想，如何判断中间有没有子串呢？假设，next[n] = k 意味着s0,s1,s...

kmp

2020-08-28

7 619

cf D - Zigzags

思维，dp，枚举题意：分析: 这题我拿到手时，是一脸懵逼。我不知道该从哪里下手才好。我率先的想法是，统计每一个索引i处，开个数组记录他后面与他数值相等的索引。再从头到尾遍历，遍历到i时，一一遍历他的索引数组。假设遍历到了j 我们确定了第三个数索引为j 第一个为i然后在i到j之间再遍历去确定...

思维 dp

2020-08-26

1 465

[HAOI2006]受欢迎的牛

tarjan，dfs 题意：分析：不知道怎么回事，这道题做的时候总是有点迷迷糊糊的，犯了好多低级错误。。。。。。总之，如果接触到tarjan的话那么我们肯定能够反映过来：一定要缩点的。缩点后啊，这张图就是一张拓扑图。有向无环。每割点都有权值，就是此节点缩的点数那现在让我们从这张有向无环图中...

dfs tarjan map

2020-08-25

1 587