苟且的狮子
苟且的狮子
全部文章
题解
2020多校(6)
CF(27)
作业(3)
区域赛真题题解(提升思维!!!)(8)
寒假模拟赛(1)
未归档(1)
苏州大学排位赛(7)
随笔(1)
归档
标签
去牛客网
登录
/
注册
苟且的狮子的博客
人一我百、人百我万!
全部文章
/ 题解
(共179篇)
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
优秀的拆分
后缀数组、重复子串、回文子串 题意: 分析: 刚拿到这题我是崩溃的,这可咋求啊?!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
首页
上一页
6
7
8
9
10
11
12
13
14
15
下一页
末页