JZYshuraK

分类

未归档(392)

/ 注册

全部文章（共392篇）

[bzoj5314][Jsoi2018]潜入行动_树形背包dp

潜入行动 bzoj-5314 Jsoi-2018 题目大意：题目链接。注释：略。想法：学长给我们除了一套考试题，三个学长一人一道这是T1. 好吧好吧，***背包...... 复杂度$O(nk)$。 Code： #include<bits/stdc++.h>...

2018-12-23

0 429

[bzoj2733][HNOI2012]永无乡_权值线段树_线段树合并

永无乡 bzoj-2733 HNOI-2012 题目大意：题目链接。注释：略。想法：它的查询操作非常友善，就是一个联通块内的$k$小值。故此我们可以考虑每个联通块建一棵权值线段树。这样的话每次修改采用线段树启发式合并，查询暴力走权值线段树即可。 Code： #in...

2018-12-23

0 393

[bzoj1014][JSOI2008]火星人prefix_非旋转Treap_hash_二分

火星人prefix bzoj-1014 JSOI-2004 题目大意：给定一个字符串，支持三种操作：1.查询；两个后缀之间的$LCP$；2.单点修改；3.插入一个字符。注释：$1\le n\le 10^5$，$1\le m\le 1.5\cdot 10^5$。想法：第一眼就是后缀数...

2018-12-17

0 417

[bzoj3879]SvT_后缀数组_RMQ_单调栈

SvT bzoj-3879 题目大意：给定一个字符串。每次询问给定$t$个位置，求两两位置开头的后缀的$LCP$之和。注释：$1\le length\le 5\cdot 10^5$，$\sum t\le 3\cdot 10^6$。想法：不难想到构建后缀数组。进而我们的问题就转化...

2018-12-17

0 382

[bzoj3238][Ahoi2013]差异_后缀数组_单调栈

差异 bzoj-3238 Ahoi-2013 题目大意：求任意两个后缀之间的$LCP$的和。注释：$1\le length \le 5\cdot 10^5$。想法：两个后缀之间的$LCP$和显然不好求。我们先构建后缀数组。那么任意两个后缀之间的$LCP$之和就是所有$sa$...

2018-12-17

0 418

[bzoj4698][Sdoi2008]Sandy的卡片_后缀数组_二分/单调队列_双指针

Sandy的卡片 bzoj-4698 Sdoi-2008 题目大意：题目链接。注释：略。想法：这个题跟一个Usaco的题特别像。我们把这些串差分现在我们要求的就是公共子串且出现次数不少于$k$的最长长度。紧接着把这$n$新串拼一起建立后缀数组。两种做法：第一种是二分...

2018-12-13

0 340

[bzoj2946][Poi2000]公共串_后缀数组_二分

公共串 bzoj-2946 Poi-2000 题目大意：给定$n$个字符串，求他们的最长公共子串。注释：$1\le n\le 5$，$1\le minlen<maxlen\le 2000$。想法：常规套路。我们把这$n$个串拼一起，中间加上$n-1$个不同的非字符集数组隔...

2018-12-12

0 421

[bzoj1717][Usaco2006 Dec]Milk Patterns 产奶的模式_后缀数组_二分答案

Milk Patterns 产奶的模式 bzoj-1717 Usaco-2006 Dec 题目大意：给定一个字符串，求最长的至少出现了$k$次的子串长度。注释：$1\le n\le 2\cdot 10^4$，$2\le k\le n$。想法：不难想到二分答案，现在我们考虑如何验证。 ...

2018-12-12

0 380

[bzoj4278][ONTAK2015]Tasowanie_后缀数组_贪心

Tasowanie bzoj-4278 ONTAK-2015 题目大意：给定两个字符串，求两个字符串二路归并之后生成的字典序最小的字符串是什么。注释：$1\le len_1,len_2\le 2\cdot 10^5$。想法：和队列变换比较像啊。我们将两个串接在一起然后建立后缀数...

2018-12-12

0 428

[bzoj2251][2010BeiJing Wc]外星联络_后缀数组

外星联络 bzoj-2251 2010-BeiJing Wc 题目大意：题目链接。注释：略。想法：这咋做啊？？？？一看数据范围才$3\cdot 10^3$。建立后缀数组。所以我们将所有后缀排序后，每个后缀的$ht[i]+1$的位置显然这个子串是第一次出现。我们统计每个子...

2018-12-12

0 452