苟且的狮子

分类

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

Dining 来自专栏

建图我们可以看看如何建图。首先保证每一份食物和饮品都只使用过一次。饿哦们可以把食物建在牛的左边，饮品建在牛的右边。食物连源点，饮品连汇点。这样就满足了。但是还有一个要注意的地方。就是每一头牛只能用一次。也就是说，我们每一头牛只能用一次。所以，要对牛进行拆点。代码如下： #include<...

2020-10-10

1 589

Network of Schools 来自专栏

缩点首先第一个任务，我们要找到至少应该发布任务的点数。我们很清楚的一点：如果这个图是一个DAG的话，我们只要在入度数为0的点处放置就可以了。但是在所给的测试样例中，我们可以看到节点1在一个环中。我们会注意到，在这个环中无论在那个点放置都可以到达所有的点。那边给了我们思路，我们先缩点，将图变为一个D...

2020-10-10

2 471

Musical Theme 来自专栏

最长不重叠子串很容易就会让人想到后缀数组。我们前后做一个差，然后就是类似求最长不重叠子串了。若两后缀的相同前缀长为i，那么最后就有i+1长的主题。所以这里不光是不重叠，还要空一。如何求解最长不重叠子串？二分，对height数组进行分组。(非常的巧妙！建议百度) 代码如下： #include<...

2020-10-09

1 533

ACM Computer Factory 来自专栏

水题看到oj下面好多人说拆点。但是，我没有拆点却也做出来了。从网络流的角度都去想没有什么障碍。我们构造出源点s和汇点t然后看有哪些机器可以和源点连，即input清一色为0或2 连(s,i)cap=Q[i]看有哪些可以可以与汇点连，即output都为1 连(i,t) cap = Q[i] 然后再看那...

2020-10-09

1 648

Fire Net 来自专栏

二分图匹配水题如果没有墙，我们直接放碉堡的话。我们可以肯定在所有放置的坐标中同一个行不能出现两次，同一个列不能出现两次。那么，有了墙的话意味着什么呢？意味着，我们有了额外的行和列！！！我们只要重新规定行和列就可以了。即，我们要找每个新出的区域。代码如下： #include<iostr...

2020-10-09

1 587

Til the Cows Come Home 来自专栏

版子题:##代码如下： #include<iostream> #include<algorithm> #include<queue> #include<vector> #include<functional> using namespace...

2020-10-09

1 563

Substring

SA、求解一共有多少不同的子串题意：分析：这题的关键在于字符仅出现{a,b,c}三种。我们想想对于一个子串ab他的同种类型为ac,bc,ba,ca,cb我们无法轻易判断这六种字符串是否有2个或两个以上的出现在一起。但是，在后缀数组的经典利用中我们可以求解一个字符串中有多少个不同的子串问...

一共有多少不同的子串 SA

2020-09-07

6 662

P4551 最长异或路径

01-trie,、贪心题意：分析：这是一道01-trie的模板题。01-trie主要用于处理异或问题。异或问题好像还有一个叫做线性基的常用方法.我们根据异或的性质(同一个数字异或两次就跟没异或一样)，所以任意两点之间的异或(u,v)等于(u,1)^(1,v)故，我们可以以1为根节点，求所有...

贪心枚举 01-trie

2020-09-06

0 639

[SDOI2016]生成魔咒

后缀数组、set、离散题解：分析：首先让我们看看这一题要求的是什么。每一个索引到最左端能构成的魔咒的数量。看到这里我们应该能反应过来。抓住不变的东西，最左端是始终不变的。如果我们把字符串reverse一下，那么求的就是每一个后缀的魔咒数量了！！！很明显的线索那么就让我们来思考一下反转后字...

set 二分查找离散后缀数组

2020-09-05

1 653

[HAOI2016]找相同字符

后缀数组、单调栈题意：分析：题意十分的清爽，但是却让人一筹莫仔细地分析我们便会发现，我们可以利用后缀数组来进行求解。我们比对s1和s2的每一个后缀。然后计算其和就可以了。对不对，其实题目中的也就是这个意思而已罢了。很简单，我们可以这样构造一个字符串s1+'$'+s2，我们求其SA和rmq。...

单调栈后缀数组

2020-09-05

1 569