ww3113306

2018年12月4日

[POI2012]OKR-A Horrible Poem hash

摘要：题面：洛谷题解：首先我们需要知道一个性质，串s的最小循环节 = len - next[len].其中next[len]表示串s的一个最长长度使得s[1] ~ s[next[len]] == s[len - next[len] + 1] ~ s[len](详细定义参见KMP) 至于为什么是成立的阅读全文

posted @ 2018-12-04 21:21 ww3113306 阅读(301) 评论(0) 推荐(0)

[APIO2014]回文串 manacher 后缀数组

摘要：题面：洛谷题解：还是这个性质：对于每个串而言，本质不同的回文串最多只有O(n)个。所以我们先求出这O(n)个本质不同的回文串，然后对整个串求一次sa。然后对于每个回文串，求出它的出现次数，更新答案即可。如何用后缀数组求一个串的出现次数？因为每个串都必然是某个后缀的前缀。因此我们先找到这个阅读全文

posted @ 2018-12-04 21:00 ww3113306 阅读(217) 评论(0) 推荐(0)

[SHOI2011]双倍回文 manacher

摘要：题面：洛谷：[SHOI2011]双倍回文‘ 题解：首先有一个性质，本质不同的回文串最多O(n)个。所以我们可以对于每个i，求出以这个i为结尾的最长回文串，然后以此作为长串，并判断把这个长串从中间劈开后左边的一半是否也是一个回文串（判断左边那半的中点的回文半径是否可以跨过当前长串的中点）。复杂阅读全文

posted @ 2018-12-04 20:51 ww3113306 阅读(171) 评论(0) 推荐(0)

2018年12月2日

[国家集训队]拉拉队排练

摘要：题面：洛谷一句话题意：找前k大回文串（不要求本质不同）题解：我们进行一遍manacher即可求出对于每个回文中心而言的最长回文半径。我们考虑求出f[i]表示回文半径为i的回文串的个数。那么对于一个i而言，它可以对哪些长回文半径产生贡献呢？ [1, r[i]]。（这个应该是很明显的）因此阅读全文

posted @ 2018-12-02 00:22 ww3113306 阅读(164) 评论(0) 推荐(0)

[TJOI2013]单词 AC自动机

摘要：题面：洛谷题解：很久之前做的题了，只不过之前一直90.。。。最近才发现是哪里写错了。我们对字符集建AC自动机。首先考虑一个暴力的做法，把文章当做一个长串，直接在自动机上跳，但是我们会发现，这样的复杂度可能退化到$n^2$. 因为对于一个类似于aaaaaaaaaaaaaaaa这样的串而言，一阅读全文

posted @ 2018-12-02 00:17 ww3113306 阅读(158) 评论(0) 推荐(0)

2018年11月19日

AC自动机

摘要：首先在学习这个之前我们需要学会trie树这个东西，详见trie树。 AC自动机就是在trie树的基础上建立起来的。先看几个定义： 1，fail指针：这个指针指向等于当前串的某一后缀的串中，深度最大的那个串。因为在trie树上任意一个点都可以代表从root到这个点所构成的串，所以假设我们现在有ab 阅读全文

posted @ 2018-11-19 22:26 ww3113306 阅读(248) 评论(0) 推荐(0)

trie树

摘要：简而言之，trie树就是把字符当做点的树。一般而言，我们建trie树都是在树上插入很多个字符串，再利用trie树的性质来做题。对于任意一个字符串，我们的插入规则如下：(此处默认所有字符串都只有小写字母) 一开始我们在根节点0. 假设当前所在的点为x，当前遍历到的字符为c。 1，我们先检测x这个节阅读全文

posted @ 2018-11-19 21:37 ww3113306 阅读(169) 评论(0) 推荐(0)

基数排序

摘要：基数排序是一种复杂度为n * max(每个数的位数)的优秀算法，平常用的不多，但求后缀数组的时候为了达到nlogn的复杂度一般都会采用基数排序，因此还是很有必要学一下的。大概的意思就是说，对于一个数列而言，我们先以个位数为权值桶排一遍得到一个新的排列，然后再在这个排列的基础上以十位数为权值桶排一遍阅读全文

posted @ 2018-11-19 21:24 ww3113306 阅读(160) 评论(0) 推荐(0)

2018年11月15日

CF724E Goods transportation 最小割 DP

摘要：照惯例CF的题不放原题链接。。。题意：一个序列上有n个点，每个点有权值pi和si。表示这个点一开始有pi个物品，最多可以卖出si个物品，每个点都可以把物品向编号更大的点运输，但是对于i < j的任意点对(i, j)最多从i到j运c个物品。求最多能卖出多少个物品。题解：如果不考虑数据范围的话，可阅读全文

posted @ 2018-11-15 20:32 ww3113306 阅读(259) 评论(0) 推荐(0)

2018年11月14日

[CQOI2009]跳舞网络流

摘要：题面：[CQOI2009]跳舞题解：首先最大时间不好求，而且数据范围很小，所以我们可以先二分一个最大时间，然后就只需要判断是否可行即可。因此我们每二分一个mid，对于每个女生，连s > x : mid , x > x' : k.对于每个男生，连x > t : mid, x' > x : k. 阅读全文

posted @ 2018-11-14 21:55 ww3113306 阅读(187) 评论(0) 推荐(0)

鸽王了属于是

公告