苟且的狮子

题解

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 570

Substring

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

一共有多少不同的子串 SA

2020-09-07

6 674

P4551 最长异或路径

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

贪心枚举 01-trie

2020-09-06

0 650

[SDOI2016]生成魔咒

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

set 二分查找离散后缀数组

2020-09-05

1 666

[HAOI2016]找相同字符

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

单调栈后缀数组

2020-09-05

1 576

优秀的拆分

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

重复子串后缀数组

2020-09-03

3 762

[TJOI2017]DNA

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

枚举后缀数组

2020-09-03

1 599

A Simple Problem

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

差分约束 kmp

2020-08-31

2 575

Just A String

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

kmp

2020-08-31

12 630

点阵

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

最大流网络流建图

2020-08-30

1 569